A．0 B．1 C．n-1 D．n
4．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4 5．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网 6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。
nnnni,j]?nA[j,i][i,j]A．
?A[i?1 B．
?A?i,jj?1 C．
?i?1 D．
?A?A?j,i?i?1+
j?1
7．下面哪一方法可以判断出一个有向图是否有环（回路）：
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历
8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A. O(n) B. O(n+e) C. O(n2) D. O(n3
) 9. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n）
10．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ ）。
A．存在 B．不存在
11．一个有向无环图的拓扑排序序列（ ）是唯一的。
A．一定 B．不一定
12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。A．G中有弧
A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 14. 关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路15．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
判断题
1. 有e条边的无向图，在邻接表中有e个结点。（ ） 2. 有向图的邻接矩阵是对称的。（ ） 3．任何无向图都存在生成树。（ ）
4. 不同的求最小生成树的方法最后得到的生成树是相同的.（ ） 5. 有环图也能进行拓扑排序。（ ）
6. 关键路径是AOE网中从源点到终点的最长路径。（ ）
填空题
1．具有10个顶点的无向图，边的总数最多为______。
2. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。 3．n个顶点的连通无向图，其边的条数至少为______。
4．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
6
5．构造连通网最小生成树的两个典型算法是______。 6. 有一个用于n个顶点连通带权无向图的算法描述如下： （1）．设集合T1与T2，初始均为空； （2）．在连通图上任选一点加入T1； （3）．以下步骤重复n-1次：
a.在i属于T1，j不属于T1的边中选最小权的边； b.该边加入T2。
上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。
7．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。 8. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。
算法应用题
1、对n个顶点的无向图，采用邻接矩阵表示，如何判别下列有关问题 1）图中有多少条边？
2）任意两个顶点i和j是否有边相连？ 3）任意一个顶点的度是多少？
2．设G=(V,E)以邻接表存储，试写出深度优先和广度优先序列。
234?1
5?1342
124? 312 435? 524?
3、已知一无向图的邻接矩阵如下，求该图从顶点V1出发的广度优先遍历和深度优先遍历序列。
0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0
4．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。 1621
215 111943 614 6
5331867
5、对下面的有向图，试利用DIJKSTRA算法从顶点1到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。
10
v5 10 v6 15
v4 4 10 v3
30 4 v2
2 20 v1
15
6、对下面的AOE网，求出各项活动的最早开始时间e(i)和最迟开始时间l(i)，并回答：工程完成的最短时间是多少？哪些是关键活动？
3 V4
5 5 v1
6 V3
3 V5
6
V7
3
1
4 V8 5 V9 2
2 4 V6
4 v10
V2
7．下图是带权的有向图G的邻接表表示法，求：
（1）．以结点V1出发深度遍历图G所得的结点序列； （2）．以结点V1出发广度遍历图G所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。
第九章 查找
选择题
1、 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )
A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 2. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储
8
3. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链表。这些链的链首
指针构成一个指针数组，数组的下标范围为 (（2）) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16
判断题
1．Hash表的平均查找长度与处理冲突的方法无关。 2. 若散列表的负载因子α<1，则可避免碰撞的产生。
3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
填空题
1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
算法应用题
1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。
３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。 ４、设散列表的长度为15，散列函数H（K）=K，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。
第十章 内部排序
选择题
1．下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入 B. 冒泡 C. 二路归并 D. 堆排序 2．下列排序算法中，其中（ ）是稳定的。
A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 3．下面的排序算法中，不稳定的是（ ）
A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 4. 在下面的排序方法中，辅助空间为O（n）的是( ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 5. 下列排序算法中，占用辅助空间最多的是：( )
A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 6．直接插入排序在最好情况下的时间复杂度为（ ）
2
A． O(logn) B． O(n) C． O(n*logn) D． O(n) 7．下列四个序列中，哪一个是堆（ ）。
A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15
9
C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 判断题
1．内排序要求数据一定要以顺序方式存储。 （ ）
2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 3．直接选择排序算法在最好情况下的时间复杂度为O（N）。（ ） 4．在待排数据基本有序的情况下，快速排序效果最好。（ ） 5．快速排序总比选择排序快。（ ）
填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。 2．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。
算法应用题
1． 对下列记录进行希尔排序（增量分别为：5，3，1）
21，27，10，14，75，45，9，28，16，55，70，18，32 2． 对下列记录进行一趟快速排序
30，41，15，48，60，18，77，25，43，10，12，61 3． 对下列序列建成一个大根堆
21，27，10，14，75，45，9，28，16，55，70，18，32
答案： 一到五章
：1.T（n)=O(n);1.T（n)=O(n);1.T（n)=O(根号n);1.T（n)=O（1); 选择：CDCBD (BC) CBB BCCAB B 判断 错错对错错错 填空1.顺序 2，（n-1）/2 3.O(1) O(N) 4.L->next==L->prior
5.3,1,2 6.SXSSXSXX 7.队列 8.字符 9. 352 第六章
DBDAB BEDAA CCBDC CB (CDFHI) 判断：对错错错错
填空 1. 9 2. 12 3. N0=N2+1 4. 99 5. 11
6. N1-1 N2+N3 7. 69
第七章
选择 BA (BD) (BC) B BBCDA BDBAB 判断 错错错错错对
10
填空1. 45 2. N 3. N-1
4. 无向图 2（n-1） 有向图 n 5. 普里姆算法 克鲁斯卡尔算法 6. N-1 普里姆算法 最小生成树
7. 活动 活动间的优先关系 事件 活动 8. （1)零
（2） Vk的入度减1，如为零则进栈 （3）环路
第九章
选择 AD (CC) (AC) 判断 错错错 填空 4；
第十章
选择 DD (CDF) DABC 判断 错错错错对 填空：1.比较 移动
2.QACSQDFXRHMY FHCDMAQSRQXY
11
