数构复习提纲.doc

期末考试题型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-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个结点起的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):相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究数据元素之间的相互关系，以及定义在其上的一组基本操作。 数据结构主要包括逻辑结构、存储结构和运算集合三部分的内容。 算法(Algorithm):是规则的有限集合，是求解特定问题的过程描述、操作步骤或指令序列。好的数据结构可以提高算法性能；通过算法研究可以加深理解数据结构。 算法的5个重要特性：1. 有穷性(Finiteness)2. 确定性(Definiteness)3. 可行性(Effectiveness)4. 输入项(Input)5. 输出项(Output)算法及其复杂性 算法复杂度：时间复杂度、空间复杂度。 与算法执行时间相关的因素： 算法选用的策略； 问题的规模； 编写程序的语言； 编译程序产生的机器代码的质量； 计算机执行指令的速度。 算法所需的存储空间包括： 输入数据所占的空间； 程序本身所占的空间； 辅助变量所占的空间。 算法时间复杂度的估算方法：从算法中选取一种原操作(对于所研究的问题来说，该操作是基本操作)，将该操作重复执行的次数作为算法时间复杂度的衡量准则。时间复杂度与原操作的执行次数之和成正比。 判断算法的时间复杂度，常见的有：O(1) O(log n) O(n) O(n log n) O(n2) O(n3) O(2n) O(n!) O(nn)特殊矩阵的压缩存储 特殊矩阵包括：下三角矩阵/上三角矩阵对称矩阵对角矩阵/带状矩阵递归函数和递归算法斐波那契、双递归函数、汉诺塔、背包问题、棋盘覆盖顺序表、折半查找算法定义：用一组地址连续的存储单元存储线性表的数据元素(a1, a2, , an)。顺序表基本操作(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 (keyLmid.key) right=mid-1;else left=mid+1;return 0; /折半查找算法的时间复杂度为O(logn)链表、循环链表栈、队列、循环队列哈希表：直接定址法、线性探测再散列、查找方法树的基本概念完全二叉树先序、中序、后序遍历二叉树（非递归）先序后继线索哈夫曼树、哈夫曼编码二叉排序树、平衡二叉树插入排序、希尔排序、冒泡排序、树形选择排序快速排序、堆排序、归并排序、基数排序、计数排序图的基本概念与存储结构深度优先搜索遍历、广度优先搜索遍历最小生成树、最短路径、拓扑序列、关键路径1-6 设数组A中只存放正数和负数。试设计算法，将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.elemi 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-Lchild) + 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(BiTree 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-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 = 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.next != 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中。