昆明理工大学数据结构试题B卷

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐昆明理工大学数据结构试题B卷昆明理工高校试卷（B）

理学院信息与计算科学专业2022级07-08学年上学期

考试科目：算法与数据结构同学姓名：学号：

一、填空题（每空1分，共16分）

1、一个算法应当具有下列特性：、、可行性、0或多个输入、1或多个输出。

2、从规律关系上讲，数据结构主要分为两大类，它们是和。

3、在一个单链表中删除＊P结点时应执行下列操作：

q=p->next;p->data=p->next->data;p->next=;free(q);

4、一个循环队列存于A［M］中，队首队尾指针分离为front和rear，则推断队空的条件为：；推断队满的条件为：。

5、广义表(a,(a,b),d,e,((i,j),k))的长度为，深度为。

6、需要压缩存储的矩阵可分为和两种。

7、在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=。

8、一个无向图有n个顶点e条边，则全部顶点的度之和为。

9、用折半查找举行检索时要求数据文件应当是表，而分块查找要求数据文件应当是表。

10、在对一组记录（50、40、95、20、15、70、60、45、80）举行堆排序时，按照初始记录构成初始大根堆后，最后4条记录为（）。

二、挑选题（每题2分，共40分）

1、组成数据的基本单位是。

A)数据项B)数据类型C)数据元素D)数据变量

2、设一数列的挨次为123456，通过栈结构不行能排成的挨次为。

A）325641B)154623C)243516D)453621

3、有一10阶的对称矩阵，采纳压缩存储方式，以行为主序，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为。

A)13B)33C)18D)40

4、线性表采纳链式存储时，其地址。

A)必需延续B)部分地址必需延续C)一定不延续D)延续与否均可

5、深度为k且有个结点的二叉树称为满二叉树

A)2k-1B)2kC)2k-1D)2k-1

6、中序遍历一棵二叉排序树所得到的结点拜访序列是键值的序列。

A)递增或递减B)递减C)递增D)无序

7、在有n个结点的二叉链表中，值为非空的链域个数为。

A)n-1B)2n-1C)2n+1D)n+1

8、有一个散列表长度为100，采纳除留余数法构造散列函数H(k)=k%P，为使散列函数具有较好性能，P的挑选应是。

A)99B)97C)91D)93

9、已知8个元素（34、76、45、18、26、54、92、65），根据依次插入结点的办法生成一棵二叉排序树，该树的深度为。

A)4B)5C)6D)7

10、在一个单链表中，已知*q结点是*p结点的前趋，若在*q与*p之间插入*s结点，则需执行。

A)q->next=s;s->next=p;B)s->next=p->next;p->next=s;

C)p->next=s->next;s->next=p;D)p->next=s;s->next=q;

11、下面程序的时光复杂度为。

for(i=0;inext->prior=p->prior;p->prior->next=p->next;

B)p->next=p->next->next;p->next->prior=p;

C)p->prior->next=p;p->prior=p->prior->prior;

D)p->prior=p->next->next;p->next=p->prior->prior;

13、循环链表的主要优点是。

A)不再需要头指针B)已知某结点位置后能简单找到其直接前趋

C)在举行插入删除运算时能保证链表不断开

D)从表中随意结点动身都能扫描囫囵链表

14、普通状况下将递归算法转换成非递归算法应当设置。

A)堆栈B)队列C)堆栈或队列D)数组

15、以下说法正确的是。

A)若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点

B)若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点

C)在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点

D)在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点

16、设有13个值，用它们组成一棵哈夫曼树，则该树共有个结点。

A)13B)12C)26D)25

17、若从二叉树的任一结点动身到根的路径上所经过的结点序列按其关键字有序，则该二叉树是。

A)二叉排序树B)哈夫曼树C)堆D)上述结果均不对

18、采纳邻接表存储的图，其深度优先遍历类似于二叉树的。

A)中序遍历B)先序遍历C)后序遍历D)层次遍历

19、下列说法中不正确的是。

A)无向图中的极大连通子图称为链通重量

B)连通图的广度优先遍历普通采纳队列来暂存刚拜访过的结点

C)图的深度优先遍历中普通采纳栈来暂存刚拜访过的结点

D)有向图的遍历不行采纳广度优先遍历

20、下面四种排序中，是不稳定排序法。

A)插入B)冒泡C)二路归并D)堆

三、

应用题（共24分）

1、设有稀疏矩阵A如下，画出该矩阵按行序存放的三元组表。（4分）

4000000500020600000000700??????????

2、已知二叉树的中序遍历序列为ACBDGHFE，后序遍历序列为ABDCFHEG，请画出该

棵二叉树。（4分）

3、已知图G=(V,E)，其中：V={a,b,c,d,e}，E={,,,,,,,

}，请画出图G，并写出其邻接矩阵和邻接表表示。（8分）

4、已知无向网如下图，试用Kruskal算法画出其最小生成树的构造过程。（8分）

四、算法分析与填空（每空2分，共20分）

1、下面程序为在单链表中查找是否存在数据值为X的结点：

JD*dlbcz(JD*h,intx)

{JD*p;p=h;

while()p=p->link;return(p);}2、下面为从带头结点的链队列中删除队首元素并存至*p中：

JD*ldsc(JD*f,JD*r,int*p)

{JD*s;

if(f==r)returnNULL;

s=f->link;;

if(s->link==NULL)r=f;

;free(s);returnr;}

3、下面为中序遍历二叉树的非递归算法：

voidzxbl(JD*r)

{inti=0;JD*p,*s[M];

p=r;

do{while(p!=NULL)

{;p=p->lc;}

if(i>0){;printf(“%c\t”,p->data);

p=p->rc;}

}while(i>0||p!=NULL);}

4、下面为Shell排序算法：

voidshellpx(JDr[],intn)

{JDx;inti,j,k;

k=n/2;

while(k>=1)

{for(;i0);

r[j+k]=x;}

;}

}

5、用二叉链表表示二叉树，其根结点指针为t，下面为用递归算法求其叶子数目：

typedefstructnode

{cha