2017年中国地质大学(武汉)计算机学院952软件综合之数据结构考研仿真模拟题
● 摘要
目录
2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研仿真模拟题（一） ... 2 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研仿真模拟题（二） . 12 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研仿真模拟题（三） . 22 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研仿真模拟题（四） . 34 2017年中国地质大学（武汉）计算机学院952软件综合之数据结构考研仿真模拟题（五） . 46
第 1 页，共 56 页
一、填空题
1． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
2． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
3． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
4． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
5． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
6． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
7． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
8． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
第 2 页，共 56 页
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
，
则结点
和在同一层上的条件是
。
9． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为 10．深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
11．组成串的数据元素只能是_____。
【答案】字符
12．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
二、选择题
13．为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。
A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储
第 3 页，共 56 页
【答案】A
【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。
14．哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数 B. 除余法中的质数 C. 冲突处理
D. 哈希函数和冲突处理 【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
15．已知广义表
用
和数取出LS 中原子e 的运算是（ ）。
【答案】C 【解析】
操作就是得到广义表中第一个的原子。
得
到得到e 。
16．n 个结点的正则二叉树中有每个结点的度或者为0或者为2的二叉树称为正则二叉树。（ ）个叶子。
【答案】D
【解析】二叉树结点总数
分别代表度为0，度为1，度为2的结点数）。
因
此
又在非空二叉树中
：且本题所给树为正则二叉树
，所
以
17．使用浏览器访问某大学Web 网站主页时，不可能使用的协议是（ ）
A.PPP B.ARP C.UDP D.SMTP 【答案】D
【解析】SMTP 是简单邮件传输协议，访问主页时并不涉及邮件相关协议。
操作就是得到除第一个原子外剩下元得
到
得
到
素构成的表
。
第 4 页，共 56 页