2017年山东师范大学管理科学与工程学院836数据结构A考研题库
● 摘要
一、填空题
1． 中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
2． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
3． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
4． 设有个结点的完全二叉树顺序存放在向量
【答案】
中，其下标值最大的分支结点为_____。
对应的前缀式为_____，若
则后缀式
的
【解析】最大的分支结点是最后一个叶子结点的父结点。
5． 建立索引文件的目的是_____。
【答案】提高查找速度
6． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
7． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
8． 设二维数组A 的行和列的下标范围分别为
【答案】时，则i=2，j=3。
9
和每个元素占2个单元，按行优先顺处的元素为_____。
当其值为
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
．
求REPLACE （S ，V , m ）=_____。
已
知
【答案】
10．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
二、算法设计题
11．写出算法，求出中序线索二叉树中给定值为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.
12．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
【答案】（1）递归算法如下：
（2）非递归算法如下：
13．设计将数组
中所有的偶数移到奇数之前的算法。要求不增加存储空间，
且时间复杂性为
【答案】算法如下：
14．设排序二叉树中结点的结构为下述三个域构成：
给出结点数据的值；
点的地址。设序，实现将
给出本结点的左儿子结点的地址；
给出本结点的右儿子结
域为正整数，该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程域之值小于等于x 的结点全部删除掉。
【答案】算法如下：