联合考试试卷(数据结构B卷)

…………………………密……………………封……………………线……………………………… 湖北省计算机类专业人才培养合作联盟 联合考试 2013-2014学年第 1 学期 期末考试试卷 学院 专业 级 学号 姓名 课程名称：数据结构 试卷类型：B卷 共 6 页 考试形式：闭卷笔试 适用范围： 学院（系） 年级 专业 本科 一、判断题 (每小题1分，共10分) 1． 数据的逻辑结构与各数据元素在计算机中如何存储有关。 2. 凡是为空的单链表都是不含任何节点的。 3． 对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。 4． 含有n个字符的字符串中所有子串的个数为n*(n+1)/2 + 1。 5． 递归算法的执行效率比功能相同的非递归算法的执行效率高。 6. 在n（n > 3）阶三对角矩阵中，每一行都有三个非零的元素。 7． 霍夫曼树中不存在度为1的节点。 8. 强连通图不能进行拓扑排序。 9. 二叉排序树是用来进行排序的。 10. 排序的稳定性是指排序算法中比较的次数保持不变，且算法能够终止。 二、填空题 (每小题1分，共10分)

B－1 共 6 页 注意事项：

1. 考生将姓名、学号等信息写在试卷相应位置； 2. 必须使用蓝(黑)色钢笔或签字笔在规定位置答题； 3. 注意字迹清楚，保持卷面整洁。

1. 一个算法具备的5个特性分别是可行性、有穷性、______、输入和输出。

2. 在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为______。

3. 栈是一种具有______特性的线性表。

4. 无论是顺序队列还是链式队列，插入和删除运算的时间复杂度都是______。

5. 递归函数f(1)=1，f(n) = f(n-1) + n(n>1)的递归出口是______。 6. 完全二叉树中节点个数为n，则编号最大的分支节点的编号是______。

7. 对n个顶点的连通图来说，它的生成树一定有______边。 8. 采用哈希存储方法时，用于计算节点存储地址的是______。 9. 对二叉排序树进行______遍历，可以得到按关键字从小到大排列的节点顺序。

10．在排序过程中，不比较关键字大小的排序方法是______。

三、单向选择题 （每小题2分，共30分）

1. 算法的时间复杂度与______有关。

A、问题规模

B、计算机硬件性能 D、程序设计语言

C、编译程序质量

2. 链表不具有的特点是______。

A、可随机访问任一元素

B、插入删除不需要移动元素 D、所需空间与线性表长度成正比

C、不必事先估计存储空间

B－2 共 6 页

…2，3，...，n， 其输出序列是P1, P2,..., …3. 已知一个栈的进栈顺序是1，…Pn, 若P1=n，则Pi的值为______。 …A、i B、n-i …C、n-i+1 D、不确定 ……4. 设顺序循环队列中数组的下标是0～N-1，其头、尾指针分别为f（指…和r（指向队尾元素），则其元素个数为______。 …向队头元素的前一个位置）…A、r-f B、r-f-1 密C、(r-f)%N+1 D、(r-f+N)%N ……5. 将递归算法转换成对应的非递归算法时，通常需要使用______保存中……间结果。 …A、队列 B、栈 …C、链表 D、树 ……6. 若3叉树中有a个度为1的节点、b个度为2的节点、c个度为3的封…节点，则该树有______个叶子节点。 …A、1 + 2b + 3c B、1 + 2b + 3c …C、2b + 3c D、1 + b + 2c ……7. 若二叉树的中序遍历序列是abcdef，且c为根节点，则______。 …A、c左子树中有两个节点 B、二叉树有两个度为0的节点 ……C、二叉树的高度为5 D、以上都不对 线…8. 无向图的邻接矩阵是一个______。 …A、对称矩阵 B、零矩阵 …C、上三角矩阵 D、对角矩阵 ……9. 在如图1所示的平衡二叉树中插入关键字50后，得到一棵新平衡二……叉树，在新平衡二叉树中，关键字37所在的节点的左右孩子节点中保存…的关键字分别是______。 …… …B－3 共 6 页 … 学院 专业 级 学号 姓名 注意事项：

1. 考生将姓名、学号等信息写在试卷相应位置； 2. 必须使用蓝(黑)色钢笔或签字笔在规定位置答题； 3. 注意字迹清楚，保持卷面整洁。

A、13，50 C、24, 53

24

B、24，50 D、24, 90

13533790

图1 一棵平衡二叉树

10. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。

A、完全图 C、有回路

B、连通图 D、一棵树

11. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定节点所在的块，则每块分为______个节点最佳。

A、9 C、6

B、25 D、5

12. 具有5层节点的AVL树至少有______个节点。

A、10 C、15

B、12 D、17

13. N条记录中按关键字大小找出TopK(k << N)条记录，使用下列______方法最节省时间。

A、堆排序

B、希尔排序

B－4 共 6 页