数据结构期末考试复习题及参考答案.doc

该【数据结构期末考试复习题及参考答案 】是由【书犹药也】上传分享，文档一共【72】页，该文档可以免费在线阅读，需要了解更多关于【数据结构期末考试复习题及参考答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第1章绪论

(1)()是数据的基本单位,在计算机程序中一般作为一种整体进行考虑和解决。
【解答】数据元素
(2)()是数据的最小单位,()是讨论数据构造时波及的最小数据单位。
【解答】数据项,数据元素
【分析】数据构造指的是数据元素以及数据元素之间的关系。
(3)从逻辑关系上讲,数据构造重要分为()、()、()和()。
【解答】集合,线性构造,树构造,图构造
(4)数据的存储构造重要有()和()两种基本措施,不管哪种存储构造,都要存储两方面的内容:()和()。
【解答】顺序存储构造,链接存储构造,数据元素,数据元素之间的关系
(5)算法具有五个特性,分别是()、()、()、()、()。
【解答】有零个或多种输入,有一种或多种输出,有穷性,拟定性,可行性
(6)在一般状况下,一种算法的时间复杂度是()的函数。
【解答】问题规模
(7)设待解决问题的规模为n,若一种算法的时间复杂度为一种常数,则表达到数量级的形式为(),若为n*log25n,则表达到数量级的形式为()。
【解答】Ο(1),Ο(nlog2n)
【分析】用大O记号表达算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。

⑴顺序存储构造中数据元素之间的逻辑关系是由()表达的,链接存储构造中的数据元素之间的逻辑关系是由()表达的。
A线性构造B非线性构造C存储位置D指针
【解答】C,D
【分析】顺序存储构造就是用一维数组存储数据构造中的数据元素,其逻辑关系由存储位置(即元素在数组中的下标)表达;链接存储构造中一种数据元素相应链表中的一种结点,元素之间的逻辑关系由结点中的指针表达。
⑵假设有如下遗产继承规则:丈夫和妻子可以互相继承遗产;子女可以继承爸爸或妈妈的遗产;子女间不能互相继承。则表达该遗产继承关系的最合适的数据构造应当是()。
A树B图C线性表D集合
【解答】B
【分析】将丈夫、妻子和子女分别作为数据元素,根据题意画出逻辑构造图。
⑶算法指的是()。
A对特定问题求解环节的一种描述,是指令的有限序列。
B计算机程序C解决问题的计算措施D数据解决
【解答】A
【分析】计算机程序是对算法的具体实现;简朴地说,算法是解决问题的措施;数据解决是通过算法完毕的。因此,只有A是算法的精拟定义。
⑷下面()不是算法所必须具有的特性。
A有穷性B确切性C高效性D可行性
【解答】C
【分析】高效性是好算法应具有的特性。
⑸算法分析的目的是(),算法分析的两个重要方面是()。
A找出数据构造的合理性 B研究算法中输入和输出的关系
C分析算法的效率以求改善 D分析算法的易读性和文档性
E空间性能和时间性能 F对的性和简要性
G可读性和文档性H数据复杂性和程序复杂性
【解答】C,E

(1)算法的时间复杂度都要通过算法中的基本语句的执行次数来拟定。
【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来拟定。
(2)每种数据构造都具有三个基本操作:插入、删除和查找。
【解答】错。如数组就没有插入和删除操作。此题注意是每种数据构造。
(3)逻辑构造与数据元素自身的内容和形式无关。
【解答】对。因此逻辑构造是数据组织的重要方面。
(4)基于某种逻辑构造之上的基本操作,其实现是唯一的。
【解答】错。基本操作的实现是基于某种存储构造设计的,因而不是唯一的。
,并用大O记号表达其执行时间。

【解答】⑴基本语句是k=k+10*i,共执行了n-2次,因此T(n)=O(n)。
⑵基本语句是k=k+10*i,共执行了n次,因此T(n)=O(n)。
⑶分析条件语句,每循环一次,i+j整体加1,共循环n次,因此T(n)=O(n)。
⑷每循环一次,循环变量y加1,最后一次y=T(n),即:
(T(n)+1)2≤n,T(n)=n1/2-1,y=0……T(n)循环体都执行,共T(n)+1次,即n1/2次,因此T(n)=O(n1/2)。
⑸x++是基本语句,因此
(D,R),其中D={1,2,3,4,5,6},
R={<1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}。试画出其逻辑构造图并指出属于何种构造。
【解答】其逻辑构造图如图1-3所示,它是一种图构造。
(x)的算法可根据下列两个公式之一来设计:
⑴A(x)=anxn+an-1xn-1+…+a1x+a0
⑵A(x)=(…((0*x+an)x+an-1)x+…+a1)x)+a0
根据算法的时间复杂度分析比较这两种算法的优劣。
【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算,而第二种算法进行了优化,减少了不必要的乘法运算。
(规定:算法用伪代码和C++描述,并分析最坏状况下的时间复杂度)
⑴对一种整型数组A[n]设计一种排序算法。
⑵找出整型数组A[n]中元素的最大值和次最大值。
学****自测及答案
(),链接存储构造的特点是()。
【解答】用元素在存储器中的相对位置来表达数据元素之间的逻辑关系,用批示元素存储地址的指针表达数据元素之间的逻辑关系。
()。
【解答】强健性
:常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。
【解答】O(1),O(log2n),O(n),O(n2),O(2n)
,从小到大排列。
n,n-n3+7n5,nlogn,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n
【解答】log2n,n1/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!
。
【解答】数据构造是指互相之间存在一定关系的数据元素的集合。而抽象数据类型是指一种数据构造以及定义在该构造上的一组操作。程序设计语言中的数据类型是一种值的集合和定义在这个值集上一组操作的总称。
,试分别画出相应的逻辑构造图,并指出属于何种构造。
⑴A=(D,R),其中D={a1,a2,a3,a4},R={}
⑵B=(D,R),其中D={a,b,c,d,e,f},R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>}
⑶C=(D,R),其中D={a,b,c,d,e,f},R={(d,b),(e,g),(a,b),(b,c),(e,g),(g,h)}
⑷D=(D,R),其中D={1,2,3,4,5,6},
R={(1,2),(1,4),(2,3),(2,4),(3,4),(3,5),(3,6),(4,6)}
【解答】⑴属于集合,其逻辑构造图如图1-4(a)所示;⑵属于线性构造,其逻辑构造图如图1-4(b)所示;⑶属于树构造,其逻辑构造图如图1-4(c)所示;⑷属于图构造,其逻辑构造图如图1-4(d)所示。
。
count=0;x=1;
while(x<=n){
x*=2;
count++;
}
returncount;
【解答】O(log2n)
第2章线性表

⑴在顺序表中,等概率状况下,插入和删除一种元素平均需移动()个元素,具体移动元素的个数与()和()有关。
【解答】表长的一半,表长,该元素在表中的位置
⑵顺序表中第一种元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是()。
【解答】108
【分析】第5个元素的存储地址=第1个元素的存储地址+(5-1)×2=108
⑶设单链表中指针p指向结点A,若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为()。
【解答】p->next=(p->next)->next
⑷单链表中设立头结点的作用是()。
【解答】为了运算以便
【分析】例如在插入和删除操作时不必对表头的状况进行特殊解决。
⑸非空的单循环链表由头指针head批示,则其尾结点(由指针p所指)满足()。
【解答】p->next=head
【分析】如图2-8所示。
⑹在由尾指针rear批示的单循环链表中,在表尾插入一种结点s的操作序列是();删除开始结点的操作序列为()。
【解答】s->next=rear->next;rear->next=s;rear=s;
q=rear->next->next;rear->next->next=q->next;deleteq;
【分析】操作示意图如图2-9所示:
⑺一种具有n个结点的单链表,在指针p所指结点后插入一种新结点的时间复杂度为();在给定值为x的结点后插入一种新结点的时间复杂度为()。
【解答】Ο(1),Ο(n)
【分析】在p所指结点后插入一种新结点只需修改指针,因此时间复杂度为Ο(1);而在给定值为x的结点后插入一种新结点需要先查找值为x的结点,因此时间复杂度为Ο(n)。
⑻可由一种尾指针唯一拟定的链表有()、()、()。
【解答】循环链表,循环双向链表,双向链表

⑴线性表的顺序存储构造是一种()的存储构造,线性表的链接存储构造是一种()的存储构造。
A随机存取B顺序存取C索引存取D散列存取
【解答】A,B
【分析】。
⑵线性表采用链接存储时,其地址()。
A必须是持续的 B部分地址必须是持续的
C一定是不持续的 D持续与否均可以
【解答】D
【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以持续,也可以不持续,甚至可以零散分布在内存中任意位置。
⑶单循环链表的重要长处是()。
A不再需要头指针了
B从表中任一结点出发都能扫描到整个链表;
C已知某个结点的位置后,可以容易找到它的直接前趋;
D在进行插入、删除操作时,能更好地保证链表不断开。
【解答】B
⑷链表不具有的特点是()。
A可随机访问任一元素B插入、删除不需要移动元素
C不必事先估计存储空间D所需空间与线性表长度成正比
【解答】A
⑸若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋,则采用()存储措施最节省时间。
A顺序表B单链表C双向链表D单循环链表
【解答】A
【分析】线性表中最常用的操作是取第i个元素,因此,应选择随机存取构造即顺序表,同步在顺序表中查找第i个元素的前趋也很以便。单链表和单循环链表既不能实现随机存取,查找第i个元素的前趋也不以便,双向链表虽然能迅速查找第i个元素的前趋,但不能实现随机存取。
⑹若链表中最常用的操作是在最后一种结点之后插入一种结点和删除第一种结点,则采用()存储措施最节省时间。
A单链表B带头指针的单循环链表C双向链表D带尾指针的单循环链表
【解答】D
【分析】在链表中的最后一种结点之后插入一种结点需要懂得终端结点的地址,因此,单链表、带头指针的单循环链表、双向链表都不合适,考虑在带尾指针的单循环链表中删除第一种结点,其时间性能是O(1),因此,答案是D。
⑺若链表中最常用的操作是在最后一种结点之后插入一种结点和删除最后一种结点,则采用()存储措施最节省运算时间。
A单链表B循环双向链表C单循环链表 D带尾指针的单循环链表
【解答】B
【分析】在链表中的最后一种结点之后插入一种结点需要懂得终端结点的地址,因此,单链表、单循环链表都不合适,删除最后一种结点需要懂得终端结点的前驱结点的地址,因此,带尾指针的单循环链表不合适,而循环双向链表满足条件。
⑻在具有n个结点的有序单链表中插入一种新结点并仍然有序的时间复杂度是()。
AO(1)BO(n)CO(n2)DO(nlog2n)
【解答】B
【分析】一方面应顺序查找新结点在单链表中的位置。
⑼对于n个元素构成的线性表,建立一种有序单链表的时间复杂度是()。
AO(1)BO(n)CO(n2)DO(nlog2n)
【解答】C
【分析】该算法需要将n个元素依次插入到有序单链表中,而插入每个元素需O(n)。
⑽使用双向链表存储线性表,其长处是可以()。
A提高查找速度B更以便数据的插入和删除
C节省存储空间D不久回收存储空间
【解答】B
【分析】在链表中一般只能进行顺序查找,因此,双向链表并不能提高查找速度,由于双向链表中有两个指针域,显然不能节省存储空间,对于动态存储分派,回收存储空间的速度是同样的。由于双向链表具有对称性,因此,其插入和删除操作更加以便。
⑾在一种单链表中,已知q所指结点是p所指结点的直接前驱,若在q和p之间插入s所指结点,则执行()操作。
As->next=p->next;p->next=s;Bq->next=s;s->next=p;
Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;
【解答】B
【分析】注意此题是在q和p之间插入新结点,因此,不用考虑修改指针的顺序。
⑿在循环双向链表的p所指结点后插入s所指结点的操作是()。
Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;
Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;
Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s
【解答】D
【分析】在链表中,对指针的修改必须保持线性表的逻辑关系,否则,将违背线性表的逻辑特性,图2-10给出备选答案C和D的图解。

⑴线性表的逻辑顺序和存储顺序总是一致的。
【解答】错。顺序表的逻辑顺序和存储顺序一致,链表的逻辑顺序和存储顺序不一定一致。
⑵线性表的顺序存储构造优于链接存储构造。
【解答】错。两种存储构造各有优缺陷。
⑶设p,q是指针,若p=q,则*p=*q。
【解答】错。p=q只能表达p和q指向同一起始地址,而所指类型则不一定相似。
⑷线性构造的基本特性是:每个元素有且仅有一种直接前驱和一种直接后继。
【解答】错。每个元素最多只有一种直接前驱和一种直接后继,第一种元素没有前驱,最后一种元素没有后继。
⑸在单链表中,要获得某个元素,只要懂得该元素所在结点的地址即可,因此单链表是随机存取构造。
【解答】错。要找到该结点的地址,必须从头指针开始查找,因此单链表是顺序存取构造。