数据结构试题(附有答案).pdfVIP

数据结构（本科）试卷7

一、选择题（每小题1分，共10分）

1.n

在一个长度为的顺序表的任一位置入一个新元素的渐进时间复杂度为（）。

2

A.O(n)B.O(n/2)C.O(1)D.O(n)

2.带头结点的单链表first为空的判定条件是：

A.first==NULL;B.first-link==NULL;

C.first-link==first;D.first!=NULL;

3.n

当利用大小为的数组顺序存储一个队列时，该队列的最大长度为（）。

A.n-2B.n-1C.nD.n+1

4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为

对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的

（），在被调用程序中可直接操纵实际参数。

A.空间B.副本C.返回地址D.地址

5.在一棵树中，（）没有前驱结点。

A.分支结点B.叶结点C.树根结点D.空结点

6.在一棵二叉树的二叉链表中，空指针数等于非空指针数加（）。

A.2B.1C.0D.1

–

7.9

对于长度为的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长

度为（）的值除以9。

A.20B.18C.25D.22

8.在有向图中每个顶点的度等于该顶点的（）。

A.入度B.出度

C.入度与出度之和D.入度与出度之差

9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于

O(nlogn)。

2

A.起泡排序B.希尔排序C.归并排序D.快速排序

10.α

当的值较小时，散列存储通常比其他存储方式具有（）的查找速度。

A.较慢B.较快C.相同

二、填空题（每小题1分，共10分）

1.二维数组是一种非线性结构，其中的每一个数组元素最多有____2___个直接前驱（或直

接后继）。

2.nAB

将一个阶三对角矩阵的三条对角线上的元素按行压缩存放于一个一维数组中，

A[0][0]B[0]B[K]A_

存放于中。对于任意给定数组元素，它应是中第

公式n*（n+1）/2+j=k_行的元素。(n为行数，j为列数)

3.