数构复习提纲

1、期末考试题型2014 年 6 月 6 日 星期五22:46一单选题 (含 20个小题，每小题 2 分，计 40分)二简答题 (含6个小题，每小题 6分，计 36分)21综合比较顺序表和链表的主要特点。22将中缀表达式 16 9 * ( 4 + 3 )转换成对应的后缀表达式 (要求按人工操作的步骤分步书写或描述 ) 。23设 const int N=3， int xN=0;void Backtrack(int t) if(t+1N) printf(n); for(int i=0; iN; i+) printf(%d,xi);else for(int i=0; iLchild & !T-Rchil

2、d) return 1; return Leafnode(T-Lchild)+Leafnode(T-Rchild);25用依次插入关键字的方法， 为序列 5，4，2，8，6，9 构造一棵平衡二叉树 (要 求保留构造过程中的各棵不平衡二叉树 ) 。26对关键字序列 503，87，512，61，908，170，897，275，653，426 分别执行下 列排序算法，写出第 1 趟排序后的关键字序列：(1)冒泡排序； (2)链式基数排序。设计题 (含 2个小题，每小题 12分，计 24分) 27给定两个带头结点的链表 La和 Lb，试设计一个高效的算法，将 La中自第 i 个 结点起的 m个结点，移

3、到 Lb 中的第 j 个结点之前。返回链表 La 和 Lb。28设计一种二进制编码， 使传送数据 a ，act ，case，cat ，ease，sea，seat ，state ， tea 的二进制编码长度最短。要求描述： (1) 数据对象； (2) 权值集； (3) 哈夫曼树； (4) 哈夫曼编码。期末复习范围2014 年 6 月 6 日 星期五 22:54数据结构基本概念 数据结构 (Data Structure) :相互之间存在一种或多种特 定关系的数据元素的集合。数据结构研究数据元素之间的相互关系，以及定义在其 上的一组基本操作。数据结构 主要包括逻辑结构、 存储结构和运算集合三部分 的

4、内容。算法 (Algorithm): 是规则的有限集合，是求解特定问题的 过程描述、操作步骤或指令序列。好的数据结构可以提高算法性能； 通过算法研究可以加 深理解数据结构。算法的 5 个重要特性：1. 有穷性 (Finiteness)2. 确定性 (Definiteness)3. 可行性 (Effectiveness)4. 输入项 (Input)5. 输出项 (Output)算法及其复杂性 算法复杂度：时间复杂度、空间复杂度。 与算法执行时间相关的因素： 算法选用的策略； 问题的规模； 编写程序的语言； 编译程序产生的机器代码的质量； 计算机执行指令的速度。算法所需的存储空间包括：输入数据所占

5、的空间；程序本身所占的空间；辅助变量所占的空间。算法时间复杂度的估算方法 ： 从算法中选取一种原操作 (对于所研究的问题来说，该操作 是 基本操作 )，将该操作重复执行的次数作为算法时间复杂 度的衡量准则。 时间复杂度与原操作的执行次数之和成正比。判断算法的时间复杂度，常见的有：O(1) O(log n) O(n) O(n log n) O(n 2) O(n3) O(2n) O(n!) O(n n)特殊矩阵的压缩存储特殊矩阵包括：下三角矩阵 / 上三角矩阵对称矩阵对角矩阵 / 带状矩阵递归函数和递归算法 斐波那契、双递归函数、汉诺塔、背包问题、棋盘覆盖 顺序表、折半查找算法定义： 用一组地址连

6、续的存储单元存储线性表的数据元素(a1, a2, , na)。顺序表基本操作(1)构造一个空的顺序表； (2)输出顺序表中所有数据元素的值；(3) 在第 i 个数据元素之前插入 1 个数据元素 ; (4)查找数据元素值 e 的数据元素 ;(6) 删除顺序表中的第 i 个数据元素；(7) 判断顺序表是否为空表；(8) 销毁顺序表。 折半查找： int BinSearch(KeyType key) left=1; right=L. n; /置区间初值 while (left=right) mid=(left+right)/2; if (key=Lmid.key) return mid; if (k

7、eyLmid.key) right=mid-1; else left=mid+1;return 0; / 折半查找算法的时间复杂度为 O(logn) 链表、循环链表 栈、队列、循环队列哈希表：直接定址法、 线性探测再散列、 查找方法 树的基本概念 完全二叉树 先序、中序、后序遍历二叉树(非递归)先序后继线索 哈夫曼树、哈夫曼编码二叉排序树、平衡二叉树 插入排序、希尔排序、冒泡排序、树形选择排序 快速排序、堆排序、归并排序、基数排序、计数排 序图的基本概念与存储结构 深度优先搜索遍历、广度优先搜索遍历 最小生成树、最短路径、拓扑序列、关键路径1- 6 设数组 A 中只存放正数和负数。试设计算法，

8、将 A 中的负数调整到前半区间， 正数调整到后半区间。分析算法的时间复杂度。int i = 0, j = n - 1;while (i j) while (Ai 0) j-;if (i = j) break;int tmp = Ai;Ai = Aj;Aj = tmp;2- 4 已知顺序表 L 递增有序。设计一个算法，将 a和 b插入 L 中，要求保持 L 递增 有序且以较高的效率实现。if (a b) int tmp = a; a = b; b = tmp; for (int i = n - 1; i = 0; i-) int j = i;if (L.elemi a) j+;if (L.ele

9、mi b) j+;L.elemj = L.elemi;if (j - i = 0) L.elemi+1 = a;L.elemi+2 = b;break; else if (j - i = 1) L.elemi+2 = b;while (L.elem-i a)L.elemi+1 = L.elemi;L.elemi+1 = a;break;3- 12 已知二叉树 T按照二叉链表存储，设计算法，计算 T 中叶子结点的数目。int Leaf(BiTree T) if (!T) return 0;if (!T-Lchild & !T-Rchild) return 1; return Leaf(T-Lch

10、ild) + Leaf(T-Rchild);3- 13 已知二叉树 T按照二叉链表存储，设计算法，交换 T 的左子树和右子树。void Swap(BiTree T) BiTree tmp = T-Lchild;T-Lchild = T-Rchild;T-Rchild = tmp;/ 不知道要不要交换所有节点的左右子树/ 如果只是交换根节点的左右子树，下面两句不要if (T-Lchild) Swap(T-Lchild);if (T-Rchild) Swap(T-Rchild);3- 15 设计算法，在先序线索二叉树中，查找给定结点 p 在先序序列中的后继。BiTree SearchSucc(Bi

11、Tree p) return P-Lchild ? P-Lchild : P-Rchild;3-21 给定 n 个整数，设计算法实现：(1) 构造一棵二叉排序树；(2) 从小到大输出这 n 个数。/(1) 构造二叉排序树 ( 假设 n 个数存在数组 A 中 )void create(BSTree& T) for (int i = 0; i data = Ai;s-Lchild = s-Rchild = NULL; if (!T) T = s; continue; BSTree p = T, q;while(p) q = p;if (s-data data) p = p-Lchild;if (s

12、-data p-data) p = p-Rchild;if (s-data data) q-Lchild = s;if (s-data q-data) q-Rchild = s;/(2) 输出二叉排序树 void print(BSTree T) if (!T) return; print(T-Lchild); printf(%d, T-data); print(T-Rchild);4- 10 设计一种排序算法，对 1000个0, 10000 之间的各不相同的整数进行排序， 要求比较次数和移动次数 尽可能少。int a10000, j = 0; /a: Hash 表， j: 计数for(i =

13、0; i 1000; i+) a ri - 1 = ri;for(i = 0; i 0) rj+ = ai;4- 13 设顺序表的结点结构为 (Type Key; int Next) ，其中， Key 为关键字， Next 为链 表指针。试设计静态链表排序算法。根据静态链表调整记录序列 (排序 )： void Arrange(RecordType *r, int n) for (i = 1; i n; +i) p = r0.next; RecordType tmp = rp; rp = ri; ri = tmp; / 交换记录位置 / 将 r0.next 指向第 i 个元素 if (ri.ne

14、xt != i) r0.next = ri.next; for (j = i+1; j =1; i-)int k=(int)pow(2,i); / 当前层最左结点编号for (int j=k; j=(int)pow(2,i+1)-1 & jLj+1 & jk+n-1) L(j+1)/2=Lj+1;L0=(int)pow(2,L0)+n-1; / 总结点数 (最后结点编号 ) /Bitree/ 基于完全二叉树的选择排序 void Sorting(int L,int n)for (int i=1; i0; k/=2)if (k%2) j=Lk-1;else j=Lk+1;if (jLk) Lk/2=j; else Lk/2=Lk;/Sorting4-16 假设采用链表存储类型： typedef struct RNodeint key; /数据域 (也是关键字域 ) struct RNode *next; /指针域 RNode, *RList;typedef RList RN;/ 链表类型 , 常变量 Nn又设 R1.n是10, 999之间的随机整数。试设计一个链表基数排序算法，将Rn中的数从小到大排序。排序结果仍存放在 Rn 中。G 中指定