2017年湖北大学数学与计算机科学学院811数据结构考研仿真模拟题
● 摘要
一、填空题
1． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
2． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
4． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
5． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。
【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
6． 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
7． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
8． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
9． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
10．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
的地址是：_____。
二、选择题
11．
已知操作符包括
的后缀表达式
将中缀表达式转换为等价
时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为
空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
A.5 B.7 C.8 D.11
【答案】A 。
【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）
。表达式所列：
产生后缀表达式的过程如下表
通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。
12．Cache 有4个行，Cache 和主存之间交换的块大小为1个字。假设某计算机按字编址，若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1