《数据结构》试卷第1套 .pdfVIP

三、单项选择题：(每小题1分，共5分)

1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:

A)顺序表B)用头指针表示的单循环链表

C)用尾指针表示的单循环链表D)单链表

2．假设以第一个元素为分界元素，对字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）

进行快速排序，则第一次划分的结果是：

A)(A,C,D,F,H,M,P,Q,R,S,X,Y)B)(A,F,H,C,D,P,M,Q,R,S,Y,X)

C)(F,H,C,D,P,A,M,Q,R,S,Y,X)D)(P,A,M,F,H,C,D,Q,S,Y,R,X)

3．下面是三个关于有向图运算的叙述：

（1）求有向图结点的拓扑序列，其结果必定是唯一的

（2）求两个指向结点间的最短路径，其结果必定是唯一的

（3）求AOE网的关键路径，其结果必定是唯一的

其中哪个（些）是正确的？

A)只有（1）B)（1）和（2）C)都正确D)都不正确

4．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为:

A)4B)5C)6D)7

5.以下关于广义表的叙述中,正确的是：

A)广义表是由0个或多个单元素或子表构成的有限序列

B)广义表至少有一个元素是子表

C)广义表不能递归定义

D)广义表不能为空表

四、填空题：(每小题2分,共20分)

1．一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,

若A[k]是非叶结点,则k的最小值是:，k的最大值是:。

2.设s=’YOUAREJUDGINGITRIGHTORWRONG’，顺序执行下列操作：

SubString(sub1,s,1,8);SubString(sub2,s,20,5);StrCat(sub1,sub2);则

最后sub1的值为：。

3.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂

度为________________。(((a),b),c)，(d)

4．广义表((((a),b),c),d)的表头是，表尾是。

5．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：

将累加。

6．要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地

址为s，子链表最后一个结点的地址为t,则应执行操作：

和。

7.用带头结点的循环链表表示的队列,若只设尾指针rear,则队空的条件

是。

8．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,

并且A[0][0]的存储地址是1024,则A[6][18]的地址是

9．在表示二叉树的二叉链表中,共有个空链域。

10．n个顶点的连通无向图至少有条边，至多有条边。

五、构造题：（每小题6分，共30分）

1．已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，给出对应的

二叉树。

2．已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括

主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。

3．给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，