计算机软件技术基础所有题目答案自学doc.docx
《计算机软件技术基础所有题目答案自学doc.docx》由会员分享，可在线阅读，更多相关《计算机软件技术基础所有题目答案自学doc.docx（73页珍藏版）》请在冰点文库上搜索。
计算机软件技术基础所有题目答案自学doc
数据结构习题答案
第一节概论
一、选择题
1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着（）。
A．数据元素具有同一的特点~B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等
2．数据结构是一门研究非数值计算的程序设计问题中计算机的（
（1））以及它们之间的（
（2））和运算的学科。
（1）~A．操作对象B．计算方法C．逻辑存储D．数据映像
（2）A．结构~B．关系C．运算D．算法
3．数据结构被形式地定义为（D，R），其中D是（
（1））的有限集合，R是D上（
（2））的有限集合。
（1）A．算法~B．数据元素C．数据操作D．逻辑结构
（2）A．操作B．映像C．存储~D．关系
4．在数据结构中，从逻辑上可以把数据结构分为（）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构~C．线性结构和非线性结构D．内部结构和外部结构
5．线性表的顺序存储结构是一种（）的存储结构。
~A．随机存取B．顺序存取C．索引存取D．Hash存取
6．算法分析的目的是（）。
A．找出数据结构的合理性B．研究算法中的输入和输出的关系~C．分析算法的效率以求改进D．分析算法的易懂性和文档性
7．计算机算法指的是（
（1）），它必须具备输入、输出和（
（2））等五个特征。
（1）A．计算方法B．排序方法~C．解决某一问题的有限运算序列D．调度方法
（2）A．可行性、可移植性和可扩充性~B．可行性、确定性和有穷性C．确定性，有穷性和稳定性D．易读性、稳定性和安全性
8．线性表若采用链表存储结构，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分必须是连续的C．一定是不连续的~D．连续不连续都可以
9．在以下的叙述中，正确的是（）。
A．线性表的线性存储结构优于链式存储结构~B．二维数组是它的每个数据元素为一个线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出
10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是（）。
~A．集合中任何两个结点之间都有逻辑关系但组织形式松散B．线性结构中结点按逻辑关系依次排列形成一条“锁链”C．树形结构具有分支、层次特性，其形态有点像自然界中的树D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
11．以下说法正确的是（）。
A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合~D．数据结构是带有结构的数据元素的集合
二、判断题
╳1．数据元素是数据的最小单位。
√2．数据结构是带有结构的数据元素的集合。
√3．数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。
╳4．数据项是数据的基本单位。
√5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。
√6．数据的物理结构是数据在计算机中实际的存储形式。
╳7．算法和程序没有区别，所以在数据结构中二者是通用的。
╳8．顺序存储结构属于静态结构，链式存储结构属于动态结构。
三、填空题
1．所谓数据的逻辑结构指的是数据元素之间的____逻辑关系_____。
2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容___数据的逻辑结构、数据的存储结构、对数据施加的操作___。
3．数据的逻辑结构包括_____集合结构___、_____线性结构___、____树型结构_____和__图状结构_____四种类型。
4．在线性结构中，开始结点__没有_前驱结点，其余每个结点有且只有__一个_个前驱结点。
5．在树形结构中，根结点只有___一个___，其余每个结点有且只有___一个___前驱结点；叶结点没有___后继__结点，其余每个结点的后继结点可以有__任意个__·
6．在图形结构中，每个结点的前驱结点和后继结点可以有___任意个___。
7．算法的五个重要特性是__可行性___、___确定性___、___有穷性___、___输入__、___输出__。
8．下列程序段的时间复杂度是__O（n）___。
for（i=1；i<=n；i++）A[i，i]=0；
9．下列程序段的时间复杂度是__O（n2）___。
S=0；
for（i=1；i<=n；i++）
for（j=1；j<=n；j++）s=s+B[i,j]；
sum=s；
10．存储结构是逻辑结构的___物理__实现。
11．从数据结构的观点看，通常所说的“数据”应分成三个不同的层次，即__数据__、__数据元素_和__数据项___。
12．根据需要，数据元素又被称为__结点__、__记录__、___元素__或__顶点_。
13．通常，存储结点之间可以有___顺序存储__、____链式存储__、____索引存储__、___散列存储_四种关联方式，称为四种基本存储方式。
14．通常从___确定性___、__可读性_、___健壮性__、_高效性__等几方面评价算法（包括程序）的质量。
15．一个算法的时空性能是指该算法的_时间复杂度和___空间复杂度_，前者是算法包含的__计算量__，后者是算法需要的___存储量__。
16．在一般情况下，一个算法的时间复杂度是__问题规模__的函数。
17．常见时间复杂度的量级有：
常数阶O（__1_）、对数阶O（__log2n___）、线性阶O（__n__）、平方阶O（_n2_）和指数阶O（__2n_）。
通常认为，具有指数阶量级的算法是__不可行__的。
18．数据结构的基本任务是数据结构的__设计__和__实现__。
19．数据对象是性质相同的__数据元素_的集合。
20．抽象数据类型是指一个__数学模型__以及定义在该模型上的一组操作。
四、应用题
1．分析下列程序段的时间复杂度。
……
i=1；
WHILE（i<=n）i=i~2；
……
答：
O（log2n）
2．叙述算法的定义及其重要特性。
答：
算法是对特定问题求解步骤的一种描述，是指令的有限序列。
其中每一条指令表示一个或多个操作。
算法应该具有下列特性：
可行性、确定性、有穷性、输入和输出。
3．简述下列术语：
数据，数据元素，数据结构，数据对象。
答：
数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。
在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。
数据结构是指相互之间存在着一种或多种关系的数据元素的集合。
数据对象是性质相同的数据元素的集合。
4．逻辑结构与存储结构是什么关系？
答：
在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。
逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。
5．将数量级210，n，n2，n3，nlog2n，log2n，2n，n!
，（2／3）n，n2／3按增长率进行排列。
答：
（2／3）n，210，log2n，n2／3，n，nlog2n，n2，n3，2n，n!
6．设有数据逻辑结构为：
D={k1，k2，k3，…，k9}，R={，，，，，，，，，}，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？
答：
图略。
开始结点k1、k2，终端结点k6、k7。
7．设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。
答：
数据逻辑结构为：
D={k1，k2，k3，…，k8}，R={，，，，，，}，其逻辑结构类型为树型结构。
8．分析下列程序的时间复杂度（设n为正整数）。
（1）intrec（intn）
{if（n==1）return
（1）；elsereturn（n~rec（n-1））；}
（2）x=91；y=100；
While（y>0）if（x>10）y--；
（3）i=1；j=0；
while（i+j<=n）
if（i>j）j++；elsei++;
（4）x=n；y=0；
while（x>=（y+1）~（y+1））y++；
答：
（1）O（n）
（2）O
（1）（3）O（n）（4）O（n1/2）
9．设n为正数。
试确定下列各程序段中前面加记号@的语句的频度：
（1）i=1；k=0；
while（i<=n-1）{@k+=10~i；i++；）
（2）k=0；
for（i=1；i<=n；i++）
for（j=i；j<=n：
j++）@k++；
答：
（1）n-1
（2）n+（n-1）+……+1=n（n+1）/2
第二节线性表
一、选择题
1．线性结构中的一个结点代表一个（）。
~A．数据元素B．数据项C．数据D．数据结构
2．线性表L=（a1，a2，…，ai，…，an），下列说法正确的是（）。
A．每个元素都有一个直接前驱和直接后继B．线性表中至少要有一个元素C．表中诸元素的排列顺序必须是由小到大或由大到小的D．~除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
3．顺序表是线性表的（）。
A．链式存储结构~B．顺序存储结构C．索引存储结构D．散列存储结构
4．对于顺序表，以下说法错误的是（）。
~A．顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B．顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C．顺序表的特点是：
逻辑结构中相邻的结点在存储结构中仍相邻D．顺序表的特点是：
逻辑上相邻的元素，存储在物理位置也相邻的单元中
5．对顺序表上的插入、删除算法的时间复杂度分析来说，通常以（）为标准操作。
A．条件判断~B．结点移动C．算术表达式D．赋值语句
6．对于顺序表的优缺点，以下说法错误的是（）。
A．无需为表示结点间的逻辑关系而增加额外的存储空间B．可以方便地随机存取表中的任一结点~C．插入和删除操作较方便D．由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）
7．在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为（）。
A．n~B．n/2C．（n-1）/2D．（n+1）/2
8．在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（）。
A．nB．n/2~C．（n-1）/2D．（n+1）/2
9．带头结点的单链表head为空的条件是（）。
A．head=NULL~B．head->next=NULLC．head->next=headD．head!
=NULL
10．非空单循环链表head的尾结点~p满足（）。
A．p->next=NULLB．p=NULL~C．p->next=headD．p=head
11．在双循环链表的~p结点之后插入~s结点的操作是（）。
A．p->next=s；s->prior=p；p->next->prior=s；s->next=p->next；B．p->next=s；p->next->prior=s；s->prior=p：
s->next=p->next；C．s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；~D．s->prior=p；s->next=p->next；p->next->pror=s；p->next=s；
12.在一个单链表中，已知~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；
13.在一个单链表中，若~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;
14.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用（）存储方式最节省时间。
~A．顺序表B.单链表C．双链表D．单循环链表
15．设rear是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为（）。
A．p=rear；rear=rear->next；free（p）B．rear=rear->next；free（rear）；C．rear=rear->next->next；free（rear）；~D．p=rear->next->next；rear->next->next=p->next；free（p）；
16．在一个单链表中，若删除~p结点的后继结点，则执行（）。
~A．q=p->next；p->next=q->next；free（q）；B．p=p->next；p->next=p->next->next；free（p）；C．p->next=p->next；free（p->next）；D．p=p->next->next；free（p->next）；
17．设指针p指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画。
A．p->prior->next->==p->next->nextB．p->prior->prior==p->next->prior~C．p->prior->next->==p->next->priorD．p->next->next==p->prior->prior
18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是（）。
A．rear和rear->next->next~B．rear->next和rearC．rear->next->next和rearD．rear和rear->next
19．循环链表的主要优点是（）。
A．不再需要头指针了B．已知某个结点的位置后，容易找到它的直接前驱C．在进行插入、删除操作时，能更好地保证链表不断开~D．从表中任一结点出发都能扫描到整个链表
20．在线性表的下列存储结构中，读取元素花费时间最少的是（）。
A．单链表B．双链表C．循环链表~D．顺序表
二、判断题
√1．顺序存储的线性表可以随机存取。
╳2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。
√3．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
╳4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。
√5．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
√6．在单链表中，可以从头结点开始查找任何一个元素。
╳7．线性表的链式存储结构优于顺序存储结构。
√8．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。
╳9．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
╳10．顺序存储方式只能用于存储线性结构。
三、填空题
1．为了便于讨论，有时将含n（n>0）个结点的线性结构表示成（a1，a2，…，an），其中每个ai代表一个__结点_。
a1称为_第一个_结点，an称为__最后一个_结点，i称为ai在线性表中的_位置__。
对任意一对相邻结点ai、ai+1（1≤i2．线性结构的基本特征是：
若至少含有一个结点，则除起始结点没有直接__前驱_外，其他结点有且仅有一个直接__前驱_；除终端结点没有直接__后继_外，其他结点有且仅有一个直接_后继__。
3．所有结点按一对一的邻接关系构成的整体就是__线性__结构。
4．线性表的逻辑结构是__线性_结构，其所含结点的个数称为线性表的___长度_。
5．在单链表中，删除p所指结点的直接后继的操作是__q=p->next；p->next=q->next；free（q）；___·
6．非空的单循环链表head的尾结点（由指针p所指）满足__p->next=head_____。
7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为__p=rear->next；q=p->next；p->next=q->next；free（q）；____。
8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为__O
（1）__，在给定值为x的结点后插入新结点的时间复杂度为__O（n）__。
9．单链表表示法的基本思想是用___指针___表示结点间的逻辑关系。
10．在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与__元素的位置_有关。
11．在一个长度为n的向量的第i（1≤i≤n+1）个元素之前插入一个元素时，需向后移动___n-i+1__个元素。
12．在一个长度为n的向量中删除第i（1≤i≤n）个元素时，需向前移动__n-i__个元素。
13．在双链表中，每个结点有两个指针域，一个指向___前驱__，另一个指向___后继___。
14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=__p->next->next；___。
15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成__单循环链表___。
16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是_删除__s指向的结点。
17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___s->next=r->next__；r->next=s；r=s；
18．在单链表中，指针p所指结点为最后一个结点的条件是__p->next=NULL___。
19．在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：
s->next=p；s->prior=p->prior；__p->prior->next__=s；p->prior=s；
20．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作：
s->next=___p->next__；p->next=s；temp=p->data；
p->data=__s->data___；s->data=__temp_；
四、应用题
1．描述以下三个概念的区别：
头指针，头结点，首元结点（第一个元素结点）。
答：
首元结点是指链表中存储的线性表中的第一个数据元素的结点。
为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。
头指针是指向链表中的第一个结点的指针。
2．何时选用顺序表，何时选用链表作为线性表的存储结构为宜？
答：
从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。
从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。
对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。
3．在顺序表中插入和删除一个结点需平均移动多少个结点？
具体的移动次数取决于哪两个因素？
答：
平均移动表中大约一半的结点，插入操作平均移动n/2个结点，删除操作平均移动（n-1）/2个结点。
具体移动的次数取决于表长和插入、删除的结点的位置。
4．为什么在单循环链表中设置尾指针比设置头指针更好？
答：
单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O
（1）时间内完成，同样在表头进行插入或删除操作也可在O
（1）时间内完成。
但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O（n）。
5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点~p从相应的链表中删除？
若可以，其时间复杂度各为多少？
答：
能删除。
双链表上删除p所指向的结点的时间复杂度为O
（1），单循环链表上删除p所指向的结点的时间复杂度为O（n）。
6．下列算法的功能是什么？
LinkListtestl（LinkListL）
{//L是无头结点的单链表
ListNode~q，~p；
if（L&&L->next）
{q=L；L=L->next；p=L;
while（p->next）p=p->next；
p->next=q;q->next=NULL；}
returnL；}
答：
如果长度大于1，则将首元结点删除并插入到表尾。
7．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。
在此情况下，应选择哪一种存储结构？
为什么？
答：
应选用链式存储结构。
因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。
而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。
8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？
为什么？
答：
应选用顺序存储结构。
因为顺序存储结构存取元素操作的时间复杂度为O
（1）。
五、算法设计题
1．试用顺序表作为存储结构，实现将线性表（a0，a1，a2，…an-1）就地逆置的操作，所谓“就地”是指辅助空间为O
（1）。
答：
（1）顺序表的就地逆置
分析：
分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。
voidSeqreverse（SeqListL）{／／顺序表的就地逆置
for（i=0；j=L.1ength-1；i{t=L.data[i];L.data[i]=L.data[j];L.data[j]=t;}}
（2）链表的就地逆置
分析：
本算法的思想是逐个地把L的当前元素r插入到新的链表头部。
voidLinkedreverse（LinkedListL）{／／链表的就地逆置
p=L->next；L->next=NULL；
while（p!
=NULL）
{r=p，p=p->next；／／r指向当前待逆置的结点，p记下下—个结点
r->next=L—>next；L->next=r；／／放到表头
}}
2．设顺序表L是一个递增（允许有
升级会员 