2017年中国地质大学(武汉)计算机学院952软件综合之数据结构考研强化模拟题
● 摘要
目录
2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研强化模拟题（一）.... 2 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研强化模拟题（二）.. 11 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研强化模拟题（三）.. 21 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研强化模拟题（四）.. 32 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研强化模拟题（五）.. 44
第 1 页，共 53 页
一、填空题
1． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
2． 建立索引文件的目的是_____。
【答案】提高查找速度
3． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
4． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
5． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
6． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
7． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
8． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素为_____。
【答案】9174；8788
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为
第 2 页，共 53 页
的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
若以列序为主存储顺序，则它的存储地址为
9． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
10．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
11．阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
12．对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
二、选择题
13．Cache 有4个行，Cache 和主存之间交换的块大小为1个字。假设某计算机按字编址，若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1 B.2 C.3 D.4
第 3 页，共 53 页
【答案】C 。
【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。
14．对序
列用希尔排序方法排序，经一趟后序列变
为
则该次采用的增量是（ ）。
A.1
B.4 C.3 D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。
15．下列因素中，不会影响信道数据传输速率的是（ ）
A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度 【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
16．若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，则在B 中确定
的位置k 的关系为（ ）。
【答案】B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为
中，当
时，i 与k 的关系为
对n 阶对称矩阵
A
以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
17．下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法 B. 短进程优先调度算法 C. 先来先服务调度算法 D. 尚响应比优先调度算法 【答案】D
第 4 页，共 53 页