数据结构复习题答案文档格式.docx
- 文档编号:6514403
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:18
- 大小:44.66KB
数据结构复习题答案文档格式.docx
《数据结构复习题答案文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构复习题答案文档格式.docx(18页珍藏版)》请在冰点文库上搜索。
next=r;
D)s->
next=f;
12.下列说法正确的是()。
A)二叉树中每个结点的度都为2B)二叉树的度为2
C)一棵二叉树的度可小于2D)二叉树中至少有一个结点的度2
13.一棵非空二叉树先序遍历与后序遍历序列正好相反,则该二叉树()。
A)所有的结点均无左孩子B)所有的结点均无右孩子
C)只有一个叶子结点D)是任意一棵二叉树
14.二叉排序树中,键值最小的结点一定()。
A)左指针为空B)右指针为空
C)左右指针均为空D)左右指针均非空
15.n个顶点的强连通图至少有()条边。
A)n-1B)nC)n+1D)n(n-1)
16.在一个有向图中,顶点入度之和与顶点出度之和的比值()。
A)1/2B)1C)2D)4
17.高度为h的二叉树只有度为0和2的结点,则此二叉树至少为( )结点。
A)2*hB)2*h-1C)2*h+1D)h+1
18.设某完全无向图中有n个顶点,则该完全无向图中有()条边。
(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1
19.设某棵二叉树中有2000个结点,则该二叉树的最小高度为()。
(A)9(B)10(C)11(D)12
20.设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。
(A)n-1(B)n(C)n+1(D)2n-1
21.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。
(A)2,3,5,8,6(B)3,2,5,8,6
(C)3,2,5,6,8(D)2,3,6,5,8
22.按照二叉树的定义,具有3个结点的二叉树有()种形态。
A)3B)4C)5D)6
23.下列排序算法中,可能会出现在最后一趟开始之前,所有元素都不在其最终
位置上是().
A)堆排序B)冒泡排序C)快速排序D)插入排序
24.一组记录的排序码为46,79,56,38,40,84。
用堆排序方法建立的初始堆为()。
A)79,46,56,38,40,80B)84,79,56,38,40,46
C)84,79,56,46,40,38D)84,56,79,40,46,38
25.将递归算法转换成对应的非递归算法时,通常需要使用()。
A)栈B)队列C)链表D)树
26.有10个结点的连通无向图,其边数至少有()。
A)8条B)9条C)10条D)11条
27.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。
A)edcbaB)decbaC)dceabD)abcde
28.高度为h的完全二叉树中所包含的结点数至少为()。
A)2*h个B)2h-1个C)2*h+1个D)h+1个
29.设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为()。
(A)O(n)(B)O(nlog2n)(C)O
(1)(D)O(n2)
30.设一棵二叉树的深度为k,则该二叉树中最多有()个结点。
(A)2k-1(B)2k(C)2k-1(D)2k-1
31.设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为()。
(A)n(B)e(C)2n(D)2e
32.在二叉排序树中插入一个结点的时间复杂度为()。
(A)O
(1)(B)O(n)(C)O(log2n)(D)O(n2)
33.设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有()条有向边。
(A)n(B)n-1(C)m(D)m-1
34.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。
(A)3(B)4(C)5(D)8
35.设用链表作为栈的存储结构则退栈操作()。
(A)必须判别栈是否为满(B)必须判别栈是否为空
(C)判别栈元素的类型(D)对栈不作任何判别
36.设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为()。
(A)O
(1)(B)O(log2n)(C)(D)O(n2)
37.设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为()。
(A)n,e(B)e,n(C)2n,e(D)n,2e
38.设某强连通图中有n个顶点,则该强连通图中至少有()条边。
(A)n(n-1)(B)n+1(C)n(D)n(n+1)
39.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。
(A)快速排序(B)堆排序(C)归并排序(D)插入排序
40.下列四种排序中()的空间复杂度最大。
(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序
二、填空题
1.设有n个无序的记录关键字,则直接插入排序的时间复杂度为________,快速排序的平均时间复杂度为_________。
2.设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为_________________________________________________________(设结点中的两个指针域分别为llink和rlink)。
3.根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为____________。
4.深度为k的完全二叉树中最少有____________个结点。
5.设初始记录关键字序列为(K1,K2,…,Kn),则用筛选法思想建堆必须从第______个元素开始进行筛选。
6.设哈夫曼树中共有99个结点,则该树中有_________个叶子结点;
若采用二叉链表作为存储结构,则该树中有_____个空指针域。
7.设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储________个队列元素;
当前实际存储________________个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。
8.设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_______个数据元素;
删除第i个位置上的数据元素需要移动表中_______个元素。
9.设一组初始记录关键字序列为(20,18,22,16,30,19),则以20为中轴的一趟快速排序结果为______________________________。
10.设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为____________。
11.头结点为H的单循环链表为空的条件是__。
12.线性表作为栈时,被称为__。
13.在堆排序、快速排序和归并排序中,若只从最坏情况下排序最快并且要节省内存空间考虑,应选取方法。
14.一棵二叉树有11个度数为0的结点,则该二叉树的二度结点个数为__。
15.平衡二叉树是每个结点的左右子树深度之差的绝对值不超过1的__。
16.关键码序列为21,12,20,35,40,51,87,33,42,90,2,18,34。
步长因子序列为3,1时,一趟希尔排序结果序列为__。
17.顺序存储的线性表相对与链接存储的线性表,其优点是__。
18.就排序的稳定性而言,简单选择排序方法是__。
19.设某无向图G中有n个顶点,用邻接矩阵A作为该图的存储结构,则顶点i和顶点j互为邻接点的条件是________。
20.设无向图对应的邻接矩阵为A,则A中第i上非0元素的个数_________第i列上非0元素的个数(填等于,大于或小于)。
21.for(i=1,t=1,s=0;
i<
=n;
i++){t=t*i;
s=s+t;
}的时间复杂度为_________。
22.设指针变量p指向单链表中结点A,指针变量s指向被插入的新结点X,则进行插入操作的语句序列为__________________________(设结点的指针域为next)。
23.设有向图G的二元组形式表示为G=(D,R),D={1,2,3,4,5},R={r},r={<
1,2>
,<
2,4>
4,5>
1,3>
3,2>
3,5>
},则给出该图的一种拓扑排序序列__________。
24.设无向图G中有n个顶点,则该无向图中每个顶点的度数最多是_________。
25.设二叉树中度数为0的结点数为50,度数为1的结点数为30,则该二叉树中总共有_______个结点数。
26.设F和R分别表示顺序循环队列的头指针和尾指针,则判断该循环队列为空的条件为_____________________。
27.设二叉树中结点的两个指针域分别为lchild和rchild,则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。
28.简单选择排序和直接插入排序算法的平均时间复杂度为___________。
29.快速排序算法的空间复杂度平均情况下为__________,最坏的情况下为__________。
30.散列表中解决冲突的两种方法是_____________和_____________。
31.设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为_________=p;
s->
right=p->
right;
__________=s;
p->
right->
left=s;
(设结点中的两个指针域分别为left和right)。
32.设完全有向图中有n个顶点,则该完全有向图中共有________条有向条;
设完全无向图中有n个顶点,则该完全无向图中共有________条无向边。
33.设关键字序列为(Kl,K2,…,Kn),则用筛选法建初始堆必须从第______个元素开始进行筛选。
34.解决散列表冲突的两种方法是________________和__________________。
35.设一棵三叉树中有50个度数为0的结点,21个度数为2的结点,则该二叉树中度数为3的结点数有______个。
36.高度为h的完全二叉树中最少有________个结点,最多有________个结点。
37.设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟直接插入排序结束后的结果的是__________________________________。
38.设有一组初始关键字序列为(24,35,12,27,18,26),则第3趟简单选择排序结束后的结果的是__________________________________。
39.设一棵二叉树的前序序列为ABC,则有______________种不同的二叉树可以得到这种序列。
40.顺序存储的长度为m的循环队列为空的条件是__。
41.线性表作为队时,被称为__。
42.就快排序和堆排序,若原始记录接近正序或反序,则最好选用方法。
43.在有序表(12、24、36、48、60、72、84)中二分查找关键字72时所需进行的关键字比较次数为__。
44.二叉排序树每个结点的左右子树深度之差的绝对值不超过1,称为__。
45.n阶对称方阵A,以下三角矩阵压缩到一维数组S[n*(n+1)/2]中,若按行序为主存储,则A的第i行第j列元素(i>
=j)对应在S中的存储位置是__。
46.顺序存储的线性表相对与链接存储的线性表,其缺点是__。
47.就排序的稳定性而言,快排序方法是__。
48.设一组初始记录关键字序列为(49,38,65,97,76,13,27,50),则第4趟直接选择排序结束后的结果为_________________。
49.设连通图G中有n个顶点e条边,则对应的最小生成树上有___________条边。
50.设有一组初始记录关键字序列为(50,16,23,68,94,70,73),则将它们调整成初始堆只需把16与___________相互交换即可。
三、解答题
1、序列70,50,18,26,37,45,62,23,46,59,105,按顺序插入结点,建立一棵二叉排序树,然后删除结点37,删除后树高不能增高。
分别画出该二叉排序树及删除结点37后的二叉排序树。
2、对带权图,给出以Prim算法构造最小生成树过程,并计算该树的权。
3、对带权图,给出以克鲁斯卡亚算法构造最小生成树过程,并计算该树的权。
4、正文为“CDDDAABBEECAAECDAACEDDABE”,设计ABCDE这5个字母的哈夫曼编码,使得正文编码最短。
5、给定权值6,12,3,75,40,30,20,65,34,给出按算法建立的哈夫曼树静态三叉链表存储结构。
6、给定权值6,12,3,75,40,30,20,65,34,构建哈夫曼树。
7、先序遍历序列a,b,c,s,g,f,d,e,j,h,k,i和中序遍历序列s,c,b,d,f,e,g,a,h,k,j,i,的二叉树,画出此二叉树,并给出其后序遍历序列。
8、画出深林转化的二叉树,并给出二叉树的先序、中序、后序遍历序列。
9、给定按关键码序列76,42,32,17,73,54,48,62,98,89,92,105,构建小顶堆逐步筛选过程。
V4
V5
V3
V2
V1
10、给定按关键码序列76,42,32,17,73,54,48,62,78,89,2,10,构建大顶堆逐步筛选过程。
11、画出有向图的邻接表和逆邻接表存储示意图。
12、画出图的邻接表存储示意图,并按邻接表给
出深度优先搜索序列和广度优先搜索序列。
13、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7,基本表长度为10,用线性探测法解决冲突,关键码按给出的顺序填入表中。
请画出哈希表,并求等概率情况下查找成功的平均查找长度。
14、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7,基本表长度为10,用二次探测法解决冲突,关键码按给出的顺序填入表中。
15、给定关键码序列30,25,46,12,7,6,21,13,15,42,哈希函数h(key)=key%7,基本表长度为7,用拉链法解决冲突,关键码按给出的顺序填入表中,且总是在链表的第一个结点前插入。
#defineTBLLEN2000
classCQTBL
{public:
voidH1();
private:
MYTYPEt[TBLLEN];
intcnt;
//记录表中元素个数
};
voidCQTBL:
:
H1()
{intlow,high;
MYTYPEm;
for(low=0,high=cnt-1;
low<
high;
)
{
while(low<
high&
&
t[low].m<
60)low++;
t[high].m>
=60)high--;
if(low<
high){m=t[low];
t[low]=t[high];
t[high]=m;
}
}
}
voidMgBAddToA(CQTBL&
b);
MgBAddToA(CQTBL&
b)
{
inti,j,len;
for(i=cnt-1,j=0,len=cnt+t-1;
i>
=0&
j<
t;
len--)
if(t[i].c>
b.t[j].c)t[len]=t[i--];
else
t[len]=b.t[j++];
for(;
j<
j++,len--)t[len]=b.t[j];
cnt=cnt+t;
5.
boolCQTBL:
AddElem(MYTYPE&
a)
{//返回真,添加成功
boolv=false;
if(cnt<
TBLLEN)
{v=true;
for(inti=cnt-1;
a.c<
t[i].c;
i--)t[i+1]=t[i];
t[i+1]=a;
cnt++;
returnv;
6.
typedefstructnode
MYTYPEe;
structnode*next;
}NODETYPE;
classLINKTBL
{public:
voidMg(LINKTBL&
NODETYPEh;
//h头结点,last指向最后一个结点
voidLINKTBL:
Mg(LINKTBL&
NODETYPE*pf,*s,*q;
for(pf=&
h,s=b.h.next;
s!
=NULL;
for(;
pf->
next!
=NULL&
pf->
next->
e.c<
=s->
e.c;
)pf=pf->
next;
q=s;
s=s->
q->
next=pf->
pf->
next=q;
pf=q;
b.h.next=NULL;
7.
NZ()
NODETYPE*s,*q;
for(s=h.next,h.next=NULL;
next=h.next;
h.next=q;
8.
intLINKTBL:
GetNodeNum()
intv=0;
NODETYPE*s;
for(s=h.next;
=&
h;
next)v++;
四、算法设计题
1、对数学成绩,将不及格和及格的学生分成前后两部分,使表前面为不及格的学生,后面为及格的学生。
不要求对这些元素按数学成绩排序,但要求尽量减少交换次数。
2、表A按语文成绩非递减有序,表B按语文成绩非递增有序,将B表学生添加到A表,使A表依然按语文成绩非递减有序,B表不变。
要求移动元素次数不超过两表长度之和。
5、表A按语文成绩非递减有序,向表中添加一个学生,并保持A表的有序性。
6、对两个按语文成绩非递减有序的带头结点单链表A和B,将B表并入A表,而不改变其排序性,并将B表设置为空表。
7、逆置单链表,即将结点顺序为:
H->
a1->
a2->
…->
an,置换为:
an->
a1。
要求,不交换元素值,通过修改结点指针完成。
8、求带头结点的单循环链表中的结点个数,不包括头结点。
9、统计二叉树中叶子结点数目
ELEMe;
structnode*lc,*rc;
}NODE;
classCTREE
intGetLeaNum(NODETYPE*t);
NODEht;
intCTREE:
GetLeaNum(NODE*t)
if(t!
=NULL)
if(t->
lc==NLLL&
t->
rc==NULL)v++;
v+=GetLeaNum(t->
lc)+GetLeaNum(t->
rc);
10、统计二叉树中只有一个子女(度为1)的结点数目
GetOneChildNum(NODE*t)
if((t->
rc!
=NULL)||(t->
lc!
=NLLL&
rc==NULL))v++;
v+=GetOneChildNum(t->
lc)+GetOneChildNum(t->
11、统计二叉树中有两个子女(度为2)的结点数目
GetTwoDgreeNum(NODE*t)
=NULL)v++;
v+=GetTwoDgreeNum(t->
lc)+GetTwoDgreeNum(t->
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)