数构复习提纲

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-

2、rchild) 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 个结点起

3、的 m个结点，移到 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、所占的空 ； 助 量所占的空 。算法 复 度的估算方法：从算法中 取一种原操作 ( 于所研究的 来 ， 操作是基本操作 )，将 操作重复 行的次数作 算法 复 度的衡量准 。 复 度与原操作的 行次数之和成正比。判断算法的 复 度，常 的有：23no(1) o(log n) o(n) o(n log n) o(n) o(n ) o(2 )n o(n!) o(n)特殊矩阵的压缩存储特殊矩 包括：下三角矩 / 上三角矩 称矩 角矩 / 状矩 递归函数和递归算法斐波那契、双 函数、 塔、背包 、棋 覆盖顺序表、折半查找算法定 ： 用一 地址 的存 元存 性表的数据元素(a , a2, n)。1, a

6、;.顺序表基本操作(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)returnmid;if (keylmid.key)right=mid-1;elseleft=mid+1;return0;

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

8、 (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.elemi b) j+;l.elemj = l.elemi;if (j - i = 0) l.elemi+1 = a;l.elemi+

9、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-lchild) + leaf(t-rchild);3-13 已知二叉树 t 按照二叉链表存储，设计算法，交换t 的左子树和右子树。

10、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(bitree p) return p-lchild ? p-lchild : p-rchild;3-21 给定 n 个整数，设计算法

11、实现：(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-data p-data) p = p-rchild;if (s-data data) q-lchild = s;if (s-data

12、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 = 0; i 1000; i+) a ri - 1 = ri;for(i = 0; i 0) rj+ = ai;4-13 设顺序表的结点结构为 (t

13、ype 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.next != i)r0.next = ri.next;for (j = i+1; j =1; i-)int k=(int)pow(2,i);/ 当前层最左结点编号f

14、or (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 中。5-5