计算机专业基础综合（数据结构）模拟试卷1（共272题）

计算机专业基础综合（数据结构）模拟

试卷1（共7套）

（共272题）

计算机专业基础综合（数据结构）模拟

试卷第1套

一、单选题（本题共34题，每题1.0分，共34分。）

1、下面是一个求最小生成树的算法，其中G是连通无向图，T是所求的生成树。

T;=G;WhileT中存在回路dobegin在T中找一条权值最大的边e；T：=T-[e]；

（T中去掉e边）End.试问该算法是哪一种求最小生成树的算法?（）

A、Prim（普里姆）算法

B、Kruskal（克鲁斯卡尔算法）

C、罗巴赫算法

D、其他算法

标准答案：B

知识点解析：由算法可以看出使用的是Knlskal算法。

2、邻接表是图的一种

A、顺序存储结构

B、链接存储结构

C、索引存储结构

D、散列存储结构

标准答案：B

知识点解析：图的邻接表存储结构是一种链接存储结构。

3、下面试图对图中路径进行定义，说法正确的是（）。

A、由顶点和相邻顶点序列构成的边所形成的序列

B、由不同顶点所形成的序列

C、由不同边所形成的序列

D、上述定义都不是

标准答案：A

知识点解析：由图的定义可知，B与c是错误的。

4、无向图中项点个数为n,那么边数最多为（）。

A、n-1

B、n（n-l）/2

C>n（n+l）/2

D、n2

标准答案：B

知识点解析：无向图中有n个顶点，如果每两个顶点之间均是相互连通的，那么此

时无向图中的边数最多，为凡（。一1）/2。

5、在一个具有n（n>0）个顶点的连通无向图中，至少需要的边数是（）。

A、n

n+1

C、n-1

D、n/2

标准答案：C

知识点解析：在无向图中，如果从一个顶点必到另一个顶点Vj（字j）有路径，则称顶

点Vi利Vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以

具有n个顶点的连通无向图至少有n一1条边。

6、以下叙述中正确的是（）。I.对有向图G,如果以任一顶点出发进行一次深度优

先或广度优先搜索能访问到每个顶点，则该图一定是完全图口.连通图的广度优

先搜索中一般要采用队列来暂存访问过的顶点m.图的深度优先搜索中一般要采

用栈来暂存访问过的顶点

A、I,n

B、口，in

c、I,m

D^I,n,in

标准答案：B

知识点解析：I的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶

点出发均能访问到每个顶点，但该图却非完全图。口、in的叙述显然是正确的。

7、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A、第i行非8的元素之和

B、第i列非8的元素之和

C、第i行非8且非。的元素个数

D、第i列非8且非0的元素个数

标准答案：D

知识点解析：有向图的邻接矩阵中，0和8表示的帮不是有向边，而入度是由邻接

矩阵的列中元素计算出来的。

8、在一个无向图中，所有顶点的度之和等于边数的（）倍。

A、1/2

B、1

C、2

D、4

标准答案：C

知识点解析：在无向图中，一条边计入两个顶点的度数。

9、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）算法。

A、前序遍历

B、中序遍历

C、后序遍历

D、按层遍历

标准答案：A

知识点解析：由图的深度优先遍历算法和二叉树的前序遍历可知选Ao

10、任何一个无向连通图（）最小生成树。

A、只有一棵

B、有一棵或多棵

C、一定有多棵

D、可能不存在

标准答案：B

知识点解析：无向连通图应有一棵或多棵最小生成树。

11、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是

（）。

A、求关键路径的方法

B、求最短路径的迪杰斯特拉方法

C、深度优先遍历算法

D、广度优先遍历算法

标准答案：C

知识点解析♦：当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺

序（退出DFSTra—verse算法）即为逆向的拓扑序列。

12、有n个顶点e条边的无向图，采用邻接表存储时，有（）个表头结点，有（）个链

表结点。

A、n,2e

B、n,2e+1

C、n-1,2e

D、n-1,2e+l

标准答案：A

知识点解析：根据邻接表的结构，无向图对应的邻接表有n个表头结点，有2e个

链表结点（每条边对应两个链表结点）。

13、对于由n个顶点组成的有向完全图来说，图中共包含（）条边，对于由n个顶点

组成的无向完全图来说，图中共包含（）条边。

A、n,n（n—1）

B、n,n（n一1）/2

C、2n,n（n—1）

D、n（n一1）,n（n—1）/2

标准答案：D

知识点解析：由完全图的定义可知本题答案为Do

14、在一个（）图中寻找拓扑序列的过程称为（）。

A、有向，拓扑排序

B、无向，拓扑排序

C、有向，最短路径搜索

D、无向，最短路径搜索

标准答案：A

知识点解析：寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序.

15、用邻接矩阵A表示图，判定任意两个顶点力和胃之间是否有长度为m的路径

相连，则只要检查（）的第i行第j列的元素是否为零即可。

A^mA

B、A

C、Am

D、Am-1

标准答案：C

知识点解析：此题考查的知识点是图的邻接矩阵存储.在图的邻接矩阵中，两点之

间有边，则值为1,否则为0。本题只要考虑Am=AxAx…x&m个A矩阵相乘后的

乘积矩阵）中（i,j）的元素值是否为。就行了。

16、当各边上的权值（）时，BFS算法可用来解决单源最短路径问题。

A、均相等

B、均互不相等

C、不一定相等

D、不确定

标准答案：A

知识点解析：此题考查的知识点是图的BFS算法。BFS是从根结点开始，沿着树

的宽度遍历树的结点，如果所有结点均被访问，则算法中止。当各边上的权值相等

时，计算边数即可，所以选A。

17、下面关于图的存储结构的叙述中正确的是（）。

A、用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关

B、用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关

C、用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关

D、用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关

标准答案：A

知识点解析：邻接矩阵法的基本思想是对于有n个顶点的图，用一维数组Vexs[n]

存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻

接矩阵。在邻接矩阵中，以顶点在Vexs数组中的下标代表顶点，邻接矩阵中的元

素存放的是顶点i到顶点j之间关系的信息。

无•邻接矩阵是对称方阵；在具体存放邻接矩阵时只需存放上（或下）三角矩阵的元素即可。

邻

向

接•对于顶点%其度数是第i行的作。元案的个数

图

矩•无向图的边数是上（或下）三角形矩阵中非。元索个数。_____

一

pr有•对于原点%第行的非元索的个数是其出度匕）。

的i00"

向

特

图•第।列的非0元素的个数是其人度/。（巴）。

点

•邻接矩阵中非。元素的个数就是图的弧的数目。

邻接表法的基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点

及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi

的边（对有向图是以顶点Vi为头或尾的弧）.

•表头向敬中每个分量就是一个单链表的头结点，分成个数就是图中的顶点数目。

•在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间。

邻

接•在无向图中，顶点匕的度是第i个链表的结点数。

表

法•对有向图可以建立正邻接表或逆邻接盘。

的•正邻接融是以顶点V为出度（即为孤的起点）而建立的邻接表。

特

点•逆邻接我是以顶点匕为人度（即为弧的终点）而建立的邻接表。

•在有向图中，第i个鞋表中的结点数是顶点匕的出（或入）度；求入（或出）度，须遍历整个邻接表。

•在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点。

18、在有向图G的拓扑序列中，若顶点叫在顶点W之前，则下列情形不可能出现

的是（）。

A、G中有弧Vvi，vj>

B、G中有一条从必到可的路径

C、G中没有弧V%,vj>

D、G中有一条从vj到Vi的路径

标准答案：D

知识点解析•：此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点Vi

与顶点Vj有一条弧，则拓扑序列中顶点力必在顶点Vj之前。若有一条从Vj到党的

路径，则顶点切不可能在顶点vj之前。所以应选D。

19、以下关于图的说法中正确的是（）。I.一个有向图的邻接表和逆邻接表中内结

点个数一定相等□.用邻接矩阵存储图，所占用的存储空间大小只与图中结点个

数有关，而与图的边数无关in.无向图的邻接矩阵一定是对称的，有向图的邻接

矩阵一定是不对称的

A、I,n

B、nyin

c、i,m

D、仅有n

标准答案：A

知识点解析：说法I是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表

的结点个数都等于有向图中的边的个数。说法口是正确的，邻接矩阵的空间复杂

度为on?),与边的个数无关。说法in是错误的，有向图的邻接矩阵不一定是不对

称的，例如，有向完全图的邻接矩阵就是对称的。

20、下列关于AOE网的叙述中，不正确的是()。

A、关键活动不按期完成就会影响整个工程的完成时间

B、任何一个关键活动提前完成，那么整个工程将会提前完成

C、所有的关键活动提前完成，那么整个工程将会提前完成

D、某些关键活动提前完成，那么整个工程将会提前完成

标准答案：B

知识点解析：此题考查的知识点是图的关键路径。在AOE网中，从始点到终点具

有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并

且不只一条。关键路径上的活动称为关键活动。A、C、D的说法都正确。但任何

一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选B。

21、一个二部图的邻接矩阵A是一个()类型的矩阵。

A、nxn矩阵

B、分块对称矩阵

C、上三角矩阵

D,下三角矩阵

标准答案：B

知识点解析：此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无

向图6=的顶点集V划分成两个子集VI和V2(V1CIV2=10),使得G中任何一条边

的两个端点一个属于VI,另一个属于V2,则称G为二部图。由于其特点，其存

储矩阵必为分块对称的，所以选B。

22、求解最短路径的Floyd算法的时间复杂度为()。

A、0(n)

B、O(n+c)

C、0(n2)

D、0(n3)

标准答案：D

知识点解析：暂无解析

）是下图所示的有向图的拓扑序列。

A、Cl,C2,C6,C7,C5,C4,C3

B、Cl,C2,C6,C3,C4,C5,C7

C、CI,C4,C2,C3,C5,C6,C7

D、C5,C7,C4,Cl,C2,C3,C6

标准答案：D

知识点解析：考查拓扑排序的算法。以1开头的拓扑排序过程，如下图所示:

输出5

66

输出7输出4

5开头的拓扑排序过程，答案中的过程如下图所示:

24、如果具有n个顶点的图是一个环，则它有（）棵生成树。

A、n2

n

C、n—1

D、1

标准答案：B

知识点解析：因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成

树，共有n种情况，所以可以有n棵不同的生成树，

25、如下图所示，在下面的5个序列中，符合深度优先遍历的序列有（）个。

①aebfdc@acfdeb③aedfcb（4）aefdbc©aecfdb

A、5

B、4

C、3

D、2

标准答案：D

知识点解析：本题中，符合深度优先遍历顺序的是I和5,其他三个序列均不符

合。

26、无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是

度为2的顶点，则图G最多有（）个顶点。

A、11

B、12

C、15

D、16

标准答案：D

2孙噌=2e

知识点解析：由于在具有n个顶点e条边的无向图中，有片，故可求

得度为2的顶点数为7个，从而最多有16个顶点。

27、对AOE网络中有关关键路径的叙述中，正确的是（）。

A、从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程

所需的最短时间

B、从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程

所需的最短时间

C、从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程

所需的最长时间

D、从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程

所需的最长时间

标准答案：A

知识点解析：本题考查关键路径的定义。关键路径：从起点到终点的最长路径长

度（路径上各活动持续时间之和）。关键活动：关键路径上的活动称为关键活动。

28、以下关于图的叙述中，正确的是（）。

A、强连通有向图的任何顶点到其他所有顶点都有瓠

B、图与树的区别在于图的边数大于或等于顶点数

C、无向图的连通分量指无向图中的极大连通子图

D、假设有图6=｛丫，｛E｝｝,顶点集VWV,EFE,则V，和｛E，｝构成G的子图

标准答窠：C

知识点解析：强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A

错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边

数。若E，中的边对应的顶点不是V，中的元素时，则V，和｛E3无法构成图，D错

误。

29、假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所

有边的时间复杂度为（）c

A、0（n）

B、O（e）

C、O(n+e)

D^O(ne)

标准答案：C

知识点解析：删除与某顶点v相关的所有边的过程如下：先删除下标为v的顶点表

结点的单链表，出边数最多为n—1,对应时间复杂度为O(n),再扫描所有边表结

点，删除所有的入边，对应时间复杂度为0(e)。故总的时间复杂度为O(n+e)。

30、若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结

点数至少是()。

A、11

B、10

C、9

D、8

标准答案：B

知识点解析：n个顶点构成的无向图中，边数9(n—l)/2,将e=36代入，有

n>9,现已知无向图是非连通的，则n至少为10。

31、已知有向图G=(V,A),其中V={a,b,c,d,e),A={,,,,,}<>对该图

进行拓扑排序，下面序列中不是拓扑排序的是().

A、a,d,c,b,e

B、d,a,b,c,e

C>a,b,d,c,e

D、a,b,c,d,e

标准答案：D

知识点解析：选项D中，删去a、b及其对应的出边后，c的入度不为0,因此有

边，故不是拓扑序列。选项A、B、C均为拓扑序列。解答本类题时:建议读者根

据边集合画出草图。

32、用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为()。

A、5

B、6

C、8

D、9

标准答案：A

知识点解析：此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有

向图，可以用来表示公共子表达式，本题中出现的5个字符作为5个顶点，其中

A+B和A可共用，所以至少5个即可，选A。

33、邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边

用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：

顶点值域指针域

vertexfirstedge

⑻邻接多重表顶点表结点结构

标记域顶点位置指针域顶点位置指针域边上信息

markivexilinkjvexjiinkinfo

（b）邻接多重表边表结点结构

关于图中各个域的说明，不正确的是（）。

A、vertex存储的是结点的数值域的内容

B、fksledge域指示第一条依附于该顶点的边

C、mark指向下一条依附于结点的边

D、info为指向和边相关的各种信息的指针域

标准答案：C

知识点解析：顶点表由两个域组成，veriex域存储和该顶点相关的信息，firstedge

域指示第一条依附于该顶点的边。边表结点由六个域组成：mark为标记域，用以

标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink

指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边：info为

指向和边相关的各种信息的指针域。

34、以下关于十字链表的说法中，不正确的是（）。

A、十字链表是有向图的另一种链式存储结构

B、行指针row为矩阵中的行位置，列指针col为矩阵中的列位置

C、数值val为矩阵中的值

D、right指针指向矩阵中的行位置，down指针指向矩阵中的列位置

标准答案：D

知识点解析：righl指向右侧的一个非零元素，down指向下侧的一个非零元素。

二、综合应用题（本题共75题，每题7.0分，共75

分。）

35、证明：具有n个顶点和多于n—1条边的无向连通图G一定不是树。

标准答案：此题考查的知识点是图的定义。具有n个顶点n—1条边的无向连通图

是自由树，即没有确定艰结点的树，每个结点均可当根。若边数多于。一1条，因

一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成

回路。形成回路的连通图不再是树（在图论中树定义为无回路的连通图）。

知识点解析：暂无解析

36、证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为

全0的充要条件是该图为无环图。

标准答案：此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规

律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身

顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧

尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素自然是

落到下三角矩阵中；命题的必要条件是要使上三角为0,则不允许出现弧头顶点编

号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编

号，应按顶点出度顺序编号。)

知识点解析：暂无解析

37、关于图(Graph)的一些问题：(I)有n个顶点的有向强连通图最多有多少条边?最

少有多少条边？(2)表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个

矩阵元素?是否为稀疏矩阵？

标准答案：(l)n(n-l),n(2)l(A不一定是稀疏矩阵提示：此题考查的知识点是图

的相关术语。(1)在有向图G中，如果对于每一对V“vj,属于V,必不等于巧，

从％到vj和从vj到增都存在路径，则称G是强连通图。最多边是所有的顶点每对

之间都有边，边数为n(n—1)；最少只有一个方向有边，为n。(2)元素个数为矩

阵的大小，即106,稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无

规律，不一定稀疏。

知识点解析：暂无解析

38、如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到

对角线以上？

标准答案：此题考查的知识点是图顶点度数。可以按各顶点的出度进行排序。n个

顶点的有向图，其顶点最大出度是n-l,最小出度为0。这样排序后，出度最大

的顶点编号为1,出度最小的顶点编号为n之后，进行调整，即若存在弧，而顶点

j的出度大于顶点i的出度，则将j的编号排在顶点i的编号之前。

知识点解析：暂无解析

39、假定图G=(V,E)是有向图，V={1,2,N},N>1,G以邻接矩阵方式存

储，G的邻接矩阵为A,即A是一个二维数组。如果i到j有边，则A[i,j]=l,否

则A[i,j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否

存在回路)，要求算法的时间复杂性为0(/)。

标准答案：此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行

DFS(v)时，若在退出DFS(v)前碰到某顶点u,其邻接点是己经访问的顶点v,则说

明v的子孙u有到v的回边，即说明有环；否则，无环。

知识点解析：暂无解析

40、对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一

的因素有哪些？

标准答案：此题考查的知识点是图的遍历。遍历不唯〜的因素有：开始遍历的顶点

不同；存储结构不同；在邻接表情况下邻接点的顺序不同。

知识点解析：暂无解析

41、G=（V,E）是一个带有权的连通图，如图所示。（1）什么是G的最小生成树?

（2）G如图所示，请找出G的所有最小生成树。

标准答案：（1）无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的

n—1条边。而最小生成树则是各边权值之和最小的生成树。（2）最小生成树有两

棵。下面给出顶点集合和边集合，编以三元组(Vi，Vj,W)形式，其中W代表权

值。V(G)={1,2,3,4,5)E1(G)={(4,5,2),(2,5,4),(2,3,5),(1,2,

7)}；E2(G)={(4,5,2),(2,4,4),(2,3,5),(1,2,7)}

知识点解析：暂无解析

42、对于如下的加权有向图,给出算法Dijkstra产生的最短路径的支撑树，设顶点

A为源点，并写出生成过程。

标准答案：顶点A到顶点B、C、D、E的最短路径依次是3、18、38、43,按

Dijkstra所选顶点过程是B、C、D、E。支撑树的边集合为具体分析如

下表所示。

Dijkstra辑法的执行过程

饰环SWD(2]D[3]D[4]i)[51

初态|A|-320X45

1IA.BIB3183843

2JA.B.CIC3183843

31A.B.C.DID3183843

4IA.B.C.D.EIE3183843

知识点解析：暂无解析

43、(I)对于有向无环图，叙述2对于以下的图，写出它

17

的4个不同的拓扑有序序列。

标准答案：(1)对有向图，求拓扑序列步骤为：①在有向图中选一个没有前驱(即入

度为零)的顶点并输出。②在图中删除该顶点及所有以它为尾的弧。③重复①和

②步，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失

败。(2)从入度为O的顶点开始，当有多个顶点可以输出时，将其按序从上往下排

列，这样不会丢掉〜种拓扑序列。从顶点1开始的可能的拓扑序列为12345678、

12354678、13456278、13546278。提示：此题考杳的知识点是拓扑排序。

知识点解析：暂无解析

44、试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj

的路径(访)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)

标准答案：算法1：intvisited[]=O：//全局变量，访问数组初始化int

dfs(AdjListg,vi){//以邻接表存储的有向图g,判断vi到vj是否有通路,返回

10visited(vi]=l；//visited是访问数组，设顶点的信息就是顶点编号

P=g[vi].firstare；//第一个邻接点while(P!=nuH){j=p—>adjvex；

if(vj==j){flag=l；return(l)；}//vi和vj有通路if(visited[j]==O)dfs(g,j)；P=P

一〉next：)//whileif(!flag)return(O)；}算法2：输出vi到vj的路径,其思想是

用一个栈存放遍历的顶点，遇到顶点vj时输出路径。voiddfs(AdjListg,inti){/

/顶点vi和顶点vj间是否有路径，如有,则输出inllop=0,stack[]；//stack是

存放顶点编号的栈visiled[i]=l；//visited数组在进入dfs前已初始化

stack[++top]=i；P=g[i].firstarc；//求第一个邻接点while(P){if(p

—>adjvex==j){stack[++top]=j；printf("顶点vi和vj的路径为：\n")；for(i=1；

i<=top；i++)printf(''%4d'',stack|i|)；exit(O)：)elseif(visited|p

_*>adjvex]==0){dfs(g,g一>adjvex)；top-----；P=p->next；}}}算法3：非递归

算法亲解。intJudge(AdjListg,inti,j){//判断n个顶点以邻接表示的有向图g

中，顶点vi各vj是否有路径，//有则返回1,否则返回0。for(i=l；i<=n；

i++)visited[i]=Oi//访问标记数组初始化intstack。，top=0；stack[++top]=vi；

while(top>0){k=stack[top-----]；P=g[k].firstarc；while(P!=null&&visited[p

->adjvexl==l)p=p—>next；//查第k个链表中第一个未访问的弧结点

if(P==null)top-----：else{i=p->adjvex；if(i==j)return(l)；//顶点vi和vj诃有

路径else{visited[i]=l；stack[++top]=i；)})whilereturn(O)；}//顶点vi和vj间

无通路

知识点解析：暂无解析

45、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在

一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注

意：图中不存在顶点到自己的弧)

标准答案：用邻接矩阵存储时，可用以卜方法实现：voidPrint(intv,intstart)[/

/输出从顶点start开始的回路for(i：1；iv=n：i++)

if(g[v][i]!=0&&visited[i]==1){//若存在边(v,i),且顶点i的状态为1printf("％

d.t,V)；iRi==start)printfV'\rT)：elsePrint(i,start)：break；}//if)//Print

voiddfs(intv){visited[v]=i；for(j=l；j<=n；j++)if(g[v][j]!=O)//存在边(v,j)

if(visited[j]!=1){if(!visited[j])dfs(j)；)//ifclsc{cycle=l；Print。，j)：}

visited|v]=2：}voidfind_cycle(){//判断是否有回路，有则输出邻妻矩阵。

visited数组为全局变量for(i=l；i<=n；i++)visited[i：=O；for(i=l；i<=n；

i++)if(!visited[i])dfs(i)：}

知识点解析：暂无解析

46、己有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路

径，若有则打印出该路径上的顶点。

标准答案:voidAllpath(AdjListg,vertypeU,verlypev){//求有向图g中顶点u

到顶点v的所有简$.路径，初始调用形莪inttop=0,S[]：S[++top]=u；

visited!U1=1；while(top>0||P){P=g|S[top|].firstarc；//君一个邻接点while(P

f=null&&visited[p->adjvex]==1)P=p->next；//下一个访问邻接点表

if(P==null)top—：//退栈else{i=p—>adjvex;//取邻接点(编号)if(i==V){//

找到从u到v的一条简单路径，输出for(k=l；k<=top；k++)printf("％3d”，s[k])：

printf(tt%3d\n'\v)：)//ifelse{visited[i]=l；s[4-+top]=i；)//else深度优先遍

历}//else)//while}

知识点解析：暂无解析

47、“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有

圈为止.造给出用“破圈法”求解给定的带权连通无句图的一棵最小代价生成树的详

细算法，并用程序实现弥所给出的算法。(注意：圈就是回路)

标准答案：voidSpnTree(AdjListg){//用“破圈法”求解带权连通无向图的一棵最

小代价生成树typedefstruct{inti,j,w：(node：//设顶点信息就是顶点编号，

权是整数nodeedge[]；scanf("％d%d"，&e,&n)；//输入边数和项点数

for(i=l；i<=e；i++)//输入e条边：顶点，权值seanf("%d%d%d"，

&edge[i].i,&edge[i].j,&edge[i].W)：for(i=2；i<=e；i++){//按边上的权

值大小，对边进行逆序排序edge[O]=edge[i]；j=i—1；while(edge|j].W=n){//

破圈，直到边数e=n一1if(connect(k))//删除第k条边若仍连通f

edgefkl.W=0；eg-；)//测试下一条边edge[k],权值置0表示该边被删除

k++；//下条边}//while}connect。是测试图是否连通的函数，可用DFS函数

或BFS函数实现，若是连通图，一次进入DFS函数或BFS函数就可遍历完全部顶

点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破

圈”结束后，可输出edge中W不为0的n—I条边。

知识点解析：暂无解析

48、设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定

义为：MAx(从co到v的最短距离{①属J'V(G)}如果v是有向图G中具有最小偏

心度的顶点，则称顶点v是G的中心点。

标准答案：设C是有向图G的邻接矩阵，求最小偏心度的顶点的步骤如卜.：(1)利

用Floyd算法求出每对顶点之间的最短路径矩阵A；(2)对矩阵A求出每列i的最

大值，得到顶点i的偏心度；(3)在这n个顶点的偏心度中，求出最小偏心度的顶

点k,即为图G的中心点。对应的算法如下：iniCenier(MGraph&G)}ini

A[MAXV][MAXV],B[MAXV]；inti,j,k,m；for(i=0；i

知识点解析：暂无解析

49、对于一个使用邻接表存储的有向图G,可以利用深度优先遍历方法，对该图中

结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接

到的顶点的入度减1,并对其未访问的、入度为0的邻接到的顶点进行递归。(1)

给出完成上述功能的图的邻接表定义。(2)定义在算法中使用的全局辅助数组。(3)

写出在遍历图的同时进行拓扑排序的算法。

标准答案：(1)邻接表定义typcdcfstructArcNodc{intadjvex;struct

ArcNode*next；[ArcNode；typedefstructVNode{vertypedata；

ArcNode*firstarc：)VNode,AdjList[MAX]；(2)全局数组定义intvisited口=0：

finished[尸0；flag=1；//flag测试拓扑排序是否成功ArcNode*final=null：//

final是指向顶点链表的指针,初始化为0(3)算法voiddfs(AdjListg,vertypeV){/

/以顶点v开始深度优先遍历有向图g,顶点信息就是顶点编号ArcNode"：//

指向边结点的临时变量printf("％d"，V)；visited[v|=l；P=g[v].firstarc；

while(P!=null){j=p—^>adjvex；if(visited[j]==l&&finished[j]==O)flag=O；//dfs结

束前出现回边elseif(visited[j]==O){dfs(g,j)；finished[j]=l：|P=P->next：|//

whilet=(ArcNode*)malloc(sizeof(ArcNode))；//申请边结点t—>adjvex=v：t

一,next=final；final=t；//将该顶点插入链表)//dfs结束int

dfs_Topsort(Adjlistg){//对以邻接表为存储结构的有向图进行拓扑排序，拓扑成

功返回1,否则返回0i=l；whilc(flag&&i<=n)if(visitcd.[i]==0){dfs(g,i)；

finished[i]=l；)//ifreturn(flag)；)

知识点解析：暂无解析

计算机专业基础综合(数据结构)模拟

试卷第2套

一、单选题(本题共22题，每题1.0分，共22分。)

1、在下面关于树的相关概念的叙述中，正确的是()。

A、只有一个结点的二叉树的度为1

B、二叉树的度一定为2

C、二叉树的左右子树可任意交换

D、深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树

标准答案：D

知识点解析：只有一个结点的二叉树的度为零。二叉树的度可以为0、I、2：二叉

树的左右子树不能任意交换。

2、已知一算术表达式的中缀形式为A+B*C・D/E,后缀形式为ABC*+DE/—，

其前缀形式为()。

A、-A+B*C/DE

B、一A+B*CD/E

C、-+*ABC/DE

D、-+A*BC/DE

标准答案：D

知识点解析：根据题目给出的中缀和后缀表达式可以得到其算术表达式为：

(A+B*C)—D/E,前缀表达式：-+A*BC/DE。

3、算术表达式a+b*(c+d/e)转为后缀表达式后为()。

A、ab+cde/*

B、abcde/+*+

C、abcde/*++

D、abcde*/++

标准答案：B

知识点解析：根据表达式a+b*(c+d/e)可知其后缀表达式为abcde/+*+。

4、某二叉树的先序遍历序列为IJKLMNO,中序遍历序列为JLKINMO,则后序遍

历序列是()。

A、JLKMNOI

B、LKNJOMI

C、LKJNOMI

D、LKNOJMI

标准答案：C

知识点解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍

由此图可以确认后序遍历的序列为

5、设森林F对应的二叉树为B,它有m个结点，B的根为P,P的右子树结点个

数为n,森林F中第一棵树的结点个数是()。

A、m-n

B、m-n-l

C、n+l

D、条件不足，无法确定

标准答案：A

知识点解析：F对应的二叉树共有m个结点，右子树上n个，左子树上有(m-n

-1)个，第一株树包括根和左子树，共(m—n)个。

6、二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是()。

A、先序遍历二叉树

B、判断两个指定位置的结点是否在同一层上

C、层次遍历二叉树

D、根据结点的值查找其存储位置

标准答案：B

知识点解析：选项A、C、D运算的时间复杂度都是0(n),而选项B的运算的时间

复杂度为0(1),因为对于指定位置p和q的两个结点，判断是否在同一层上，只

需判断两者[Iog2p]=[log2q]是否成立。

7、设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100,那么

此二叉树中所包含的结点数最少为()。

A、188

B、200

C、199

D、201

标准答案：C

知识点解析：除根结点层只有1个结点外，其他各层均有两个结点，结点总数

=2x(100—1)+1=199。

8、树是结点的有限集合，一棵树中有()根结点。

A、有。个或1个

B、有。个或多个

C、有且只有一个

D、有1个或1个以上

标准答案：C

知识点解析：根据树的基本定义可知，每个树只能有且只有一个根结点。

9、下列二叉排序树中，满足平衡二叉树定义的是()。

A、

B、

C、

D、

标准答案：B

知识点解析：考查平衡二叉树的定义。根据平衡二叉树的定义有，任意结点的左右

子树高度差的绝对值不超过lo而其余三个选项均可以找到不符合的结点。

10、把树的根结点的层数定义为1,其他结点的层数等于其父结点所在层数加上

I。设T是一棵二又树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们

所在的层数分别为大代和入0,当关系式％Ki—入Kjgl一定成立时，则称T为一棵

()。

A、满二义树

B、二叉查找树

C、平衡二义树

D、完全二叉树

标准答案：C

知识点解析：此题干的叙述符合平衡二义树的定义。

11、设森林F中有三棵对，第一、第二、第三棵树的结点个数分别为Mi、M2和

M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。

A、Mi

B、M1+M2

C、M3

D、M2+M3

标准答案：D

知识点解析：森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结

点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵

树和第二棵树构成的，因此结点数为M2+M3。

12、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点

个数是（）。

A、10

B、11

C、16

D、不确定

标准答案：B

知识点解析：根据二叉树的性质可知，度为。的结点个数比度为2结点个数多一

个,即110=02+1o

13、具有10个叶结点的二叉树中有（）个度为2的结点。

A、8

B、9

C、10

D、11

标准答案：B

知识点解析：根据二叉树的性质no=n2+1,可知度为2的结点个数为9。

14、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为

1的结点数为2个，则度为O的结点数为（）个。

A、4

B、5

C、6

D、7

标准答案：C

知识点解析：一棵度为3的树，总结点数n=n（）+n]+n2+n3，而总分支总数为

noxO+n1x2+n2X1+nsx2,由于分支总数加1为结点总数，可得出n（）=6o

15、已知一棵二叉树，共有n个结点，那么此二叉树的高度为（）。

A、nlog2n

B、log2n

C>[log2n]+l

D、不确定

标准答案：D

知识点解析：已知一棵二叉树共有n个结点，但二叉树的形式没有给出，因此，二

叉树的高度不能确定。

16、已知一棵二叉树，第m层上最多含有结点数为（）。

A、2m

B、2m-1-1

C、2md

D、2m-l

标准答案：C

知识点解析：根据二叉树的性质，二叉树的第m层上最多有2m"。

17、有关二叉树下列说法正确的是（）。

A、二叉树就是度为2的树

B、一棵二叉树的度可以小于2

C、二叉树中至少有一个结点的度为2

D、二叉树中任何一个结点的度都为2

标准答案：B

知识点解析：本题考查二义树的概念。

18、一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（）。

A、CABDEFG

B、ABCDEFG

C、DACEFBG

D、BAECFDG

标准答案：B

知识点解析：由题可得A为根结点，并且B为A的孩子结点。选项A,C应为A

的左孩子，其前序序列应为AC……o选项B,当B为A的右孩子，C为B的右孩

子时，满足题目要求。选项C,类似选项A,其前序序列应为AD……o选项D,

B为A的左孩子，C为A的右子树的根，E为C的左子树，FDG为C的右子树，

其前序序列应为ABEC……o

19、已知一个二叉树有1025个结点，那么由此推断二叉树的高h为（）。

A、11

B、10

C、11〜1025

D、10—1024

标准答案：C

知识点解析：右完全二叉树中1025>27即最少需要11层，最多需要有1025

层。

20、一棵完全二叉树，共有n个结点，那么，其叶结点数共有（）个。

A、n/2

B、n

C、（n-l）/2

D、(n+l)/2

标准答案：D

知识点解析：此问题可以利用二叉树及完全二叉树的性质来求解。设i、j、k分别

为度为0、I、2的结点数目，则n=i+j+k。根据二叉树的性质有i=k+l,即k=i一

1,代入上式，得n=2i+j—1,即i=(n-j+l)/2。由于完全二又树中最多只有一个度

为1的结点，同时考虑到i为整数，(1)当j=0时，比时n=i+k=2k+l为奇数，则

i=(n+l)/2；(2)当j=l时,此时n=i+k+l=2k+2为偶数，则i=(n+l)/2向下取整。

所以选D。

21、()的遍历仍需要栈的支持。

A、前序线索树

B、中序线索树

C、后序线索树

D、中序线索树和前序线索树

标准答案：C

知识点解析：由于后序遍历先访问子树后访问根结点，从本质上要求运行栈中存放

祖先的信息，即使对二叉树进行后序线索化，仍然不能脱离栈的支持对此二叉树进

行遍历。

22、已知一棵二叉树高度为h,在此二叉树中只有度为0和度为2的结点，那么这

棵二叉树的结点个数最少为()。

A、2h

B、2h-I

C、2h+l

D、h+1

标准答案：B

知识点解析：暂无解析

二、综合应用题(本题共7题，每题1.0分，共7分。)

23、已知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描

述结构体)。

标准答案：二叉树是递归定义的，以递归方式建立最简单。二叉树建立过程如下：

BiTreeCreat(){//建立二叉树的二叉链表形式的存储结构ElemTypex：BiTree

bt；scanf(',%d,\&x)；//本题假定结点数据域为整型if(x==0)bt=null；else

if(x>0){bt=(BiNode*)malloc(sizeof(BiNode))；bt—>data=x：bt->lchild=Creat()；

bt>ichild-Creat():}elseerror("输入错误");ieturn(bt)；)//结束BiTree

知识点解析：暂无解析

24、判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描述结构体)。

标准答案：判断此二又树是否为完全二叉树的算法设计如下：im

JudgeComplete(BiTreebt){//判断二叉树是否是完全二叉树，如是，返回1；否

则，返回0intOg=0；BiTreeP=bt,Q[]：//Q是队列,元素是二叉树结点指

针，容量足够大if(P=null)return1：Queuelnit(Q)；Queueln(Q,P)；//初始化

队列，根结点指针入队while(!QueueEmpty(Q)){P=QueueOul(Q)：//出队if(p

->lchild&&!tag)QueueIn(Q,P->lchild)；//左孩子入队else{if(P

—>lehild)retum0：//前边已有结点为空，本结点不空elsetag=l；//首次出

现结点为空if(p—>rchild&&!tag)Queueln(Q,P—>rchild)；//右孩子入队else

if(p->rchild)return0；elsetag=1：))//whilereturn1；)//JudgcComplctc

知识点解析：暂无解析

25、以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。

标准答案：当森林(树)以孩子兄弟表示法存储时\若结点没有孩子(fch=null),则它

必是叶子，总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟(nsib)子树上叶结

点个数之和。typedefstructnode{elemTypedata；//数据域structnode*fch,

*nsib；//孩子与兄弟域}*Tree；intLcaves(Trcct){//计算以孩子一兄弟表示

法存储的森林的叶子数if⑴if(t一,fch=：null)//若结点无孩子，则该结点必是

叶子return(1+Leaves(t->nsib))；//返回叶子结点和其兄弟子树中的叶子结点数

elsercturn(Lcaves(t->fch)+Lcaves(t->nsib))；//孩了•子树和兄弟子树中口I子数之

和}

知识点解析：暂无解析

26、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L；

中序序列为：D,J,G,B,E,H,A,C,K,I,L,F。(1)写出该二又树的后序

序列。(2)画出该二叉树。(3)求该二叉树的高度以及该二叉树中度为2、1、0的结

点个数。

标准答案：此题只需从前序序列、中序序列得到唯一确定的二叉树即可。(1)J,

G,D.H,E,R,K,L,I,F.C.A»(2)二叉树的形式如下图所示：

(3)高度是5,度为0的结点个数为4,度为1的结

点个数为5,度为2的结点个数为3。

知识点解析：暂无解析

27、有n个结点的二叉树，已知叶结点个数为no。（1）写出求度为1的结点的个数

的山的计算公式。（2）若此树是深度为k的完全二叉树，写出n为最小的公式。

（3）若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。

标准答案：（1）设度为2的结点个数为止,»n=n0+ni+n2o由二叉树的性质

no=n2+Ln=2no+nj—1,所以度为1的结点的个数〃=n+l—2no;（2）当树是深度

为k的完全二叉树时，n的最小值min（n）=2k/。（3）当二叉树中只有度为0和度为2

的结点时，n=2n（）—1（其中n为树中的总结点数，顼为度为0的结点数目）。

知识点解析：暂无解析

28、已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉

二叉树的转换规则如下：（I）树的根结点为二叉树的根结点；（2）每个结点的第一个

子结点（最左的子树）作为该结点的左孩子：（3）每个结点的右孩子为在树中与该结

点的左孩子邻近的兄弟，所有具有兄弟关系的结点用指针链接起来。转换成二叉

29、在一棵表示有序集S的二叉搜索树(binarysearchtree)中，任意一条从根到叶结

点的路径将S分为3部分：在该路径左边结点中的元素组成的集合Si；在该路径

上的结点中的元素组成的集合S2;在该路径右边结点中的元素组成的集合S3。

S=S]US2US3o若对于任意的a6Si，beS2»cESs>是否总有aSbWc?为什么?

标准答案：不是。如下图所示的二叉搜索树:

取从4到12的路径，则S尸{1,2,3,7),S2={4,8,10,12},S3为空集，取Si

中的元素7和S2中的元素4,令a=7,b=4,有a>b。则上述命题不成立。

知识点解析：暂无解析

计算机专业基础综合(数据结构)模拟

试卷第3套

一、单选题(本题共24题，每题1.0分，共24分。)

1、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查

找法查找一个记录，其平均查找长度ASL为().

A、(n—1)/2

B、n/2

C、(n+l)/2

D、n

标准答案：C

知识点解析：此题考查的知识点是顺序查找长度ASL的计算。假设表长度为n,

那么查找第i个数据元素需进行n—i+l次比较，即G=n—i+l。又假设查找每个数

据元素的概率相等，即Pi=l/n,则顺序查找算法的平均查找长度为：

ASL=VP,Ct=—YC,=~Y(n-i+I)=--(n1)

父「田nG2所以应选C。

顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为((1)),二

分法查找只适用于查找顺序存储的有序表，平均比较次数为((2))。在此假定N为

线性表中结点数，且每次查找都是成功的。

2、(1)

A、N+1

B、21og2N

C、logzN

D、N/2

标准答案：D

知识点解析：暂无解析

3、(2)

A、N+1

B、210g2N

C、log2N

D、N/2

标准答案：C

知识点解析：此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所

给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+l)/

2,即查找成功时的平均比较次数约为表长的一半。二分法查找过程可用一个称为

判定树的二义树描述，由于判定树的叶子结点所在层次之差最多为1,故n个结点

的判定树的深度与n个结点的完全二叉树的深度相等，均为[log2n]+l。这样，折半

查找成功时，关键字比较次数最多不超过Uog2n]+1,所以，(1)应选择D,(2)应选

Co

4、适用于折半查找的表的存储方式及元素排列要求为()。

A、链接方式存储，元素无序

B、