《计算机专业基础综合历年真题试卷汇编2_真题无答案.pdf》由会员分享，可在线阅读，更多相关《计算机专业基础综合历年真题试卷汇编2_真题无答案.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！5.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是_。SSS_SINGLE_SEL A b，c，a，b，d，e，g，f B e，a，f，g，b，h，c，d C d，b，c，a，h，e，f，g D a，b，c，d，h，e，f，g 6.设有向图 G=(V，E)，顶点集 V=V 0，V 1，V 2，V 3)，边集 E=v 0，v 1，v 0，v 2，v 0，v 3，v 1，v 3。若从顶点 V 0
2、开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是_。SSS_SINGLE_SEL A 2 B 3 C 4 D 5 7.下列关于最小生成树的叙述中，正确的是_。最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同 SSS_SINGLE_SEL A 仅 B 仅 C 仅、D 仅、8.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是_。SSS_S
3、INGLE_SEL A (V 1，V 3)B (V 1，V 4)C (V 2，V 3)D 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！(V 3，V 4)9.对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各项点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是_。SSS_SINGLE_SEL A d，e，f B e，d，f C f，d，e D f，e，d 10.对下图进行拓扑排序，可以得到不同拓扑序列的个数是_。SSS_SINGLE_SEL
4、A 4 B 3 C 2 D 1 11.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是_。SSS_SINGLE_SEL A 存在，且唯一 B 存在，且不唯一 C 存在，可能不唯一 D 无法确定是否存在 12.对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是()。SSS_SINGLE_SEL A 3，1，2，4，5，6 B 3，1，2，4，6，5 C 3，1，4，2，5，6 D 3，1，4，2，6，5 13.下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是_。SSS
5、_SINGLE_SEL 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！A c 和 e B d 和 c C f 和 d D f 和 h 14.已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多的是_。SSS_SINGLE_SEL A 4 B 5 C 6 D 7 15.下列选项中，不能构成折半查找中关键字比较序列的是_。SSS_SINGLE_SEL A 500，200，450，180 B 500，450，200，180 C 180，500，200，450 D 180，200
6、，500，450 2.综合应用题 综合应用题 41-47 小题。1.已知有 6 个顶点(顶点编号为 05)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：1)写出图 G 的邻接矩阵 A。2)画出有向带权图 G。SSS_TEXT_QUSTI 已知含有 5 个顶点的图 G 如下图所示。请回答下列问题：SSS_TEXT_QUSTI 2.写出图 G 的邻接矩阵 A(行、列下标从 0 开始)。SSS_TEXT_QUSTI 3.求 A 2，矩阵 A 2 中位于 0 行 3 列元素值的含义是什么?欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除
7、！我们将竭诚为您提供优质的文档！SSS_TEXT_QUSTI 4.若已知具有 n(n2)个顶点的图的邻接矩阵为 B，则 B m(2mn)中非零元素的含义是什么?某网络中的路由器运行 OSPF 路由协议，表 5-1 是路由器 R1 维护的主要链路状态信息(LSI)，图 5-3 是根据表 5-1 及 R1 的接口名构造出来的网络拓扑。请回答下列问题：SSS_TEXT_QUSTI 5.本题中的网络可抽象为数据结构中的哪种逻辑结构?SSS_TEXT_QUSTI 6.针对表 5-1 中的内容，设计合理的链式存储结构，以保存表 5-1 中的链路状态信息(LSI)。要求给出链式存储结构的数据类型定义，并画出
8、对应表 5-1 的链式存储结构示意图(示意图中可仅以 ID 标识结点)。SSS_TEXT_QUSTI 7.按照迪杰斯特拉(Dijkstra)算法的策略，依次给出 R1 到达图 5-3 中子网1921xx 的最短路径及费用。8.带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决的方法：设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v；重复步骤，直到 u 是目标顶点时为止。请问上述方法能否求得最
9、短路径?若该方法可行，请证明之；否则，请举例说明。SSS_TEXT_QUSTI 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！已知有 6 个顶点(项点编号为 05)的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。要求：SSS_TEXT_QUSTI 9.写出图 G 的邻接矩阵 A。SSS_TEXT_QUSTI 10.画出有向带权图 G。SSS_TEXT_QUSTI 11.求图 G 的关键路径，并计算该关键路径的长度。一个长度为 L(L1)的升序序列 S，处在第个位置的数称为 s 的中位数。例如，若序列 S
10、1=(11，13，15，17，19)，则 Sl 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2=(2，4，6，8，20)，则 Sl 和 S2 的中位数是 11。现有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：SSS_TEXT_QUSTI 12.给出算法的基本设计思想。SSS_TEXT_QUSTI 13.根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。SSS_TEXT_QUSTI 14.说明你所设计算法的时间复杂度和空间复杂度。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！1