青岛科技大学《数据结构》课程练习题及答案
A．G中有弧
A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 14. 关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路 15. 下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上
16．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 二、判断题
1. 图中的顶点就是指数据结构中的数据元素。（ ）
2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ） 3. 有e条边的无向图，在邻接表中有e个结点。（ ）
4. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ） 5. 无向图的邻接矩阵可用一维数组存储。（ ）
6．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ）
7．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ ） 8．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 9．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ） 10. 广度遍历生成树描述了从起点到各顶点的最短路径。（ ） 11．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 12. 最小生成树问题是构造连通网的最小代价生成树。（ ）
13. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（ ） 14．AOV网的含义是以边表示活动的网。（ ） 15．在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（ ） 三、填空题
1. 判断一个无向图是一棵树的条件是______。 2．有向图G的强连通分量是指______。
3．一个连通图的______是一个极小连通子图。
4．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。 5．在有n个顶点的有向图中，每个顶点的度最大可达______。
6．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
7．无向图G的邻接表表示中，每个顶点邻接表中所含的结点数等于该顶点的______。 8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}
11
青岛科技大学《数据结构》课程练习题及答案
现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
9. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。
10．构造连通网最小生成树的两个典型算法是______。
11. kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。
12．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______。
13. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。 四、应用题
1．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 2．请回答下列关于图(Graph)的一些问题： （1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
（2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀
疏矩阵？ （3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 3．解答问题。设有数据逻辑结构为： B = (K, R), K = {k1, k2, ?, k9}
R={
（1）．画出这个逻辑结构的图示。 （2）．相对于关系R, 指出所有的开始接点和终端结点。 （3）．分别对关系R中的开始结点，举出一个拓扑序列的例子。 （4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。 4．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D
SHUN C E F LI D F A ZHOU B F
设项目A ,B ,?，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件). （1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列.
5．已知世界六大城市为:北京(PE)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) PE N PA L PE 109 82 81 N 109 58 55 PA 82 58 3 L 81 55 3 T 21 108 97 95 M 124 32 92 89 12
青岛科技大学《数据结构》课程练习题及答案
T M 21 124 108 32 97 92 95 89 113 113
（1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法;
（3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 6．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 V2 V3 V4 V5 V6 V7 V8 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。
第8章 查找
一、选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2.对线性表进行折半查找时，要求线性表必须（ ）
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
3．若要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性
4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 5.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR
6. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
7. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行多少次探测？( )
13
青岛科技大学《数据结构》课程练习题及答案
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
8. 哈希表的地址区间为0-17,哈希函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。
A． 8 B. 9 C. 10 D. 11 二、判断题
1．哈希函数的选取平方取中法最好。( )
2. 顺序查找法适用于存储结构为顺序或链接存储的线性表。( ) 3. 折半查找法的查找速度一定比顺序查找法快 。( )
4. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。( ) 5．最优二叉树是平衡二叉树。( )
6.虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。( ) 7.二叉排序树删除一个结点后，仍是二叉排序树。( ) 三、填空题
1.在n个元素的顺序表，使用监视哨顺序查找，若查找失败，则比较关键字的次数为__ __。 2.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。 3.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________ 4.平衡二叉树又称__________。 5.平衡因子的定义是__________。
6.__________法构造的哈希函数肯定不会发生冲突。
7.动态查找表和静态查找表的重要区别在于前者包含有____________运算，而后者不包含这两种运算。 四、应用题
1.在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？
2.设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
3.设一个哈希表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键字{10,100,32,45,58,126,3,29,200,400,0}散列到表中。
（1）哈希函数采用除留余数法，用% hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键字可能产生多少次冲突。
（2）哈希函数采用先将关键字各位数字折叠相加，再用% hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。
第9章 排序
一、选择题
1．下列排序方法中，哪一个是稳定的排序方法？（ ）
A．简单选择排序 B．折半插入排序 C．希尔排序 D．快速排序 2．若要求尽可能快地对序列进行稳定的排序，则应选（ ）。
A．快速排序 B．归并排序 C．冒泡排序 D．插入排序 3．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。
A．直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序
4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84
14
青岛科技大学《数据结构》课程练习题及答案
则采用的排序是 ( )。A.选择 B.冒泡 C.快速 D. 插入
5．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序 B.shell排序 C.堆排序 D.冒泡排序
6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D.堆 7.就平均性能而言，目前最好的内排序方法是( )排序法。
A.冒泡 B. 希尔插入 C.交换 D. 快速
8．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9.下列排序算法中，占用辅助空间最多的是：( )。
A.归并排序 B.快速排序 C.希尔排序 D.堆排序
10.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键字字的记录，加入到已排序记录的末尾，该排序方法是（ ）。 A.选择 B.冒泡 C.插入 D.堆 11．用直接插入排序方法对下面四个序列进行排序（升序），元素比较次数最少的是（ ）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80
C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40
12.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( ) 。
A.l B.4 C.3 D.2
13．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
A．?n/2? B．?n/2?-1 C．1 D．?n/2? +2 14.以下序列不是堆的是( )。
A. (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10)
C. (10,20,40,60,66,77,80,82,85,98,100) D. (100,85,40,77,80,60,66,98,82,10,20)
二、判断题：
1．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 2．简单选择排序算法在最好情况下的时间复杂度为O（n）。（ ） 3．在待排数据基本有序的情况下，快速排序效果最好。（ ）
4．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ） 5．堆肯定是一棵平衡二叉树。（ ）
6．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ） 7．归并排序辅助存储空间为O（1）。（ ）
8．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （ ）
9．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ ）
10．在任何情况下，归并排序都比简单插入排序快。（ ） 三、填空题
1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记
15
青岛科技大学《数据结构》课程练习题及答案
录的_____。
5．直接插入排序用监视哨的作用是_______。 6．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 9．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。
四、应用题
1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。
2．在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 3．在堆排序、快速排序和合并排序中：
(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？
(3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？
(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 4．设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？ 5．奇偶交换排序如下所述：对于初始序列A[1]，A[2],?,A[n],第一趟对所有奇数i（1<=i
(2)写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。 五、算法设计题：
1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
16