数据结构与算法期末样卷(附答案).doc

厦门大学《数据结构与算法》课程试卷
　软件　学院　08　级　数字媒体工程　专业
主考教师：陈海山　 试卷类型：A卷

E请将答案按序写在学校统一印制的专用答题卷上，写在本卷或自备纸上者一律不得分。

一．单项选择题 (本题含25个小题，每个小题2分，计50分)

二．综合应用题 (含5个小题，每小题10分，计50分)

1．设LinkList是链表存储结构，试分析下列算法的时间复杂度，并简述程序的主要功能。
void CrList( LinkList &L, int n )
{
LinkList p, q=L;
for ( i =0; i<n; ++i )
{
p=( LinkList ) malloc( sizeof( int ) );
q->next=p;
p->data=rand( ); // rand( )：产生一个随机整数
q=p;
}
p->next=NULL;
} // 算法结束

[参考答案]
该算法的时间复杂度主要由for ( i = 0；i < n；++ i )命令决定(即主要由链表长度决定)，因此算法的时间复杂度为O(n)。
程序的主要功能：创建一个含有n个结点的线性链表L，其中数据元素由随机函数产生。

2．画出与下列两个已知遍历序列对应的一颗二叉树：
先序遍历序列：A B G E K C F H J D
中序遍历序列：G B K E A H F J C D

[参考答案]
A
B
C
G
E
F
D
K
H
J

3．已知无向图如下，试绘制一棵从A点开始的广度优先生成树。
A
E
B
C
F
G
D

[参考答案]
从A点开始的一棵广度优先生成树如下(六种情况之一)：
A→B→C→D时： A→C→D→B时： A→D→B→C时：
A
E
B
C
F
G
D
A
E
B
C
F
G
D
A
E
B
C
F
G
D

A→B→D→C时： A→C→B→D时： A→D→C→B时：
A
E
B
C
F
G
D
A
E
B
C
F
G
D
A
E
C
F
G
D
B

4．已知关键字集={ 19，23，55，11，30，47，28，38，15，51，42 }，表长m=7，哈希函数H(key)=key%7+1。试给出由链表地址法产生的哈希地址和哈希链表示意图。

[参考答案]
由链表地址法产生的哈希地址是：6，3，7，5，3，6，1，4，2，3，1
哈希链表示意图如下：
1

28

42
L

2

15
L

3

23

30

51
L

4

38
L

5

11
L

6

19

47
L

7

55
L

5．设n个整数存放在数组a中。试设计堆排序算法，将数组a中的数据从小到大排序。

[参考答案]
将数组a中的数据从小到大排序的堆排序算法如下：
void HeapSort(int *a, int n)
{
// 建堆：将a整理成大顶堆
for (int i=n/2; i>0; --i) HeapAdjust(a, i, n);
// 排序：依次将根结点移到第i个位置
for (i=n; i>1; i--)
{
int x=a[1];
a[1]=a[i];
a[i]=x;
HeapAdjust(a, 1, i-1);
}
} //算法时间复杂度为O(nlogn)

// 将根结点调整成大顶堆
void HeapAdjust(int *r, int s, int t)
{
for (int j=2*s; j<=t; j*=2)
{
if (j<t && r[j+1]>r[j]) ++j;
if (r[s]>=r[j]) break;
int x=r[s];
r[s]=r[j];
r[j]=x;
s=j;
}
} //算法时间复杂度为O(logn)

4