(完整)数据结构考试题5 .pdfVIP

(完整)数据结构考试题5--第1页

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和

学号。

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

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

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

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

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

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

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

A.0(1)B.O(logn)C.0(n)D.0(n)

22

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进栈的正

确操作是。

A.top++;data[top]=x;B.data[top]=x;top++;

C.top--;data[top]=x;D.data[top]=x;top--;

6.若某循环队列有队首指针front和队尾指针rear,在队不满时进队操作仅会改

变。

A.frontB.rearC.front和rearD.以上都不队

7.设循环队列中数组的下标是0〜N-1,其队头、队尾指针分别为f和r(f指向队首元素的前

r。

一位置，指向队尾元素)，则其元素个数为

A.r-fB.r-f-1C.(r-f)%N+1D.(r-f+N)%N

8.T4,12344211,T

设树的度为其中度为、、、的结点个数分别为、、、则中的

叶子结点个数是。

A.5B.6C.7D.8

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

A.99B.100C.101D.199

10.F41234abcd,

设森林中有棵树，第、、、棵树的结点个数分别为、、、将森林

F转换为一颗二叉树B,则二叉树B根结点的左子树上的结点个数是。

A.a-1B.aC.a+b+cD.b+c+d

(完整)数据结构考试题5--第1页

(完整)数据结构考试题5--第2页

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

I.回路是简单路径

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