《计算机软件技术基础》课后题概论.docx

《计算机软件技术基础》课后题概论.docx

《《计算机软件技术基础》课后题概论.docx》由会员分享，可在线阅读，更多相关《《计算机软件技术基础》课后题概论.docx（56页珍藏版）》请在冰点文库上搜索。

《计算机软件技术基础》课后题概论

数据结构习题答案

第一节概论

一、选择题

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．下列程序段的时间复杂度是_______。

for（i=1；i<=n；i++）A[i，i]=0；

9．下列程序段的时间复杂度是_______。

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（___）、对数阶O（_____）、线性阶O（____）、平方阶O（___）和指数阶O（___）。

通常认为，具有指数阶量级的算法是____的。

18．数据结构的基本任务是数据结构的_____和_____。

19．数据对象是性质相同的____的集合。

20．抽象数据类型是指一个_____以及定义在该模型上的一组操作。

四、应用题

1．分析下列程序段的时间复杂度。

……

i=1；

WHILE（i<=n）i=i*2；

……

__

2．叙述算法的定义及其重要特性。

3．简述下列术语：

数据，数据元素，数据结构，数据对象。

4．逻辑结构与存储结构是什么关系？

5．将数量级210，n，n2，n3，nlog2n，log2n，2n，n!

，（2／3）n，n2／3按增长率进行排列。

6．设有数据逻辑结构为：

D={k1，k2，k3，…，k9}，R={，，，，，，，，，}，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

7．设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。

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++；

答：

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．线性结构中的一个结点代表一个（）。

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．nB．n/2C．（n-1）/2D．（n+1）/2

8．在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（）。

A．nB．n/2C．（n-1）/2D．（n+1）/2

9．带头结点的单链表为空的条件是（）。

A．head=NULLB．head->next=NULLC．head->next=headD．head!

=NULL

10．非空单循环链表head的尾结点*p满足（）。

A．p->next=NULLB．p=NULLC．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->priorC．p->prior->next->==p->next->priorD．p->next->next==p->prior->prior

18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是（）。

A．rear和rear->next->nextB．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≤i

2．线性结构的基本特征是：

若至少含有一个结点，则除起始结点没有直接____外，其他结点有且仅有一个直接___；除终端结点没有直接___外，其他结点有且仅有一个直接____。

3．所有结点按一对一的邻接关系构成的整体就是____结构。

4．线性表的逻辑结构是____结构，其所含结点的个数称为线性表的_____。

5．在单链表中，删除p所指结点的直接后继的操作是___；p->next=q->next；free（q）；

6．非空的单循环链表head的尾结点（由指针p所指）满足_________。

7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为____；q=p->next；p->next=q->next；free（q）；____。

8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为___，在给定值为x的结点后插入新结点的时间复杂度为____。

9．单链表表示法的基本思想是用______表示结点间的逻辑关系。

10．在顺序表中插入或删除一个元素，平均需要移动____元素，具体移动的元素个数与____有关。

11．在一个长度为n的向量的第i（1≤i≤n+1）个元素之前插入一个元素时，需向后移动_____个元素。

12．在一个长度为n的向量中删除第i（1≤i≤n）个元素时，需向前移动_____个元素。

13．在双链表中，每个结点有两个指针域，一个指向_____，另一个指向______。

14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=___。

15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成_______。

16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是_____s指向的结点。

17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____；r->next=s；r=s；

18．在单链表中，指针p所指结点为最后一个结点的条件是____。

19．在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：

s->next=p；s->prior=p->prior；______=s；p->prior=s；

20．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作：

s->next=_______；p->next=s；temp=p->data；

p->data=______；s->data=____；

四、应用题

1．描述以下三个概念的区别：

头指针，头结点，首元结点（第一个元素结点）。

答：

2．何时选用顺序表，何时选用链表作为线性表的存储结构为宜？

答：

3．在顺序表中插入和删除一个结点需平均移动多少个结点？

具体的移动次数取决于哪两个因素？

答：

4．为什么在单循环链表中设置尾指针比设置头指针更好？

答：

5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p从相应的链表中删除？

若可以，其时间复杂度各为多少？

答：

6．下列算法的功能是什么？

LinkList*testl（LinkList*L）

{//L是无头结点的单链表

LinkList*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；}

答：

7．如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。

在此情况下，应选择哪一种存储结构？

为什么？

答：

8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？

为什么？

答：

五、算法设计题

假设算法中用到的顺序表和链表结构如下：

#definemaxsize100;

Typedefstructnode1{datatypedata[maxsize];intlength}SeqList;

Typedefstructnode2{datatypedata;structnode2*next}LinkedList;

1．试用顺序表作为存储结构，实现将线性表（a0，a1，a2，…an-1）就地逆置的操作，所谓“就地”是指辅助空间为O

（1）。

答：

（1）顺序表的就地逆置

（2）链表的就地逆置

2．设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x插入L中，并使L仍为一个有序表。

答：

3.设单链表L是一个递减有序表，试写一个算法将x插入其中后仍保持L的有序性。

答：

4.试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。

答：

5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。

试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。

答：

6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。

7．单链表L是一个递减有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删结点空间，这里min和max是两个给定的参数。

8．编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B，其头结点指针分别为pa和pb，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。

9．假设以两个元素值递增有序排列的线性表A、B分别表示两个集合，要求另辟空间构造一个线性表C，其元素为两集合的交集，且表C中的元素值也递增有序排列。

用顺序表实现并写出C的算法。

11．假设在长度大于1的单循环链表中，既无头结点也无头指针。

s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。

12．计算带头结点的循环链表的结点个数。

13．已知由单链表表示的线性表中，含有三类字符的数据元素（如：

字母字符、数字字符和其他字符），试编写算法构造三个以循环链表表示的线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

14、己知A、B和C为三个递增有序的线性表，现要求对A表进行如下操作：

删去那些既在B表中出现又在C表中出现的元素。

试对顺序表编写实现上述操作的算法（注：

题中未特别指明同一表中的元素值各不相同）。

15．双循环链表中，设计满足下列条件的算法。

（1）在值为x的结点之前插入值为y的结点。

（2）删除值为x的结点。

16．设有一个双循环链表，其中有一结点的指针为p，编写算法将p与其右边的一个结点进行交换。

17．设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个可访问频度域freq，在链表启用之前，其初始值均为0。

每当链表进行一次LocateNode（L，x）操作时令元素值为x的结点中freq域的值加l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。

试写一符合上述要求的LocateNode操作的算法。

18．给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。

19．根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。

20．约瑟夫环问题：

任给正整数n、k，按下述方法可得排列1，2，…，n的一个置换：

将数字l，2，…，n环形排列，按顺时针方向从1开始计数；计满k时输出该位置上的数字（并从环中删去该数字），然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。

例如，n=10、k=3时，输出的置换是3，6，9，2，7，1，8，5，10。

分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。

第三节栈和队列

一、选择题

1．设有一顺序栈s，元素s1，s2，s3，s4，s5，s6依次入栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（）。

A．2B．3C．5D．6

2．若一个栈的输入序列是a、b、c，则通过入栈、出栈操作可能得到a、b、c的不同排列个数为（）。

A．4B．5C．6