当前位置：文档之家 › 数据结构第七章考试题库(含答案)

数据结构第七章考试题库(含答案)

  • 格式：doc
  • 大小：514.00 KB
  • 文档页数：51

1 / 51 第七章 图

一、选择题

1．图中有关路径的定义是〔 〕.[北方交通大学 2001 一、24 〔2分〕]

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列

C．由不同边所形成的序列 D．上述定义都不是

2．设无向图的顶点个数为n,则该图最多有〔 〕条边.

A．n-1 B．n/2 C． n/2 D．0 E．n2

[清华大学 1998 一、5 〔2分〕][西安电子科技大 1998 一、6 〔2分〕]

[航空航天大学 1999 一、7 〔2分〕]

3．一个n个顶点的连通无向图,其边的个数至少为〔 〕.[##大学 1999 四、4 <4分>]

A．n-1 B．n C．n+1 D．nlogn；

4．要连通具有n个顶点的有向图,至少需要〔 〕条边.[航空航天大学 2000 一、6<2分〕]

A．n-l B．n C．n+l D．2n

5．n个结点的完全有向图含有边的数目〔 〕.[中山大学 1998 二、9 〔2分〕]

A．n*n Ｂ．n〔n＋１〕 C．n／2 D．n*〔n－l〕

6．一个有n个结点的图,最少有〔 〕个连通分量,最多有〔 〕个连通分量.

A．0 B．1 C．n-1 D．n

[邮电大学 2000 二、5 〔20/8分〕]

7．在一个无向图中,所有顶点的度数之和等于所有边数〔 〕倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的〔 〕倍.[哈尔滨工业大学 2001 二、3 〔2分〕]

A．1/2 B．2 C．1 D．4

8．用有向无环图描述表达式*〔〔A+B〕/A〕,至少需要顶点的数目为< >.[中山大学1999一、14]

A．5 B．6 C．8 D．9

9．用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是< >.

A．逆拓扑有序 B．拓扑有序 C．无序的 [中科院软件所

1998]

10．下面结构中最适于表示稀疏无向图的是〔 〕,适于表示稀疏有向图的是〔 〕.

A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表

[工业大学 2001 一、3 <2分>]

11．下列哪一种图的邻接矩阵是对称矩阵？〔 〕[北方交通大学 2001 一、11 〔2分〕]

A．有向图 B．无向图 C．AOV网 D．AOE网

12． 从邻接阵矩 可以看出,该图共有〔①〕个顶点；如果是有向图该图共有〔②〕 条弧；如果是无向图,则共有〔③〕条边.[中科院软件所 1999 六、2〔3分〕]

①．A．9 B．3 C．6 D．1 E．以上答案均不正确

②．A．5 B．4 C．3 D．2 E．以上答案均不正确

③．A．5 B．4 C．3 D．2 E．以上答案均不正确

13．当一个有N个顶点的图用邻接矩阵A表示时,顶点Vi的度是〔 〕.[南京理工大学1998一、4<2分〕] 2 / 51 A． B． C． D．+

14．用相邻矩阵A表示图,判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连,则只要检查〔 〕的第i行第j列的元素是否为零即可.[武汉大学 2000 二、7]

A．mA B．A C．Am D．Am-1

15. 下列说法不正确的是〔 〕.[青岛大学 2002 二、9 〔2分〕]

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图

B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程

16．无向图G=,其中：V={a,b,c,d,e,f},E={,,,,,,},对该图进行深度优先遍历,得到的顶点序列正确的是〔 〕.[南京理工大学 2001 一、14 〔1.5分〕]

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

17. 设图如右所示,在下面的5个序列中,符合深度优先遍历的序列有多少？〔 〕

[南京理工大学 2000 一、20 〔1.5分〕]

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b

c

A．5个 B．4个 C．3个 D．2个

第17题图 第18题图

18.下图中给出由7个顶点组成的无向图.从顶点1出发,对它进行深度优先遍历得到的序列是< ① >,而进行广度优先遍历得到的顶点序列是〔 ② 〕.[中科院软件所 1999 六、2-〔1〕〔2分〕]

①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确

②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确

19．下面哪一方法可以判断出一个有向图是否有环〔回路〕：[东北大学 2000 4、2〔4分〕]

A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径

20. 在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为< >.

A. O B. O C. O D. O

[合肥工业大学 2001 一、2 〔2分〕]

21. 下面是求连通网的最小生成树的prim算法：集合VT,ET分别放顶点和边,初始为〔 1 〕,下面步骤重复n-1次: a：〔 2 〕；b：〔 3 〕；最后：〔 4 〕.[南京理工大学 1997 一、11_14

〔8分〕]

〔1〕．A．VT,ET为空 B．VT为所有顶点,ET为空

C．VT为网中任意一点,ET为空 D．VT为空,ET为网中所有边

〔2〕．A. 选i属于VT,j不属于VT,且〔i,j〕上的权最小

B．选i属于VT,j不属于VT,且〔i,j〕上的权最大

C．选i不属于VT,j不属于VT,且〔i,j〕上的权最小

D．选i不属于VT,j不属于VT,且〔i,j〕上的权最大

〔3〕．A．顶点i加入VT,〔i,j〕加入ET B. 顶点j加入VT,〔i,j〕加入ET

C. 顶点j加入VT,〔i,j〕从ET中删去 D．顶点i,j加入VT,〔i,j〕加入3 / 51 ET

〔4〕．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树

C．ET中有n-1条边时为生成树,否则无解 D．ET中无回路时,为生成树,否则无解

22. <1>. 求从指定源点到其余各顶点的迪杰斯特拉〔Dijkstra〕最短路径算法中弧上权不能为负的原因是在实际应用中无意义；

<2>. 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O ；〔图用邻接矩阵表示〕

<3>. Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路.

上面不正确的是〔 〕.[南京理工大学 2000 一、21 〔1.5分〕]

A．<1>,<2>,<3> B．<1> C．<1>,<3> D．<2>,<3>

23．当各边上的权值< >时,BFS算法可用来解决单源最短路径问题.[中科院计算所2000一、3 <2分〕]

A．均相等 B．均互不相等 C．不一定相等

24. 求解最短路径的Floyd算法的时间复杂度为< >.[合肥工业大学 1999 一、2 〔2分〕]

A．O〔n〕 B. O〔n+c〕 C. O〔n*n〕 D. O〔n*n*n〕

25．已知有向图G=,其中V={V1,V2,V3,V4,V5,V6,V7},

E={,,,,,,,,},G的拓扑序列是〔 〕.

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7

C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7

[航空航天大学 2000 一、7 〔2分〕]

26．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列〔 〕.

A．存在 B．不存在[中科院计算所1998 二、6 <2分〕][中国科技大学 1998二、6〔2分〕]

27．一个有向无环图的拓扑排序序列〔 〕是唯一的.[邮电大学 2001 一、3 〔2分〕]

A．一定 B．不一定

28. 在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是〔 〕.

A．G中有弧 B．G中有一条从Vi到Vj的路径

C．G中没有弧 D．G中有一条从Vj到Vi的路径

[南京理工大学 2000 一、9 〔1.5分〕]

29. 在用邻接表表示图时,拓扑排序算法时间复杂度为< >.

A. O B. O C. O D. O

[合肥工业大学 2000 一、2 〔2分〕][南京理工大学 2001 一、9 〔1.5分〕]

[青岛大学 2002 二、3 〔2分〕]

30. 关键路径是事件结点网络中〔 〕.[西安电子科技大学 2001应用 一、4 〔2分〕]

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径

合集下载

数据结构第七章复习题

数据结构第七章复习题

数据结构第七章复习题

第7章排序

一、选择题

1．某内排序方法的稳定性是指( D )。

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法 D．以上都不对

2．下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入

B. 冒泡

C. 二路归并

D. 堆

3．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序

B. 快速排序，堆排序

C. 直接选择排序，归并排序

D. 归并排序，冒泡排序

6．若要求尽可能快地对序列进行稳定的排序，则应选（B）。

A．快速排序 B．归并排序 C．冒泡排序

13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( A ) A．选择排序法 B. 插入排序法 C. 快速排序法 D.

堆积排序法15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ D ）。

A．直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序

22．下列排序算法中( B )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A.快速排序

B. shell排序

C. 堆排序 D.冒泡排序

23．下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择

B. 冒泡

C. 归并

D. 堆

27. 在下面的排序方法中，辅助空间为O（n）的是( D ) 。

A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序

31. 就平均性能而言，目前最好的内排序方法是( D )排序法。

A. 冒泡

B. 希尔插入

C. 交换

D. 快速

35. 下列排序算法中，占用辅助空间最多的是：( A )

A. 归并排序

B. 快速排序

C. 希尔排序

D. 堆排序

36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A)排序法。

《数据结构与算法》第7章 查找_复习测试

《数据结构与算法》第7章 查找_复习测试

第7章 查找 复习测试题

一、单选题

1．顺序查找适合于存储结构为（ D ）的线性表。

A）散列存储 B）压缩存储

C）索引存储 D）顺序或链式存储

2．如果要求用线性表既能较快地查找，又能适应动态变化的要求，则可采用（ A ）查找方法。

A）分块查找 B）顺序查找

C）折半查找 D）基于属性

3．已知一如下10个记录的表，其关键字序列为（2，15，19，25，30，34，44，55，58，80），用折半查找法查找关键字为55的记录，比较次数是（ B ）。

A）1次 B）2次

C）3次 D）4次

4．二叉排序树中，最小值结点的（ A ）。

A）左指针一定为空 B）右指针一定为空

C）左、右指针均为空 D）左、右指针均不为空

5．哈希表的地址区间为0~16，哈希函数为H（K）=K MOD 17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到哈希表中，则元素59存放在哈希表中的地址为（ C ）。

A）8 B）9

C）10 D）11

6．设有一组记录的关键字为（19，14，23，1，68，20，84，27，55，11，10，79），用链地址法构造散列表，散列函数为H（key）=key MOD 13，散列地址为1的链中有（ D ）个记录。

A）1 B）2

C）3 D）4

7．索引顺序表中包含（ A ）。

A）顺序表和索引表 B）索引表

C）顺序表 D）索引

8．向一棵AVL（平衡二叉树）插入元素时，可能要对最小不平衡子树进行调整，此调整分为（ C ）种旋转类型。

A）2 B）3

C）4 D）5

9．适用于折半查找的表的存储方式及元素排列要求为（ D ）。

A）链接方式存储，元素无素 B）链接方式存储，元素有素

C）顺序方式存储，元素无序 D）顺序方式存储，元素有序

10．按（ B ）遍历二叉排序树得到的序列是一个有序序列。

《数据结构(C语言版 第2版)》(严蔚敏 著)第七章练习题答案

《数据结构(C语言版 第2版)》(严蔚敏 著)第七章练习题答案

《数据结构（C语言版第2版）》（严蔚敏著）

第七章练习题答案

第7章查找

1．选择题

（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。A．(n-1)/2B．n/2C．(n+1)/2D．n

答案：C

解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。A．链接方式存储，元素无序B．链接方式存储，元素有序

C．顺序方式存储，元素无序D．顺序方式存储，元素有序

答案：D

解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找

法。A．顺序查找B．折半查找

C．分块查找D．哈希查找

答案：C

解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就

可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量

移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，

则它将依次与表中（）比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50

C．20，50D．30，88，50

答案：A

解释：表中共10个元素，第一次取(1+10)/2=5，与第五个元素20比较，58大于20，再

取(6+10)/2=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A．3B．4C．5D．6

答案：B

解释：22个记录的有序表，其折半查找的判定树深度为log222+1=5，且该判定树不是

满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。A．相同B．完全不同

数据结构第七章课后习题答案

数据结构第七章课后习题答案

百度文库 - 让每个人平等地提升自我

1

7_1

对于图题7.1（P235）的无向图，给出：

（1） 表示该图的邻接矩阵。

（2） 表示该图的邻接表。

（3） 图中每个顶点的度。

解：

（1） 邻接矩阵：

0111000

1001100

1001010

1110111

0101001

0011001

0001110

（2） 邻接表：

1：2----3----4----NULL;

2: 1----4----5----NULL;

3: 1----4----6----NULL;

4: 1----2----3----5----6----7----NULL;

5: 2----4----7----NULL;

6: 3----4----7----NULL;

7: 4----5----6----NULL;

（3） 图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2

对于图题7.1的无向图，给出：

（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序

（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：

存储结构：

本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.

算法分析：

首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。百度文库 - 让每个人平等地提升自我