《数据结构》试卷(样卷).docVIP

学 院 商学院 专业班级 学 号 姓 名 ---○---○--- ---○---○--- ………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 中南大学考试试卷（样卷） 20 ~20 学年 学期 数据结构 课程 时间100分钟 48 学时，3 学分，闭卷，总分100分，占总评成绩70% 题 号 一 二 三 四 五 六 七 八 九 十 合 计 得 分 评卷人 复查人 得 分 评卷人 一、填空题(本题20分，每空1分) 1. 在单链表中，除第一个元素结点外，任一结点的存储位置均由___ _______其直接前驱结点的链域的值 _ ____指示。 2. 以折半查找方法查找一个线性表时，此线性表必须是____顺序存储结构______存储的___有序_____表。 3. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为____n-i___ 。 4. 栈下溢是指在_______ _______时进行出栈操作 5. 若进栈序列为 123456, 则能否得到 243156____、324165___ _、432156__ __、235164__ __ 的出栈序列 (能或不能)。 6. 在一个小顶堆中，堆顶结点的值是所有结点中的_______最小值_______，在一个大顶堆中，堆顶结点的值是所有结点中的_____最大值_________。 7. 若给定数组a[0..6]的各分量值分别为：A,B,C,D,E,F,G，按这些值顺序建立的完全二叉树的中序遍历结果序列为___DBEAFCG_____________, 后序遍历的结果序列为____DEBFGCA____________。 8. 在一棵二叉树中，第5层上的结点数最多为____16_____。 9. 假定一组记录的关键字为（46，79，56，38，40，80，36，40，75，66，84，24），对其进行插入排序的过程中，第三趟插入排序的结果为：__ 46 56 79 38，40，80，36，40，75，66，84，24 ________ __ _。（注：按非降序排列）。 10. 一棵含999个结点的完全二叉树的深度为__10_____。 11. 链式堆栈中弹出一个元素的操作序列为（设栈顶指针为top）____________、____________、____________、____________。 得 分 评卷人 二、构图题(本题40分) 1. 设有八个权值分别为（8, 7, 6, 5, 4, 3, 2, 1）的结点，构造其哈夫曼树，并计算其WPL的值。（注：WPL为带权路径长度。要求：画出哈夫曼树的完整构造过程）（10分）102 三、 四、 2. 从空树起，依次插入关键字11，22，9，88，7，10，12，30，23，构造一棵二叉排序树。 （1）画出该二叉排序树；（7分） （2）画出从（1）所得树中删除关键字为88的结点之后的二叉排序树。（3分） 3. 写出下面这棵普通树的先根及后根遍历结果，并将之转化为二叉树。（要求：画出转化过程）（10分） ① ② ③ ④ 先根遍历：即为二叉树的前序遍历12596103478 ⑤ ⑥ ⑦ ⑧ 后根遍历：即为二叉树的中序遍历95106237841 ⑨ ⑩ 4. 试写出序列{50,26, 38, 80, 70, 90, 8, 30} 按快速排序方法的第一趟排序过程及其它各趟排序结果。（10分） 23 26 38 8 50 90 70 80 学 院 商学院 专业班级 学 号 姓 名 ---○---○--- ---○---○--- ………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 得 分 评卷人 三、Hash表（本题15分） 1. 设表为HT[0..12],即表的大小为m=13。现采用法解决冲突。散列函数为： H(key)=key%13注：％是求余数运算mo