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

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

试卷总分：100得分：100

第1题,判定“带头结点的链队列为空”的条件是

A、Q.front==NULL

B>Q.rear二二NULL

C、Q.front==Q.rear

D、Q.front!=Q.rear

正确答案:c

第2题，对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为

A、0(n)0(n)

B、0(n)0(1)

C、0(1)0(n)

D、0(1)0(1)

正确答案:C

第3题，由同一关键字集合构造的各棵二叉排序树

A、其形态不一定相同，但平均查找长度相同

B、其形态不一定相同，平均查找长度也不一定相同

C、其形态均相同，但平均查找长度不一定相同

D、其形态均相同，平均查找长度也都相同

正确答案:B

第4题,对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结

果为

A、(19,23,56,34,78,67,88,92)

B、(23,56,78,66,88,92,19,34)

C、(19,23,34,56,67,78,88,92)

D、(19,23,67,56,34,78,92,88)

正确答案：D

第5题,可有效提高次关键字查找效率的文件是

A、顺序文件

B、倒排文件

C、散列文件

D、VSAM文件

正确答案:B

第6题，数据结构中所定义的数据元素，是用于表示数据的

A、最小单位

B、最大单位

C、基本单位

D、不可分割的单位

正确答案:C

第7题,若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时

间复杂度为

A、0(0)

B、0(1)

C、0(n)

D、0(n2)

正确答案:C

第8题，若vi,vj是有向图的一条边，则称

A、vi邻接于vj

B、vj邻接于vi

C、vi和vj相互邻接

D、vi与vj-不相令B接

正确答案:B

第9题,若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t),则在二分查找关键字b的过程中,

先后进行比较的关键字依次为

A、f,c,b

B、f,d,b

C>g,c,b

D、g,d,b

正确答案:A

第10题,高度为5的完全二叉树中含有的结点数至少为

A、16

B、17

C、31

D、32

正确答案:A

第11题，含n个关键字的二叉排序树的平均查找长度主要取决于

A、关键字的个数

B、树的形态

C、关键字的取值范围

D、关键字的数据类型

正确答案:A

第12题，队列和栈的主要区别是

A、逻辑结构不同

B、存储结构不同

C、所包含的运算个数不同

D、限定插入和删除的位置不同

正确答案:D

第13题，已知散列表的存储空间为T[0..18],散列函数H(key)=key%17,并用二次探测法处

理冲突。散列表中已插入下列关键字：T[5]=39,T[6]=57和T[7]=7,则下一个关键字23插

入的位置是

A、T⑵

B、T[4]

C>T[8]

D、T[10]

正确答案:C

第14题,根据数据元素的关键字直接计算出该元素存储地址的存储方法是

A、顺序存储方法

B、链式存储方法

C、索引存储方法

D、散列存储方法

正确答案:D

第15题,下列关键字序列中，构成小根堆的是

A、{84,46,62,41,28,58,15,37)

B、{84,62,58,46,41,37,28,15)

C、{15,28,46,37,84,41,58,62)

D、{15,28,46,37,84,58,62,41)

正确答案:D

第16题，ISAM文件和VSAM文件的区别之一是

A、前者是索引顺序文件，后者是索引非顺序文件

B、前者只能进行顺序存取，后者只能进行随机存取

C、前者建立静态索引结构，后者建立动态索引结构

D、前者的存储介质是磁盘，后者的存储介质不是磁盘

正确答案:C

第17题,适宜进行批量处理的文件类型是

A、顺序文件

B、索引顺序文件

C、散列文件

D、多关键字文件

正确答案:A

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

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

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

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

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

正确答案:B

第19题，某带头结点的单链表的头指针为head,判定该链表为非空的条件是

A、head==NU