(完整版)中国海洋大学06-07数据结构第1学期A卷+答案.docx

该【(完整版)中国海洋大学06-07数据结构第1学期A卷+答案 】是由【小熙】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【(完整版)中国海洋大学06-07数据结构第1学期A卷+答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。中国大海大学命题专用纸(首页)
2006学年第

1

学期

试题名称

:

数据结构

(A

卷)

共

2

页

第

1

页
专业年级:

学号

姓名

讲课教师

分数
一、简答以下术语:(10分)
1、算法的时间复杂度
2、栈与行列的异同
3、完整二叉树、二叉排序树
二、填空(10分)
1、在双向循环链表L中,删除指针P所指结点的语句序列是,
,free(p)。
2、将下三角矩阵A[1..8,1..8]的下三角部分逐行地储存到开端地点为1000的内存单
,则A(6,4)的地点为。
3、高度为5的三阶B-树起码有个结点。
4、分别采纳堆排序、迅速排序、插入排序和合并排序算法对初始状态已为递加序列的
数据表进行递加排序,最省时间的是算法。
三、(8分)已知一棵二叉树的中序序列是

dcbgeahfijk

,后序序列是

dcegbfhkjia

,
请结构出该二叉树。
四、(10分)假定用于通讯的电文仅由8个字母构成,字母在电文中出现的频次分别是
,,,,,,,。请设计它们相应的哈夫曼编码。使用0~7的二进制表示形式是另一种编码方案,请比较两种方案的优弊端。
五、(10分)设散列表地点空间为0..6,散列函数为H(x)=imod7,此中i为键值x中第一个字母在字母表中的序号,若键值的输入序列为
Jen,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec,用链地点法办理矛盾,
结构散列表;2)求出在等概率状况下,查找成功时的均匀查找长度。
六、(15分)
(1)对以下数据表,写出采纳希尔排序算法排序的每一趟的结果。
(100,12,20,31,1,5,44,66,61,200,30,80,150,4,8)
(2)对以下数据表,写出采纳迅速排序算法排序的第一趟的结果。
(70,12,20,150,44,66,61,200,30,80,28)
讲课
张海燕
命题教师或命题负责人
院系负责人
教师
签
字
签
字
年月日
中国大海大学命题专用纸(附页)
2006学年第1学期试题名称:数据结构(A)共2页第2页
七、(6分)画出对应于递加有序表A[1..21]进行二分查找的判断树。
八、(15分)对以下的网,1)写出其毗邻矩阵。
2)求其最小生成树。(写出各步状态)
3B
A
73
4
D
21
5
CE
九、(8分)试编写一算法,实现无头结点的单链表的就地逆置,即利用原表的储存空间将线性表(a1,a2,,an-1,an)逆置为(an,an-1,,,a2,a1)。
十、(8分)设计算法以判断二叉树T能否为二叉排序树(设T中随意两个结点的值均不相等
(设二叉树以二叉链表来储存,结点结构为:Lchild│data│Rchild)

)。
2006学年第一学期数据结构(A)卷试题答案
一、简答题(共10分,每个术语2分)
算法的时间复杂度:一个算法履行所需的均匀时间长度,其描绘了算法效率的高低。
栈与行列的异同:栈是先进后出,只好在栈顶插入元素或删除元素;行列是先进先出,在队头删除元素,队尾插入元素。
完整二叉树:若一棵二叉树从上到下,从左到右挨次编号与满二叉树对应编号完整同样。则
称此二叉树为完整二叉树。
二叉排序树:或许是一棵空树,或许拥有这样性质的树:(1)左子树结点的值均小于根结点的值,(2)右子树结点的值均大于根结点的值,(3)左、右子树分别是二叉排序树。
二、填空题(共10分,每个填空2分)
1.

p

prior

next=p

next,p

next

prior=p

prior
2.

1072


三、(8分,依据所结构的二叉树正确的比率给分
答:由二叉树的中序序列dcbgeahfijk,后序序列

)
dcegbfhkjia

,结构的二叉树以下:
a
bi
dghj
四、(10分)
c
e
f
k
答:(1)(9分,
依据正确的比率给
分)所结构的哈夫曼树为
:
假定8个字母分别为
a,b,c,d,e,f,g,
,,,,,,,
。对左子树路径赋为
0,右子树赋为1,则a,b,c,d,e,f,
g,h,i的哈夫曼编码为:
a:0110b:0111c:110d:10e:010f:00g:1110h:1111
带权路径长度WPL=
wili=*4+*4+*3+022*2+*3+*2+*4+*4
(1分)0~7二进制表示以下:
:000,
:001
,
:010,
:011
:100,
:101
,
:110,
:111
带权路径长度
WPL=
wi
li=(
)
比较可知:哈夫曼编码为不等长码,信源压缩度高。
1
五、(10分)
(1)(9分,)
用链地点法办理矛盾,结构散列表以下:
0
Nov
∧
1
Apr
Aug
Oct
∧
2
^
3
Jen
Jun
Jul
∧
4
Dec
∧
5
Sep
∧
6
Feb
Mar
May
∧
(2)(1分)均匀查找长度
L=1/12
(6*1+3*2+3*3
)
六、(15分)
(1)(7分,依据正确的比率给分)
假定各趟希尔排序的间隔分别为
7,3,
1。
第一趟排序结果:
8
1220
30
1
54
66
61
2003**********
第二趟排序结果:
4
1
5
8
12
20
30
31
61
15044
8020066
100
第三趟排序结果:
1
4
5
8
12
20
30
31
44
6**********
200
2)(8分,依据正确的比率给分)选用70为枢轴
初始重点字:70
12
20
150
44
66
61
200
30
80
28
i
j
第一次互换后:28
12
20
150
44
66
61
200
30
80
i
j
第二次互换后:28
12
20
44
66
61
200
30
80
150
i
j
第三次互换后:28
12
20
30
44
66
61
200
80
150
i
j
第四次互换后:28
12
20
30
44
66
61
200
80
150
i
j
第一趟排序结果:
28
12
20
30
44
66
61
70
200
80
150
七、(6分,依据判断树的正确比率给分)
答:二分查找的判断树以下:
111
516
281319
4710151821
八:(15分)
0347
3
4025
(1)(7分)毗邻矩阵为:
73201
510
i
1(Vb)
2(Vc)
3(Vd)
4(Ve)
U
V_U
Vex
Va
Va
Va
[Va]
[Vb,Vc,Vd,
adj
3
4
7
Ve]
Vex
Va
Vb
[Va,Vb]
[Vc,Vd,Ve]
adj
0
4
3
Vex
Vd
Vd
[Va,Vb,Vd]
[Vc,Ve]
adj
0
2
0
1
Vex
Vd
[Va,Vb,Vd,
[Vc]
adj
0
2
0
0
Ve]
Vex
adj
0
0
0
(2)(8分)3
最小生成树为:A
D
2
C
九:(8分,依据解题思路的正确程度给分)
函数编写以下:
单链表以以下图:
PMN
A1A2A3

[Va,Vb,Vd,
0Ve,Vc]
B
3
1
E
An-1
An
StatusReverse(Linklist*L)
{inti=1;P=L;
for(;i<;i+=3﹚
{m=p→next;n=m→next;
m→next=p;n→next=m;
p=n;
}
L→next=Null;
}
十、(8分,依据解题思路的正确程度给分)
判断二叉树能否为二叉排序树的程序以下:
intPaixu(BinTree*T)
{intm,n;if(!T){
if((T→data<T→lchild→data=‖(T→data>T→rchild→data))return0;
m=Paixu(T→(lchild));
if(!m)return0;
n=Paixu(T→rchild);
if(!n)return0;
}
return1;
}