2008数据结构试卷.doc

学 院 商学院 专业班级 学 号 姓 名 ---○---○--- ---○---○--- ………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 中南大学考试试卷 2009 ~2010 学年 2 学期 数据结构 课程 时间100分钟 48 学时，3 学分，闭卷，总分100分，占总评成绩70% 题 号 一 二 三 四 五 六 七 八 九 十 合 计 得 分 评卷人 复查人 （注：直接在试卷上答题！！！） 得 分 评卷人 一、填空题(本题20分，每空1分) 1. 以折半查找方法查找一个线性表时，此线性表必须是__________存储的________表。 2. 内部排序分为插入、交换、选择、___ _ ___、___ _ ___排序五类。 3. 在长度为n的顺序表中删除第i个元素时移动数为_______ 。 4. 假设以数组Q[0..m-1]存放循环队列的元素,若判断队空的条件为“rear= =front”，则判断队满的条件为 。 5. 栈的操作特点为__ _ _；若已知进栈序列为123456，则能否得到345612__ _ _、123456__ _ _、216534__ _ _ 的出栈序列(能/不能)。 6. 若给定数组T[0..7]的各元素值分别为：a,b,c,d,e,f,g,h，按这些值建立的完全二叉树的先序遍历结果序列为___ ___ , 中序遍历结果序列为___ ___ ，后序遍历结果序列为___ ___ 。 7. 深度为7的满二叉树有__ _个结点，其中叶结点的个数为_________。 8. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，该线性表宜采用_ ______存储结构。 9. 中缀表达式A-(B+C/D)*E的前缀形式是___ ___ ，其后缀形式是_ __ ___ 。 10. 在头指针为head的带头结点的单链表的第一个元素结点前插入一个结点q的主要操作步骤是_____ __ ____；______ ______（设各结点的指针域为link）。 得 分 评卷人 二、计算题（5分） 1. 已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，求该树中叶结点的个数。（5分） 三、 四、 得 分 评卷人 三、构图题(本题35分) 1. 假设字符a,b,c,d,e,f,g,h}中各字符的使用频度分别是0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10｝。试用哈夫曼（huffman）算法设计一套二进制编码。 要求：（1）画出哈夫曼树；（要求有完整构造过程） （2）给出SET中各字符的编码表。（10分） 2. 从空树起，依次插入关键字48，18，27，45，42，46，22，47；构造一棵二叉排序树。画出该二叉排序树；（5分） 3. 写出下面这棵普通树的先根及后根遍历结果，并将之转化为二叉树。（要求：画出转化过程）（10分） ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 学 院 商学院 专业班级 学 号 姓 名 ---○---○--- ---○---○--- ………… 评卷密封线 ……………… 密封线内不要答题，密封线外不准填写考生信息，违者考试成绩按0分处理 ……………… 评卷密封线 ………… 4. 写出序列{46，56，38，40，80，36，75，66，84，24}按快速排序方法的第一趟排序过程及其它各趟排序结果。（10分）（结果按非降序排列！） 得 分 评卷人 四、Hash表（本题15分） 1.设有关键字序列K=19，01，23，14，55，20，84，27，68，11，10，77；存放在地址空间为100～116的散