《数据结构与算法》模拟试卷五
一、名词解释（5*3=15分）
数据结构完全二叉数 AOE网队列拓扑排序
二、填空题（1*16=16分）
1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为
______。
2.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点
的条件是______。
3.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出
栈序列中第30个元素为______。
4.一种抽象数据类型包括______和______两个部分。
5.线性表的链式存储方式中，每个结点包括两个域，分别是______和______ 。
6.在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为
空的条件分别为单链表中______ 和 ______ 。
7.在一棵二叉树中，度为0的结点的个数是10，则度为2的结点个数是_________
8.一个有n个结点的二叉树的深度最大为___________，最小为__________
9.n个定点的连通图至少有_______条边。
10.二分查找的存储结构仅限于________，且是__________
11.在对一组记录(54，38，96，72，60，15，60，45，83)进行直接插入排序时，
当把第6个记录60插入到有序表时，为寻找插入位置需比较________次。
三、选择题（1*10=10分）
1.在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，
则执行 _______。
A、HL=p; p->next=HL;
B、p->next=HL; HL=p;
C、p->next=HL; p=HL;
D、p->next=HL->next; HL->nxet=p;
2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n+1）时，
需要从前向后依次移动_______个元素。
A、n-i
B、n-i+1
C、n-i-1
D、i
3.在一个顺序队列中，队首指针指向队首元素的_______位置。
A、当前
B、后一个
C、前一个
D、后面
4.计算递归函数如不用递归过程通常借助的数据结构是____。
A、线性表
B、双向队列
C、树
D、栈
5.如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的
____。
A、先序排列
B、中序排列
C、后序排列
D、层序排列
6.栈的插入和删除操作在_____进行。
7. A 栈顶 B 栈底 C 任意位置 D 指定位置
8.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径
长度为_____。
A 24
B 71
C 48
D 53
8. 图的广度优先搜索类似于树的_____遍历。
A．先根 B．中根 C. 后根 D．层次
9. 在单链表中插入一个结点，要修改_____个结点的指针域。
A 1
B 2
C 3
D 4
10.二叉树有_____种基本形态。
A 2
B 3
C 4
D 5
四、计算和应用题（共21分）
1、假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。
2
12.R 13.48 14.70 15.33 16.65 17.24 18.56 19.12 20.92
写出在将它调整为大根堆的过程中每一次筛选后R的状态。
3、已知一组关键字为（19，14，23，1，68，20，27，83，99），试按哈希函数H(key) = key Mod 7和链地址法处理冲突构造哈希表
（同一链表中关键字按自小到大排列）。
五、算法填空（2*9=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) ;
(5) ;
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.key<r[mid].key)high=mid-1;
else (2) ;
}
for(i=*n; (3) ;i--)
r[i+1]=r[i];
(4) ;
*n++;
}
(1)
(2)
(3)
(4)
六、算法设计题（2*10=20分）
1.试写一个算法，逆置带头结点的单链表 L
2.给出二叉树的二叉链表存储结构，编写递归算法，计算二叉树中的叶子结点个
数。