《数据结构与算法》模拟试卷四
一、名词解释（5*3=15分）
数据结构 满二叉树 栈 哈夫曼树 拓扑排序 二、 填空题（1*16=16分）
1. 在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为
______。
2. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结
点的条件是_____。
3. 如果入栈序列是1，3，5，„，97，99，且出栈序列的第一个元素为99，则
出栈序列中第30个元素为______。
4. 根据数据元素之间关系的不同特性，通常有下列四类基本结构：_____、
_____、 _____、_____ 。
5. 数据元素之间的关系在计算机中可用顺序映像和非顺序映像表示，由此得到
两种存储结构是：_____ 、_____。 6. 线性表的链式存储方式中，每个结点包括两个域，分别是：_____ 和 _____ 。 7. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表
为空的条件分别为 _____和 _____ 。
8. 一棵高度为5的二叉树中最少含有_____个结点，最多含有_____个结点； 9. 在对一组记录(54，38，96，72，60，15，60，45，83)进行直接插入排序时，
当把第6个记录60插入到有序表时，为寻找插入位置需比较________次。 三、选择题（10*1=10分）
1. 对线性表进行折半查找最方便的存储结构是_____。
A、顺序表 B、有序的顺序表 C、链表 D、有序的链表 2. 计算递归函数如不用递归过程通常借助的数据结构是_____。 A、线性表 B、双向队列 C、树 D、栈
3. 如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的
_____。
A、先序排列 B、中序排列 C、后序排列 D、层序排列 4. n个结点的线索二叉树中线索的数目为_____。
A、(n-1)个 B、n个 C、（n+1）个 D、(n+2)个 5. 设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，
则判定Q为空队列的条件是_____。 A.(rear-front)%m= =1 B.front= =rear
C.(rear-front)%m= =m-1 D.front= =(rear+1)%m
6. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结
点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在_____。 A.BT[i/2] B.BT[2*i-1] C.BT[2*i] D.BT[2*i+1] 7. 连通图是指图中任意两个顶点之间_____。
A.都连通的无向图 B.都不连通的无向图 C.都连通的有向图 D.都不连通的有向图
8. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平
均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为_____。
A n B n/2 C (n+1)/2 D (n-1)/2
9. 若一个栈的输入序列是1，2，3，4，„，n，输出序列的第一个元素是n，
则第i个输出元素是_____。
A 不确定 B n-i C n-i+1 D n-i-1 10. 在单链表中插入一个结点，要修改____个结点的指针域。
A 1 B 2 C 3 D 4 四、计算和应用题（共21分）
1. 已知一二叉树先序遍历顺序为 ABDCEGHIJF，中序为 DBAGEIJHCF，试构造该
二叉树。 2. 证明：具有n个结点的完全二叉树的深度为log2n1 。
3. 待排序关键字（34,12,28,45,66,7,3,21），写出快速排序的第一趟快排过
程。 五、算法阅读题（9*2=18分）
1. 如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,
每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。
int EnQueue(CirQueue *Q,DataType x){ if( (1) ) return 0; Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)% MAXQSIZE
(2) return 1; }
int DeQueue(CirQueue *Q,DataType *x){ if( (3) ) return 0; *x=Q->data[Q->front]; Q->front= (4) ; ;
return 1; } (1) (2) (3)
(4) (5)
2. 下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，
其中参数*n为表r的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。
void BinInsert(SeqList r,int *n,DataType x) { int low=1,high=*n,mid,i; while(low<=high) { mid= (1) ;
if (x.keyfor(i=*n; (3) ;i--) r[i+1]=r[i]; (4) ; *n++; } (1) (2) (3) (4) 六、算法设计题（2*10=20分）1. 试写一个算法，逆置带头结点的单链表 L。
2. 编写递归算法，将二叉树中所有结点的左右子树相互交换。