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

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

试卷总分：100得分：100

第1题,BFS算法可用来解决单源最短路径问题的条件是当各边上的权值

A、均相等

B、均互不相等

C、不一定相等

D、任意值

正确答案：

第2题,下列序列中不构成堆的是

A、(1,2,5,3,4,6,7,8,9,10)

B、(10,5,8,4,2,6,7,1,3)

C、(10,9,8,7,3,5,4,6,2)

D、(1,2,3,4,10,9,8,7,6,5)

正确答案：

第3题,若要在单链表中的结点p之后插入一个结点s则应执行的语句是

A、s-next=p-next;p-next=s;

B、p-next=s;s-next=p-next;

C、p-next=s-next;s-next=p;

D、s-next=p;p-next=s-next;

正确答案：

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

A、4

B、5

C、8

D、9

正确答案:C

第5题，假设在构建散列表时采用线性探测解决冲突若连续插入的n个关键字都是同义词则查

找其中最后插入的关键字时所需进行的比较次数为

A、n-1

B、n

C、n+1

D、n+2

正确答案：

第6题,文件中主关键字能唯一标识

A、一个记录

B、一组记录

C、一个类型

D、一个文件

正确答案：

第7题,假设以数组A[m]存放循环队列的元素已知队列的长度为length指针rear指向队尾

元素的下一个存储位置则队头元素所在的存储位置为

A、(rear-length+m+1)%m

B、(rear-length+m)%m

C、(rear-length+m-1)%m

D、(rear-length)%m

正确答案:B

第8题,设顺序存储的线性表共有123个元素按分块查找的要求等分成3块若对索引表采用顺

序查找来确定块并在确定的块中进行顺序查找则在查找概率相等的情况下分块查找成功时的

平均查找长度为

A、21

B、23

C、41

D、62

正确答案：

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

A、最小单位

B、最大单位

C、基本单位

D、不可分割的单位

正确答案:C

第10题,对n个关键字的序列进行快速排序平均情况下的空间复杂度为

A、0(1)

B、0(logn)

C、0(n)

D、0(nlogn)

正确答案：

第11题,若允许表达式内多种括号混合嵌套则为检查表达式中括号是否正确配对的算法通常

选用的辅助结构是

A、栈

B、线性表

C、队列

D、二叉排序树

正确答案：

第12题,下面关于数据结构正确的说法是

A、一种数据类型

B、数据的存储结构

C、一组性质相同的数据元素的集合

D、相互之间存在一种或多种特定关系的数据元素的集合

正确答案:D

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

结构是

A、栈

B、队列

C、树

D、图

正确答案:C

第14题,下面的说法中正确的是1任何一棵二叉树的叶子节点在三种遍历中的相对次序不变

2按二叉树定义具有三个节点的二叉树共有6种

A、(1),(2)

B、(1)

C、(2)

D、(1),(2)都错

正确答案：

第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题,设一个栈的输入序列为12345则借助一个栈所得到的输出序列不可能是

A、23415

B、54132

C、23145

D、15432

正确答案:

第17题,对关键字序列51437286进行快速排序时以第一个元素5为基准的一次划分的结果为

A、(1,2,3,4,5,6,7,8)

B、(1,4,3,2,5,7,8,6)

C、(2,1,4,3,5,7,8,6)

D、(8,7,6,5,4,3,2,1)

正确答案：

第18题,在下列各种文件中不能进行顺序查找的文件是

A、顺序文件

B、索引文件

C、散列文件

D、多重表文件

正确答案：

第19题,若将数据结构形式定义为二元组KR其中K是数据元素的有限集合则R