《2018年江苏省培养单位南京天文光学技术研究所864程序设计之数据结构考研强化五套模拟题.doc》由会员分享，可在线阅读，更多相关《2018年江苏省培养单位南京天文光学技术研究所864程序设计之数据结构考研强化五套模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2018年江苏省培养单位南京天文光学技术研究所864程序设计之数据结构考研强化五套模拟题-一、单项选择题1 关键路径是AOE 网中（ ）。A. 从始点到终点的最短路径B. 从始点到终点的最长路径C. 从始点到终点的边数最多的路径D. 从始点到终点的边数最少的路径【答案】B【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目) 。路径长度最长的路径称作关键路径(critical path)。 2 下列介质访问控制方法中, 可能发生冲突的是（ ）A.CDMAB.CSMAC.TDMA
2、CD.FDMA【答案】B【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。 3 下列关于USB 总线特性的描述中, 错误的是（ ）。A. 可实现外设的即插即用和热插拔B. 可通过级联方式连接多台外设C. 是一种通信总线, 可连接不同外设D. 同时可传输2位数据, 数据传输率高【答案】D 。【解析】USB 总线即通用串行总线, 它的特点有:(1)即插即用; (2)热插拔; (3)有很强的链接能力能将所有外设链接起来, 且不损失带宽;(4)有很好的可扩展性; (5)高速传输, 速度可达480Mbps 。所有A , B , C 都符合USB 总线的特点。对于选项D , USB
3、是串行总线, 不能同时传输两位数据, 所以答案为D 。 4 已知一算术表达式的中缀表达式为a (bc/d)*e，其后缀形式为（ ）。 A.B.C.D.【答案】D【解析】后缀表达式:在程序语言中，运算符位于两个操作数后面的表达式。 5 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。 图 有向带权图A.d , e , fB.e , d , fC.f , d , eD.f , e , d【答案】C 。【解析】本题主要考查
4、Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。 6 已知序列25, 13, 10, 12, 9是大根堆, 在序列尾部插入新元素18, 将其再调整为大根堆, 调整过程中元素之间进行的比较次数是（ ）。A.1B.2C.4D.5【答案】B【解析】对堆插入或删除一个元素, 有可能不满足堆的性质, 堆被破坏, 需要调整为新堆。(1)为原堆,(2)为插入18后,(3)比较10与18, 交换后,(4)比较25与18, 不交换, 即为调整后的新的大根堆。因此调整过程中元素之间进行的比较次
5、数为2。 7 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是 （ ）A.27B.46C.54D.56【答案】B【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为 8 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）A.2B.3 C.4D.5【答案】B【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B , 分为3组:9, 13, 20; 1, 7, 23; 4, 8, 15都是升序有序, 所以B 正确 -一、单项选择题-考研试题-
