2022-2022昆明理工大学第一学期数据结构复习试卷试题

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐2022-2022昆明理工大学第一学期数据结构复习试卷试题

数据结构模拟试题

考试科目：数据结构A

1.下面程序的时光复杂为（）

for（i=1，s=0；inext=p;q->next=s;

B.p->next=s->next;s->next=p;

C.q->next=s->next;s->next=p;

D.p->next=s;s->next=q;

7.栈和队列的共同点是（）。

A.都是先进先出

B.都是先进后出

C.只允许在端点处插入和删除元素

D.没有共同点

8.有六个元素6，5，4，3，2，1的挨次进栈，问下列哪一个不是合法的出栈序列？（）

A.543612

B.453126

C.234156

D.346521

9.设C语言数组Data[m+1]作为循环队列SQ的存储空间，front为队头指针，rear为队

尾指针，则执行出队操作的语句为（）

A.front=front+1

B.front=（front+1）%m

C.rear=(rear+1)%(m+1)

D.front=(front+1)%(m+1)

10.一棵二叉树上有50个度为2的结点，其中叶子结点的个数是（）

A．100B．51C．25D．以上答案都不对

11.二叉树的第I层上最多含有结点数为（）

A．2IB．2I-1-1C．2I-1D．2I-1

12.一棵有n个结点的彻低二叉树，按层次从上到下，同一层从左到右挨次存储在一维数

组A[1..n]中，则二叉树中第i个结点（i从1开头用上述办法编号）的右孩子在数组A中的位置是（）

A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)

C．A[i-2]D．条件不充分，无法确定

13.n个结点的线索二叉树上含有的线索数为（）

A．2nB．n－lC．n＋lD．n

14.以下说法错误的是()

A．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

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

C．已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，由于不知道树的根结点是哪一个。

D．在前序遍历二叉树的序列中，任何结点的子树的全部结点都是直接跟在该结点的之后。

15.任何一个带权的无向连通图的最小生成树（）

A．惟独一棵B．有一棵或多棵C．一定有多棵D．可能不存在

16.设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1B．n(n-1)/2C．n(n+1)/2D．0vE．n2

17.要连通具有n个顶点的有向图，至少需要（）条边。

A．n-lB．n+1C．nD．2n

18.当采纳分块查找时，数据的组织方式为()

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必需有序，每块内最大（或最小）的数据组成索引块

C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D.以上都不是

19.下图所示的4棵二叉树,()是平衡二叉树。

ABCD

20.下列排序算法中，在待排序数据已有序时，花费时光反而最多的是()排序。A．冒泡B.希尔

C.迅速

D.堆

二、填空题（每空1分，共20分）

1.一个算法的时光复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

2.线性表的物理结构主要包括_____________和______________两种状况。

3.通常从正确性、易读性、________和高效率等4个方面评价算法（包括程

序）的质量。

4.挨次表的存储密度为________，而链表的存储密度为________。

5.线性表是由n（n≥0）个数据元素所构成的有限序列，其中n为数据元素的个数，称

为线性表的，n=0的线性表称为。

6.线性表中有且仅有一个开头结点和终端结点，除开头结点和终端结点之外，其它每一个

数据元素有且仅有一个，有且仅有一个。

7.栈是_______的线性表，其运算遵循_______的原则。8.5．队列是限制插入只能在表的一端，而删除在表的另一端举行的线性表，其特点是

_______。

9.具有n个结点的二叉树中,一共有2n个指针域,其中惟独

________个用来指向结点的左

右孩子，其余的________个指针域为NULL。

10.树的主要遍历办法有前序、________、________等三种。

11.在挨次表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值

15，需做的关键码比较次数为____.12.在有向图的邻接矩阵表示中，计算第i个顶点入度的办法是______。13.对n个记录的表R[1..n]举行容易挑选排序，所需举行的关键字间的平均比较次数

为。

三、简述题（每题10分共30分）

1．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）

2．已知一个无向图如下图所示，要求用Prim算法生成最小生成树（假设以①为起点，试画出构造过程）。

3．对于给定的一组键值：83，40，63，84，35，96，57，39，79。请画出