科目名称：数据结构
请注意：答案必须写在答题纸上（写在试题上无效）。
一、单项选择题（每小题2分，共20分）
1．每个结点有多个后继结点的数据结构有____ ______。
A） 线性表        B） 队列          C） 图            D） 栈
2．一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是___ ______。
A）2 3 4 1 5      B）5 4 1 3 2        C）2 3 1 4 5        D）1 5 4 3 2
3．以下的4棵二叉树中，_________不是完全二叉树。
            A）                    B）                C）                    D）
4．一棵非空二叉树的前序序列和中序序列正好相同，则该二叉树一定满足_______。
A）其中任意一结点均无左孩子      B）其中任意一结点均无右孩子
C）是一棵完全二叉树              D）是任意一棵二叉树
5．一棵度为4的树，n1 ,n2 ,n3 ,n4分别是度为1 ，2 ，3 ，4的结点个数，终端结点个数为n0 ，则有___ _____。
A）n0 = n1 + n2 + n3 + n4            B）n0 = 2n4 + n3 + 1     
C）n0 = 4n4 + 3n3 + 2n2 + n1          D）n0 = 3n4 + 2n考试之后3 + n2 + 1
6．关键码序列K = { 23， 40， 28， 19， 20， 42 }，经过筛选法建堆过程后，得到的最小堆为___ ______。
A）19，20，28，40，23，42          B）19，28，20，40，23，42        
C）42，40，28，23，20，19          D）42，28，40，20，23，19
7．有向图G用邻接矩阵A存储，则顶点i的入度等于A中____ _____。
A）第i行元素之和                B）第i行的元素之和与第i列元素之和的乘积
C）第i行与第i列元素之和        D）第i列元素之和
8．有拓扑排序的图，一定是____ _____。
A）有环图      B）无向图    C）无环有向图      D）无环任意图
9．有一个有序表为{ 2，11，16，23，32，45，51，62，73，79，80，94，97 }，当二分检索关键码值为94的数据元素时，_____ _______次比较后查成功。
A）1          B）2          C）3              D）4
10．在待排序的元素序列基本有序的情况下，下面的____________算法效率最高。
A）插入排序        B）选择排序        C）快速排序        D）归并排序
二、已知某二叉树的前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ，请完成：
（1）画出该二叉树；
（2）将该二叉树转换为对应的森林。  （10分）
三、给定序列K = { 12，8，10，14，16，6 }，请完成：
（1）按K中关键码的顺序依次插入一棵初始为空的二叉搜索树，画出插入完成后的二叉搜索树；
（2）以序列K作为一组给定的权值，构造关于K的一棵哈夫曼（Huffman）树，并求它的带权外部路径长度。  （12分）
四、已知一个带权图G的顶点集V和边集E分别为：
V = { a，b，c，d，e，f }，
E ={(a，b)，(a，c)，(b，c)，(c，d)，(b，e)，(c，e)，(d，f)，(e，f) }，
E中各边对应的权值如下：
(a，b)：1， (a，c)：3， (b，c)：3， (c，d)：6，
(b，e)：4， (c，e)：5， (d，f)：4， (e，f)：5
请完成：
（1）画出图G；
（2）画出图G的邻接表表示；
（3）根据（2）中画出的邻接表，写出从顶点a出发进行深度优先搜索（DFS）产生的深度优先序列；
（4）从顶点a开始，用Prim算法构造图G的一棵最小生成树，并画出生成过程。
（20分）
五、下图是一带权有向图，试采用Dijkstra算法求从顶点a到其他各顶点的最短路径，要求给出整个计算过程。（13分）
六、若一棵树中有度数为1 至m 的各种结点数为n1,n2,…,nm(nm 表示度数为m 的结点个数)请推导出该树中共有多少个叶子结点n0 的公式。（10分）
七、在堆排序、快速排序和合并排序中：
(1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？
(3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？
(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ （10分）
八、已知一组元素的排序码为{ 42，55，13，46，94，5，17，70 }，利用快速排序，每次都取子序列的中间元素作为轴值，写出每一层划分后的排列结果。（10分）
九、一个线性表关键码值集合为{ 26，23，40，45，33，55，31，69 }，设散列地址空间为HT[11]（下标位置为0，1，…，10），散列函数为 h( K ) = K % 7，并用线性探查法解决冲突。请完成：
（1）画出相应的散列表；
（2）计算在等概率下成功检索的平均检索长度。  （15分）
十、编写一个函数count（），传入参数为一棵二叉树（不是二叉搜索树BST）和一个较小的值mink和一个较大的值maxk，返回值介于mink和maxk之间的结点数目。（15分）
十一、假设有一个循环链表的长度大于1，结点中数据的数据类型为DataType，且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，要求写出：
（1）循环链表的类型定义；
（2）在该循环链表中，删除所有DataType值为X结点的算法。  （15分）
 
附赠材料：
考试做题技巧
会学习,还要会考试
      时间分配法： 决定考场胜利的重要因素
    科学分配答题时间,是决定考场能否胜利的重要因素。有了时间上的合理安排,同学们紧张的心情就可以得到舒缓与放松,考试水平也就能最大限度的得到发挥。下面,我们为同学们介绍一个应对的好办法时间分配法。
    第一,考前分配好时间。从发试卷到正式开考前有几分钟的阅卷时间拿到试卷并填好卷头以后,要浏览整张试卷,查看试卷的容量、试题的难易程度。然后,根据题目、题量、分值和难易程度分配做题时间,易题和少分题少用时间,难题和多分题多用时间。
    比如数学,按分值分配,选择题大约应安排在50~55分钟左右完成,非选择题大约安排90~95分钟左右完成为宜。同学们平时做题时,可以先测试自己每一部分题目的做题时间,定下一个
标准,然后考试时根据试卷题目情况,在原来的基础上调整。看到哪一部分有较难的题目,可适当多匀一点时间。
    第二,每个题目有一个时间标准。如果遇到一道题目,思考了3~5分钟仍然理不清解题的思路时,应视为难题可暂时放弃,等到后面有了思路或答完卷之后再回头来做。这样一来就不会出现不能控制时间而影响答后面题目
    况。同时,要注意虽然每个题目有一定的时间限制,但也不要每题都看否则会弄得自己很紧张
    第三,考试最后的15分钟。不管还有多少题目没有完成,考试的最后15分钟一定要先将答题卡涂好,避免答题无效。
        答题六注意：规范答题不丢分
    提高考分的另一个有效方法是减少或避免不规范答题等非智力因素造成的失分,具体来说考场答题要注意以下六点：
    第一,考前做好准备工作。做题前要做好准备工作,包括认真检查答题卡页数和条形码上的姓名、考号与本人的姓名、准考证上的号是否相符等。此外,还要准确填写答题卡的相关信息,正确粘贴条形码,注意不能超出框外。
    第二,使用规定的笔作答。答选择题时,考生必须用2B型铅笔在答题卡上的“选择题答题区”内将对应题目的选项字母点涂黑