1、考试题型选择题： 21 分填空题： 18 分判断题： 15 分图表题： 26 分算法题： 20 分1.什么是图的邻接矩阵表示法？什么是图的邻接表表示法？在这两种存储结构上如何计算顶点的度？邻接矩阵一个有 n 个顶点的图 G=(V,E)的邻接矩阵是一个 n n 的矩阵 A，A 的每个元素是0 或 1。设 V=0,1,2,n-1,如果 G 是无向图，则 A 的元素定义为：1 (u,v) EA(u,v) =0 其他如果 G 是有向图，则 A 的元素定义为：1 EA(u,v) =0 其他如果 G 是带权的图，则邻接矩阵中值为 1 的元素应替换为权值，有时需要将 0替换为 。(详见 PPT unit7-
2、1 20-21)邻接表要点：1. 为图中每一个顶点建立一个单链表；2. 顶点 u 的单链表中，每一个结点 v 表示一个邻接点，即代表一条边(u,v) 或 3. 结点和边的结构如下：4.每个单链表的头指针存入一个一维数组，以表示一个图。(详见 PPT unit7-1 20-21)2.什么是堆？什么是最大堆？什么是最小堆？如何利用下推（筛选）操作建堆？如何利用逐步插入结点（上推）的操作建堆？一个大小为 n 的堆（heap）是一棵包含 n 个结点的完全二叉树。每个结点的关键字值大于等于双亲结点的关键字值的堆称为最小堆（MinHeap） 。最小堆的另一定义当完全二叉树以顺序方式存储时，实际上得到的是结
3、点序列，所以最小堆又可以定义为：堆是 n 个元素的序列（k 1,k2,kn） ，当且仅当满足ki k2i 且 ki k2i+1, ( i=1,2,n/2 ) 时,称为最小堆。函数 AdjustDown（向下调整）设序列以顺序方式保存在一维数组中，数组元素具有可比较大小的类型。函数 AdjustDown 假定从数组中 r+1 到 n，这 n-r 个位置上的元素已满足 ki k2i 且 ki k2i+1,(i=r+1,2,n/2) 条件，现向下调整第 r 位置上的元素，如果 kr大于 k2r 和 k2r+1,(即左、右孩子)中的较小的元素，则将 kr与该较小元素交换，继续这样(向下调整)的过程，直
4、到不再需要调整，或到达堆的底部为止。（详见 PPT unit 6 堆排序 PPT unit 4-2 堆）3.什么是二叉树的前序、中序、后序遍历？给出其中的两种遍历次序如何写出第三种遍历次序？先序遍历若二叉树为空，则空操作；否则,访问根结点；先序遍历左子树；先序遍历右子树。中序遍历若二叉树为空，则空操作；否则,中序遍历左子树；访问根结点；中序遍历右子树。后序遍历 若二叉树为空，则空操作；否则,后序遍历左子树；后序遍历右子树；访问根结点。(详见 PPT unit4-1 21-22)4.什么是二叉搜索树和 AVL 树？有何性质？如何进行插入和查找的操作？二叉搜索树（binary search tre
5、e）也称二叉排序树（binary sort tree） 。二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：（1）每个结点由关键字值表征，所有结点的关键字值各不相同；（2）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（3）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；（4）左、右子树也分别是二叉搜索树。(详见 PPT unit5-1 22)二叉搜索树的搜索算法搜索算法思路是：若二叉树为空，则搜索失败。否则，将 k 与根的关键字值比较，若 k 小于该关键字值，则用同样的方法搜索左子树，而不必搜索右子树;若 k 大于该关键字值，则用同样的方法搜索右
6、子树，而不必搜索左子树 ;若 k 等于该关键字值，则搜索成功终止。二叉搜索树的插入算法插入算法思路是：(1)确定新元素的插入位置。搜索插入位置的方法与 Search 函数的做法类似，但要求在从根结点往下搜索过程中，用指针 q 记录下当前元素的双亲结点。如果在搜索中，遇到相同关键字值的元素，则表明有重复元素，那么显示 Duplicate 信息。(2)插入新元素如果二叉搜索树是空树，则新元素 e 成为树根。如果 e 的关键字值小于 q 结点的值，则将新元素 e 作为 q 的左孩子，否则作为其右孩子。AVL 树：一棵 AVL 树或者是空树，或者是具有下列性质的二叉搜索树：它的左子树和右子树都是 AV
7、L 树，且左子树和右子树的高度之差的绝对值不超过 1。（每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子 balance 。 ）(详见 PPT unit5-2 4)AVL 树的插入（详见 PPT unit5-2）在向一棵本来是高度平衡的 AVL 树中插入一个新结点时，如果树中某个结点的平衡因子的绝对值 |balance| 1，则出现了不平衡，需要做平衡化处理。在 AVL 树上定义了重载操作“”和“, ,都是图 G 中的边。路径长度: 指路径上边的数目。(详见 PPT unit7-1 11)6. 什么是链表？怎样完成插入和删除操作？用链接方式表
8、示的线性表为链表(详见 PPT unit2 29)插入和删除操作详见 PPT unit2 38-437. 什么是逻辑结构？什么是存储结构？有哪几种典型的逻辑结构和存储结构？逻辑结构：数据元素之间的逻辑关系。集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系；线性结构：结构中的数据元素之间存在一对一的关系；树形结构：结构中的数据元素之间存在一对多的关系；图结构：结构中的数据元素之间存在多对多的关系。(详见 PPT unit1 12)存储结构：逻辑结构在存储器中的映象。数据的存储结构：“ 数据元素” 的存储；“关系”的存储数据元素的存储方法用二进制位(bit) 的位串表示数
9、据元素e.g.(321)10 = (101000001)2A = (001000001)2关系的存储方法顺序存储：以相对的存储位置表示后继关系链式存储：以附加信息(指针) 表示后继关系(详见 PPT unit1 15-16)8. 什么是栈、队列？它们有哪些典型的使用场合？栈的定义：栈是限定插入和删除操作都在表的一端进行的线性表。若栈中无元素，则为空栈。允许插入和删除元素的一端称为栈顶，另一端称为栈底。S=(a1,a2,an) （栈的应用详见 PPT unit 3）队列是限定在表的一端插入，在表的另一端删除的线性表。若队列中无元素，则为空队列。队尾允许插入元素的一端队头允许删除元素的另一端Q=(
10、a1,a2,an) （队列栈的应用详见 PPT unit 3）9. 什么是循环链表？什么是循环队列？它们有什么区别？循环链表：不带表头结点的单循环链表(详见 PPT unit2 45)循环队列：把数组从逻辑上看成是一个头尾相连的环。(详见 PPT unit3 36)10. 什么是算法复杂度？什么是复杂度分析？算法的空间复杂度：是程序运行从开始到结束所需的存储量。渐近时间复杂度：使用大 O 记号表示的算法的时间复杂度，称为算法的渐近时间复杂度。 (详见 PPT unit1 86-93)11. 什么是拓扑排序？拓扑排序算法怎样进行?拓扑排序是求解网络问题所需的主要算法，PERT (Program
11、Evaluation and Review Technique，计划评审技术)和 CPM (Critical Path Method，关键路径法)都要用到。(详见 PPT unit7-2 5)拓扑排序算法： 1）在图中找一个入度为零的顶点，输出之；2）从图中删除该顶点及其所有出边（产生新的入度为零的顶点）3）重复(1)、(2)，直到所有顶点都输出，或图中剩下的顶点再也没有入度为零的顶点(存在有向回路) 为止。(详见 PPT unit7-2 8)12.怎样实现链式栈和链式队列？栈的链接表示法（链式栈）：链式栈的定义和操作的实现类似于单链表，请自行实现之。不带表头结点的单链表(详见 PPT uni
12、t3 14 及以前)队列的链接表示法（链式队列）：链式栈的定义和操作的实现类似于单链表，留作作业，请实现之。不带表头结点的单链表（详见 PPT unit3 46 及以前） （自行看作业）13.选择排序、堆排序、冒泡排序、快速排序、Shell 排序算法是怎样进行的？简单选择排序：该方法的基本思想是：第 1 趟在初始序列(A0 An-1)中找一个最小值，与序列中第一个元素 A0交换，这样子序列(A0)有序，下一趟排序在子序列(A1 An-1)中进行。第 i 趟排序在子序列(Ai-1 An-1)中找最小值元素与子序列中第一个元素 Ai-1交换。进过 n-1 趟排序后使得初始序列有序。(详见 PPT
13、unit6 8)冒泡排序：它的思想是：第 1 趟在序列(A0 An-1)中从前往后进行两个相邻元素的比较，若后者小，则交换，比较 n-1 次。第 1 趟排序结束，最大元素被交换到 An-1中(即沉底)。下一趟排序只需在子序列(A0 An-2)中进行。如果在某一趟排序中未交换元素，说明子序列已经有序，则不再进行下一趟排序。即两两比较，小者前移，大者后沉(详见 PPT unit6 15)快速排序的基本思想是：对任意给定的序列中元素 Rs(关键字为 Ks)，经过一趟排序后，将原序列分割成两个子序列，其中，前一个子序列中的所有元素的关键字均小于等于 Ks,后一个子序列中元素的关键字均大于等于 Ks。我
14、们称元素 Rs 为分割元素以后只需对 2 个子序列分别以同样的算法进行快速排序，直到子序列为空或只有一个元素时得到有序序列。由算法概述可看出这个算法可以用递归来实现。(详见 PPT unit6 20)堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法 FilterDown( ) 形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。(详见 PPT unit6 32)希尔排序（Shell 排序）方法又称为缩小增量排序。该方法的基本思想是：设待排序对象序列有 n 个对象，首先取一个整数 gap 1，则该结点的双亲的序号为 i/2 ，当 i=1 时，该结点为二叉树的根;(2) 若
15、 2i n，则该结点的左孩子的序号为 2i，否则该结点无左孩子。若 2i+1 n，则该结点的右孩子的序号为 2i+1，否则该结点无右孩子.(详见 PPT unit4-1 14)18.在树中，结点数与边数之间有什么关系？怎样计算各种不同度的结点个数之间的关系？结点数与边数之间的关系请自行总结各种不同度的结点个数之间的关系：任意一棵二叉树中，若叶结点的个数为n0，度为 2 的结点的个数为 n2，则必有 n0=n2+1。设二叉树的度为 1 的结点数为 n1，树中结点总数为 n，则 n=n0+n1+n2。除根结点没有双亲外，每个结点都有且仅有一个双亲，所以有 n-1=n1+2n2 作为孩子的结点。因此
16、有 n0=n2+1，结论成立。19.什么是散列表？典型的散列函数有哪些？散列表要解决的主要问题是什么？散列函数：反映元素的关键字(key)与其在结构中的存储位置(loc)之间的关系的函数(h)，即 loc(key)=h(key)散列表(hash,哈希表)：用散列函数建立起来的表。为建立散列表，(1)首先需要确定散列函数。(2)根据散列函数，可计算出关键字在散列表中的地址，从而可将集合中的元素映射到散列表中。(详见 PPT unit5-2 105)“好”的散列函数：(1)均分布，少冲突；(2)计算简便，快速。(1)除留余数法（最常用）： h(key)=key % M (M 为散列表表长 )一般取
17、不超过 M 的素数 P 更好。(2)平方取中法：h(key)=(key) 2 的中间若干位 k其中：位数 k 应满足：10 k-1n 10 k ，n 为集合中元素个数。(3) 分段法：a)分段相加法 h(key)=关键字分成位数相同的若干段相加b)分段折叠相加法 h(key)=关键字分成位数相同的若干段折叠相加取的位数与散列表地址位数相同，若和超过指定的位数，则去掉最高位。(4) 数字分析法：取分布均匀的若干位。(详见 PPT unit5-2 108-111)20. 树和二叉树有何不同？怎样在树和二叉树之间进行转换？二叉树有哪几种典型的形状？树不能为空，而二叉树可以为空。二叉树结点的子树要区分
18、左子树和右子树，即使只有一棵子树也要进行区分，这是二叉树与树的最主要的差别。(详见 PPT unit4-1 10)典型的二叉树：二叉搜索树，二叉平衡树，满二叉树，完全二叉树（自己写的 可能还有别的 ）多叉树转二叉树：多叉树的根结点为二叉树的根，多叉树的结点的第一个儿子变成二叉树对应结点的左孩子，多叉树的结点的右兄弟（出自百度）21. 归并排序、插入排序算法是怎样执行的？归并排序的基本思想是：(1)初始时，将有 n 个元素的序列看成是 n 个长度为 1 的有序子序列，(2)然后两两合并子序列，得到 n/2 个长度为 2 或 1 的有序子序列；再两两合并，直到得到一个长度为 n 的有序序列时结束。(详见 PPT unit6 28)插入排序算法方法的基本思想是：将序列中第 1 个元素作为一个有序序列，然后将剩下的 n-1 个元素按关键字大小依次插入该有序序列，经过 n-1 趟排序后即成为有序序列。(详见 PPT unit6 12)22. 在顺序表上和链表上进行插入和删除操作的算法复杂度是多少 ？顺序表上插入渐近时间复杂度：O(n)
