2017年山东师范大学信息科学与工程学院914数据结构B[专业硕士]考研导师圈点必考题汇编
● 摘要
一、填空题
1． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
2． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
3． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
4． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
5． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ） { if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;
if （node->rflag）（3）; else {do t=*x；; while （*x==node ）; *x=t;
} }
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
6． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
7． 表达式
【答案】
8． 设广义表
则
的后缀表达式是_____。
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
9． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
10．二进制地址为011011110000，大小为
【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为式如下：
当大小为4时，起始地址
为
当大小为16时，起始地址为
：和
其伙伴块的起始地址计算公
和
块的伙伴地址分别为：_____
二、算法设计题
11．写出一趟快速排序算法。
【答案】算法如下：
12．对给定关键字序号
要求在无序记录
中找到关键字从小到大排在第j 位上的记
录，写一个算法利用快速排序的划分思想实现上述查找（要求用最少的时间和最少的空间）。
例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下：
13．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如：
第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：
1，4，7……第一个数组
9，12，28，29，45……第二个数组 【答案】算法如下：