计算机专业基础综合（数据结构）模拟试卷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一1B、n(n-1)／2C、n(n+1)／2D、n2标准答案：B知识点解析：无向图中有n个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为凡(n一1)／2。5、在一个具有n(n＞0)个顶点的连通无向图中，至少需要的边数是()。A、nB、n+1C、n-1D、n／2标准答案：C知识点解析：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以具有n个顶点的连通无向图至少有n一1条边。6、以下叙述中正确的是()。I．对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图Ⅱ．连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点Ⅲ．图的深度优先搜索中一般要采用栈来暂存访问过的顶点A、I，ⅡB、Ⅱ，ⅢC、I，ⅢD、I，Ⅱ，Ⅲ标准答案：B知识点解析：I的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。Ⅱ、Ⅲ的叙述显然是正确的。7、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中()。A、第i行非∞的元素之和B、第i列非∞的元素之和C、第i行非∞且非0的元素个数D、第i列非∞且非0的元素个数标准答案：D知识点解析：有向图的邻接矩阵中，0和∞表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。8、在一个无向图中，所有顶点的度之和等于边数的()倍。A、1／2B、1C、2D、4标准答案：C知识点解析：在无向图中，一条边计入两个顶点的度数。9、采用邻接表存储的图的深度优先遍历算法类似于二叉树的()算法。A、前序遍历B、中序遍历C、后序遍历D、按层遍历标准答案：A知识点解析：由图的深度优先遍历算法和二叉树的前序遍历可知选A。10、任何一个无向连通图()最小生成树。A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在标准答案：B知识点解析：无向连通图应有一棵或多棵最小生成树。11、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是()。A、求关键路径的方法B、求最短路径的迪杰斯特拉方法C、深度优先遍历算法D、广度优先遍历算法标准答案：C知识点解析：当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出DFSTra—verse算法)即为逆向的拓扑序列。12、有n个顶点e条边的无向图，采用邻接表存储时，有()个表头结点，有()个链表结点。A、n，2eB、n，2e+1C、n-1，2eD、n-1，2e+1标准答案：A知识点解析：根据邻接表的结构，无向图对应的邻接表有n个表头结点，有2e个链表结点(每条边对应两个链表结点)。13、对于由n个顶点组成的有向完全图来说，图中共包含()条边，对于由n个顶点组成的无向完全图来说，图中共包含()条边。A、n，n(n一1)B、n，n(n—1)／2C、2n，n(n—1)D、n(n一1)，n(n一1)／2标准答案：D知识点解析：由完全图的定义可知本题答案为D。14、在一个()图中寻找拓扑序列的过程称为()。A、有向，拓扑排序B、无向，拓扑排序C、有向，最短路径搜索D、无向，最短路径搜索标准答案：A知识点解析：寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。15、用邻接矩阵A表示图，判定任意两个顶点vi和vj之间是否有长度为m的路径相连，则只要检查()的第i行第j列的元素是否为零即可。A、mAB、AC、AmD、Am-1标准答案：C知识点解析：此题考查的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两点之间有边，则值为1，否则为0。本题只要考虑Am=A×A×…×A(m个A矩阵相乘后的乘积矩阵)中(i，j)的元素值是否为0就行了。16、当各边上的权值()时，BFS算法可用来解决单源最短路径问题。A、均相等B、均互不相等C、不一定相等D、不确定标准答案：A知识点解析：此题考查的知识点是图的BFS算法。BFS是从根结点开始，沿着树的宽度遍历树的结点，如果所有结点均被访问，则算法中止。当各边上的权值相等时，计算边数即可，所以选A。17、下面关于图的存储结构的叙述中正确的是()。A、用邻接矩阵存储图占用空间大小只与图中顶点数有关，与边数无关B、用邻接矩阵存储图占用空间大小只与图中边数有关，与顶点数无关C、用邻接表存储图占用空间大小只与图中顶点数有关，与边数无关D、用邻接表存储图占用空间大小只与图中边数有关，与顶点数无关标准答案：A知识点解析：邻接矩阵法的基本思想是对于有n个顶点的图，用一维数组Vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在Vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。邻接表法的基本思想：对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。第i个单链表表示依附于顶点Vi的边(对有向图是以顶点Vi为头或尾的弧)。18、在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是()。A、G中有弧＜vi，vj＞B、G中有一条从vi到vj的路径C、G中没有弧＜vi，vj＞D、G中有一条从vj到vi的路径标准答案：D知识点解析：此题考查的知识点是图的拓扑排序。根据拓扑排序的定义，若顶点vi与顶点vj有一条弧，则拓扑序列中顶点vi必在顶点vj之前。若有一条从vj到vi的路径，则顶点vi不可能在顶点vj之前。所以应选D。19、以下关于图的说法中正确的是()。I．一个有向图的邻接表和逆邻接表中的结点个数一定相等Ⅱ．用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关Ⅲ．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的A、I，ⅡB、Ⅱ，ⅢC、I，ⅢD、仅有Ⅱ标准答案：A知识点解析：说法I是正确的，邻接表和逆邻接表的区别仅在于出边和入边，边表的结点个数都等于有向图中的边的个数。说法Ⅱ是正确的，邻接矩阵的空间复杂度为O(n2)，与边的个数无关。说法Ⅲ是错误的，有向图的邻接矩阵不一定是不对称的，例如，有向完全图的邻接矩阵就是对称的。20、下列关于AOE网的叙述中，不正确的是()。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，那么整个工程将会提前完成C、所有的关键活动提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程将会提前完成标准答案：B知识点解析：此题考查的知识点是图的关键路径。在AOE网中，从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径称为关键路径，并且不只一条。关键路径上的活动称为关键活动。A、C、D的说法都正确。但任何一个关键活动提前完成，不一定会影响关键路径，所以根据题意应选B。21、一个二部图的邻接矩阵A是一个()类型的矩阵。A、n×n矩阵B、分块对称矩阵C、上三角矩阵D、下三角矩阵标准答案：B知识点解析：此题考查的知识点是二部图的定义与存储。二部图定义为：若能将无向图G=的顶点集V划分成两个子集V1和V2(V1∩V2=)，使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图。由于其特点，其存储矩阵必为分块对称的，所以选B。22、求解最短路径的Floyd算法的时间复杂度为()。A、O(n)B、O(n+c)C、O(n2)D、O(n3)标准答案：D知识点解析：暂无解析23、下列4组含C1—C7的结点序列中，()是下图所示的有向图的拓扑序列。A、C1，C2，C6，C7，C5，C4，C3B、C1，C2，C6，C3，C4，C5，C7C、C1，C4，C2，C3，C5，C6，C7D、C5，C7，C4，C1，C2，C3，C6标准答案：D知识点解析：考查拓扑排序的算法。以1开头的拓扑排序过程，如下图所示：以5开头的拓扑排序过程，答案中的过程如下图所示：24、如果具有n个顶点的图是一个环，则它有()棵生成树。A、n2B、nC、n—1D、1标准答案：B知识点解析：因为n个顶点构成的环共有n条边，去掉其中任意一条便是一棵生成树，共有n种情况，所以可以有n棵不同的生成树。25、如下图所示，在下面的5个序列中，符合深度优先遍历的序列有()个。①aebfdc②acfdeb③aedfcb④aefdbc⑤aecfdbA、5B、4C、3D、2标准答案：D知识点解析：本题中，符合深度优先遍历顺序的是1和5，其他三个序列均不符合。26、无向图G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，则图G最多有()个顶点。A、11B、12C、15D、16标准答案：D知识点解析：由于在具有n个顶点e条边的无向图中，有，故可求得度为2的顶点数为7个，从而最多有16个顶点。27、对AOE网络中有关关键路径的叙述中，正确的是()。A、从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间B、从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间C、从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间D、从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间标准答案：A知识点解析：本题考查关键路径的定义。关键路径：从起点到终点的最长路径长度(路径上各活动持续时间之和)。关键活动：关键路径上的活动称为关键活动。28、以下关于图的叙述中，正确的是()。A、强连通有向图的任何顶点到其他所有顶点都有弧B、图与树的区别在于图的边数大于或等于顶点数C、无向图的连通分量指无向图中的极大连通子图D、假设有图G={V，{E}}，顶点集V’∈V，E’∈E，则V’和{E’}构成G的子图标准答案：C知识点解析：强连通有向图的任何顶点到其他所有顶点都有路径，但未必有弧，A错误。图与树的区别是逻辑上的，而不是边数的区别，图的边数也可能小于树的边数。若E’中的边对应的顶点不是V’中的元素时，则V’和{E’}无法构成图，D错误。29、假设有n个顶点e条边的有向图用邻接表表示，则删除与某个顶点v相关的所有边的时间复杂度为()。A、O(n)B、O(e)C、O(n+e)D、O(ne)标准答案：C知识点解析：删除与某项点v相关的所有边的过程如下：先删除下标为v的顶点表结点的单链表，出边数最多为n—1，对应时间复杂度为O(n)，再扫描所有边表结点，删除所有的入边，对应时间复杂度为O(e)。故总的时间复杂度为O(n+e)。30、若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是()。A、11B、10C、9D、8标准答案：B知识点解析：n个顶点构成的无向图中，边数≤n(n一1)／2，将e=36代入，有n≥9，现已知无向图是非连通的，则n至少为10。31、已知有向图G=(V，A)，其中V={a，b，c，d，e}，A={，，，，，}。对该图进行拓扑排序，下面序列中不是拓扑排序的是()。A、a，d，c，b，eB、d，a，b，c，eC、a，b，d，c，eD、a，b，c，d，e标准答案：D知识点解析：选项D中，删去a、b及其对应的出边后，c的入度不为0，因此有边，故不是拓扑序列。选项A、B、C均为拓扑序列。解答本类题时，建议读者根据边集合画出草图。32、用有向无环图描述表达式(A+B)*((A+B)／A)，至少需要顶点的数目为()。A、5B、6C、8D、9标准答案：A知识点解析：此题考查的知识点是有向无环图的定义。有向无环图是一个无环的有向图，可以用来表示公共子表达式，本题中出现的5个字符作为5个顶点，其中A+B和A可共用，所以至少5个即可，选A。33、邻接多重表的存储结构和十字链表类似，也是由顶点表和边表组成，每一条边用一个结点表示，其顶点表结点结构和边表结点结构如下图所示：关于图中各个域的说明，不正确的是()。A、vertex存储的是结点的数值域的内容B、firstedge域指示第一条依附于该顶点的边C、mark指向下一条依附于结点的边D、info为指向和边相关的各种信息的指针域标准答案：C知识点解析：顶点表由两个域组成，vertex域存储和该顶点相关的信息，firstedge域指示第一条依附于该顶点的边。边表结点由六个域组成：mark为标记域，用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；iIink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边：info为指向和边相关的各种信息的指针域。34、以下关于十字链表的说法中，不正确的是()。A、十字链表是有向图的另一种链式存储结构B、行指针row为矩阵中的行位置，列指针col为矩阵中的列位置C、数值val为矩阵中的值D、right指针指向矩阵中的行位置，down指针指向矩阵中的列位置标准答案：D知识点解析：right指向右侧的一个非零元素，down指向下侧的一个非零元素。二、综合应用题(本题共15题，每题1.0分，共15分。)35、证明：具有n个顶点和多于n一1条边的无向连通图G一定不是树。标准答案：此题考查的知识点是图的定义。具有n个顶点n—1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n一1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树(在图论中树定义为无回路的连通图)。知识点解析：暂无解析36、证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全0的充要条件是该图为无环图。标准答案：此题考查的知识点是无环图的定义。根据题意，该有向图顶点编号的规律是让弧尾顶点的编号大于弧头顶点的编号。由于不允许从某顶点发出并回到自身顶点的弧，所以邻接矩阵主对角线元素均为0。先证明该命题的充分条件。由于弧尾顶点的编号均大于弧头顶点的编号，在邻接矩阵中，非零元素(A[i][j]=1)自然是落到下三角矩阵中；命题的必要条件是要使上三角为0，则不允许出现弧头顶点编号大于弧尾顶点编号的弧，否则，就必然存在环路。(对该类有向无环图顶点编号，应按顶点出度顺序编号。)知识点解析：暂无解析37、关于图(Graph)的一些问题：(1)有n个顶点的有向强连通图最多有多少条边?最少有多少条边?(2)表示有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?标准答案：(1)n(n—1)，n(2)106，不一定是稀疏矩阵提示：此题考查的知识点是图的相关术语。(1)在有向图G中，如果对于每一对vi，vj，属于V，vi不等于vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。最多边是所有的顶点每对之间都有边，边数为n(n一1)；最少只有一个方向有边，为n。(2)元素个数为矩阵的大小，即106，稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律，不一定稀疏。知识点解析：暂无解析38、如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上?标准答案：此题考查的知识点是图顶点度数。可以按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n一1，最小出度为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]=1，否则A[i，j]=0。请给出一个算法思想，该算法能判断G是否是非循环图(即G中是否存在回路)，要求算法的时间复杂性为O(n2)。标准答案：此题考查的知识点是图的遍历。采用深度优先遍历算法，在执行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。支撑树的边集合为{，，，}，具体分析如下表所示。知识点解析：暂无解析43、(1)对于有向无环图，叙述求拓扑有序序列的步骤。(2)对于以下的图，写出它的4个不同的拓扑有序序列。标准答案：(1)对有向图，求拓扑序列步骤为：①在有向图中选一个没有前驱(即入度为零)的顶点并输出。②在图中删除该顶点及所有以它为尾的弧。③重复①和②步，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。(2)从入度为O的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉～种拓扑序列。从顶点1开始的可能的拓扑序列为12345678、12354678、13456278、13546278。提示：此题考查的知识点是拓扑排序。知识点解析：暂无解析44、试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)。(注意：算法中涉及的图的基本操作必须在存储结构上实现。)标准答案：算法1：intvisited[]=0：／／全局变量，访问数组初始化intdfs(AdjListg，vi){／／以邻接表存储的有向图g，判断vi到vj是否有通路，返回1或0visited[vi]=1；／／visited是访问数组，设顶点的信息就是顶点编号P=g[vi]．firstarc；／／第一个邻接点while(P!=null){j=p一>adjvex；if(vj==j){flag=1；return(1)；}／／vi和vj有通路if(visited[j]==0)dfs(g，j)；P=P一>next：}／／whileif(!flag)return(0)；}算法2：输出vi到vj的路径，其思想是用一个栈存放遍历的顶点，遇到顶点vj时输出路径。voiddfs(AdjListg，inti){／／顶点vi和顶点vj间是否有路径，如有，则输出inllop=0，stack[]；／／stack是存放顶点编号的栈visited[i]=1；／／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(0)：}elseif(visited[p一>adjvex]==0){dfs(g，g一>adjvex)；top一一；P=p一>next；}}}算法3：非递归算法求解。intJudge(AdjListg，inti，j){／／判断n个顶点以邻接表示的有向图g中，顶点vi各vj是否有路径，／／有则返回1，否则返回O。for(i=1；i<=n；i++)visited[i]=0i／／访问标记数组初始化intstack[]，top=0；stack[++top]=vi；while(top>0){k=stack[top一一]；P=g[k]．firstarc；while(P!=null&&visited[p一>adjvex]==1)p=p一>next；／／查第k个链表中第一个未访问的弧结点if(P==null)top一一：else{i=p一>adjvex；if(i==j)return(1)；／／顶点vi和vj间有路径else{visited[i]=1；stack[++top]=i；}}}whilereturn(0)；}／／顶点vi和vj间无通路知识点解析：暂无解析45、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路(找到一条即可)。(注意：图中不存在顶点到自己的弧)标准答案：用邻接矩阵存储时，可用以下方法实现：voidPrint(intv，intstart){／／输出从顶点start开始的回路for(i：1；i<=n：i++)if(g[v][i]!=0&&visited[i]==1){／／若存在边(v，i)，且顶点i的状态为1printf(”％d．t，V)；if(i==start)printf(”＼n”)：elsePrint(i，start)：break；}／／if}／／Printvoiddfs(intv){visited[v]=i；for(j=1；j<=n；j++)if(g[v][j]!=0)／／存在边(v，j)if(visited[j]!=1){if(!visited[j])dfs(j)；}／／ifelse{cycle=1；Print(j，j)：}visited[v]=2：}voidfind_cycle(){／／判断是否有回路，有则输出邻接矩阵。visited数组为全局变量for(i=1；i<=n；i++)visited[i]=0；for(i=1；i<=n；i++)if(!visited[i])dfs(i)：}知识点解析：暂无解析46、已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则打印出该路径上的顶点。标准答案：voidAllpath(AdjListg，vertypeU，vertypev){／／求有向图g中顶点u到顶点v的所有简单路径，初始调用形式inttop=0，S[]：S[++top]=u；visited[U]=1；while(top>0||P){P=g[S[top]]．firstarc；／／第一个邻接点while(Pf=null&&visited[p一>adjvex]==1)P=p->next；／／下一个访问邻接点表if(P==null)top--：／／退栈else{i=p一>adjvex;／／取邻接点(编号)if(i==V){／／找到从u到v的一条简单路径，输出for(k=1；k<=top；k++)printf(”％3d”，s[k])：printf(tt％3d＼n”，v)：}／／ifelse{visited[i]=1；s[++top]=i；}／／else深度优先遍历}／／else}／／while}知识点解析：暂无解析47、“破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)标准答案：voidSpnTree(AdjListg){／／用“破圈法”求解带权连通无向图的一棵最小代价生成树typedefstruct{inti，j，w：}node；／／设顶点信息就是顶点编号，权是整数nodeedge[]；scanf(”％d％d”，&e，&n)；／／输入边数和项点数for(i=1；i<=e；i++)／／输入e条边：顶点，权值seanf(”％d％d％d”，&edge[i]．i，&edge[i]．j，&edge[i]．W)；for(i=2；i<=e；i++){／／按边上的权值大小，对边进行逆序排序edge[0]=edge[i]；j=i一1；while(edge[j]．W=n){／／破圈，直到边数e=n一1if(connect(k))／／删除第k条边若仍连通fedge[k]．W=0；eg--；}／／测试下一条边edge[k]，权值置0表示该边被删除k++；／／下条边}／／while}connect()是测试图是否连通的函数，可用DFS函数或BFS函数实现，若是连通图，一次进入DFS函数或BFS函数就可遍历完全部顶点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破圈”结束后，可输出edge中W不为0的n一1条边。知识点解析：暂无解析48、设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAx{从ω到v的最短距离{ω属于V(G)}如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。标准答案：设C是有向图G的邻接矩阵，求最小偏心度的顶点的步骤如下：(1)利用Floyd算法求出每对顶点之间的最短路径矩阵A；(2)对矩阵A求出每列i的最大值，得到顶点i的偏心度；(3)在这n个顶点的偏心度中，求出最小偏心度的顶点k，即为图G的中心点。对应的算法如下：intCenter(MGraph&G)}intA[MAXV][MAXV]，B[MAXV]；inti，j，k，m；for(i=0；i知识点解析：暂无解析49、对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中结点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减1，并对其未访问的、入度为0的邻接到的顶点进行递归。(1)给出完成上述功能的图的邻接表定义。(2)定义在算法中使用的全局辅助数组。(3)写出在遍历图的同时进行拓扑排序的算法。标准答案：(1)邻接表定义typedefstructArcNode{intadjvex;structArcNode*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*t：／／指向边结点的临时变量printf(”％d”，V)；visited[v]=1；P=g[v]．firstarc；while(P!=null){j=p一>adjvex；if(visited[j]==l&&finished[j]==0)flag=0；／／dfs结束前出现回边elseif(visited[j]==0){dfs(g，j)；finished[j]=1；}P=P一>next：}／／whilet=(ArcNode*)malloc(sizeof(ArcNode))；／／申请边结点t一>adjvex=v：t一>next=final；final=t；／／将该顶点插入链表}／／dfs结束intdfs_Topsort(Adjlistg){／／对以邻接表为存储结构的有向图进行拓扑排序，拓扑成功返回1，否则返回0i=1：while(flag&&i<=n)if(visited．[i]==0){dfs(g，i)；finished[i]=1；}／／ifreturn(flag)；}知识点解析：暂无解析计算机专业基础综合（数据结构）模拟试卷第2套一、单选题(本题共22题，每题1.0分，共22分。)1、在下面关于树的相关概念的叙述中，正确的是()。A、只有一个结点的二叉树的度为1B、二叉树的度一定为2C、二叉树的左右子树可任意交换D、深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树标准答案：D知识点解析：只有一个结点的二叉树的度为零。二叉树的度可以为0、1、2：二叉树的左右子树不能任意交换。2、已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／一，其前缀形式为()。A、一A+B*C／DEB、一A+B*CD／EC、-+*ABC／DED、-+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、JLKMNOIB、LKNJOMIC、LKJNOMID、LKNOJMI标准答案：C知识点解析：由先序和中序遍历序列确定一棵二叉树，再给出这棵二叉树的后序遍历序列。由此图可以确认后序遍历的序列为LKJNOMI。5、设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中第一棵树的结点个数是()。A、m-nB、m-n-1C、n+1D、条件不足，无法确定标准答案：A知识点解析：F对应的二叉树共有m个结点，右子树上n个，左子树上有(m一n一1)个，第一株树包括根和左子树，共(m一n)个。6、二叉树若用顺序方法存储，则下列四种算法中运算时间复杂度最小的是()。A、先序遍历二叉树B、判断两个指定位置的结点是否在同一层上C、层次遍历二叉树D、根据结点的值查找其存储位置标准答案：B知识点解析：选项A、C、D运算的时间复杂度都是O(n)，而选项B的运算的时间复杂度为O(1)，因为对于指定位置p和q的两个结点，判断是否在同一层上，只需判断两者[log2p]=[log2q]是否成立。7、设某二叉树中只有度为0和度为2的结点，如果此二叉树的高度为100，那么此二叉树中所包含的结点数最少为()。A、188B、200C、199D、201标准答案：C知识点解析：除根结点层只有1个结点外，其他各层均有两个结点，结点总数=2×(100一1)+1=199。8、树是结点的有限集合，一棵树中有()根结点。A、有0个或1个B、有0个或多个C、有且只有一个D、有1个或1个以上标准答案：C知识点解析：根据树的基本定义可知，每个树只能有且只有一个根结点。9、下列二叉排序树中，满足平衡二叉树定义的是()。A、

B、

C、

D、

标准答案：B知识点解析：考查平衡二叉树的定义。根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个选项均可以找到不符合的结点。10、把树的根结点的层数定义为1，其他结点的层数等于其父结点所在层数加上I。设T是一棵二叉树，Ki和Kj是T中子结点数小于2的结点中的任意两个，它们所在的层数分别为λKi和λKj，当关系式|λKi一λKj|≤1一定成立时，则称T为一棵()。A、满二叉树B、二叉查找树C、平衡二叉树D、完全二叉树标准答案：C知识点解析：此题干的叙述符合平衡二叉树的定义。11、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是()。A、M1B、M1+M2C、M3D、M2+M3标准答案：D知识点解析：森林转换成对应的二叉树，第一棵树的根结点作为此二叉树的根结点，第一棵树除根结点外其他结点时此二叉树的左子树。二叉树的右子树为第二棵树和第二棵树构成的，因此结点数为M2+M3。12、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()。A、10B、11C、16D、不确定标准答案：B知识点解析：根据二叉树的性质可知，度为0的结点个数比度为2结点个数多一个，即n0=n2+1。13、具有10个叶结点的二叉树中有()个度为2的结点。A、8B、9C、10D、11标准答案：B知识点解析：根据二叉树的性质n0=n2+1，可知度为2的结点个数为9。14、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为O的结点数为()个。A、4B、5C、6D、7标准答案：C知识点解析：一棵度为3的树，总结点数n=n0+n1+n2+n3，而总分支总数为n0×0+n1×2+n2×1+n3×2，由于分支总数加1为结点总数，可得出n0=6。15、已知一棵二叉树，共有n个结点，那么此二叉树的高度为()。A、nlog2nB、log2nC、[log2n]+1D、不确定标准答案：D知识点解析：已知一棵二叉树共有n个结点，但二叉树的形式没有给出，因此，二叉树的高度不能确定。16、已知一棵二叉树，第m层上最多含有结点数为()。A、2mB、2m-1一1C、2m-1D、2m-1标准答案：C知识点解析：根据二叉树的性质，二叉树的第m层上最多有2m-1。17、有关二叉树下列说法正确的是()。A、二叉树就是度为2的树B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为2标准答案：B知识点解析：本题考查二叉树的概念。18、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是()。A、CABDEFGB、ABCDEFGC、DACEFBGD、BAECFDG标准答案：B知识点解析：由题可得A为根结点，并且B为A的孩子结点。选项A，C应为A的左孩子，其前序序列应为AC……。选项B，当B为A的右孩子，C为B的右孩子时，满足题目要求。选项C，类似选项A，其前序序列应为AD……。选项D，B为A的左孩子，C为A的右子树的根，E为C的左子树，FDG为C的右子树，其前序序列应为ABEC……。19、已知一个二叉树有1025个结点，那么由此推断二叉树的高h为()。A、11B、10C、11～1025D、10～1024标准答案：C知识点解析：右完全二叉树中1025＞210，即最少需要11层，最多需要有1025层。20、一棵完全二叉树，共有n个结点，那么，其叶结点数共有()个。A、n／2B、nC、(n-1)／2D、(n+1)／2标准答案：D知识点解析：此问题可以利用二叉树及完全二叉树的性质来求解。设i、j、k分别为度为0、1、2的结点数目，则n=i+j+k。根据二叉树的性质有i=k+1，即k=i一1，代入上式，得n=2i+j—1，即i=(n-j+1)／2。由于完全二又树中最多只有一个度为1的结点，同时考虑到i为整数，(1)当j=0时，此时n=i+k=2k+1为奇数，则i=(n+1)／2；(2)当j=1时，此时n=i+k+1=2k+2为偶数，则i=(n+1)／2向下取整。所以选D。21、()的遍历仍需要栈的支持。A、前序线索树B、中序线索树C、后序线索树D、中序线索树和前序线索树标准答案：C知识点解析：由于后序遍历先访问子树后访问根结点，从本质上要求运行栈中存放祖先的信息，即使对二叉树进行后序线索化，仍然不能脱离栈的支持对此二叉树进行遍历。22、已知一棵二叉树高度为h，在此二叉树中只有度为0和度为2的结点，那么这棵二叉树的结点个数最少为()。A、2hB、2h一1C、2h+1D、h+1标准答案：B知识点解析：暂无解析二、综合应用题(本题共7题，每题1.0分，共7分。)23、已知一个二叉树，用二叉链表形式存储，给出此二叉树建立过程算法(可不描述结构体)。标准答案：二叉树是递归定义的，以递归方式建立最简单。二叉树建立过程如下：BiTreeCreat(){／／建立二叉树的二叉链表形式的存储结构ElemTypex：BiTreebt；scanf(”％d”，&x)；／／本题假定结点数据域为整型if(x==0)bt=null；elseif(x>0){bt=(BiNode*)malloc(sizeof(BiNode))；bt一>data=x：bt一>lchild=Creat()；bt一>rchild=Creat()：}elseerror(”输入错误”)；return(bt)；}／／结束BiTree知识点解析：暂无解析24、判别给定的二叉树是否是完全二叉树，并给出设计的算法(可不描述结构体)。标准答案：判断此二又树是否为完全二叉树的算法设计如下：intJudgeComplete(BiTreebt){／／判断二叉树是否是完全二叉树，如是，返回1；否则，返回0inttag=0；BiTreeP=bt，Q[]：／／Q是队列，元素是二叉树结点指针，容量足够大if(P==null)return1：QueueInit(Q)；Queueln(Q，P)；／／初始化队列，根结点指针入队while(!QueueEmpty(Q)){P=QueueOut(Q)：／／出队if(p一>lchild&&!tag)QueueIn(Q，P一>lchild)；／／左孩子入队else{if(P一>lehild)retum0：／／前边已有结点为空，本结点不空elsetag=1；／／首次出现结点为空if(p一>rchild&＆!tag)Queueln(Q，P一>rchild)；／／右孩子入队elseif(p一>rchild)return0；elsetag=1：}}／／whilereturn1；}／／JudgeComplete知识点解析：暂无解析25、以孩子一兄弟表示法存储的森林的叶子结点数(要求描述结构)。标准答案：当森林(树)以孩子兄弟表示法存储时，若结点没有孩子(fch=null)，则它必是叶子，总的叶子结点个数是孩子子树(fch)上的叶子数和兄弟(nsib)子树上叶结点个数之和。typedefstructnode{elemTypedata；／／数据域structnode*fch，*nsib；／／孩子与兄弟域}*Tree；intLeaves(Treet){／／计算以孩子一兄弟表示法存储的森林的叶子数if(t)if(t一>fch=：null)／／若结点无孩子，则该结点必是叶子return(1+Leaves(t->nsib))；／／返回叶子结点和其兄弟子树中的叶子结点数elsereturn(Leaves(t->fch)+Leaves(t->nsib))；／／孩子子树和兄弟子树中叶子数之和}知识点解析：暂无解析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，B，K，L，I，F，C，A。(2)二叉树的形式如下图所示：(3)高度是5，度为0的结点个数为4，度为1的结点个数为5，度为2的结点个数为3。知识点解析：暂无解析27、有n个结点的二叉树，已知叶结点个数为n0。(1)写出求度为1的结点的个数的n1的计算公式。(2)若此树是深度为k的完全二叉树，写出n为最小的公式。(3)若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。标准答案：(1)设度为2的结点个数为n2，则n=n0+n1+n2。由二叉树的性质n0=n2+1，n=2n0+n1一1，所以度为1的结点的个数n1=n+1一2n0；(2)当树是深度为k的完全二叉树时，n的最小值min(n)=2k-1。(3)当二叉树中只有度为0和度为2的结点时，n=2n0一1(其中n为树中的总结点数，n0为度为0的结点数目)。知识点解析：暂无解析28、已知一棵树的结点表示如下，其中各兄弟结点是依次出现的，画出对应的二叉树。标准答案：相应的树如下图所示：树到二叉树的转换规则如下：(1)树的根结点为二叉树的根结点；(2)每个结点的第一个子结点(最左的子树)作为该结点的左孩子；(3)每个结点的右孩子为在树中与该结点的左孩子邻近的兄弟，所有具有兄弟关系的结点用指针链接起来。转换成二叉树如下图所示：知识点解析：暂无解析29、在一棵表示有序集S的二叉搜索树(binarysearchtree)中，任意一条从根到叶结点的路径将S分为3部分：在该路径左边结点中的元素组成的集合S1；在该路径上的结点中的元素组成的集合S2；在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1，b∈S2，c∈S3，是否总有a≤b≤c?为什么?标准答案：不是。如下图所示的二叉搜索树：取从4到12的路径，则S1={1，2，3，7}，S2={4，8，10，12}，S3为空集，取S1中的元素7和S2中的元素4，令a=7，b=4，有a＞b。则上述命题不成立。知识点解析：暂无解析计算机专业基础综合（数据结构）模拟试卷第3套一、单选题(本题共24题，每题1.0分，共24分。)1、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A、(n—1)／2B、n／2C、(n+1)／2D、n标准答案：C知识点解析：此题考查的知识点是顺序查找长度ASL的计算。假设表长度为n，那么查找第i个数据元素需进行n—i+1次比较，即Ci=n—i+1。又假设查找每个数据元素的概率相等，即Pi=1／n，则顺序查找算法的平均查找长度为：所以应选C。顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为((1))，二分法查找只适用于查找顺序存储的有序表，平均比较次数为((2))。在此假定N为线性表中结点数，且每次查找都是成功的。2、(1)A、N+1B、2log2NC、log2ND、N／2标准答案：D知识点解析：暂无解析3、(2)A、N+1B、2log2NC、log2ND、N／2标准答案：C知识点解析：此题考查的知识点是各类查找算法的比较次数计算。顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log2n]+1。这样，折半查找成功时，关键字比较次数最多不超过[log2n]+1。所以，(1)应选择D，(2)应选C。4、适用于折半查找的表的存储方式及元素排列要求为()。A、链接方式存储，元素无序B、链接方式存储，元素有序C、顺序方式存储，元素无序D、顺序方式存储，元素有序标准答案：D知识点解析：此题考查的知识点是折半查找的特点。折半查找要求顺序存储且元素有序，所以应选D。5、具有12个关键字的有序表，折半查找的平均查找长度为()。A、3．1B、4C、2．5D、5标准答案：A知识点解析：此题考查的知识点是折半查找的思想。把关键字按完全二叉树的形式画出查找树，按结点高度计算比较次数。12个结点可以画出高度为4的完全二叉树，1层1个结点比较1次，2层2个结点比较2次，3层4个结点比较3次，4层5个结点比较4次，37／12=3．1，应选A。6、折半查找的时间复杂性为()。A、O(n2)B、O(n)C、O(nlog2n)D、O(log2n)标准答案：D知识点解析：此题考查的知识点是折半查找的效率。其查找效率与比较次数有关，折半查找成功时，关键字比较次数最多不超过[log2n]+1，所以其效率为O(log2n)，应选D。7、当采用分块查找时，数据的组织方式为()。A、数据分成若干块，每块内数据有序B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C、数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D、数据分成若干块，每块(除最后一块外)中数据个数需相同标准答案：B知识点解析：分块查找是将数据分成若干块，块间有序，块内不必有序。8、下面函数的功能是实现分块查找，空白处应该添加的内容是()。intBlkSearch(int*nz，intkey，intblock，intBLK，intlen){inti；block=block—1：if(len<=0){puts("表为空!")：return0：}if(BLK>len)BLK=len；for(i=block*BLK；i<(block+1)*BLK&&nz[i]!=0；i++){if(______){printf(”找到第％d个数是％d＼n”，i，key)；return0；}}printf(”＼n”)：printf(”查找结束＼n”)；return0；}A、nz[i]==keyB、nz[i]==BLKC、nz[i]==blockD、nz[i]==0标准答案：A知识点解析：如果当前的值与所查找关键字相等，则完成查找。二叉查找树的查找效率与二叉树的((1))有关，在((2))时其查找效率最低。9、(1)A、高度B、结点的多少C、树形D、结点的位置标准答案：C知识点解析：暂无解析10、(2)A、结点太多B、完全二叉树C、呈单枝树D、结点太复杂标准答案：C知识点解析：二叉查找树的查找效率与树形有关，当结点呈单枝树排列时效率最低。11、在一棵高度为h的理想平衡二叉树中，最少含有()个结点，最多含有()个结点。A、2h2h-1B、2h一12hC、2h+12h一1D、2h-12h一1标准答案：D知识点解析：由平衡二叉树的特性可知，一棵高度为h的理想平衡二叉树中，含有结点数最少的情形是：前h一1层为满二叉树，第h层只有一个结点，因而结点总数为(2h-1一1)+1=2h-1。含有结点数最多的情形是：该树是一棵高度为h的满二叉树，因而结点总数为2h一1。12、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是()。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)标准答案：C知识点解析：分别根据给出的序列构建平衡二叉树，得出C与其他不同。13、关于B一树，下列说法中不正确的是()。A、B一树是一种查找树B、所有的叶结点具有相同的高度C、2-3树中，所有非叶子结点有l或者3个孩子结点D、通常情况下，B一树不是二叉树标准答案：C知识点解析：B一树定义如下：一棵m阶B一树，或者是空树，或者是满足以下性质的m叉树：(1)根结点或者是叶子，或者至少有两棵子树，至多有m棵子树。(2)除根结点外，所有非终端结点至少有[m／2]棵子树，至多有m棵子树。(3)所有叶子结点都在树的同一层上。(4)每个结点应包含如下信息：(n，A0，K1，A1，K2，A2，…，Kn，An)。其中：Ki(1≤i≤n)是关键字，且Ki＜Ki+1(1≤i≤n一1)；Ai(i=0，1，…，n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki，Ai所指向的子树中所有结点的关键字都大于Ki。n是结点中关键字的个数，且[m／2]—1≤n≤m一1，n+1为子树的棵数。14、在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是()。A、30．36B、38，48，28C、48，18，38，28D、60，30，50，40，38，36标准答案：C知识点解析：设Ni表示深度为h的平衡二叉树中含有的最少结点数，有：N0=0，N1=1，N2=2；计算的公式为：Nh=Nh-1+Nh-2+1；N3=N2+N1+1=4；N4=N3+N2+1=7；N5=N4+N3+1=12；N6=N5+N4+1=20＞15。也就是说，高度为6的平衡二叉树最少有20个结点，因此15个结点的平衡二叉树的高度为5，而最小叶子结点的层数为3，所以选项D错误。选项A在查找30后，指针应该指向左孩子，而不是右孩子；选项B与选项A存在同样的问题，因而选项A、B错误。而选项C的查找路径如下图所示：15、下面关于m阶B树的说法中，正确的是()。①每个结点至少有两棵非空子树。②树中每个结点至多有m-1个关键字。③所有叶子在同一层上。④当插入一个数据项引起B树结点分裂后，树长高一层。A、①②③B、②③C、②③④D、③标准答案：D知识点解析：根据B树定义可知只有③正确。16、下面关于B和B+树的叙述中，不正确的是()。A、B树和B+树都是平衡的多叉树B、B树和B+树都可用于文件的索引结构C、B树和B+树都能有效地支持顺序检索D、B树和B+树都能有效地支持随机检索标准答案：C知识点解析：此题考查的知识点是B一树和B+树的定义。B+树是应文件系统所需而发展出的一种B一树的变形树。一棵m阶的B+树和m阶的B一树的差异在于：(1)有n棵子树的结点中含有n个关键字。(2)所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。(3)所有的非终端结点可以看成是索引部分，结点中仅含其子树(根结点)中的最大(或最小)关键字。通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。所以B+树能有效地支持随机检索和顺序检索。显然应选C。17、m阶B一树是一棵()。A、m叉排序树B、m叉平衡排序树C、m-1叉平衡排序树D、m+1叉平衡排序树标准答案：B知识点解析：此题考查的知识点是m阶B一树的定义。B一树是一种平衡的多路排序树，m阶即m叉。应选B。18、若对有18个元素的有序表做二分查找，则查找A[3]的比较序列的下标为()。A、1，2，3B、9，4，2，3C、10，5，3D、9，2，3标准答案：D知识点解析：二分查找判定树如下图所示，查找A[3]的比较序列的下标为9，4，2，3，本题选D。[*42]19、有一个有序表{1，3，9，12，32，41，45，62，75，77，82，95，100}，当用二分查找法查找值为82的结点时，经()次比较后查找成功。A、1B、2C、4D、8标准答案：C知识点解析：n=13，R[11]=82，第1次与R(1+13)／2=7]=45比较，第2次与R(8+13)／2=10]=77比较，第3次与R[(11+13)／2=12]=95比较，第4次与R(10+12)／2=11]=85比较时成功，总共比较4次。20、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，则每块分为()个结点最佳。A、9B、25C、6D、625标准答案：B知识点解析：分块查找时最佳块数为。21、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为()。A、O(n)B、P(log2n)C、O(nlog2n)D、O(n2)标准答案：B知识点解析：有n个结点且为完全二又树的二叉排序树的高度为log2n。22、对包含n个关键码的散列表进行检索，平均检索长度为()。A、O(log2n)B、O(n)C、O(nlog2n)D、不直接依赖于n标准答案：D知识点解析：对散列表进行检索，平均检索长度仅与装填因子α有关，而与关键字个数n无关。23、在散列表上，每个地址单元所链接的同义词表的()。A、键值相同B、元素值相同C、散列地址相同D、含义相同标准答案：C知识点解析：由同义词的定义可知本题答案为C。24、设哈希表长m=14，哈希函数H(key)=keymod11。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用二次探测再散列法处理冲突，则关键字为49的结点的地址是()。A、8B、3C、5D、9标准答案：D知识点解析：addr(49)=49mod11=5，冲突；h1=(5+1*1)mod11=6，仍冲突；h2=(5+2*2)mod11=9，所以本题答案为D。二、综合应用题(本题共19题，每题1.0分，共19分。)25、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。标准答案：根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre(初值为null)和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#definetrue1#definefalse0tvpedefstructnode{datatypedata；structnode*llink，*rlink；}*BTree；voidJudgeBST(BTreet，intflag){／／判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论if(t!=null&&flag){JudgeBST(t一>llink，flag)；／／中序遍历左子树if(pre==null)pre=t；／／中序遍历的第一个结点不必判断elseif(pre一>datadata)pre=t；／／前驱指针指向当前结点elseflag=false；／／不是二叉排序树JudgeBST(t一>rlink，flag)；／／中序遍历右子树}}本题的另一算法是依照定义，二叉排序树的左右子树都是二叉排序树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：intJudgeBST(BTreet){／／判断二叉树t是否是二叉排序树，若是，返回true，否则，返回falseif(t==null)returntrue；if(JudgeBST(t一>llink)&&JudgeBST(t一>rlink)){／／若左右子树均为二叉排序树m=max(t一>llink)；n=min(t->rlink)；／／左子树中最大值和右子树中最小值return(t一>data>m&&t一>datarlink!：null)p=p一>rlink；returnp一>data；}}intmin(BTreeP){／／求二叉树右子树的最小值if(P==null)returnmaxint；／／返回机器最大整数else{while(p一>llink!=null)P=P一>rlink：returnp一>data；}}知识点解析：暂无解析26、某个任务的数据模型可以抽象为给定的k个集合：S1，S2，…，Sk。其中Si(1≤i≤k)中的元素个数不定。在处理数据过程中将会涉及元素的查找和新元素的插入两种操作，查找和插入时用一个二元组(i，x)来规定一个元素，i是集合的序号，x是元素值。设计一种恰当的数据结构来存储这k个集合的元素，并能高效地实现所要求的查找和插入操作。(1)构造数据结构，并且说明选择的理由。(2)若一组数据模型为S1={10．2，1．7，4．8，16．2}，S2={1．7，8．4，0．5}，S3={4．8，4．2，3．6，2．7，5．1，3．9}，待插入的元素二元组为(2，11．2)和(1，5．3)，按你的设计思想画出插入元素前后的数据结构状态。标准答案：借助于分块查找思想，在建立数据顺序表的同时，建立一索引表。数据表中按k个集合分块(元素个数不一定相等)，索引表中有两个域，一是各集合最后一个元素在数据表中的位置(一维数组中的下标)，二是集合的个数(k)。实现数据运算时，根据给定的二元组(i，x)，首先在索引表中找到集合i的位置，然后在数据表中查找x。查到x，则查找成功，返回x在数据表中的位置，否则查找失败。若要插入，则将数据表中的数据后移，插入x，同时修改索引表。typedefstruct{datatypedata；}rectype；typedefstruct{inta[]；／／a数组容量够大，存储各集合最后一个数据在数据表中的下标intk；／／集合个数}index：inISetSearch_Insert(rectypeR[]，indexid，datatypeX，inti){／／数据表R，查找第i个集合的元素X，若查找成功，返回其位置;／／否则将其插入第i个集合if(i<1||i>id．k){printf(”无第％d个集合＼n”，i)；exit(0)：}if(i==1)first=0；／／first指向第i个集合在数据表的首址elsefirst=id．a[i—1]+1；last=id．a[i]；／／last是第i个集合在数据表中的末址for(j=first；jid．A[i]；j--)t／／查找失败，将x插入数据表R[j+1]=R[j]；／／元素后移R[j+1]=x；／／将x插入到原第i个集合最后一个元素之后for(j=i;j≤k；j++)id．a[j]++；／／修改索引表中各集合最后一个元素的下标}由于各集合元素个数不等，各块长度不等且块间无序，索引表中用数组表示，数组中元素值是各集合最后一个元素在数据表中的下标。按本算法插入(2，11．2)和(1，5．3)，数据表前后状态如下：插入前，索引表中a数组的内容是3，6，12，插入后修改为4，8，14。知识点解析：暂无解析27、假设K1,…，Kn是n个关键词，试解答：(1)试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn时，用算法建立一棵以LLINK—RLINK链接表示的二叉查找树。(2)设计一个算法，打印出该二叉查找树的嵌套括号表示结构。假定该二叉查找树的嵌套括号表示结构为B(A，D(C，E))。标准答案：(1)非递归建立二叉排序树，在二叉排序树上插入的结点都是叶子结点。typedefstructnode{Elemtypedata；structnode*LLINK，*RLINK；}node*BiTree：voidCreate_BST(BiTreebst，datatypeK[]，intn){／／以存储在数组K中的n个关键字，建立一棵初始为空的二又排序树inti：BiTreeP，f：for(i=1；i<=n；i++){p=bst：f=null；／／在调用Create_BST时，bst=nullwhile(P!=null)if(P->dataRLINK；}／／f是P的双亲elseif(p一>data>K[i]){f=P；P=p一>LLINK；}S=(BiTree)malloc(sizeof(BiNode))；／／申请结点空间s->data=K[i];s->LLINK=null;s一>RLINK=null；if(f==null)bst：S；／／根结点elseif(S->datadata)f->LLINK=S；／／左子女elsef一>RLINK=s：／／右子树根结点的值大于等于根结点的值}}(2)本题要求输出遍历二叉排序树的嵌套括号表示。其算法思想是，若二叉排序树非空，则输出根结点，再输出其左右子树。在输出其左右子树前，要输出左括号，在输出其右子树前要输出逗号，在输出其右子树后要输出右括号，在左右子树均空情况下，则不输出括号。voidPrint(BiTreet){／／以嵌套括号表示结构打印二叉排序树if(t!=null){printf(t一>data)；／／打印根结点值if(t一>LLINK||t一>LLINK)；／／左子女和右子女中至少有一个不空printf(”(”)；／／输出左括号Print(t一>LLINK)i／／输出左子树的嵌套括号表示if(t一>RLINK)printf(”，”)；／／若右子树不空，输出逗号Print(t一>RLINK)；／／输出右子树的嵌套括号表示printf(”)”)；／／输出右括号}}知识点解析：暂无解析28、写出在二叉排序树中删除一个结点的算法，使删除后仍为二又排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。描述上述算法。标准答案：voidDelete(BSTreet，P){／／在二叉排序树t中，删除f所结点的右孩子(由P所指向)if(P一>lchild==null){f一>rchild=P一>rchild；free(P)；}／／p无左子女else{／／用P左子树中的最大值代替P结点的值q=p一>lchild；s=q；while(q一>rchild){s=q；q=q一>rchild；}／／查P左子树中序序列最右结点if(s==p一>lchild)／／p左子树的根结点无右子女{p一>data=s一>data；p一>lchild=s一>lchild；free(S)；}else{p一>data=q一>data；s一>rchild=q一>lchild；free(q)；}}}知识点解析：暂无解析29、已知二叉树排序树中某结点指针p，其双亲结点指针为fp，p为fp的左孩子。试编写算法，删除p所指结点。标准答案：本题用被删结点右子树中最小值(中序遍历第一个)结点代替被删结点。w)idDelete(BSTreebst，P，fp){／／在二叉排序树bst上，删除fp所指结点的左子女(由P所指向)if(!p一>lchild){fp一>lchild=p一>rchild；free(P)；}／／p无左子女elseif(!p一>rchild){fp一>lchild=p一>lehild；flee(P)；}／／p无右子女else／／P有左子女和右子女{q=P一>rchild；s=q；／／用P右子树中的最小值代替P结点的值while(q一>lchild){S=q；q=q一>lchild；}／／查P右子树中序序列最左结点if(S==p一>rehild)／／p右子树的根结点无左子女{p一>data=s一>data；p一>rchild=s一>rchild；frees)；}else{p一>data=q一>data；s一>lchild=q一>rchild；free(q