2017年哈尔滨工业大学深圳研究生院854计算机基础(含数据结构、计算机组成原理)之数据结构考研强化模拟题
● 摘要
一、选择题
1． 归并排序中，归并的趟数是（ ）。
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数增加一倍。所以
所以归并的趟数为
2． 使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP B.ARP C.UDP D.SMTP 【答案】D 【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
3． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。
4． 循环队列元素数是（ ）。
【答案】A
【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。
和队尾
的概念，在队头进行出队操作，
如果为负则元
可能为正也可能为负，为正时元素个数=
存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的
素的个数=所以统一的公式就是
5． 在任意一棵非空二叉排序树T1中，删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是（ ）
I. 若v 是T1的叶结点，则T1与T3不同 II. 若v 是T1的叶结点，则T1与T3相同 III. 若v 不是T1的叶结点，则T1与T3不同 IV . 若v 不是T1的叶结点，则T1与T3相同 A. 仅 I 、III B .仅 I 、IV C. 仅 II 、III D. 仅 II 、IV 【答案】C
【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。
6． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图
D.G 所有顶点的度的总和为n （n-1） 【答案】A
【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。
7． 假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分，已知别用IEEE754单精度和双精度浮点数格式表示）
位机器中执行下列关系表达式，则结果为“真”的是（ ）。
A. 仅I 和II B. 仅I 和III C. 仅II 和III D. 仅III 和IV 【答案】B
II 中，f 的数据类型从float 【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f时需要对阶，对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。
8． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ , 每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）（ ）
：
A.
B.
C.
D. 【答案】C
【解析】总线带宽=总线工作频率X （总线宽度/8）, 由于地址线与数据线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为所以选C
9． 已知一棵有2011个结点的树，其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115 B.116 C.1895 D.1896 【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点（因为一个非终端结点
若在32
相关内容
相关标签