2．
3． a b c d - * + e f / -
4．
4、 1. （1）图的邻接表 （略）
1 2 3 4 5 6 （2）. 遍历结果1、2、3、4、6、5 （3）． 生成树
2．最后hash表为 [本题答案应唯一。数据每放错一个扣1分。]
五 编程
堆，必须从键值为（ ? ）的结点开始对每个结点进行一次堆调 整。
三、问答题。（每题6分，共24分） 1． 直接选择排序是选出n个数据元素中最小的（或最大
的），与最左（右）边的数据元素相交换，然后按同 样的办法考虑剩下的n-1数据元素直到只剩下一个数据 元素为止。请分析直接选择排序算法的时间复杂度。 2． 已知关键字序列为36, 31, 20, 32, 66, 48,依次将各 元素插入到一棵初始为空的二叉排序树，画出对应的 二叉排序树。 3． 已知二叉树如左下图，试写出后序遍历结果。
二、填空题
（1）．12 （2）．1095 1225（3）．18 （4）．28 （5）． 4 （6）．12 （7）．O（n） （8）．行/列里1的个数 （9）．连通图 （10）．60
三、问答题 1．从n个数据中选择一个最值数据，需要n－1次比较，然后从从n－1个 数据中选择一个最值数据，需要n－2次比较，依次类推。其时间复杂度 为O（n2）
A. 栈 B. 队列 C.哈希表（Hash Table） D.
线性表
4. 设计一个判别表达式中左、右括号是否配对出现的算
法，采用（ ？ ）数据结构最佳。
A. 栈 B. 队列 C. 顺序结构线性表 D. 链式结构线
性表
5. 若某栈的输入序列为1,2,3,…,n，输出序列的第一个
元素为n，则第2个输出元素为（ ？ ）。
15．有n个球队参加的某联赛按单循环方式进行比赛，那么共需要进行（ ？ ）场比赛。 A．n(n-1) /2 B. n C. n(n-1) D. n+1
二、填空题（每题2分，共20分） 1．采用特殊字符作为串的结束，串S=“WinFilename”需要至少 长度为（ ? ） 的字符数组存放。 2．已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单 元。现将其下三角部分按行优先次序存储在起始地址为1000的 连续内存单元中，则元素A[5，6]对应的地址为（ ? ）。 3．已知完全二叉树的第5层有3个结点(根结点为第1层)，则其 结点数是（ ? ） 4．已知二叉树中叶子结点数为12，仅有一个孩子的结点数为 5，则总结点数是（ ? ）。 5．具有12个结点的完全二叉树的高度（空树高度为0）为 （ ? ）。
2. 设Hash函数为H(K)=K
mod
7，哈希表的地址空间为
0，．．．，6，开始时哈希表为空，用平方探测法解决冲
突，请画出依次插入键值9，14，10，30，56后的哈希表。
五、算法设计题。（共8分）
已知二叉树用二叉链表存储，试编写一函数实现计算该树的高度。 请定义必要的数据结构。
一、选择题
CABAB CDCBB ACDDA
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 11. 下列序列中，（ ？ ）是执行第一趟快速排序后得到的序列（排
序的关键字类型是字符串）。
A.[da,ax,eb,de,bb] ff [ha,gc] B.[cd,eb,ax,da] ff [ha,gc,bb]
C.[gc,ax,eb,cd,bb] ff [da,ha] D.[ax,bb,cd,da] ff [eb,gc,ha] 12．对包含N个元素的散列表进行查找，平均查找长度 （ ）
6．高度（空树高度为0）为5的AVL树，其结点数最少是 （ ? ）。
7．在链式结构的线性表中插入元素的算法复杂度是（ ? ）。 8．已知一个无向图的邻接矩阵表示，计算第j个结点的度的方 法是（ ? ）。 9．G为无向图，如果从G的某个顶点出发进行一次遍历，即可 访问图的每个顶点，则该图一定是（ ? ）图。 10．对于键值序列{12,13,11,18,60,15,7,18,25,100}，建里初始
4．现有森林如右上图，请画出对应的二叉树。
四、算法应用、分析题（共18分）
1. 图G各顶点的连接关系及相应权值如下图所示。（1）画出图
的邻接表存储图示（2）并从顶点1开始对图进行广度优先遍
历，写出遍历结果；（3）使用Kruskal算法求该图的最小生成 树，给出的形成过程。（11分）
5 4 1 53 3 2 6 2 6 4 6 7 3
重庆邮电大学 20xx－20xx 学年 《 数据结构 》 模拟考试题
题号 一 二 三 四 五 六 总分 分数 评卷人
注意：答案写到后面的答题纸上，按要求答题，并请保持字迹
清楚，容易阅读。
一、选择题（每题2分，共30分）
1. 栈和队列的共同点有（ ？ ）。
A．都是先进先出
B．都是后进先出
C．不会删除中间的元素 D． 完全没有共同点
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个元素
的时间复杂度为（ ？ ）（1<= i <= n+1 ）。
A. O(0) B. O(1) C. O(n)
D. O(n2)
9. 已知数据表A中每个元素距其最终位置不远，则采用（ ？ ）排序
算法最节省时间。
A.堆排序 B.直接插入排序 C.快速排序 D.简单选择排序 10. 任何一个无向连通图的最小生成树（ ？ ）。
2. 链表不具有的特点是（ ？ ）。
A.可随机访问任一元素
B.插入、删除不需要移
动元素
C.不必事先估计存储空计算机主机与打印机之间速度不匹配问题时通
常设置一个打印数据缓冲区，主机将要输出的数据依次写
入该缓冲区，而打印机则依相同次序从该缓冲区中取出数
据打印。该缓冲区作为数据结构是一个（ ？ ）结构。
A、为 O(log2N) B、为O(N) C、不直接依赖于N D、三者都 不是 13. 给定下列有向图和初始结点V1, 按深度优先遍历的结点序列为( ？ )
A、V1，V3，V4，V5，V2 B、V1，V2，V3，V4，V5 C、V1，V2，V5，V3，V4 D、V1，V2，V4，V5，V3
14. 串是（？）。 A.不少于一个字母的序列 B. 任意个字母的序列 C.不少于一个字符的序列 D.有限个字符的序列
A. 1
B. n-1
C. n
D.都有可能
6. 首先访问某结点的左子树，然后访问该结点，最后访问结
点的右子树，这种遍历称为（ ？ ） A.前序遍历 B.后序遍历 C. 中序遍历 D.层次遍
历 7. 下列排序算法中，时间复杂度不受数据初始状态影响，恒 为O(nlog2n)的是（ ？ ）。
A. 快速排序 B.冒泡排序 C.直接选择排序 D. 堆排序