2018年广西师范学院计算机与信息工程学院818计算机基础之数据结构考研核心题库
● 摘要
一、单项选择题
1． 从堆中删除一个元素的时间复杂度为（ ）。
A.O(1) B.
C.O(n) D.
【答案】B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
2． 下列选项中，不属于网络体系结构中所描述的内容是（ ）.
A. 网络的层次
B. 每一层使用的协议
C. 协议的内部实现细节
D. 每一层必须完成的功能
【答案】C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C.
3． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历
B. 中序遍历
C. 后序遍历
【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
4． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
。
C. (1)和(2)
D.(1)和(3)
【答案】A
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”的反例如下图2所示
.
图
1
图2
, 采用4级指令流水线, 每个段的执行需要1个时钟周期。假定CPU 5． 某CPU 主频为
A.
B.
C.
D.
【答案】C 条指令/秒 条指令/秒 条指令/秒 条指令/秒 执行了100条指令, 在其执行过程中没有发生任何流水线阻塞, 此时流水线的吞吐率为（ ） 【解析】采用4级流水线执行100条指令, 在执行过程中共用
CPU 的主频是, 也就是说每秒钟有
条指令/秒,
故答案为C 。
6． 对进行基数排序，一趟排序的结果是:（ ）
A. 05， 46， 13， 55， 94， 17， 42 B.
C. 42，13， 94，05， 55， 46，17
D. 05，13， 46，55，17，42，94
【答案】C
【解析】基数排序有两种:最低位优先和最高位优先。
①最低位优先的过程 个时钟周期。 个时钟周期。流水线的吞吐率为
先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完
成了基数排序的整个过程。
②以r 为基数的最低位优先排序的过程 假设线性表由结点序列
成，
其中
分配:开始时，把
收集:把构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:
表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。
线性表。
7． 已知一棵有2011个结点的树, 其叶结点个数为116, 该树对应的二叉树中无右孩子的结点个数是（ ）。
A.115
B.116
C.1895
D.1896
【答案】D
【解析】每个非终端结点转换成二叉树后都对应一个无右孩子的结点(因为一个非终端结点至少有一个孩子结点, 其最右边的孩子结点转换成二叉树后一定没有右孩子) , 另外, 树根结点转换成二叉树后也没有右孩子。题目中树的总结点数是2011, 叶结点个数是116, 则非终端结点个数是2011-116=1895, 则该树对应的二叉树中无右孩子的结点个数是1895+1=1896。
8． 某计算机存储器按字节编址, 主存地址空间大小为64MB ,
现用位的RAM 芯片组成32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。
A.22位
B.23位
C.25位
D.26位
【答案】D
【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
9． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有（ ）个叶子。 A.
相关内容
相关标签