《数据结构》期末考试试题及答案

《数据结构》期末考试试题及答案

(2003-2004学年第2学期)

单项选择题1、C2、D3、A4、D5、C6、D7、A8、B9、CIO、C

1.对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为

(C)o

(A)、正确性(B).可行性(C).健壮性(D).输入性

2.设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为(d)。

for(i=n-l；i>=0；i—)

for(j=0；j<i；j++)S；

(A)、n2(B).O(nlgn)(C).O(n)(D).O(n2)

3.折半查找法适用于(a)»

(A),有序顺序表(B)、有序单链表

(C)、有序顺序表和有序单链表都可以(D)、无限制

4.顺序存储结构的优势是(d)o

(A)、利于插入操作(B)、利于删除操作

(C)、利于顺序访问(D)、利于随机访问

5.深度为k的完全二叉树，其叶子结点必在第(c)层上。

(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-FirstSearch(DFS)遍历思想实际上是二叉树(a)遍历方

法的推广。

(A)、先序(B)、中序(C)、后序(D)、层序

8.在下列链队列Q中，元素a出队的操作序列为(ab)

(A)、p=Q.front->next;p->next=Q.front->next;

(B)、p=Q.front->next;Q.front->next=p->next;

(C)^p=Q.rear->next;p->next=Q.rear->next;

(D)、p=Q->next;Q->next=p->next;

9.Huffman树的带权路径长度WPL等于(c)

(A)、除根结点之外的所有结点权值之和(B)、所有结点权值之和

(C)、各叶子结点的带权路径长度之和(D)、根结点的值

10.线索二叉链表是利用(C)域存储后继结点的地址。

(A)、Ichild(B)、data(C)、rchild(D)、root

二、填空题

1.逻辑结构决定了算法的设计，而存储结构决定了算法的_____实

现。

2.栈和队列都是一种特殊的线性表,栈的插入和删除只能在栈顶

进行。

3.线性表(肌山，…,a„)的顺序存储结构中，设每个单元的长度为L,元素为

的存储地址LOC(a)为____________________

4.已知一双向链表如下(指针域名为next和prior)：

/

现将p所指的结点插入到x和y结点之间，其操作步骤

%：;

5.n个结点无向完全图的的边数为

n个结点的生成树的边数为

6.已知一有向无环图如下：

任意写出二种拓扑排序序列：、。

7.已知二叉树的中序遍历序列为BCA,后序遍历序列为CBA,则该二叉树的先序

遍历序列为，层序遍历序列为。

三、应用题

1.设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要

求用线性探测法处理冲突。(6分)

⑴构造HASH表。

(2)分别求查找成功和不成功时的平均查找长度。

2.给定表（19,14,22,15,20,21,56,10）.（8分）

（1）按元素在表中的次序，建立一棵二叉排序树

（2）对（1）中所建立的二叉排序树进行中序遍历，写出遍历序列。

（3）画出对（2）中的遍历序列进行折半查找过程的判定树。

3.已知二个稀疏矩阵A和B的压缩存储三元组表如下：

AB

iJVijV

13-5252

246337

252413

42-152-9

529558

写出A-B压缩存储的三元组表。（5分）

4.已知一维数组中的数据为（18,12,25,53,生）,试写出插入排序（升序）过

程。并指出具有n个元素的插入排序的时间复杂度是多少？（5分）

5.已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。（8分，要有

过程）

ABCDEF

A006510000

B6co005300

C500007002

D1570064

E003006006

F000024600

（1）求从顶点A开始的最小生成树。

（2）分别画出以A为起点的DFS生成树和BFS生成树。

6.已知数据六个字母及在通信中出现频率如下表：

ABCDEF

0.150.150.10.10.20.3

把这些字母和频率作为叶子结点及权值，完成如下工作（7分，要有过程）。

（1）画出对应的Huffman树。

（2）计算带权路径长度WPL

（3）求A、B、C、D、E、F的Huffman编码。

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

求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）

三、设计题（30分，每题10分，用C语言写出算法，做在答题纸

±）

1.已知线性表（机朋…,④）以顺序存储结构为存储结构，其类型定义如下：

#defineLIST_INIT_SIZE100〃顺序表初始分配容量

typedefstruct{

Elemtype*elem;〃顺序存储空间基址

intlength;〃当箭隹度（存储元素个数）

JSqList;

设计一个算法，删除其元素值为的结点（假若是唯一的）。并求出其算法的

平均时间复杂度。其算法函数头部如下：

StatusListDelete（Sqlist&L,Elemtypex）

2.设顺序栈如左图所示。

其中结点定义如下：

typedefstruct{

Elemtype*base;〃栈底指针

Elemtype*top;〃栈顶指针

JStack;

设计算法，将栈顶元素出栈并存入e中.base

3.设二叉链树的类型定义如下：

typedefintElemtype;

typedefstructnode{

Elemtypedata;

structnode*lchild,*rchild;

JBinNode,*BinTree;

试写出求该二叉树叶子结点数的算法：

StatusCountLeaves(BinTree&root,int&n)

{//nisthenumberofleaves

答案:

选择题(每题1分)

1、C2、D3、A4、D5、C6、D7、A8、B9、CIO、C

一、填空题

1.设计、实现

2.特殊、栈顶

3.LOC(al)+(i-l)*L

4.p->next=q->next;q->next->prior=p;q->next=p;p->prior=q;

5.n(n-l)/2>n-1

6.ADCBFEG.ABCDEFFG

7.ABC、ABC

二、应用题

1(1)Hash表(4分)

地址0123456789101112

关键安132164572282412

探测次数171231311

(2)查找成功的平均查找长度：(1分)

(5*1+1*2+2*3+1*7)/9=20/9

查找不成功的平均查找长度：(1分)

(2+1+9+8+7+6+5+4+3+2+1)/13=

2(1)、构造(3分)

(2)、1014151920212256(2分)

(3)、(3分)

3、（5分,每行0.5）

ijV

13-5

246

337

413

42-1

5218

558

4、初始关键字:[18]12255318

第一趟：[12^^8]255318

第二趟：[121824]早18

第二趟：[12182553]18

第四趟：[1218"53]（4分）

O(n2)(1分)。

5、7分

(1)4分

(2)4分

6、⑴3分

F

ABCD

(2)WPL=O.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)

(3)A：010B：OilC