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

【奥鹏】数据结构11-[东北大学]《数据结构II》在线平时作业3

试卷总分：100得分：100

第1题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中

某个顶点出度的时间复杂度为

A、0(D)

B、0(e)

C、0(n+e)

D、0(n2)

正确答案:A

第2题,索引非顺序文件的特点是

A、主文件无序,索引表有序

B、主文件有序,索引表无序

C、主文件有序,索引表有序

D、主文件无序,索引表无序

正确答案:A

第3题，二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A[1][1]的存

储地址为420,A[3][3]的存储地址为446,则A[5][5]的存储地址为

A、470

B、471

C、472

D、473

正确答案:C

第4题,在单链表中，指针-p指向元素为x的结点，实现“删除x的后继”的语句是

A、p=p-next;

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

C、p-next=p;

D、p=p-next-next;

正确答案:B

第5题，引入二叉线索树的目的是

A、加快查找结点的前驱或后继的速度

B、为了能在二叉树中方便的进行插入与删除

C、为了能方便的找到双亲

D、使二叉树的遍历结果唯一

正确答案:A

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

A、2k-1

B、2k-l-1

C、2k-l

D、2k

正确答案:C

第7题,下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是

A、分块查找

B、顺序查找

C、二分查找

D、散列查找

正确答案:D

第8题,某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E则该二叉树对应的

森林包括的树的棵树是

A、1

B、2

C、3

D、4

正确答案:B

第9题，已知循环队列的存储空间为数组data[21],且当前队列的头指针和尾指针的值分别

为8和3,则该队列的当前长度为

A、5

B、6

C、16

D、17

正确答案:C

第10题，在长度为n的顺序表中删除第i个元素（lWiWn）时，元素移动的次数为

A、n-i+1

B、i

C、i+1

D、n-i

正确答案:D

第11题,从逻辑上可以把数据结构分为两大类，即

A、动态结构、静态结构

B、顺序结构、链式结构

C、线性结构、非线性结构

D、初等结构、构造型结构

正确答案:C

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

A、深度优先搜索算法

B、广度优先搜索算法

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

D、拓扑排序算法

正确答案:B

第13题,为便于判别有向图中是否存在回路，可借助于

A、广度优先搜索算法

B、最小生成树算法

C、最短路径算法

D、拓扑排序算法

正确答案:D

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

A、逻辑结构不同

B、存储结构不同

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

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

正确答案：D

第15题，在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若

p-next-next=head,贝ij

A、p指向头结点

B、p指向尾结点

C、p的直接后继是头结点

D、P的直接后继是尾结点

正确答案:D

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

上

A、操作的有限集合

B、映象的有限集合

C、类型的有限集合

D、关系的有限集合

正确答案:D

第17题,通常将链串的结点大小设置为大于1是为了

A、提高串匹配效率

B、提高存储密度

C、便于插入操作

D、便于删除操作

正确答案:B

第18题,对长度为n的关键字序列进行堆排序的空间复杂度为

A、0(log2n)

B、0(1)

C、0(n)

D、0(n*log2n)

正确答案:B

第19题，在一个带权连通图G中，权值最小的边一定包含在G的

A、最小生成树中

B、深度优先生成树中

C、广度优先生成树中

D、深度优先生成森林中

正确答案:A

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