结点。
四、算法设计
1、写出中序遍历的递归和非递归算法。
2、编写一算法，计算二叉树T中结点的个数。
五、简答题
1、写出下列二叉树的先序遍历、中序遍历、后序遍历序列。
2、给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈夫曼树，给出各字符的编码值。
第7章习题 一、选择题
1、具有5个顶点的有向图至少应有 条边才能确保一个强连通图。 A. 4 B. 5 C. 6 D. 7
2、在一个无向图中，所有顶点的度数之和等于所有边数 B 倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的 C 倍。 A.
1 B. 2 C. 1 D. 4 23、下列图的邻接矩阵是对称矩阵的是 。
A. 有向图 B. AOV网 C. AOE网 D. 无向图 4、关键路径是指AOE（Activity On Edge）网中 。
A. 最长的回路 B. 最短的回路 C. 从源点到汇点的最长路径 D. 从源点到汇点的最短路径 5、在有向图的邻接表存储结构中，顶点v在链表结点中出现的次数是 。
A. 顶点v的入度 B. 顶点v的出度 C. 顶点v的度 D. 依附于顶点v的边数 6、下面的叙述中，不正确的是 。
A. 任何关键活动不按期完成就会影响整个工程的完成时间 B. 任何一个关键活动提前完成，将使整个工程提前完成 C. 所有关键活动都提前完成，将使整个工程提前完成
D. 所有关键活动不按期完成就会影响整个工程的完成时间 7、无向图G=（V，E），其中V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列是 。
A. a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b
8、G是一个非连通的无向图，共有28条边，则该图至少有 个顶点。 A. 9 B. 8 C. 7 D. 6
9、下面 方法可以判断出一个有向图是否有环（回路）。
A. 深度优先遍历 B. 求最短路径 C. 拓扑排序 D. 求关键路径
10、在有向图G的拓扑排序中，若顶点vi在顶点vj之前，则下列情形不可能出现的是 。 A. G中有弧
C. G中有一条从vi到vj的路径 D. G中有一条从vj到vi的路径
二、判断题
1、对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。
2、有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。 3、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不惟一。 4、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。 5、图的深度优先遍历序列是不惟一的。
6、连通图上各边的权值均不相同，则该图的最小生成树一定惟一。
三、填空题
1、n个顶点的连通图用邻接矩阵表示时，该矩阵至少有 个非零元素。 2、在有向图的邻接矩阵中，计算第i个顶点入度的方法是 。 3、有向图G可以进行拓扑排序的条件是 。
4、AOV网中，顶点表示 ，边表示 。AOE网中，顶点表示 ，边表示 。
四、算法设计
1、已知图G是无向图，编写一个算法，将图G用邻接矩阵表示。（即构造无向图createUDG(MGraph &G)的邻接矩阵算法）。
参考算法：
Status createUDG(MGraph &G) // 构造无向图G
{ scanf(&G.vexnum, &G.arcnum); // 输入无向图的顶点和边的个数 for( i=0;i i=LocateVex(G,v1);j= LocateVex(G,v2); // 确定v1和v2在G中位置 G.arcs[i][j].adj=1; // 说明 if(IncInfo) Input(*G>arcs[i][j].info); // 若弧含有相关信息，则输入 G.arcs[j][i]=G.arcs[i][j]; // 置 return OK; V5 V1 } V6 五、简答题 V2 V4 1、如图所示为一个有向图，试给出： (1)每个顶点的入度和出度 V3 (2)邻接矩阵 (3)邻接表 (4)强连同分量 2、给出下图所示图(a)和图(b)，按照下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 假定它们采用邻接表表示，并且假定每个顶点邻接表中的节点是按顶点序号从大到小的次序链接的。 2 1 0 0 4 1 5 6 5 3 4 7 9 8 3 2 6 7 8 图a 图b 3、对于下图，画出最小生成树： (1)从顶点v0出发，按照Prim算法求出最小生成树； (2)按照Kruskal算法求出最小生成树。 4、写出下图全部不同的拓扑排序序列。 1 2 12 5 0 4 15 7 6 8 13 6 16 4 1 6 4 8 5 10 920 12 5 9 3 3 2 第3题 第4题 第9章、第10章习题 一、选择题 1、若查找每个元素的概率相等，则在长度为n的顺序表上查找到表中任一元素的平均查找长度为 。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2、设哈希地址空间为0~m-1，k为记录的关键字，哈希函数采用除留余数法，即H(k)=k%p，为了减少发生冲突的频率，一般取p为 。 A. m B. 大于m的最小质数 C. 小于或等于m的最大质数 D. 小于等于m的最大合数 3、对包含n个元素的哈希表进行查找，平均查找长度 。 A. 为O(n) B. 与装填因子有关 C. 为O(log2n) D. 与n无关 4、若有m个关键字互为同义词，若用线性探测法处理冲突，把这m个元素存入哈希表中，至少要 进行 次探测。 A. m(m+1)/2 B. m+1 C. m D. m-1 5、下列排序算法中， 算法是不稳定的。 A. 起泡排序 B. 直接插入排序 C. 归并排序 D. 快速排序 6、数据（8,9,10,4,5,6,20,1,2）只能是下列排序算法中的 两趟排序后的结果。 A. 选择排序 B. 起泡排序 C. 直接插入排序 D. 堆排序 7、对数据序列（10,9,15,20,5,7,18,6,12,8），若用堆排序的筛选方法建立的初始堆是 ；若用快速排序法，用第一个元素与其他元素比较，排序一趟后的结果是 ；起泡排序排序一趟后的结果是 ；初始增量为5的希尔排序一趟后的结果是 。 A . 5,6,7,10,8,15,18,20,12,9 B. 9,10,15,5,7,18,12,6,8,20 C. 5,9,6,8,7,10,18,15,20,12 D. 8,9,6,7,5,10,18,20,12,15 E. 7,9,6,12,5,10,18,15,20,8 F. 9,10,15,5,7,18,6,12,8,20 G. 以上都不对 二、判断题 1、进行折半查找的表必须是顺序存储的有序表。 2、对二叉排序树进行先序遍历得到的结点的值的序列是一个有序序列。 3、直接选择排序是一种稳定的排序算法。 4、在任何情况下，起泡排序比快速排序的速度慢。 5、堆排序采用的是顺序存储；小根堆的最大元素一定是末端结点；n个元素组成堆的深度为 ?log2n?+1。 三、填空题 1、在n个元素的线性表中顺序查找，若查找成功，则关键字的比较次数最多为 次，使用监视哨时，若查找失败，则关键字的比较次数为 次。 2、在线性表（2,3,5,9,12,17,23,30,34,40,42,49）中，用折半查找法查找关键字为24的记录，关键字的比较次数为 次，所比较的元素依次为 。 3、排序算法的稳定性是指 。 4、除基数排序外的其他排序算法，主要的两种基本操作是 和 。 四、简答题 1、依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。 (1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列; (3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。 2、对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。 （1）插入90 （2） 插入25 （3） 插入45 （4）删除60 （5）删除80 5030808 2035 4060100 3、给定关键码序列（26,25,20,33,21,24,45,204,42,38,29,31），要用哈希法进行存储，规定装填因子α=0.6。 （1）请给出除余法的哈希函数。 （2）用开放定址线性探测法解决冲突，请画出插入所有的关键码后得到的哈希表。 4、设哈希函数为H(K)=K MOD 11,解决冲突的方法为链接法，试将下列关键字集合{35,67,42,21,29,86,95,47,50,36,91}依次插入到哈希表中（画出哈希表的示意图）。并计算平均查找长度ASL。 5、给出待排序序列的关键字序列为{26, 31, 75, 41, 87, 15, 41, 10, }，请用堆排序的方法写出该序列的排序过程。（设为大根堆） 6、给出待排序序列的关键字序列为{100, 87, 52, 61, 27, 170, 37, 45, 61, 118, 14, 88, 32}，请用快速排序的方法写出该序列排序的过程。 7、判别以下序列是否为堆（小根堆或大根堆）。如果不是，则把它调整为堆。 （1）{100，86，48，73，35，39，42，57，66，21}； （2）{12，70，33，65，24，56，48，92，86，33}； （3）{05，56，20，23，40，38，29，61，35，76，28，100}；
