《数据结构》期末复习及答案.doc
《《数据结构》期末复习及答案.doc》由会员分享，可在线阅读，更多相关《《数据结构》期末复习及答案.doc（11页珍藏版）》请在冰点文库上搜索。
一、选择题
1、根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A、v1,v2,v3,v5,v4B、v1,v2,v3,v4,v5
C、v1,v3,v4,v5,v2D、v1,v4,v3,v5,v2
2、数据结构被形式地定义为（K,R）,其中K是①的有限集，R是K上的②有限集。
①A、 算法B、数据元素 C、数据操作 D、逻辑结构
②A、 操作 B、映象 C、存储 D、关系
3、在数据结构中，从逻辑上可以把数据结构分成________。
A、动态结构和静态结构 B、紧凑结构和非紧凑结构
C、线性结构和非线性结构D、内部结构和外部结构
4、具有n个顶点的有向图最多有（）条边。
A、nB、n（n-1）C、n（n+1）D、
C、可读性和文档性 D、数据复杂性和程序复杂性
5、计算机算法指的是①，它必须具备输入、输出和②等5个特性。
①A、计算方法 B、排序方法
C、解决问题的有限运算序列 D、调度方法
②A、可执行性、可移植性和可扩充性
B、可行性、确定性和有穷性
C、确定性、有穷性和稳定性
D、易读性、稳定性和安全性
6.下面关于线性表的叙述中，错误的为（ ）
A.顺序表使用一维数组实现的线性表
B.顺序表必须占用一片连续的存储单元
C.顺序表的空间利用率高于链表 ;
D.在链表中，每个结点只有一个链域
7.带头结点的单链表head为空的判断条件是（ ）
A.head=NIL B.head↑.next=NIL
C.head↑.next=head D.head<>NIL
8.队列通常采用两种存储结构是（ ）
A.顺序存储结构和链表存储结构 B.散列方式和索引方式
C.链表存储结构和数组 D.线性存储结构和非线性存储结构
9.深度为5的二叉树至多有（ ）个结点。
A.16 B.32 C.31 D.10
10.设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用（ ）法。
A.冒泡排序 B.快速排序
C.堆排序 D.基数排序
11、线性表采用链式存储时，其地址（）。
A、必须是连续的；B、部分地址必须是连续的；
C、一定是不连续的；D、连续与否均可以。
12、用链表表示线性表的优点是（）。
A、便于随机存取
B、花费的存储空间较顺序存储少
C、便于插入和删除
D、数据元素的物理顺序与逻辑顺序相同
13、某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。
A、单链表
B、双链表
C、单循环链表
D、带头结点的双循环链表
14、一个向量（一种顺序表）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_______。
（易）
A、110B、108C、100D、120
15、不带头结点的单链表head为空的判定条件是______。
A、head==NULL;B、head->next==NULL;
C、head->next==head;D、head!
=NULL;
16、带头结点的单链表head为空的判定条件是______。
A、head==NULL;B、head->next==NULL;
C、head->next==head;D、head!
=NULL;
17、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;
C、s->next=p->next;p=s;D、p->next=s;s->next=p;
18、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行______。
A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;
C、q->next=s;s->next=p;D、p->next=s;s->next=q;
19、非空的循环单链表head的尾结点（由p所指向）满足____。
A、p->next==NULLB、p==NULL
C、p->next==headD、p==head
20、在一个单链表中，若删除p所指结点的后续结点，则执行____。
A、p->next=p->next->next；B、p=p->next;p->next=p->next->next；
C、p->next=p->next;D、p=p->next->next；
21、判定一个循环队列QU（最多元素为m,m==Maxsize-1）为满队列的条件是____。
A、（（rear-front）+Maxsize）%Maxsize==m
B、rear-front-1==mC、front==rearD、front==rear+1
22、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。
A、（rear-front+m）%mB、rear-front+1
C、rear-front-1D、rear-front
23、栈和队列的共同点是____。
A、都是先进后出
B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点
24、栈操作的原则是（）
A、先进先出B、后进先出C、只能进行插入D、只能进行删除
25、在顺序栈中，判断栈s为空的条件是（）
A、t.base==NULLB、st.top==st.stacksize
C、st.top-st.base>=st.stacksizeD、st.top==st.base
26、在顺序栈中，判断栈s满的条件是（）
A、st.base==NULLB、st.top==st.stacksize
C、st.top-st.base>=st.stacksizeD、st.top==st.base
27、串的长度是（）。
（易）
A、串中不同字母的个数B、串中不同字符的个数
C、串中所含的字符的个数D、串中所含字符的个数，且大于0
28、以下叙述中正确的是。
A、串是一种特殊的线性表 B、串的长度必须大于零
C、串中无素只能是字母 D、空串就是空白串
29、串是一中特殊的线性表，其特殊性体现在____。
A、可以顺序存储 B、数据元素是一个字符
C、可以链接存储 D、数据元素可以是多个字符
30、设有两个串p和q，求q在p中首次出现的位置的运算称作____。
A、连接B、模式匹配C、求子串D、求串长
答案：
1、C，B2、D，B3、C4、B，A5、C，B6、D7、B8、A9、A10、C
二、名词解释：
1、数据2、数据元素3、数据对象4、数据结构5、数据类型6、算法
7、压缩存储8、特殊矩阵9、稀疏矩阵10、结点的度11、叶结点12、分支结点
13、双亲结点14、无向图中顶点的度15、有向图中顶点的度
答案：
1、数据——是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称。
2、数据元素——数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理。
3、数据对象：
性质相同的数据元素的集合。
4、数据结构：
相互具有一种或多种关系的数据元素的集合。
5、数据类型：
是具有相同性质的计算机数据的集合及在这个数据上的一组运算，是和数据结构密切相关的概念。
6、算法：
对特定问题求解步骤的一种描述，是有限指令的集合。
7、压缩存储：
为多个值相同的元分配一个存储空间，对零元不分配存储空间。
8、特殊矩阵：
值相同的元素或者是零元素分布的有规律则称为特殊矩阵。
9、稀疏矩阵：
在一个m*n的矩阵中，有t个非0元，其稀疏因子为t/（m*n），如果稀疏因子小于0.05就称为稀疏矩阵。
10、所谓结点的“度”，是指树中一个结点拥有的子树数目。
因此，结点的度也就是该结点的后继结点的个数。
11、树中度为0的结点被称为叶结点。
叶结点也就是终端结点。
12、树中度大于0的结点称为分支结点，或非终端结点。
13、在树中，把一个结点称作是它所有后继结点的双亲结点。
双亲结点有时也被称作父结点。
14、在无向图中顶点vi的“度”，是指与它相邻接的顶点的个数。
15、在有向图中一个顶点vi的度是指它的入度与出度之和。
三、填空题
1、下面程序段的时间复杂度是o（_m*n）______。
O（m*n）
for（i=0;i for（j=0;j a[i][j]=0;
2、下面程序段的时间复杂度是___o（n）____。
O（）
i=s=0；
while（s {
i++; /*i=i+1*/
s+=i; /*s=s+i*/
}
3、下面程序段的时间复杂度是__o（n2）_____。
O（）
s=0;
for（i=0;i for（j=0;j s+=b[i][j];
sum=s;
5、数据元素可以由若干（数据项）组成，（数据元素）是数据的基本单位，（数据项）是数据的最小单位。
（易）
6、数据结构分为两部分，即（逻辑）结构和（物理）结构。
7、数据的存储方式分为（顺序）存储和（链式）存储。
8、顺序存储是一种（随机存取）的存储方式，是用一组（连续）的存储空间存储数据，而链式存储是用一组（任意）的存储空间存储数据。
（易）
9、有一棵树如图6、5所示，回答下面的问题：
⑴这棵树的根结点是____；
⑵这棵树的叶子结点是____；
⑶结点D的度是____；
⑷这棵树的度是____；
⑸这棵树的深度是____；
图6.5一棵树
⑹结点H的子女是____；
⑺结点H的双亲结点是____；
（8）结点N的祖先是________。
答案：
（1）A
（2）EFGIJKLN（3）2（4）4（5）5（6）LMN（7）C（8）ACHM
10、一个图的（邻接矩阵）表示法是唯一的，而（邻接表）表示法是不唯一的。
11、有向图中的结点前驱后继关系的特征是（一个结点可能有若干个前驱，也可能有若干个后继）。
12、二叉树通常有（顺序）存储结构和（链式）存储结构。
13、二叉树有不同的链式存储结构，其中最常用的是（二叉链表）与（三叉链表）。
14、线索二叉树的左线索指向其（某种遍历序列的直接前驱结点），右线索指向其（某种遍历序列的直接后继结点）。
15、遍历一棵二叉树包括访问（根结点）、遍历（左子树）和遍历（右子树）三个方面。
16、在二叉树中，某一结点x在第L层，x若有双亲，其双亲应在（L-1）层；若有孩子，其孩子应在（L+1）层。
17、二维数组A[10…20][5…10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是（1208）。
18、在一个m*n的矩阵中，若a[0][0]是第一个元素，则a[i][j]是第（i*n+j）个元素。
19、在线性表L=（a1,a2,……,an）中，L称为线性表的（名字），n称为线性表的（长度）。
20、在双向链表中，若结点p是结点q的前驱，现要删除结点q，需要完成的操作是（p.next=q.next）；（q.next.prior=q.prior）；
21、空串是（零个字符的串），其长度等于（零）。
22、已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为（v1,v2,v3,v6,v5,v4），其从顶点v1出发的宽度优先搜索序列为（v1,v2,v5,v4,v3,v6）。
v1
v3
v2
v4
v5
v6
v2
v5
v4
v3
v5
^
^
v6
v4
v6
v3
图7.4图G的邻接表
23、对n个元素的序列进行起泡排序时，最少的比较次数是（n-1）。
四、判断题
1、线性表的逻辑顺序与存储顺序总是一致的。
2、顺序存储的线性表可以按序号随机存取。
3、顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。
4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
答案：
1-5×√√√×
6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
7、线性表的链式存储结构优于顺序存储结构。
8、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（易）
答案：
6-10√×√√×
11、线性表中，每一个元素均存在前驱。
12、线性表中，每一个元素均存在后继。
13、线性表中，存在唯一一个被称为第一元素的元素。
14、线性表中，存在唯一一个被称为最后一个元素的元素。
15、线性结构是一种一对一的结构。
答案：
11-15××√√√
1、栈和队列都是限制存取点的线性结构
2、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点。
答案：
1-2√×
1、空串是由空白字符组成的串
2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。
3、串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序执行过程中动态分配得到的。
4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。
5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。
6、广义表的表头一定是列表。
7、广义表的表尾一定是列表。
8、空串的长度为零。
9、广义表的元素即可以是原子，也可以是子表。
10、广义表中的子表与串中的子串的含义一样。
答案：
1-5×√√××6-10×√√√×
1、二叉树中每个结点有两个子女结点，而对一般的树则无此限制，因此二叉树是树的特殊情形。
2、二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。
3、当k≥1时，高度为k的二叉树至多有2k-1个结点。
4、完全二叉树的某结点若无左孩子，则它必是叶结点。
5、若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。
6、存在这样的二叉树，对它采用任何次序的遍历，结果相同。
7、中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。
8、将一棵树转换成二叉树后，根结点没有左子树。
9、由树转换成二叉树，其根结点的右子树总是空的。
10、在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树。
11、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。
12、霍夫曼树一定是满二叉树。
答案：
1-4×××√5-8×√√×9-12√×××
五、简答题：
1、什么是算法，其基本性质是什么？
1、算法是对特定问题求解步骤的一种描述，是有限指令的集合。
其基本性质如下：
1）有穷性：
算法对任意合法的输入均能在有限时间、有限步骤后完成。
2）确定性：
算法的每一步骤的含义都是唯一、确定的，对于相同的输入均能得到相同的输出。
3）可行性：
算法的每一个步骤和指令都应在已实现的算法的基础上完成。
4）输入：
任一个算法必须有0个或多个输入。
5）输出：
任一个算法必须有1个或多个输出。
2、算法的要求是什么？
2、算法的要求是：
1）正确性：
算法能正确描述待求解问题的需求，没有逻辑错误，据此算法书写的程序，对于任何合法的输入，都有得到正确的、说明需求的结果。
2）可读性：
算法应简洁、明晰，易于阅读和理解，便于算法的移植和交流，有利于增加算法的生命力。
3）健壮性：
当输入的数据非法时，算法要能作出适当的处理，不会产生难以预料的结果。
4）高效率性：
一般来说，对同一问题的多种算法，首先选择执行时间相对较短、存储空间相对较少的算法，然后考虑易于实现的算法。
3、结构共分几类？
其各自的性质是什么？
3、结构共分为四类，分别为：
1）集合：
所有元素除共在同一集合外，没有其他关系。
2）线性结构：
元素间是一对一的关系。
3）树型结构：
元素间是一对多的关系。
4）图型结构：
元素间是多对多的关系。
4、请写出下列广义表的表长、表头、表尾。
（1）A=（）
（2）B=（e）（3）C=（a,b,（c,d,e））（4）D=（a,D）
答案：
（1）表长为0，表头为（），表尾为（）
（2）表长为1，表头为e，表尾为（）
（3）表长为3，表头为a，表尾为（b,（c,d,e））
（4）表长为2，表头为a，表尾为（D）
5、试列出图7.8中三种拓扑排序序列。
152364152634156234
6、具有3个结点的二叉树有几种形态，分别为什么？
（易）
7、将左图中的森林转化成二叉树（中）
8.画出图用链表实现树的孩子表示法
答案：
6、具有3个结点的二叉树有五种形态，如图所示：
答案：
7、转化成的二叉树如图：
答案：
8、
六、算法设计题：
1、试写一算法，求随机输入的三个整数的最大值。
答案：
1、intmax（intx,inty,intz）
{intt;
t=x>y?
x:
y;
t=t>z?
t:
z;
returnt;
}
2、计算s=1-2!
+3!
-………..+10!
。
答案：
3、百钱百鸡问题。
main（）
{intx,y,z;
for（x=1;x<20;x++）
for（y=1;y<33;y++）
{z=100-x-y;
if（100==5*x+3*y+z/3.0）
printf（“%d,%d,%d\n”,x,y,z）;
}
}
4．编写一个程序，要求有键盘输入三个数，计算以这三个数为边长的三角形的面积（假定输入的边长是有效的）。
5.有一函数，其函数关系如下，试编程求对应于每一自变量的函数值。
1（x<0）
y=0（x=0）
-1（x>0）
答案：
1、#include“math.h”
*
***
*****
***
*
main（）
{floata,b,c,p,s;
scanf（“%f%f%f”,&a,&b,&c）;
p=（a+b+c）/2;
s=sqrt（p*（p-a）*（p-b）*（p-c））;
printf（“%.2f\n”,s）;
}
2、main（）
{intx,y;
scanf（“%d”,&x）;
if（x<0）y=1;
if（x=0）y=0;
if（x>0）y=-1;
prinft（“%d\n”,y）;
}
6、编写一程序，求的值
7、菱形的输出（前5行）
答案：
1、main（）
{inti,sum=0;
for（i=1;i<=100;i++）sum+=i;
printf（“sum=%d\n”,sum）;
}
2、main（）
{inti,j;
for（i=1;i<=3;i++）
{for（j=1;j<=3-i;j++）printf（““）;
for（j=1;j<=2*i-1;j++）printf（“*”）;
printf（“\n”）;
}
for（i=1;i<=2;i++）
{for（j=1;j<=i;j++）printf（““）;
for（j=1;j<=5-2*i;j++）printf（“*”）;
printf（“\n”）;
}
}
8、从键盘上输入一个大写字母，要求改用小写字母输出。
（中）
9、输入一个圆的半径，求其周长及面积并输出。
答案：
1、main（）
{charc;
scanf（“%c”,&c）;
c=c+32;
printf（“%c\n”,c）;
}
2、#definetPI3.14
main（）
{floatr,s,c;
scanf（“%f”,&r）;
s=PI*r*r;
c=2*PI*r;
printf（“s=%.2f,c=%.2f\n”,s,c）;
}
10、用辗转相除法求两个正整数的最大公约数。
程序如下：
main（）
{intr，m，n，k，t;
seanf（“％d,%d”,&m,＆n）;
if（m{t=m;m=n;n=t;}
k=m*n;r=m%n;
while（r!
=0）
{m=n;n=r;r=m％n;}
升级会员 