数据结构考试题5.pdfVIP

数据结构考试题5

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。

每张答题纸都要写上姓名和学号。

一、单项选择题（每小题2分，共20小题，共计40分）

1.某算法的空间复杂度为O(1)，则。

A.该算法执行不需要任何辅助空间

B.该算法执行所需辅助空间大小与问题规模n无关

C.该算法执行不需要任何空间

D.该算法执行所需全部空间大小与问题规模n无关

2.在长度为n的顺序表中插入一个元素，对应算法的时间复杂度

为。

(1)(log2n)(n)(n2)

3.设线性表中有n个元素，以下运算中，在单链表上实现要比在

顺序表上实现效率更高。

A.删除指定位置元素的后一个元素

B.在最后一个元素的后面插入一个新元素

C.顺序输出前k个元素

D.交换第i个元素和第n-i+1个元素的值（i=1，2，…，n）

4.以下数据结构中元素之间为非线性关系的是。

A.栈

B.队列

C.线性表

D.以上都不是

5.若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，

则以下元素x进栈的正确操作是。

++;data[top]=x;[top]=x;top++;

;data[top]=x;[top]=x;top--;

6.若某循环队列有队首指针front和队尾指针rear，在队不满时

进队操作仅会改

变。

和rearD.以上都不队

7.设循环队列中数组的下标是0～N-1，其队头、队尾指针分别为

f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数

为。

C.(r-f)％N+1

D.(r-f+N)％N

8.设树T的度为4，其中度为1、2、3、4的结点个数分别为4、

2、1、1，则T中的叶子结点个数是。

9.一棵哈夫曼树中共有199个结点，它用于多少个字符的编码。

10.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为

a、b、c、d，将森林F转换为一颗二叉树B，则二叉树B根结点的左

子树上的结点个数是。

C.a+b+c+c+d

11.下列关于图的叙述中，正确的是。

Ⅰ.回路是简单路径

Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ.若有向图中存在拓扑序列，则该图不存在回路

A.仅Ⅱ

B.仅Ⅰ、Ⅱ

C.仅Ⅲ

D.仅Ⅰ、Ⅲ

12.以下关于有向图的说法中，正确的是。

A.强连通图是任何顶点到其他所有顶点都有边

B.完全有向图一定是强连通图

C.有向图中任一顶点的入度等于出度

D.有向图边集的子集和顶点集的子集可构成原有向图的子图

13.无向图的邻接矩阵是一个。

A.对称矩阵

B.零矩阵

C.上三角矩阵

D.对角矩阵

14.如果从无向图的任一顶点出发进行一次广度优先遍历即可访问

所有顶点，则该图一定是。

A.完全图

B.连通图

C.有回路

D.一棵树

15.用Dijkstra算法求一个带权有向图G中从顶点0出发的最短

路径，在算法执行的某时刻，S={0,2,3,4}，下一步选取的目标顶点可

能是。

A.顶点2

B.顶点3

C.顶点4

D.顶点7

16.哈希表中出现冲突是指。

A.两个元素具有相同的序号

B.两个元素的关键字不同，而其他属性相同

C.数据元素过多

D.两个元素的关键字不同，而对应的哈希函数值（存储地址）相

同

17.适合于折半查找的数据组织方式是。