2017年山东师范大学管理科学与工程学院836数据结构A考研仿真模拟题
● 摘要
一、填空题
1． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
2． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
3． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
4． 设二维数组A 的行和列的下标范围分别为
【答案】
当其值为
和
每个元素占2个单元，按行优先顺处的元素为_____。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
时，则i=2，j=3。
5． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。 6． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
7． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
8． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
9． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】视哨。
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监
二、算法设计题
11．设计将数组
中所有的偶数移到奇数之前的算法。要求不增加存储空间，
且时间复杂性为
【答案】算法如下：
12．设从键盘输入一整数的序列：当
﹣1时，将入找；当【答案】算法如下：
相应的信息。
试编写算法实现：用栈结构存储输入的整数，
时，输出栈顶整数并出找。算法应对异常情况（入栈满等）给出
13．已知顺序表中有m 个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到
【答案】算法如下：
14．写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag ，lc ，data ，rC ，rtag ）。其中，data 存放结点的值；lc 、rc 为指向左、右孩子或该结点前驱、 后继的指针，ltag 、rtag 为标志域，若值为0，则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其 前驱、后继结点的指针。
【答案】算法如下：
//先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在
//设P 指向二叉树的根结点
结束
InOrder
//在中序线索二叉树T 中，求给定值为X 的结点的
后继结点
//首先在T 树上査找给定值为X 的结点，由p 指向
/ /若P 的右标志为1, 则P 的rc 指针指向其后继
//结点P 的右子树中最左边的结点是结点P 的中序后继 }//结束 AfterXnode.