10－11第一学期期末考试试卷
《期末考试》
                   
                                                                         
一、名词解释 （每小题4分，共20分。）
    例：平衡二叉树
二、填空题（每小题2分，共10分。）
1.如果一棵完全二叉树中有1001个结点，则树中包含的叶子结点有  个。
三、问答题（每小题5分，共10分。）
1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么
情况下使用顺序表比链表好？
四、应用题（每小题5分，共30分。）
1.下表给出了字符在文本中出现的次数，请为这些字符设计编码方案并写出所设计的编码，要求设计的编码能正常译码并且平均码长最短。
数据结构与算法题库
字符
a
b
c
d
e
f
g
出现次数
12
32
21
15
27
34
9
2. 已知图如下： 
请画该图的最小生成树，并分别写出从顶点1出发按深度优先搜索遍历得到的顶点序列和按
广度优先搜索遍历等到的顶点序列（设每个顶点邻接表中的结点按顶点序号从大到小链接）。
3. 若对一个关键字序列{15,76,41,20,16,28,57,31}进行哈希造表，其哈希函数为H(key)=key%13, 处理冲突的方法为二次探测再散列，探测序列为：
Hi=(H(key)+di)%13    di =12,22,32……
解答下列问题：
（1）画出该哈希表。
（2）对表中关键字31、20、16进行查时，所需进行的比较次数各为多少？
（3）该哈希表在等概率查时查成功的平均查长度为多少？
4. 对序列（Tom, Dot, Simth, Kim, Ege, Ann, Jim, Kit）按字母顺序进行堆排序，画出初始堆及每选出一个排序码后堆的变化。
四、算法设计题（每题10分，30分。）
1.已知整数序列(a1,a2,…an)按顺序存储，且每个元素是均不相等。设计把所有正数移到所有的负数前面的算法(要求算法耗费时间和使用辅助空间尽可能的少)。
2.设二叉树中各结点保存的数据均为整数，设计算法判断该树是否为一棵二叉排序树，并说明你设计的算法的正确性。
3. 设计非递归算法，实现二叉树（以二叉链表存储）进行先序遍历。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。