2018年杭州电子科技大学计算机学院851数据结构考研强化五套模拟题
● 摘要
一、是非题
1． 若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而釆用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
2． 负载因子(装填因子) 是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素:哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
3． 堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，排序树，更不会是平衡二叉树。
可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉
4． 直接访问文件也能顺序访问，只是一般效率不高。（ ）
【答案】×
【解析】直接访问文件不能进行顺序访问，只能按关键字随机存取。在ISAM 文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止。
5． 外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（ ）
【答案】×
【解析】外部排序方法:按可用内存大小，将外存上含n 个记录的文件分成若干长度为2的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存，通常称这些有序子文件为归并段或顺串(run)。对这些归并段进行逐趟归并，使归并段(有序的子文件) 逐渐由小至大，直至得到整个有序文件为止。一般情况下，外部排序所需总的时间=内部排序(产生初始归并段) 所需的时间m*tIS+外存信息读写的时间
第 2 页，共 59 页 内部归并所
需的时间。
6． 哈夫曼树无左右子树之分。（ ）
【答案】×
【解析】哈夫曼树就是一棵二叉树。
二、单项选择题
7． 在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
【答案】C 。
【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案是C 。
8． 设无向图的顶点个数为m 则该图最多有（ ）条边。
A.n-1 B. C.
D.0E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为。
9． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB , 采用页式存储管理, 页面大小为4KB , TLB(快表) 采用全相联映射, 有4个页表项, 内容如下表所示。
则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ）
A.0153180H
B.0035180H
第 3 页，共 59 页
C.TLB 缺失
D. 缺页
【答案】A
【解析】虚拟地址为03FFF180H , 其中页号为03FFFH , 页内地址为180H , 根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H ,
页框号与页内地址之和即为物理地址
。
10．链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
【答案】B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
11．在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.
C.1 D.
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。
12．若无向图
是（ ）。
A.6
B.15
C.16
D.21
【答案】C
【解析】要保证无向图G 在任何情况下都是连通的, 即任意变动图G 中的边, G 始终保持连通。首先需要图G 的任意6个结点构成完全连通子图
再添加一条边将第7个结点与, 需条边, 然后连接起来, 共需16条边。本题非常容易错误地选择选项A , 主要原中含7个顶点, 则保证图G 在任何情况下都是连通的, 则需要的边数最少因是对“保证图G 在任何情况下都是连通的”的理解, 分析选项A , 在图G 中, 具有7个顶点6条边并不能保证其一定是连通图, 即有n-1条边的图不一定是连通图。分析选项D , 图G 有7个顶点21条边, 那么图G 一定是无向完全图, 无向完全图能保证其在任何情况下都是连通的, 但是这不符
第 4 页，共 59 页