数据结构期末考试试题 .pdfVIP

武汉大学计算机学院

2010年－2011学年第一学期“数据结构”考试试题（A）

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

1.下列各项中属于逻辑结构的是。

A.哈希表B.有序表C.单链表D.顺序表

2.以下算法的时间复杂度为。

voidfun(intn)

{inti=1;while(i=n)i=i*2;}

2

A.O(n)B.O(n)C.O(nlogn)D.O(logn)

22

3.在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动个元素。

A.nB.i-1C.n-iD.n-i+1

4.判断带头结点的循环单链表L中只有一个结点的条件是。

A.L==NULLB.L-next==L

C.L-next-next==LD.L-next==NULL

5.中缀表达式a*(b+c)-d的后缀表达式是。

A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd

6.设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前

一个位置，r指向队尾元素的位置），则其元素个数为。

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

7.若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，

队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元

素，再加入两个元素后，rear和front的值分别为。

A.1和5B.2和4C.4和2D.5和1

8.稀疏矩阵采用压缩存储后，通常必会失去功能。

A.顺序存储B.随机存取C.输入输出D.以上都不对

9.一棵有124个叶子结点的完全二叉树，最多有个结点。

A.247B.248C.249D.250

10.n个结点的线索二叉树上含有的线索个数为。

A.2nB.n-1C.n+1D.n

11.由带权为9、2、5、7的4个叶子结点构成的一棵哈夫曼树的带权路径长度是。

A.23B.37C.46D.44

12.若邻接表中有奇数个边表结点，则一定是。

A.图中有奇数个结点B.图中有偶数个结点

C.图为无向图D.图为有向图

13.最小生成树指的是。

A.由连通图所得到的边数最少的生成树

B.由连通图所得到的顶点数相对较少的生成树

C.连通图中所有生成树中权值之和为最小的生成树

D.连通图的极小连通子图

14.以下关于图的叙述中正确的是。