高升本课程复习资料-计算机高本-数据结构与算法-数据结构 复习题2

 **** **** **** **** **** **** **** **** *** * *** * * * * * * * * ： ： * 名 级 年* 业 *姓 专 * * * * * * * * *： ： 号 院* 证 *考 准 学* *** **** **** **** **** **** **** **** **** **** **** **** 课程名称： 数据结构- 树、排序 课程考试试卷 题 号 一 二 三 四 五 六 七 八 总分 阅卷 教师 得 分 …………………………………………………………………………………………………… 得 一、单选题（每小题 2 分，共10分，本题所给四个答案中只有一个是正分 确的） 1．将含有100个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上而下，同一层从左向右连续编号，则编号最小的叶子结点的编号为 。 （A）47 （B）48 （C）49 （D）50 2．对一颗二叉排序树进行 得到的结点序列是一个有序序列。 （A）前序周游 （B）中序周游 （C）后序周游 （D）层次周游 3．设只含根结点的二叉树的高度为1，则高度为10的二叉树, 至少有_________个结点。 （A）10 （B）20 （C）30 （D）40 4．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。下列四种排序方法中 是稳定．．．的排序方法。 （A）shell排序 （B）快速排序 （C）归并排序 （D）简单选择排序 5．若表R在排序前已按键值递增顺序排列，则 算法的比较次数最少。 （A）直接插入排序 （B）快速排序 （C）归并排序 （D）选择排序 得 二、填空题（每空 1 分，共5分） 分 1. 已知完全二叉树的第5层有8个结点(根结点在第1层), 则其叶结点数是

_____12_______。 2. 在有n个叶结点的Huffman树中, 共有__2n－1___个结点。 3. 采用____顺序表____结构来存储和表示完全二叉树是最有效的。 4. 当记录个数比较少且基本有序时，__直接插入排序___是最有效的排序方法。 5. 内部排序问题的时间复杂度的下限是 _ O(nlogn) 。 得 分 三、判断题（若正确，在括号内打“”，否则打“×”；每题1分，共5分） 1．没有一个结点的二叉树称为空树。 （  ） 2．一棵二叉树不能存储在一维数组中。 （ × ） 3．归并排序即适合内排序，也适合外排序。 （  ）

4．快速排序在最差情况下的时间复杂度是O（n2），此时它的性能并不比冒泡排序更好。

（  ） 5．删除二叉排序树中的一个结点, 再重新插入进去, 一定能得到原来的二叉排序树。

（ × ） 四、解析题（每题10分，共50分） 1． 根据下面的字母/频率表构造一棵Huffman树, 并给出各字母的Huffman编码。 得 分 A B C D E 1 4 9 16 25 解答： 55301451A4B9C16D25E A的编码 0000 B的编码 0001 C的编码 001 D的编码 01 E的编码 1

2． 已知一棵二叉树如下，请分别写出按前序、中序、后序和层次遍历时得到的结点序列。 解答： 前序遍历得到的结点序列为：A B D G C E F H 中序遍历得到的结点序列为：D F B A E C H F 后序遍历得到的结点序列为：G D B E H F C A 层次遍历得到的结点序列为：A BＣＤＥＦＧＨ 3．请证明非空满二叉树的叶结点数等于其分支结点数加1。 证明: 设分支结点数为n, 根据满二叉树的定义, 每一个分支结点都有两个非空子结点, 所以共有2n个非空子结点, 加上根结点, 该二叉树总共有2n+1个结点, 除去n个分支结点, 剩下n+1个叶结点 4．请画出把如下的完全二叉树构建成最大值堆的过程。

5．采用直接插入排序算法, 对关键字序列(49, 38, 65, 97, 76, 13, 27 )按从小到大的次序进行排序, 写出每趟排序的结果。 解答： 初始关键字: [49] 38 65 97 76 13 27 i=1: [38 49] 65 97 76 13 27 i=2: [38 49 65] 97 76 13 27 i=3: [38 49 65 97] 76 13 27 i=4: [38 49 65 76 97] 13 27 i=5: [13 38 49 65 76 97] 27 i=6: [13 27 38 49 65 76 97] 五、算法设计题（每题10分，共30分） 得 分 1．下面给出了冒泡排序的算法，请在算法的空缺处填入适当内容，使之能够正常工作，得到一个递增的序列。 Void bubsort(Elem A[], int n) {//数组R中有n个记录 int i,j; Elem t； for (i=0; ① ; i++) { for (int j=n-1; ② ; j--) { if (A[j] < A[j-1]) {//交换 ③ ; ④ ; ⑤ ; } } } 1： ii 3: t = A[j] 4: A[j-1] = A[j] 5: A[j] = t 2．试设计一个前序周游二叉树的函数。

void preorder(BinNode* subroot) { if (subroot == NULL) return; visit(subroot); preorder(subroot->left()); preorder(subroot->right()); } 3．编写求二叉树的结点数目的算法。 int nodenumbet (bitree *root) { if (root = = NULL) return 0; return (1+ nodenumber (root->lchild) + nodenumber (root->rchild)); }