东大21秋学期学期《数据结构Ⅱ》在线平时作业2[答案]

东大21秋学期学期《数据结构Ⅱ》在线平时作业2[答案]答案

《数据结构Ⅱ》在线平时作业2

试卷总分:100  得分:100

一、单选题 (共 20 道试题,共 100 分)

1.判断两个串大小的基本准则是

A.两个串长度的大小

B.两个串中首字符的大小

C.两个串中大写字母的多少

D.对应的第一个不等字符的大小

正确答案:-----

 

2.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为

正确答案:-----

A.ABCDEF

正确答案:-----

B.ABCEFD

C.ABFCDE

正确答案:-----

D.ABCDFE

正确答案:-----

 

3.采用ISAM或VSAM组织的文件是

A.索引非顺序文件

B.顺序文件

C.索引顺序文件

D.散列文件

正确答案:-----

 

4.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用

A.深度优先搜索算法

B.广度优先搜索算法

C.求最小生成树的prim算法

D.拓扑排序算法

正确答案:-----

 

5.链栈与顺序栈相比，比较明显的优点是

A.插入操作更加方便

B.删除操作更加方便

C.不会出现下溢的情况

D.不会出现上溢的情况

正确答案:-----

 

6.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为

A.n-1

B.n

C.n+l

D.2n

正确答案:-----

 

7.一棵树高为K的完全二叉树至少的结点是

A.2k –1

正确答案:-----

正确答案:-----

B.2k-1 –1

C.2k-1

D.2k

正确答案:-----

 

8.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是

A.2

B.3

C.5

D.6

正确答案:-----

 

9.当采用分快查找时，数据的组织方式为

A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.数据分成若干块，每块（除最后一块外）中数据个数需相同

正确答案:-----

 

10.抽象数据类型的三个组成部分分别为

A.数据对象、数据关系和基本操作

B.数据元素、逻辑结构和存储结构

C.数据项、数据元素和数据类型

D.数据元素、数据结构和数据类型

正确答案:-----

 

11.下面关于线性表的叙述中，错误的是

A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

正确答案:-----

 

12.设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是

A.8

B.3

C.5

D.9

正确答案:-----

正确答案:-----

 

13.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是

A.G中有弧<Vi，Vj>

B.G中有一条从Vi到Vj的路径

C.G中没有弧<Vi,Vj>

D.G中有一条从Vj到Vi的路径

正确答案:-----

 

14.在待排关键字序列基本有序的前提下，效率最高的排序方法是

A.直接插入排序

B.快速排序

C.直接选择排序

D.归并排序

正确答案:-----

 

15.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是

A.树的后根遍历与其对应的二叉树的后根遍历相同

B.树的后根遍历与其对应的二叉树的中根遍历相同

C.树的先根遍历与其对应的二叉树的中根遍历相同

D.以上都不对

正确答案:-----

 

16.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

A.4

B.5

C.8

D.9

 

17.下面的叙述不正确的是

A.线性表在链式存储时，查找第i个元素的时间同i的值成正比

B.线性表在链式存储时，查找第i个元素的时间同i的值无关

C.线性表在顺序存储时，查找第i个元素的时间同i 的值成反比

D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

正确答案:-----

 

21.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为

A.n-1

B.&euml;n/m&ucirc;-1

C.&eacute;(n-1)/(m-1)&ugrave;

D.&eacute;n/(m-1)&ugrave;-1

正确答案:-----

 

19.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是

A.LL型

B.LR型

C.RL型

D.RR型

正确答案:-----

 

20.二叉树中第5层上的结点个数最多为

A.8

B.15

C.16

D.32

正确答案:-----

 

东大21秋学期学期《数据结构Ⅱ》在线平时作业2[答案]历年参考题目如下：

19秋学期《数据结构Ⅱ》在线平时作业1

试卷总分:100  得分:100

一、单选题 (共 20 道试题,共 100 分)

1.高度为5的完全二叉树中含有的结点数至少为

A.32

B.31

C.17

D.16

 

2.通常将链串的结点大小设置为大于1是为了

A.提高存储密度

B.提高串匹配效率

C.便于插入操作

D.便于删除操作

 

3.在VSAM文件的控制区间中，记录的存储方式为

A.有序顺序

B.有序链接

C.无序顺序

D.无序链接

 

4.在一棵高度为k的满二叉树中，结点总数为

A.2k-1

B.2k-1

C.2k

D.&euml;log2k&ucirc;+1

 

5.已知广义表的表头为a，表尾为(b,c)，则此广义表为

A..(a,b,c)

B..(a,(b,c))

C..((a,b,c))

D..((a),b,c)

 

6.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为

A.8

B.5

C.18

D.11

 

7.如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为

A.插入排序

B.归并排序

C.堆排序

D.冒泡排序

 

8.栈是一种操作受限的线性结构，其操作的主要特征是

A.进优于出

B.后进先出

C.出优于进

D.先进先出

 

9.下面的叙述不正确的是

A.线性表在顺序存储时，查找第i个元素的时间同i的值无关

B.线性表在顺序存储时，查找第i个元素的时间同i 的值成反比

C.线性表在链式存储时，查找第i个元素的时间同i的值无关

D.线性表在链式存储时，查找第i个元素的时间同i的值成正比

 

10.n个顶点的有向完全图中含有向边的数目最多为

A.n(n-1)/2

B.n(n-1)

C.n-1

D.n

 

11.采用ISAM或VSAM组织的文件是

A.顺序文件

B.索引顺序文件

C.索引非顺序文件

D.散列文件

 

12.除第一层外，满二叉树中每一层结点个数是上一层结点个数的

A.3倍

B.2倍

C.1倍

D.1/2倍

 

13.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是

A.队列

B.树

C.栈

D.图

 

14.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为

A.&eacute;n/(m-1)&ugrave;-1

B.&euml;n/m&ucirc;-1

C.&eacute;(n-1)/(m-1)&ugrave;

D.n-1

 

15.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是

A.tail(head(LS))

B.head(tail(tail(head(LS))))

C.head(tail(head(tail(LS))))

D.head(tail(LS))

 

16.算法的时间复杂度主要取决于

A.难度

B.问题的规模

C.待处理数据的初态

D.A和B

 

17.已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有

A.以上答案都不对

B.dacb

C.cadb

D.bdac

 

18.设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是

A.D，C，B，A

B.D，A，B，C

C.A，C，D，B

D.A，B，C，D

 

19.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为

A.n+l

B.n+2

C.n-1

D.n

 

20.n个顶点的强连通图中至少含有

A.n条有向边

B.n(n-1)条有向边

C.n(n-1)/2条有向边

D.n-1条有向边