文档介绍：数据结构与算法分析一期末复习题及答案。。
单选题(每题2分，共20分)对一个算法的评价，不包括如下(B)方面的内容。
•荏茜为亲结点白灌链表HL中，要向表头插入一个由指针p偏向的络点，贝=p->adjvex;if(!visited[j])(cout<<j<<'';visited[j]=true;QInsert(Q,j);
}p=p->next;}}五、}算法填空(共8分)如下为二分查找的非递归算法，试将其填写完整。
IntBinsch(ElemTypeA[],intn,KeyTypeK)(
intlow=0;
inthigh=n-1;
while(low<=high)(intmid=_;口]£*==returnmid;//查我成功，返elseif(K<[mid].key);//else〃在右子表上继续查return-1;〃查找失败，返回-1六、乂—编写算祥(共8分)土―一、HL是单链表的头指针，试写出删除头结点的算法。
ElemTypeDeleFront(LNode*&HL)参考答案
6
5
5
1
5
1
3
2
-
1
快速
1.
7.
有序
n-1
2.
8.
有序序列
后缀表达式
式）
3.
9.
2nn-1
n+1
4.
10.
2i+1
2i+2
5.
11.
开放定址法
链接法
(i-1)/2
（或逆波兰
.
.
分)
(1)
归并
运算题(每题6分，共24分)
((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7
))(3
(z
5U
图8
(2)
2.
3.
BFS:
4.
三兀组线性表的顺序存储表示如图7示。
如图8所示。
四、
DFS:
GL所表示的图。
三、五、
（low+high）/2low=mid+1
算法填空（8分）
high=mid-1
四、六、
编写算法（8分）
接表
拓朴排序为：4365721
阅读算法（每题7分，共14分）1.（1）判断n是否是素数（或质数）（2）O（仆）：从初始点Vi出发广度优先搜索由邻ElemTypeDeleFront（LNode*&HL）（if（HL==NULL）（cerr<<"空表"<<endl;exit（1）;}
LNode*p=HL;
HL=HL->next;
ElemTypetemp=p->data;
deletep;returntemp;}单选题（每题2分，共20分）栈和依列的共同宇寺点是（/）。
只充并茬端点处措入和丽除兀彖都是先进后出都是先进先出D展百共同、一…用链接万式存储的队列，在进行插入运算时（D）.
*,、尾搭针都要修改』“腿」、尾指针可能都要修改以下数据结构中哪一个是非线性结构？（D）[m][n],假设也0][0]存放位置在644（10）,A[2][2]存放位置在676（10）,每个元"一个空间，问A[3][3]（10）存放在什么位置？脚注（1。）表示用10进制表示。（C）。
°元素之二叉树的第k层的结点数最多为（D）.
2仁1
-1
+1
-1
D.
若有18个元素的汀序表您近隹鬼组a[19]\现进行二分查曲则查我a「a:D)
—…个兀素放A[1]中，序列的下标依次为(,2,，若选
中,第一]的比较
,5,2,,4,2,364,46^20,10）进行作为散列函数，则散初
对于线性表(7,34,55,25,散列存储谛？若选用H(K)=K%9地址为1的元素有(D)个，"亩景勺无向图，该图至少应有(A能确保是一个连值图。：正确性强壮性高效率
)条边才
易读性
(n3+n2log2n+14n)/n2,其数量级表示为O(n)若理链善倒？丁棵盘约迎知每个黄点阕狒密、一台左盘工布去传工质沔个指针。在这种存储结利代[
个指缶桢*其中*_n-1_个指针域
gy箫普吨啷纣
后缀算式923+-102/-的值为-1。中缀算式(3+4X)-2Y/3对应的后缀算式为_34X^+2^*3/-。
…-还有指向左孩子和右孩子的两个指针。
2n斤+