数据结构试题

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

2. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2)

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

A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;

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

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

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

对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（ ），在被调用程序中可直接操纵实际参数。

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

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

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

8. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. –1

8. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。 A. 20 B. 18 C. 25 D. 22

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

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

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

O(nlog2n)。

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

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

A. 较慢

B. 较快

C. 相同

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

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

直接后继）。

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

A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_________行的元

素。

3. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。

4. 在一个链式栈中，若栈顶指针等于NULL则为________。

5. 主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，

它们都需要利用栈保存调用后的_________地址。

6. 在一棵树中，______结点没有后继结点。

7. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为______。假

定根结点的层数为0。

8. 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之

差的绝对值不超过________。

12. n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。

13. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为

________索引，若对应数据对象表中的若干个表项，则称此索引为________索引。

八、 判断题（每小题1分，共10分）

1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间

的逻辑顺序。

3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

4. 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

5. 一个广义表的表尾总是一个广义表。

6. 当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后

再按条件把它逐层向下调整，直到调整到合适位置为止。

7. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为

O(h)。

8. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有

关。