山东大学20年春季《数据结构》（ C 卷）辅导
《数据结构》模拟卷一、单项选择题
1．数据结构是（ ）。
A．一种数据类型
B．数据的存储结构
C．一组性质相同的数据元素的集合
D．相互之间存在一种或多种特定关系的数据元素的集合
2．算法分析的目的是（ ）。
A．辨别数据结构的合理性
B．评价算法的效率
C．研究算法中输入与输出的关系
D．鉴别算法的可读性
3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。
A．插入 B．删除
C．排序 D．定位
4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。
A．3，2，6，1，4，5 B．3，4，2，1，6，5
C．1，2，5，3，4，6 D．5，6，4，2，3，1
5．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。
A．15 B．16
C．17 D．18
6．二维数组A按行优先顺序存储，若数组元素A的存储地址为1087，A的存储地址为1153，则数组元素A的存储地址为（ ）。
A．1207 B．1209
C．1211 D．1213
7．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ）。
A．队列 B．栈
C．线性表 D．有序表
8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ ）。
A．不一定相同 B．都相同
C．都不相同 D．互为逆序
9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ ）。
A．层次遍历算法 B．前序遍历算法
C．中序遍历算法 D．后序遍历算法
10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）。
A．图中每个顶点的入度 B．图中每个顶点的出度
C．图中弧的条数 D．图中连通分量的数目
11．图的邻接矩阵表示法适用于表示（ ）。
A．无向图 B．有向图
C．稠密图 D．稀疏图
12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（ ）。
A．i B．i+1
C．n-i D．n-i+1
二、填空题
1．栈是_______的线性表，其运算遵循_______的原则。
2．_______是限定仅在表尾进行插入或删除操作的线性表。
3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。
4．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。
5．在二叉树中，指针p所指结点为叶子结点的条件是______。
6．具有256个结点的完全二叉树的深度为______。
7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。
8．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。
9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。
10．不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。
三、解答题
1．某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。
2．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。
（1）画出该二叉树；
（2）画出与（1）求得的二叉树对应的森林。
3．已知带权图的邻接表如下所示，其中边表结点的结构为：
依此邻接表从顶点C出发进行深度优先遍历。
（1）画出由此得到的深度优先生成树；
（2）写出遍历过程中得到的从顶点C到其它各顶点的带权路径及其长度。
参考答案：
1.
2.
(1)
(2)
3.
(1)
(2)
顶点C到顶点A的带权路径为（C,D,B,A），其长度为8+20+11=39
顶点C到顶点B的带权路径为（C,D,B），其长度为8+20=28
顶点C到顶点D的带权路径为（C,D），其长度为8
顶点C到顶点E的带权路径为（C,D,B,F,E），其长度为8+20+9+14=51
顶点C到顶点F的带权路径为（C,D,B,F），其长度为8+20+9=37
四、算法设计题
1．已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的
一个叶子结点插入进去，并使之成为TT的右子树的（中序序列）第一个结点（同时要修改
相应的线索关系）。
2．写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。
参考答案：
1.答案：[题目分析]若使新插入的叶子结点S成T右子树中序序列的第一个结点，则应在T的右子树中最左面的结点（设为p）处插入，使S成为结点p的左子女。则S的前驱是T，后继是p.
void ThrTreeInsert(BiThrTree T,S)
//在中序线索二叉树T的右子树上插入结点S，使S成为T右子树中序遍历第一个结点
{p=T->rchild; //用p去指向T的右子树中最左面的结点
while(p->ltag==0) p=p->lchild;
S->ltag=1;S->rtag=1; //S是叶子，其左右标记均为1
S->lchild=T;S->rchild=p;//S的前驱是根结点T，后继是结点p
p->lchild=S;p->ltag=0;//将p的左子女指向S ，并修改左标志为0
}//结束 ThrTreeInsert
2．答案：[题目分析]在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，结点p在中序和后序下均无前驱。
BiThrTree InPostPre (BiThrTree t,p)
//在中序线索二叉树t中，求指定结点p在后序下的前驱结点q
{BiThrTree q;
if (p->rtag==0) q=p->rchild; //若p有右子女，则右子女是其后序前驱
else if (p->ltag==0) q=p->lchild;//若p无右子女而有左子女，左子女是其后序前驱。
elseif(p->lchild==null) q=null;//p是中序序列第一结点，无后序前驱
else //顺左线索向上找p的祖先，若存在，再找祖先的左子女
{while(p->ltag==1 && p->lchild!=null) p=p->lchild;
if(p->ltag==0) q=p->lchild;//p结点的祖先的左子女是其后序前驱
elseq=null; //仅右单枝树（p是叶子），已上到根结点，p结点无后序前驱
}
return(q); }//结束InPostPre
页:
[1]