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

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐《数据结构》期末考试试题及答案贵州高校理学院数学系信息与计算科学专业

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

(2022-2022学年第2学期)

一、单项挑选题

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

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

2．设S为C语言的语句,计算机执行下面算法时，算法的时光复杂度为（）。

for(i=n-1；i>=0；i--)

for(j=0；jnext;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等于（）

（A）、除根结点之外的全部结点权值之和（B）、全部结点权值之和

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

10．线索二叉链表是利用（）域存储后继结点的地址。

（A）、lchild（B）、data（C）、rchild（D）、root

二、填空题

1．规律结构打算了算法的，而存储结构打算了算法的。

2．栈和队列都是一种的线性表，栈的插入和删除只能在举行。

3．线性表（a1,a2,…,an）的挨次存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为4．已知一双向链表如下(指针域名为next和prior)：

q

p

现将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分)

(1)构造HASH表。

(2)分离求查找胜利和不胜利时的平均查找长度。

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

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

AB

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

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

5．已知一网络的邻接矩阵如下，求从顶点A开头的最小生成树。(8分，要有过程)

ABCDEF??

??∞∞∞∞∞∞356156BA

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

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

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

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

（1）画出对应的Huffman树。（2）计算带权路径长度WPL。

（3）求A、B、C、D、E

、F的Huffman编码。7．已知有如下的有向网：

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

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

1．已知线性表（a1,a2,…,an）以挨次存储结构为存储结构，其类型定义如下：

#defineLIST_INIT_SIZE100//挨次表初始分配容量

typedefstruct{

Elemtype*elem;//挨次存储空间基址

intlength;//当前长度（存储元素个数）

}SqList;

设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时光复杂度。其算法函数头部如下：

StatusListDelete(Sqlist//栈底指针

Elemtype*top;//栈顶指针

}Stack;

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

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

typedefintElemtype;

typedefstructnode{

Elemtypedata;

structnode*lchild,*rchild;

}BinNode,*BinTree;

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

StatusCountLeaves(BinTree&root,int&n)

{//nisthenumberofleaves

……

}

答案：

挑选题（每题1分）

1、C

2、D

3、A

4、D

5、C

6、D

7、A

8、B

9、C10、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分）

（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)

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

第一趟：[1218]255318

其次趟：[121825]5318

第三趟：[12182553]18

第四趟：[1218182553]（4分）O（n2）（1分）。

5、7分

（1）4分

A

B1C

32

（2）4分

5D4

EF

6、(1)3分

（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；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分)

StatusListDelete(Sqlist

for(i=0;ilength;i++)

if(L->elem[i]==x)break;

if(i=L->length)returnERROR;

for(j=i;jlengthi-1;j++)

L->elem[j]=L->elem[j+1];

L->length--;

}（8分）

平均时光复杂度：（2分）

设元素个数记为n，则平均时光复杂度为：

∑=-=-=nininnE12

1)(