2017年山东师范大学信息科学与工程学院836数据结构A考研仿真模拟题
● 摘要
一、填空题
1． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
2． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
3． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
5． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
6． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
7． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
第 2 页，共 37 页
其中
队头和队尾指针分别为front 和rear , 则此循
8． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
9． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
10．循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
二、算法设计题
11．已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA （P ，q ）, 该算法寻找结点 P 的父亲结点q ，设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG , LLINK , INFO , RL1NK , RTAG ）, 且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下：
在中序线索树t 上，求结点p 的双亲结点q
{q=p; //暂存
//找P 的中序最右下的结点
//顺右线索找到q 的后继（P 的袓先结点）
//若后继是头结点，则转到根结点
根结点无双亲
}//找最右结点的过程中回找到
P
第 3 页，共 37 页
//准备到左子树中找
P
12．设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。
【答案】算法如下：
//将满二叉树的后序序列转为前序序列，11、hl 、12、h2是序列初始和最后结点的下标。
//根结点
//左子树或右子树的结点数
//将左子树前序序列转为
后序序列
后序序列
13．设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下：
构造的哈希表如图所示：
//将右子树前序序列转为
第 4 页，共 37 页