2018年湖南师范大学数学与计算机科学学院865数据结构考研强化五套模拟题
● 摘要
一、判断题
1． 在任何情况下，归并排序都比简单插入排序快。（ ）
【答案】×
【解析】错误。待排序序列为正序时，简单插入排序比归并排序快。
2． 设模式串的长度为m ，目标串的长度为n ，当n ≈m 且处理只匹配一次的模式时，朴素的匹配(即子串定位函数) 算法所花的时间代价可能会更为节省。（ ）
【答案】 √
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
3． 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
【答案】 ×
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
4． 基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
5． 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）
【答案】 ×
【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。
6． 串长度是指串中不同字符的个数。（ ）
【答案】 ×
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
二、填空题
7． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。
【答案】A[2][3]
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。
8． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
9． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
11．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为
其中:left 指向其左孩子，
【答案】
left 指向其前驱；，right 指向其后继。
， right 指向其右孩子，，，
12．当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
三、单项选择题
13．下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）
A. 仅1
B. 仅2
C. 仅1, 2
D. 仅2, 3
【答案】C
【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响
14．计算机算法指的是解决问题的步骤序列，它必须具备（ ）三个特性。
A. 可执行性、可移植性、可扩充性
B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
【答案】B
【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，或者说，算法是对计算机上执行的计算过程的具体描述，也就是解决问题的步骤序列。一个算法通常需要具备五大特性:有穷性；确定性；可执行性；输入一个算法有零个或多个输入；输出一个算法有零个或者多个输出。
15．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后, 先处理较长的分区可以减少递归次数
C. 每次划分后, 先处理较短的分区可以减少递归次数
D. 递归次数与每次划分后得到的分区的处理顺序无关
【答案】D
【解析】快速排序是递归的, 递归过程可用一棵二叉树给出, 递归调用层次数与二叉树的深度一致。例如:待排序列{48, 62, 35, 77, 55, 14, 35, 98) , 采用快速排序方法, 其对应递归调用过程的二叉树如下图所示。