华南农业大学珠江学院-生病祝福语

《数据结构》期末考试试题及答案
(2003-2004学年第2学期)
贵州大学理学院数学系信息与计算科学专业
一、 单项选择题
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为
（ ）。
(A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性
2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。
for(i=n-1；i>=0；i--)
for(j=0；j (A)、n
2
(B). O(nlgn) (C). O(n) (D). O(n
2
)
3．折半查找法适用于（ ）。
（A）、有序顺序表 （B）、有序单链表
（C）、有序顺序表和有序单链表都可以 （D）、无限制
4．顺序存储结构的优势是（ ）。
（A）、利于插入操作 （B）、利于删除操作
（C）、利于顺序访问 （D）、利于随机访问
5．深度为k的完全二叉树，其叶子结点必在第（ ）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k
6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ）
（A）、11 （B）、13 （C）、48 （D）、37
7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法
的推广。
（A）、先序 （B）、中序 （C）、后序 （D）、层序

8．在下列链队列Q中，元素a出队的操作序列为（ ）

a
front
b c
d
∧



Q
（A）、p=->next; p->next= ->next;
（B）、p=->next; ->next=p->next;
（C）、p=->next; p->next= ->next;
（D）、p=Q->next; Q->next=p->next;
9． Huffman树的带权路径长度WPL等于（ ）
（A）、除根结点之外的所有结点权值之和 （B）、所有结点权值之和
（C）、各叶子结点的带权路径长度之和 （D）、根结点的值
10．线索二叉链表是利用（ ）域存储后继结点的地址。
第 1 页 共 7 页

（A）、lchild （B）、data （C）、rchild （D）、root
二、填空题
1． 逻辑结构决定了算法的 ，而存储结构决定了算法
的 。
2． 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。
3． 线性表（a
1
,a
2
,…,a
n
）的顺序存储结构中，设每个单元的长度为L，元素a
i
的存储地址LOC(a
i
)为
4． 已知一双向链表如下(指针域名为next和prior)：

y


x



q

e

p

现将p所指的结点插入到
x
和
y
结点之间，其操作步骤
为： ；
； ； ；
5．n个结点无向完全图的的边数为 ，
n个结点的生成树的边数为 。
6．已知一有向无环图如下：

D


A


C


E

B
F


G




任意写出二种拓扑排序序列： 、 。
7．已知二叉树的中序遍历序列为BCA，后序遍 历序列为CBA，则该二叉树的先序
遍历序列为 ，层序遍历序列为 。

三、应用题
1． 设散列函数H(k)=k % 13,设关键字系列为{2 2,12,24,6,45,7,8,13,21},要
求用线性探测法处理冲突。(6分)
(1) 构造HASH表。
(2) 分别求查找成功和不成功时的平均查找长度。

2． 给定表（19,14,22,15,20,21,56,10）.（8分）
（1） 按元素在表中的次序，建立一棵二叉排序树
第 2 页 共 7 页

（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。
（3） 画出对(2)中的遍历序列进行折半查找过程的判定树。
3． 已知二个稀疏矩阵A和B的压缩存储三元组表如下：
A B
i
1
2
2
4
5
j
3
4
5
2
2
V
-5
6
2
-1
9






i
2
3
4
5
5
j
5
3
1
2
5
V
2
7
3
-9
8
写出A-B压缩存储的三元组表。（5分）

4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过
程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)

5． 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有
过程)
A B C D E F
A

651


B

653

C

572


D

15764

E

36 6


F


246

（1）求从顶点A开始的最小生成树。
（2）分别画出以A为起点的DFS生成树和BFS生成树。

6．已知数据六个字母及在通信中出现频率如下表：
A
0.15
B
0.15
C
0.1
D
0.1
E
0.2
F
0.3
把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。
（1） 画出对应的Huffman树。
（2） 计算带权路径长度WPL。
（3） 求A、B、C、D、E、F的Huffman编码。
第 3 页 共 7 页

7． 已知有如下的有向网：








A

2 5

B
3
E
6

4 10 6 1 2
C D
求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）
三、
设计题
（30分，每题10分,用C语言写出算法，做在答题纸
上）
1． 已知线性表（a
1
,a
2
,…,a
n
）以顺序存储结构为存 储结构，其类型定义如下：
#define LIST_INIT_SIZE 100 顺序表初始分配容量
typedef struct {
Elemtype *elem; 顺序存储空间基址
int length; 当前长度（存储元素个数）
}SqList;
设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：
Status ListDelete(Sqlist &L,Elemtype x)
{
……
}

2．设顺序栈如左图所示。
其中结点定义如下： top
typedef struct {
Elemtype *base; 栈底指针
Elemtype *top; 栈顶指针
}Stack;
设计算法，将栈顶元素出栈并存入e中． base

3．设二叉链树的类型定义如下：
typedef int Elemtype;
typedef struct node{
Elemtype data;
struct node *lchild, *rchild;
}BinNode, *BinTree;
试写出求该二叉树叶子结点数的算法:
第 4 页 共 7 页

a
n


…

a
2

a
1

Status CountLeaves(BinTree &root,int &n)
{n is the number of leaves
……
}
答案：
选择题（每题1分）
1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C
一、填空题
1．设计、实现
2．特殊、栈顶
3．LOC（a1）+(i-1)*L
4．p->next=q->next;q->next->prior=p; q->next=p;p->prior=q;
5．n(n-1)2、n-1
6．ADCBFEG、ABCDEFFG
7．ABC、ABC
二、应用题
1 （1）Hash表（4分）
0 1 2 3 4 5 6 7 8 9
地址
13 21 6 45 7 22
关键安
7 1 2 3 1
探测次数
1
（2）查找成功的平均查找长度：（1分）
（5*1+1*2+2*3+1*7）9=209
查找不成功的平均查找长度：（1分）
（2+1+9+8+7+6+5+4+3+2+1）13=
2（1）、构造（3分）

19



14 22



10 15 20 56



21

(2)、10 14 15 19 20 21 22 56（2分）
（3）、（3分）



第 5 页 共 7 页
10
8
3
11
24
1
12
12
1

3、(5分，每行0.5)
i j v
1 3 -5
2 4 6
3 3 7
4 1 3
4 2 -1
5 2 18
5 5 8
4、 初始关键字： [18] 12 25 53 18
第 一 趟：[12 18] 25 53 18
第 二 趟：[12 18 25] 53 18
第 三 趟：[12 18 25 53] 18
第 四 趟：[12 18 18 25 53]
O（n
2
）（1分）。
5、7分
（1）4分
A

B 1 C
3 2
5 D 4
E F
（2）4分






6、(1) 3分







E F


A B C D

第



6

页



共



7

页



4分）


（

（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)
（3）A：010 B：011 C：110 D：111 E：00 F；10 （3分）
12、A-B：（A、B） 1分
A-C：（A、D、C） 2分
A-D：（A、D） 1分
A-E：（A、D、E） 2分
三，设计题（20分）
1、(10分)
Status ListDelete(Sqlist &L,ElemType x)
{
int i,j;
for(i=0;ilength;i++)
if(L->elem[i]==x) break;
if(i=L->length) return ERROR;
for(j=i;jlengthi-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
} （8分）
平均时间复杂度：（2分）
设元素个数记为n，则平均时间复杂度为：
1
n
n1

E

(ni)
n
i1
2
2（10分）
void pop(Stack &S,Elemtype &e)
{
if(==) return ERROR;
--;
e=*;
}
2、（10分）
voidCountLeaves(BinTree T,int &n)
{
if(T)
{
if((!(T->lchild)&&!( T->rchild)) n++;
CountLeaves (T->lchild,n);
CountLeaves (T->rchild,n);
}
}
第 7 页 共 7 页

《数据结构》期末考试试题及答案
(2003-2004学年第2学期)
贵州大学理学院数学系信息与计算科学专业
一、 单项选择题
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为
（ ）。
(A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性
2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。
for(i=n-1；i>=0；i--)
for(j=0；j (A)、n
2
(B). O(nlgn) (C). O(n) (D). O(n
2
)
3．折半查找法适用于（ ）。
（A）、有序顺序表 （B）、有序单链表
（C）、有序顺序表和有序单链表都可以 （D）、无限制
4．顺序存储结构的优势是（ ）。
（A）、利于插入操作 （B）、利于删除操作
（C）、利于顺序访问 （D）、利于随机访问
5．深度为k的完全二叉树，其叶子结点必在第（ ）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k
6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ）
（A）、11 （B）、13 （C）、48 （D）、37
7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法
的推广。
（A）、先序 （B）、中序 （C）、后序 （D）、层序

8．在下列链队列Q中，元素a出队的操作序列为（ ）

a
front
b c
d
∧



Q
（A）、p=->next; p->next= ->next;
（B）、p=->next; ->next=p->next;
（C）、p=->next; p->next= ->next;
（D）、p=Q->next; Q->next=p->next;
9． Huffman树的带权路径长度WPL等于（ ）
（A）、除根结点之外的所有结点权值之和 （B）、所有结点权值之和
（C）、各叶子结点的带权路径长度之和 （D）、根结点的值
10．线索二叉链表是利用（ ）域存储后继结点的地址。
第 1 页 共 7 页

（A）、lchild （B）、data （C）、rchild （D）、root
二、填空题
1． 逻辑结构决定了算法的 ，而存储结构决定了算法
的 。
2． 栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。
3． 线性表（a
1
,a
2
,…,a
n
）的顺序存储结构中，设每个单元的长度为L，元素a
i
的存储地址LOC(a
i
)为
4． 已知一双向链表如下(指针域名为next和prior)：

y


x



q

e

p

现将p所指的结点插入到
x
和
y
结点之间，其操作步骤
为： ；
； ； ；
5．n个结点无向完全图的的边数为 ，
n个结点的生成树的边数为 。
6．已知一有向无环图如下：

D


A


C


E

B
F


G




任意写出二种拓扑排序序列： 、 。
7．已知二叉树的中序遍历序列为BCA，后序遍 历序列为CBA，则该二叉树的先序
遍历序列为 ，层序遍历序列为 。

三、应用题
1． 设散列函数H(k)=k % 13,设关键字系列为{2 2,12,24,6,45,7,8,13,21},要
求用线性探测法处理冲突。(6分)
(1) 构造HASH表。
(2) 分别求查找成功和不成功时的平均查找长度。

2． 给定表（19,14,22,15,20,21,56,10）.（8分）
（1） 按元素在表中的次序，建立一棵二叉排序树
第 2 页 共 7 页

（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。
（3） 画出对(2)中的遍历序列进行折半查找过程的判定树。
3． 已知二个稀疏矩阵A和B的压缩存储三元组表如下：
A B
i
1
2
2
4
5
j
3
4
5
2
2
V
-5
6
2
-1
9






i
2
3
4
5
5
j
5
3
1
2
5
V
2
7
3
-9
8
写出A-B压缩存储的三元组表。（5分）

4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过
程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)

5． 已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有
过程)
A B C D E F
A

651


B

653

C

572


D

15764

E

36 6


F


246

（1）求从顶点A开始的最小生成树。
（2）分别画出以A为起点的DFS生成树和BFS生成树。

6．已知数据六个字母及在通信中出现频率如下表：
A
0.15
B
0.15
C
0.1
D
0.1
E
0.2
F
0.3
把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。
（1） 画出对应的Huffman树。
（2） 计算带权路径长度WPL。
（3） 求A、B、C、D、E、F的Huffman编码。
第 3 页 共 7 页

7． 已知有如下的有向网：








A

2 5

B
3
E
6

4 10 6 1 2
C D
求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）
三、
设计题
（30分，每题10分,用C语言写出算法，做在答题纸
上）
1． 已知线性表（a
1
,a
2
,…,a
n
）以顺序存储结构为存 储结构，其类型定义如下：
#define LIST_INIT_SIZE 100 顺序表初始分配容量
typedef struct {
Elemtype *elem; 顺序存储空间基址
int length; 当前长度（存储元素个数）
}SqList;
设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：
Status ListDelete(Sqlist &L,Elemtype x)
{
……
}

2．设顺序栈如左图所示。
其中结点定义如下： top
typedef struct {
Elemtype *base; 栈底指针
Elemtype *top; 栈顶指针
}Stack;
设计算法，将栈顶元素出栈并存入e中． base

3．设二叉链树的类型定义如下：
typedef int Elemtype;
typedef struct node{
Elemtype data;
struct node *lchild, *rchild;
}BinNode, *BinTree;
试写出求该二叉树叶子结点数的算法:
第 4 页 共 7 页

a
n


…

a
2

a
1

Status CountLeaves(BinTree &root,int &n)
{n is the number of leaves
……
}
答案：
选择题（每题1分）
1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C
一、填空题
1．设计、实现
2．特殊、栈顶
3．LOC（a1）+(i-1)*L
4．p->next=q->next;q->next->prior=p; q->next=p;p->prior=q;
5．n(n-1)2、n-1
6．ADCBFEG、ABCDEFFG
7．ABC、ABC
二、应用题
1 （1）Hash表（4分）
0 1 2 3 4 5 6 7 8 9
地址
13 21 6 45 7 22
关键安
7 1 2 3 1
探测次数
1
（2）查找成功的平均查找长度：（1分）
（5*1+1*2+2*3+1*7）9=209
查找不成功的平均查找长度：（1分）
（2+1+9+8+7+6+5+4+3+2+1）13=
2（1）、构造（3分）

19



14 22



10 15 20 56



21

(2)、10 14 15 19 20 21 22 56（2分）
（3）、（3分）



第 5 页 共 7 页
10
8
3
11
24
1
12
12
1

3、(5分，每行0.5)
i j v
1 3 -5
2 4 6
3 3 7
4 1 3
4 2 -1
5 2 18
5 5 8
4、 初始关键字： [18] 12 25 53 18
第 一 趟：[12 18] 25 53 18
第 二 趟：[12 18 25] 53 18
第 三 趟：[12 18 25 53] 18
第 四 趟：[12 18 18 25 53]
O（n
2
）（1分）。
5、7分
（1）4分
A

B 1 C
3 2
5 D 4
E F
（2）4分






6、(1) 3分







E F


A B C D

第



6

页



共



7

页



4分）


（

（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)
（3）A：010 B：011 C：110 D：111 E：00 F；10 （3分）
12、A-B：（A、B） 1分
A-C：（A、D、C） 2分
A-D：（A、D） 1分
A-E：（A、D、E） 2分
三，设计题（20分）
1、(10分)
Status ListDelete(Sqlist &L,ElemType x)
{
int i,j;
for(i=0;ilength;i++)
if(L->elem[i]==x) break;
if(i=L->length) return ERROR;
for(j=i;jlengthi-1;j++)
L->elem[j]=L->elem[j+1];
L->length--;
} （8分）
平均时间复杂度：（2分）
设元素个数记为n，则平均时间复杂度为：
1
n
n1

E

(ni)
n
i1
2
2（10分）
void pop(Stack &S,Elemtype &e)
{
if(==) return ERROR;
--;
e=*;
}
2、（10分）
voidCountLeaves(BinTree T,int &n)
{
if(T)
{
if((!(T->lchild)&&!( T->rchild)) n++;
CountLeaves (T->lchild,n);
CountLeaves (T->rchild,n);
}
}
第 7 页 共 7 页