数据结构期末考试复习总结DOCWord格式.docx
《数据结构期末考试复习总结DOCWord格式.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试复习总结DOCWord格式.docx（31页珍藏版）》请在冰点文库上搜索。
4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。
见图12
图12
图11
四、阅读算法（每题7分，共14分）
1.LinkListmynote（LinkListL）
{//L是不带头结点的单链表的头指针
if（L&
&
L->
next）{
q=L；
L=L－>
next；
p=L；
S1：
while（p－>
next）p=p－>
S2：
p－>
next=q；
q－>
next=NULL；
}
returnL；
请回答下列问题：
（1）说明语句S1的功能；
查询链表的尾结点
（2）说明语句组S2的功能；
将第一个结点链接到链表的尾部，作为新的尾结点
（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。
返回的线性表为（a2,a3,…,an,a1）
2.voidABC（BTNode*BT）
{
ifBT{
ABC（BT->
left）;
right）;
cout<
<
BT->
data<
'
;
该算法的功能是：
递归地后序遍历链式存储的二叉树
五、算法填空（共8分）
二叉搜索树的查找——递归算法:
boolFind（BTreeNode*BST,ElemType&
item）
if（BST==NULL）
returnfalse;
//查找失败
else{
if（item==BST->
data）{
item=BST->
data;
//查找成功
return__true__;
elseif（item<
BST->
data）
returnFind（___BST->
left__,item）;
elsereturnFind（____BST->
right__,item）;
}//if
六、编写算法（共8分）
统计出单链表HL中结点的值等于给定值X的结点数。
intCountX（LNode*HL,ElemTypex）
{inti=0;
LNode*p=HL;
//i为计数器
while（p!
=NULL）
{if（P->
data==x）i++;
p=p->
next;
}//while,出循环时i中的值即为x结点个数
returni;
}//CountX
数据结构试卷
（二）
三、应用题（36分）
1．设一组初始记录关键字序列为（45，80，48，40，22，78），则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
（22，40，45，48，80，78），（40，45，48，80，22，78）
2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
q->
llink=p;
rlink=p->
rlink;
p->
rlink->
llink=q;
rlink=q;
3．设一组有序的记录关键字序列为（13，18，24，35，47，50，62，83，90），查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
2,ASL=91*1+2*2+3*4+4*2）=25/9
4．设一棵树T中边的集合为{（A，B），（A，C），（A，D），（B，E），（C，F），（C，G）}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
树的链式存储结构略，二叉树略
5．
设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。
E={（1，3），（1，2），（3，5），（5，6），（6，4）}
6．设有一组初始记录关键字为（45，80，48，40，22，78），要求构造一棵二叉排序树并给出构造过程。
四、算法设计题（16分）
1．设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O（n）的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O（n）的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
voidquickpass（intr[],ints,intt）
inti=s,j=t,x=r[s];
while（i<
j）{
j&
r[j]>
x）j=j-1;
if（i<
j）{r[i]=r[j];
i=i+1;
r[i]<
x）i=i+1;
j）{r[j]=r[i];
j=j-1;
r[i]=x;
2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
typedefstructnode{intdata;
structnode*next;
}lklist;
voidintersection（lklist*ha,lklist*hb,lklist*&
hc）
lklist*p,*q,*t;
for（p=ha,hc=0;
p!
=0;
next）
{for（q=hb;
q!
q=q->
next）if（q->
data==p->
data）break;
if（q!
=0）{t=（lklist*）malloc（sizeof（lklist））;
t->
data=p->
next=hc;
hc=t;
数据结构试卷（三）
三、计算题（每题10分，共30分）
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。
2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，试：
H（36）=36mod7=1;
H１（22）=（1+1）mod7=2;
….冲突
H（15）=15mod7=1;
….冲突H2（22）=（2+1）mod7=3;
H１（15）=（1+1）mod7=2;
H（40）=40mod7=5;
H（63）=63mod7=0;
H（22）=22mod7=1;
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
`0123456
63
36
15
22
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
ASL=
3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。
（8,9,4,3,6,1）,10,（12,18,18）
（1,6,4,3）,8,（9）,10,12,（18,18）
1,（3,4,6）,8,9,10,12,18,（18）
1,3,（4,6）,8,9,10,12,18,18
1,3,4,6,8,9,10,12,18,18
四、算法设计题（每题15分，共30分）
1．设计在单链表中删除值相同的多余结点的算法。
设计在单链表中删除值相同的多余结点的算法。
typedefintdatatype;
typedefstructnode{datatypedata;
voiddelredundant（lklist*&
head）
lklist*p,*q,*s;
for（p=head;
for（q=p->
next,s=q;
）
if（q->
data）{s->
next=q->
free（q）;
q=s->
else{s=q,q=q->
2．设计一个求结点x在二叉树中的双亲结点算法。
设计一个求结点x在二叉树中的双亲结点算法。
structnode*lchild,*rchild;
}bitree;
bitree*q[20];
intr=0,f=0,flag=0;
voidpreorder（bitree*bt,charx）
if（bt!
=0&
flag==0）
if（bt->
data==x）{flag=1;
return;
else{r=（r+1）%20;
q[r]=bt;
preorder（bt->
lchild,x）;
rchild,x）;
voidparent（bitree*bt,charx）
inti;
preorder（bt,x）;
for（i=f+1;
i<
=r;
i++）if（q[i]->
lchild->
data==x||q[i]->
rchild->
if（flag==0）printf（"
notfoundx\n"
）;
elseif（i<
=r）printf（"
%c"
bt->
data）;
elseprintf（"
notparent"
数据结构试卷（四）
1、画出广义表LS=（（）,（e）,（a,（b,c,d）））的头尾链表存储结构。
2、下图所示的森林：
（1）求树（a）的先根序列和后根序列；
（1）ABCDEF;
BDEFCA；
（2）ABCDEFGHIJK;
BDEFCAIJKHG林转换为相应的二叉树；
（2）求森林先序序列和中序序列；
ABCDEF;
（3）将此森林转换为相应的二叉树；
3、设散列表的地址范围是[0..9]，散列函数为H（key）=（key2+2）MOD9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。
H（4）=H（5）=0,H（3）=H（6）=H（9）=2,H（8）=3,H
（2）=H（7）=6
四、算法设计题（每题10分，共30分）
1．设单链表中有仅三类字符的数据元素（大写字母、数字和其它字符），要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
设单链表中有仅三类字符的数据元素（大写字母、数字和其它字符），要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
typedefchardatatype;
voidsplit（lklist*head,lklist*&
ha,lklist*&
hb,lklist*&
lklist*p;
ha=0,hb=0,hc=0;
p=head）
head=p->
next=0;
if（p->
data>
='
A'
Z'
）{p->
next=ha;
ha=p;
elseif（p->
0'
9'
next=hb;
hb=p;
}else{p->
hc=p;
2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
voidswapbitree（bitree*bt）
bitree*p;
if（bt==0）return;
swapbitree（bt->
lchild）;
rchild）;
p=bt->
lchild;
bt->
lchild=bt->
rchild;
rchild=p;
3.在链式存储结构上建立一棵二叉排序树。
在链式存储结构上建立一棵二叉排序树。
#definen10
typedefstructnode{intkey;
voidbstinsert（bitree*&
bt,intkey）
if（bt==0）{bt=（bitree*）malloc（sizeof（bitree））;
key=key;
rchild=0;
elseif（bt->
key>
key）bstinsert（bt->
lchild,key）;
elsebstinsert（bt->
rchild,key）;
voidcreatebsttree（bitree*&
bt）
for（i=1;
=n;
i++）bstinsert（bt,random（100））;
数据结构试卷（五）
三、应用题（32分）
1.
设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。
DEBCA
2.设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。
E={（1,5）,（5,2）,（5,3）,（3,4）},W=10
3.设一组初始记录关键字序列为（15，17，18，22，35，51，60），要求计算出成功查找时的平均查找长度。
ASL=（1*1+2*2+3*4）/7=17/7
4.设散列表的长度为8，散列函数H（k）=kmod7，初始记录关键字序列为（25，31，8，27，13，68），要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。
ASL1=7/6，ASL2=4/3
四、算法设计题（28分）
1．设计判断两个二叉树是否相同的算法。
设计判断两个二叉树是否相同的算法。
intjudgebitree（bitree*bt1,bitree*bt2）
if（bt1==0&
bt2==0）return
（1）;
elseif（bt1==0||bt2==0||bt1->
data!
=bt2->
data）return（0）;
elsereturn（judgebitree（bt1->
lchild,bt2->
lchild）*judgebitree（bt1->
rchild,bt2->
rchild））;
2．设计两个有序单链表的合并排序算法。
设计两个有序单链表的合并排序算法。
voidmergelklist（lklist*ha,lklist*hb,lklist*&
lklist*s=hc=0;
while（ha!
hb!
=0）
if（ha->
hb->
data）{if（s==0）hc=s=ha;
else{s->
s=ha;
};
ha=ha->
else{if（s==0）hc=s=hb;
s=hb;
hb=hb->
if（ha==0）s->
elses->
数据结构试卷（六）
四、算法设计题（20分）
1．设计在顺序有序表中实现二分查找的算法。
设计在顺序有序表中实现二分查找的算法。
structrecord{intkey;
intothers;
intbisearch（structrecordr[],intk）
intlow=0,mid,high=n-1;
while（low<
=high）
mid=（low+high）/2;
if（r[mid].key==k）return（mid+1）;
elseif（r[mid].key>
k）high=mid-1;
elselow=mid+1;
return（0）;
2．设计判断二叉树是否为二叉排序树的算法。
设计判断二叉树是否为二叉排序树的算法。
intminnum=-32768,flag=1;
voidinorder（bitree*bt）
=0）{inorder（bt->
if（minnum>
key）flag=0;
minnum=bt->
key;
inorder（bt->
3.在链式存储结构上设计直接插入排序算法
在链式存储结构上设计直接插入排序算法
voidstraightinsertsort（lklist*&
lklist*s,*p,*q;
intt;
if（head==0||head->
next==0）return;
elsefor（q=head,p=head->
p=q->
for（s=head;
s!
=q->
s=s->
next）if（s->
if（s==q->
next）q=p;
else{q->
next=p->
next=s->
s->
next=p;
t=p->
data=s->
data=t;
数据结构试卷（七）
1.设计在链式结构上实现简单选择排序算法。
设计在链式结构上实现简单选择排序算法。
voidsimpleselectsorlklist（lklist*&
intmin,t;
for（q=head;
min=q->
s=q;
for（p=q->
next）if（min>
data）{min=p->
s=p;
if（s!
=q）{t=s->
data=q->
2.设计在顺序存储结构上实现求子串算法。
设计在顺序存储结构上实现求子串算法。
voidsubstring（chars[],longstart,longcount,chart[]）
longi,j,length=strlen（s）;
if（start<
1||start>
length）printf（"
Thecopypositioniswrong"
elseif（start+count-1>
Toocharacterstobecopied"
else{for（i=start-1,j=0;
start+count-1;
i++,j++）t[j]=s[i];
t[j]='
\0'
3.设计求结点在二叉排序树中层次的算法。
设计求结点在二叉排序树中层次的算法。
intlev=0;
voidlevel（bitree*bt,intx）
{lev++;
key==x）return;
x）level（bt->
elselevel（bt->
数据结构试卷（八）
1.设计一个在链式存储结构上统计二叉树中结点个数的算法。
设计一个在链式存储结构上统计二叉树中结点个数的算法。
voidcountnode（bitree*bt,int&
count）
{count++;
countnode（bt->
lchild,count）;
rchild,count）;
2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。
typedefstruct{intvertex[m];
intedge[m][m];
}gadjmatrix;
typedefstructnode1{intinfo;
intadjvertex;
structnode1*nextarc;
}glinklistnode;
typedefstructnode2{intvertexinfo;
glinklistnode*firstarc;
}glinkheadnode;
voidadjmatrixtoadjlist（gadjmatrixg1[],glinkheadnodeg2[]）
inti,j;
glinklistnode*p;
for（i=0;
=n-1;
i++）g2[i].firstarc=0;
i++）for（j=0;
j<
j++）
if（g1.edge[i][j]==1）
p=（glinklistnode*）malloc（sizeof（glinklistn
升级会员 