22春季东北大学《数据结构Ⅱ》在线平时作业2

【奥鹏】数据结构II-［东北大学］《数据结构II》在线平时作业2

试卷总分：100得分：100

第1题,判断两个串大小的基本准则是

A、两个串长度的大小

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

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

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

正确答案:D

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

的序列为

A、ABCDEF

B、ABCEFD

C、ABFCDE

D、ABCDFE

正确答案:D

第3题，采用ISAM或VSAM组织的文件是

A、索引非顺序文件

B、顺序文件

C、索引顺序文件

D、散列文件

正确答案:C

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

A、深度优先搜索算法

B、广度优先搜索算法

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

D、拓扑排序算法

正确答案:B

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

A、插入操作更加方便

B、删除操作更加方便

C、不会出现下溢的情况

I）、不会出现上溢的情况

正确答案:D

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

A、n-1

B、n

C、n+1

D、2n

正确答案:C

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

A、2k-1

B、2k-l-1

C、2k-l

D、2k

正确答案:c

第8题，设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序

是2、3、4、6、5、1,则栈的容量至少应该是

A、2

B、3

C、5

D、6

正确答案:B

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

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

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

组成索引块

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

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

正确答案:B

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

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

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

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

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

正确答案:A

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

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

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

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

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

正确答案:B

第12题,设哈希表长为14,哈希函数H(key)=key%ll,表中已有数据的关键字为15,38,

61,84,四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的

位置是

A、8

B、3

C、5

D、9

正确答案:A

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

A、G中有弧Vi,Vj

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

C、G中没有弧Vi,Vj

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

正确答案:D

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

A、直接插入排序

B、快速排序

C、直接选择排序

D、归并排序

正确答案:A

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

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

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

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

D、以上都不对

正确答案:B

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

A、4

B、5

C、8

D、9

正确答案:C

第17题,下面的叙述不正确的是

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

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

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

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

正确答案:B

第18题,若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为

A、n-1

B、en/mu-1

C、6(n-1)/(m-l)u

D、en/(m-1)u-1

正确答案:C

第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点

是A,并已知A的左、右孩子的平衡因子分别为-