数据结构复习题二及答案Word文档格式.docx
《数据结构复习题二及答案Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构复习题二及答案Word文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
（A）1（B）n（C）nlog2n（D）n2
5．设一组初始关键字记录关键字为（20，15，14，18，21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为（）。
（A）10，15，14，18，20，36，40，21
（B）10，15，14，18，20，40，36，21
（C）10，15，14，20，18，40，36，2l
（D）15，10，14，18，20，36，40，21
6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
（A）O
（1）（B）O（log2n）（C）（D）O（n2）
7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
（A）n，e（B）e，n（C）2n，e（D）n，2e
8.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
（A）n（n-1）（B）n+1（C）n（D）n（n+1）
9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。
（A）快速排序（B）归并排序（C）堆排序（D）插入排序
10.下列四种排序中（）的空间复杂度最大。
（A）插入排序（B）冒泡排序（C）堆排序（D）归并排序
11．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。
（A）20（B）30（C）40（D）45
12．执行一趟快速排序能够得到的序列是（）。
（A）[41，12，34，45，27]55[72，63]
（B）[45，34，12，41]55[72，63，27]
（C）[63，12，34，45，27]55[41，72]
（D）[12，27，45，41]55[34，63，72]
13．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
（A）head==NULL（B）head->
next==NULL
（C）head->
next==head（D）head!
=NULL
14．时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（）。
（A）堆排序（B）冒泡排序（C）希尔排序（D）快速排序
15．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
（A）空或只有一个结点（B）高度等于其结点数
（C）任一结点无左孩子（D）任一结点无右孩子
16．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。
（A）堆排序（B）冒泡排序（C）快速排序（D）希尔排序
17．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。
（A）3（B）4（C）5（D）6
18．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。
（A）O（n）（B）O（n2）（C）O（n1/2）（D）O（1og2n）
19．二路归并排序的时间复杂度为（）。
（A）O（n）（B）O（n2）（C）O（nlog2n）（D）O（1og2n）
20.深度为k的完全二叉树中最少有（）个结点。
（A）2k-1-1（B）2k-1（C）2k-1+1（D）2k-1
21.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。
（A）front->
next=s；
front=s；
（B）s->
next=rear；
rear=s；
（C）rear->
（D）s->
next=front；
22.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。
（A）O（n+e）（B）O（n2）（C）O（ne）（D）O（n3）
23.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
（A）98（B）99（C）100（D）101
24.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。
25.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。
（A）第i行非0元素的个数之和（B）第i列非0元素的个数之和
（C）第i行0元素的个数之和（D）第i列0元素的个数之和
26．下列程序段的时间复杂度为（）。
for（i=0；
m；
i++）for（j=0；
j<
t；
j++）c[i][j]=0；
j++）for（k=0；
k<
n；
k++）c[i][j]=c[i][j]+a[i][k]*b[k][j]；
（A）O（m*n*t）（B）O（m+n+t）（C）O（m+n*t）（D）O（m*t+n）
27．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
（A）n-i（B）n+l-i（C）n-1-i（D）i
28．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。
（A）N1-1（B）N2-1（C）N2+N3（D）N1+N3
29．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。
（A）O（n）（B）O（nlog2n）（C）O（n2）（D）O（1og2n）
30．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。
（A）p->
right=s；
s->
left=p；
p->
right->
left=s；
right=p->
right；
s->
（C）p->
31．下列各种排序算法中平均时间复杂度为O（n2）是（）。
（A）快速排序（B）堆排序（C）归并排序（D）冒泡排序
32．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
（A）n-i（B）n-1-i（C）n+l-i（D）不能确定
33．设散列表中有m个存储单元，散列函数H（key）=key%p，则p最好选择（）。
（A）小于等于m的最大奇数（B）小于等于m的最大素数
（C）小于等于m的最大偶数（D）小于等于m的最大合数
34．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。
（A）4（B）5（C）6（D）7
35.设完全无向图中有n个顶点，则该完全无向图中有（）条边。
（A）n（n-1）/2（B）n（n-1）（C）n（n+1）/2（D）（n-1）/2
36.设顺序表的长度为n，则顺序查找的平均比较次数为（）。
（A）n（B）n/2（C）（n+1）/2（D）（n-1）/2
37.设有序表中的元素为（13，18，24，35，47，50，62），则在其中利用二分法查找值为24的元素需要经过（）次比较。
（A）1（B）2（C）3（D）4
38.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。
（A）6（B）11（C）5（D）6.5
39.设有向无环图G中的有向边集合E={<
1，2>
2，3>
3，4>
1，4>
}，则下列属于该有向图G的一种拓扑排序序列的是（）。
（A）1，2，3，4（B）2，3，4，1（C）1，4，2，3（D）1，2，4，3
40.设有一组初始记录关键字序列为（34，76，45，18，26，54，92），则由这组记录关键字生成的二叉排序树的深度为（）。
二、填空殖（每空1分共20分）
1.数据的物理结构主要包括_____________和______________两种情况。
2.设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；
若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。
3.设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。
4.设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。
5.设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。
6.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。
7.__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。
8.设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。
9.不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。
10.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。
11.设一组初始记录关键字为（72，73，71，23，94，16，5），则以记录关键字72为基准的一趟快速排序结果为___________________________。
12.设有向图G中有向边的集合E={<
4，2>
4，3>
}，则该图的一种拓扑序列为____________________。
13.下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。
structrecord{intkey;
intothers;
};
inthashsqsearch（structrecordhashtable[],intk）
{
inti,j;
j=i=k%p;
while（hashtable[j].key!
=k&
&
hashtable[j].flag!
=0）{j=（____）%m;
if（i==j）return（-1）;
if（_______________________）return（j）;
elsereturn（-1）;
14.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。
typedefstructnode{intkey;
structnode*lchild;
structnode*rchild;
}bitree;
bitree*bstsearch（bitree*t,intk）
{
if（t==0）return（0）;
elsewhile（t!
=0）
if（t->
key==k）_____________;
elseif（t->
key>
k）t=t->
lchild;
else_____________;
15．for（i=1，t=1，s=0；
i<
i++）{t=t*i；
}的时间复杂度为_________。
16．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。
17．设有向图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>
}，则给出该图的一种拓扑排序序列__________。
18．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。
19．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。
20．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。
21．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。
22．简单选择排序和直接插入排序算法的平均时间复杂度为___________。
23．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。
24.散列表中解决冲突的两种方法是_____________和_____________。
25.设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1）s->
next=___________；
2）p->
3）t=p->
4）p->
data=___________；
5）s->
data=t；
26.设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。
27.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。
28.对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。
29.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。
30.设一组初始记录关键字序列为（20，12，42，31，18，14，28），则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。
31.设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。
32.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。
33.设一组记录关键字序列为（80，70，33，65，24，56，48），则用筛选法建成的初始堆为_______________________。
34.设无向图G（如右图所示），则其最小生成树上所有边的权值之和为_________________。
三、应用题
1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。
2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，试：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
`0123456
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。
4.在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。
A01234567
data
60
50
78
90
34
40
next
3
5
7
2
4
1
5.请画出下图的邻接矩阵和邻接表。
6.已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={（1,2）3,（1,3）5,（1,4）8,（2,5）10,（2,3）6,（3,4）15,
（3,5）12,（3,6）9,（4,6）4,（4,7）20,（5,6）18,（6,7）25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
7.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。
8.阅读算法，回答问题。
LinkListmynote（LinkListL）
{//L是不带头结点的单链表的头指针
if（L&
L->
next）
q=L；
L=L－>
p=L；
S1：
while（p－>
next）p=p－>
S2：
p－>
next=q；
q－>
next=NULL；
}
returnL；
请回答下列问题：
（1）说明语句S1的功能；
（2）说明语句组S2的功能；
（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。
四、算法设计题
1.设计在单链表中删除值相同的多余结点的算法。
2.设计在顺序有序表中实现二分查找的算法。
3.设计判断二叉树是否为二叉排序树的算法。
4.设计计算二叉树中所有结点值之和的算法。
5.设计将所有奇数移到所有偶数之前的算法。
6.设计判断单链表中元素是否是递增的算法。
数据结构复习题二答案
一、选择题
1-10BBAAABDCCD
11-20DAAADDBACB
21-30CACDBAAACD
31-40DCBCACCDAA
二、填空题
1.顺序存储结构、链式存储结构
2.9，501
3.5
4.出度，入度
5.0
6.e=d
7.中序
8.7
9.O
（1）
10.i/2，2i+1
11.（5，16，71，23，72，94，73）
12.（1，4，3，2）
13.j+1，hashtable[j].key==k
14.return（t），t=t->
rchild
15.O（n）
16.s->
next=p->
next;
next=s
17.（1，3，2，4，5）
18.n-1
19.129
20.F==R
21.p->
lchild==0&
rchild==0
22.O（n2）
23.O（nlog2n），O（n）
24.开放定址法，链地址法
25.p->
next，s->
26.50
27.m-1
28.6，8
29.快速，堆
30.19/7
31.CBDA
32.6
33.（24，65，33，80，70，56，48）
34.8
1.
2.H（36）=36mod7=1;
H１（22）=（1+1）mod7=2;
….冲突
H（15）=15mod7=1;
….冲突H2（22）=（2+1）mod7=3;
H１（15）=（1+1）mod7=2;
H（40）=40mod7=5;
H（63）=63mod7=0;
H（22）=22mod7=1;
（1）0123456
63
36
15
22
（2）ASL=
3.（8,9,4,3,6,1）,10,（12,18,18）
（1,6,4,3）,8,（9）,10,12,（18,18）
1,（3,4,6）,8,9,10,12,18,（18）
1,3,（4,6）,8,9,10,12,18,18
1,3,4,6,8,9,10,12,18,18
4.线性表为：
（78，50，40，60，34，90）
5.邻接矩阵：
邻接表如图11所示：
图11
6.用克鲁斯卡尔算法得到的最小生成树为：
（1,2）3,（4,6）4,（1,3）5,（1,4）8,（2,5）10,（4,7）20
7.如图（7）
图（7）
8.
（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a2,a3,…,an,a1）
typedefintdatatype;
typedefstructnode{datatypedata;
structnode*next;
}lklist;
voiddelredundant（lklist*&
head）
lklist*p,*q,*s;
for（p=head;
p!
=0;
p=p->
{
for（q=p->
next,s=q;
q!
=
升级会员 