《数据结构与算法》清华典型例题.docx

《数据结构与算法》清华典型例题.docx

《《数据结构与算法》清华典型例题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》清华典型例题.docx（102页珍藏版）》请在冰点文库上搜索。

《数据结构与算法》清华典型例题

6.3典型例题

一、单项选择题

[例6-1]数据结构用集合的观点可以表示为一个二元组DS＝（D，R）。

其中，D是（①）的有穷集合，R是D上（②）的有限集合。

①A.算法B.数据元素C.数据操作D.逻辑结构

②A.操作B.映像C.存储D．关系

解析：

由数据结构的集合形式化定义可知，本题答案为：

①B；②D。

[例6-2]数据的常用存储结构中不包括（）。

A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构

解析：

数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储

方法和散列存储方法。

由此可知，本题答案为：

B。

[例6-3]算法指的是（①），它必须具备（②）这三个特性。

①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法

②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性

C．确定性、有穷性、稳定性D．易读性、稳定性、安全性

解析：

算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。

它

必须满足以下性质：

输人性、输出性、有穷性、确定性、无二义性和可行性。

由此可知，本

题答案为：

①㈠②B。

[例6-4]在下面的程序段中，对x的赋值语句的执行频度为（）。

for（i=0；i

for（j=0；j

x=x+l：

A．O（2n）B．O（n）C．O（n2）D．O（1bn）

解析：

语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。

本题

中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，

显然此语句的执行次数为n×n＝n2次。

由此可知，本题答案为：

C。

二、填空题

[例6-5]是数据的基本单位，通常由若干个组成，是数据的最小单位。

解析：

本题是基本概念题，知识点为数据结构的相关概念。

本题答案为：

数据元素；数

据项；数据项。

三、应用题

[例6-6]简述数据结构的定义。

解析：

数据结构是指数据元素之间的相互关系，即数据的组织形式。

数据结构通常包

括三个方面的内容，分别是数据的逻辑结构、数据的存储结构（物理结构）和在这些数据上

定义的运算。

用集合的观点可以把数据结构表示为一个二元组DS＝（D，R）。

其中，D是数

据元素的有穷集合，R是D上关系的有限集合。

[例6-7]分析以下程序段的时间复杂度。

for（i=0；i

{

x=x+1；//语句②

for（j=0；j<2*n；j++）//语句③

y++；//语句④

}

解析：

语句的执行频度指的是语句重复执行的次数。

一个算法中所有语句的执行频度之和构成了该算法的运行时间。

在本例算法中，语句①的执行频度是n+l，语句②的执行频度是n，语句③的执行频度是n（2n+2）＝2n2-2n，语句④的执行频度是n（2n+1）＝2n2+n。

该程序段的时间复杂度T（n）＝（n+1）+n+（2n2+2n）+（2n2+n）＝4n2+5n+1＝O（n2）。

实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。

在上例中，语句④为基本操作，其执行频度为2n2+n，因此，

该算法的时间复杂度T（n）＝2n2+n＝O（n2）。

[例6-8]分析以下程序段的时间复杂度。

i=1；

while（i<=m）

i=i*2；

解析：

上述算法的基本操作语句是i＝i*2，设其执行频度为T（n），则有：

2T（n）≤n，即

T（n）≤lbn＝O（lbn）。

因此，该程序段的时间复杂度为O（lbn）。

7.3典型例题

一、单项选择题

[例7-1]在数据结构中，与所使用计算机无关的数据叫（①）结构；链表是一种采用（②）存储结构存储的线性表；链表适用于（③）查找；在链表中进行（④）操作的效率比在线性表中进行该操作的效率高。

①A．存储B．物理C．逻辑D．物理和逻辑

②A．顺序B．网状C．星式D．链式

③A．顺序B．二分法C．顺序及二分法D．随机

④A．二分法查找B．快速查找C．顺序查找D．插入

解析：

本题考查的是基本概念。

本题答案为：

①C；②D；③A；④D。

[例7-2]链表不具备的特点是（）。

A．插入和删除不需要移动元素B．可随机访问任一结点

C．不必预分配空间D．所需空间与其长度成正比

解析：

线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个

结点。

本题答案为：

B。

[例7-3]不带头结点的单链表head为空的判定条件是（）。

A．head＝＝NULLB．head_>next＝＝NULL

C．head_>next＝＝headD．head!

＝NULL

解析：

在不带头结点的单链表head中，head指向第一个数据结点。

空表即该表没有结

点，head＝＝NULL表示该单链表为空。

本题答案为：

A。

[例7-4]带头结点的单链表head为空的判定条件是（）。

A．head＝＝NULLB．head—>next＝＝NULL

C．head—>next＝＝headD．head!

＝NULL

解析：

在带头结点的单链表head中，head指向头结点。

空表即该表只有头结点，head—>next＝＝NULL表示该单链表为空。

本题答案为：

B。

[例7-5]带头结点的循环单链表head中，head为空的判定条件是（）。

A．head＝＝NULLB．head—>next＝＝NULL

C．head—>next＝＝headD．head!

＝NULL

解析：

在带头结点的循环单链表head中，head指向头结点。

空表即该表只有头结点，head—>next＝＝head表示该单链表为空。

本题答案为：

C。

[例7-6]线性表采用链式存储时其存储地址（）。

A．必须是连续的B．部分地址必须是连续的

C．一定是不连续的D．连续不连续都可以

解析：

链式存储采用动态存储，地址一般不连续。

本题答案为：

D。

[例7-7]在双向链表的*p结点前插入新结点*s的操作为（）。

A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior；

B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior；

C．s—>next=p；s—>prior=p—>prior；p—prior=s；p—>prior—>next=s；

D．s—>next=p；s—>prior=p—>prior；p—prior—>next=s；p—>prior=s；

解析：

在双向链表的*p结点前插入新结点*s的操作如图7.12所示，图中虚线为所

作的操作，序号为操作顺序。

本题答案为：

D。

图7.12双向链表插入结点的过程示意图

（例7-8）若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用（）存储方式最节省运算时间。

A．单链表B．双向链表

C．给出表头指针的循环单链表D．给出尾指针的循环单链表

解析：

在链表中插入或删除一个结点，需修改相邻结点的指针域。

上述四个选项中，

只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。

本题答案

为：

D。

[例7-9]若线性表中有2n个元素，算法（）在单链表上实现要比在顺序表上实现效率更高。

A．删除所有值为x的元素B．在最后一个元素的后面插入一个新元素

C．顺序输出前k个元素D．交换其中某两个元素的值

解析：

对于选项A，在单链表上和顺序表上实现的时间复杂度都为O（n），但后者要移动大量的元素，因此在单链表上实现效率更高。

本题答案为：

A。

（例7-10）在长度为n的（）上，删除第一个元素，其算法复杂度为O（n）。

A．只有表头指针的不带头结点的循环单链表

B．只有尾指针的不带表头结点的循环单链表

C．只有表尾指针的带头结点的循环单链表

D．只有尾指针的带表头结点的循环单链表

解析：

本题答案为：

A。

具体算法如下：

linklist*delfirst（linklist*h）

{

Linklist*p＝h；

while（p—>next!

＝h）//找到表尾结点

p＝p—>next；

p—>next=h—>next；

free（h）；

returnp一>next；//返回头指针

}

二、填空题

[例7-11]在单链表中结点*p后插入结点*s的指令序列为；。

解析：

在单链表中结点*p后插入结点*s，即将*p的后继结点变为*s的后继结点，

*s则成为*p的后继结点。

操作指令序列为：

s—>next＝p—>next；p—>next＝s。

[例7-12]在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为

和；而根据指针的链接方式，链表又可分为和。

解析：

本题答案为：

单链表；多重链表；循环链表；普通链表（非循环链表）。

[例7-13]在单链表中，要删除某一个指定的结点，必须找到该结点的结点。

解析：

由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指

向该结点的后继结点。

本题答案为：

前驱。

[例7-14]在一个长度为n的顺序表中删除第i（0≤i≤n一1）个元素，需向前移动个元素。

解析：

需将第i个元素后的元素依次前移一个位置，总共移动（n-1）-（i+1）+1个元素。

本题答案为：

n-i-1。

[例7-15]在一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是；在给定值为x的结点后插入一个新结点的时间复杂度是。

解析：

在*p结点后插入一个新结点*s的操作是：

s—>next＝p—>next；p—>next＝

s；其时间复杂度为0

（1）。

在给定值为x的结点后插入一个结点，首先要找到该结点，然后再进行插入。

找到该

结点的时间复杂度为O（n），插入的时间复杂度为O

（1）。

本题答案为：

O

（1）；O（n）。

三、应用题

（例7-16）设A是一个线性表（a0，a1，…，ai，…，an-1），采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?

若元素插在ai和ai+1之间

（0≤i≤n-1）的概率为

，则平均每插入一个元素所需要移动的元素个数是多少?

解析：

在等概率情况下，平均每插入一个元素需要移动的元素个数为：

若元素插在ai和ai+l之间（0≤i≤n-1）的概率为

，则平均每插入一个元素所需

要移动的元素个数为：

（例7-17）简述线性表采用顺序存储方式和链式存储方式的优缺点。

解析：

顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。

链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。

[例7-18]若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?

为什么?

解析：

应采用链式结构来存储该线性表。

采用链式存储结构来存储线性表，在进行插

入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平

均移动指针域的次数为表长的一半；而采用顺序存储结构存储线性表，在进行插入和删除

操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。

因为指针域的移动

操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。

（例7—19）

（1）写出在双向链表中的结点*p前插入一个结点*s的语句序列。

（2）写出判断带头结点的双向循环链表L为空表的条件。

解析：

（1）s—>prior＝p—>prior；p—>prior—>next＝s；

s—>next＝p；p—>prior＝s；

（2）（L＝＝L—>next）&&（L＝＝L—>prior）

[例7-20]链表所表示的元素是否是有序的?

如果有序，则有序性体现在何处?

链表所表示的元素是否一定要在物理上是相邻的?

有序表的有序性又如何理解?

解析：

链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。

链表所表示的元素在物理上不一定相邻。

有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。

四、算法设计题

（例7-21）编写一个算法，将一个带头结点的单链表逆转。

要求在原链表空间上进行逆转，即不允许构造新的链表结点；

解析：

从单链表的一种构造方法——头插法中可以得知，该方法构造的线性表中结点的顺序与插人次序相反。

因此我们可以将表结点从前往后逐个拆下并用头插法插人新表，所构造的单链表即为原表的逆转。

具体算法如下：

linklist*reverse（1inklist*h）

{

linklist*p，*q，*r；

p＝h—>next；

h—>next=NULL；//构造空表

while（p!

＝NULL）

{

q=p；//拆下结点

p=p—>next；

q—>next=h—>next；//用头插法插入

h—>next=q；

}

returnh；

}

（例7-22）已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。

解析：

要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个

大于等于x的元素之前。

应先在表中找到该位置，然后后移该元素，空出一个位置，再将x

插入。

具体算法如下：

insert（sqlist*La，datatypex）//La为指向顺序表的指针

{

inti=0，j；

while（i<=La—>last）//查找插入位置i

{

if（x<=La—>data[i]）

break；

i++；

}

for（j=La—>last+1；j>i；j--）//后移所有大于等于x的元素

La—>data[j]=La—>data[j-1]；

La—>data[i]＝x；//将x插入

La—>last++；//表长度加1

}

（例7-23）用顺序表A、B表示集合，编写算法求集合A和集合B的交集C（假设A、B表内无重复元素）。

’

解析：

求C＝A∩B，C中元素是A、B中的公共元素。

对于表A中的每个元素，在表B中扫描，若有与它相同的元素，则为交集元素，将其放到C中。

具体算法如下：

intersection（sqlistA，sqlistB，sqlist*C）

{

inti，j，k＝0；

for（i＝0；i<＝A．1ast；i++）

{

j=0；

while（j<＝B.1ast&&A.dara[i]!

＝B.data[j]

j++；

if（j<＝B.1ast）//表示A.data[i]在B中

C—>data[k++]＝A.data[i]

}

C—>last=k—l；//修改表长度

}

[例7-24]编写一个算法，计算在头指针为head的单链表中数据域值为x的结点个数。

解析：

先设一计数器n，初值为0。

然后遍历链表中的每个结点，每遇到一个结点都需

要判断其数据域值是否为x，如果是，计数器n加1。

遍历完成后计数器n的值就是所求的

结点数。

具体算法如下：

intcount（linklist*head,datatypex）

{

intn=0；

linklist*p；

p=head；

while（p!

=NULL）

{

if（p—>data==x）

n++;

p=p—>next；

}

returnn；

}

（例7-25）用单链表La、Lb表示集合A、B，编写算法求集合A和集合B的差集C，

并用链表Lc表示（假设A、B内无重复元素）。

解析：

根据集合运算规则可知，集合A—B中包含所有属于集合A而不属于集合B的

元素。

具体做法是：

从头到尾扫描单链表La，并判断当前元素是否在单链表Lb中；若不

在，则将其插入单链表Lc中。

具体算法如下：

linklist*difference（linklist*La,linklist*Lb）

{

linklist*Lc,*pa,*pb,*s,*r；

pa=La—>next

Lc=（linklist*）malloc（sizeof（linklist））;

r=Lc;

while（pa!

=NULL）

{

pb=Lb—>next;

while（phb!

=NULL&&pb—>data!

=pa—>data）

pb=pb—>next；

if（pb==NULL）

{

s=（linklist*）malloe（sizeof（linklist））;

s—>data=pa—>data；

r—>next=s；

r—s；

}

pa=pa—>next；

}

r—>next=NULL；

returnLc；

}

（例7-26）已知两个头指针分别为La和Lb的单链表，它们的元素按值递增有序。

编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。

解析：

由于题目要求不开辟另外的链表空间，所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。

从头到尾逐个比较La和Lb表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。

当La或Lb为空后，把另一个链表余下的结点链接到新表的末尾。

具体算法如下：

linklist*union（linklist*La,linklist*Lb）

{

linklist*pa,*pb,*r；

pa=La—>next；

pb=Lb—>next；

r=La；//以*La为新表头结点，r为新表尾指针

free（Lb）;//释放Lb表头结点

while（pa!

=NULL&&pb!

=NULL）

{

if（pa—>datadata）

{

r=pa;

pa=pa—>next；

}

elseif（pa—>datadata）

{

r—>next=pb；

r=pb；

pb=pb—>next;

r—>next=pa；

}

else//pa->data==Pb—>data的情况

{

r=pa；//将原La表结点插入，原Lb表结点删除

pa=pa—>next；

s=pb；

pb=pb—>next；

free（s）；

}

}

if（pa==NULL）//将Lb表剩余结点链到新表

r—>next=pb；

returnLa；//返回新表头结点地址

}

（例7-27）设计——个将循环双链表中结点*p与其后继结点交换位置的算法。

解析：

本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。

具体算法如下：

intswap（dlinklist*p）

{

dlinklist*q；

if（p—>next==p—>prior）//只有一个数据结点，不能交换

return0；//交换失败

q=p—>next；//q指向*p的后继

p—>next=q—>next；//删除*q

q—>next—>prior=p；

q—>prior=p—>prior；//把*q插入*p前

q—>next=p；

p—>prior—>next=q；

p—>prior=q；

return1；//交换成功

}

8.3典型例题

一、单项选择题

[例8-1]在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top为栈顶指针，则向栈中压入一个元素时top的变化是（）。

A．top不变B．top=nC．top=top-1D．top=top+1

解析：

本题答案为：

C。

（例8-2）一个栈的进栈序列是a，b，c，d，e，则不可能的出栈序列是（）。

A．edcbaB．decbaC。

dceabD．abcde

解析：

栈的特点是先进后出。

在选项C中，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈顶到栈底应该是b、a，不可能a先出栈。

本题答案为：

C。

[例8-3]若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若pl＝3，则p2为（）。

A．可能是2B．不一定是2C．可能是1D．一定是1

解析：

当p1＝3时，表示3最先出栈，前面l、2应该在栈中。

此时若出栈，则p2为2；

此时若进栈，则p2可能为3，4，5，…，n的任何一个。

本题答案为：

A。

[例8-4]若一个栈的输入序列为1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。

A．n—iB．n—i—1C．iD．n—i+1

解析：

本题答案为：

D。

（例8-5）栈和队列的共同点是（）。

A．都是先进后出B．都是先进先出

C．只允许在表端点处插入和删除元素D．没有共同点

解析：

栈和队列都是操作受限的线性表，只允许在表端点处进行插入和删除操作。

本

题答案为：

C。

（例8-6）向一个栈顶指针为top的链栈中插入一个s所指的结点时，操作语句序列为（）。

A．top—>next=top；B．s—>next=top—>next；top—>next=s；

C．s—>next＝top；top＝s；D．s—>next=top；top＝top—>next；

解析：

向链栈中插入一个结点，就是在不带头结点的单链表的表头插入一个结点。

本

题答案为：

C。

[例8-7]在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据进行打印。

该缓冲区应该是一个（）结构。

A．栈B．队列C．数组D．线性表

解析：

本题答案为：

B。

（例8-8）一个队列的入队序列是1，2，3，4，则队列的输出序列是（）。

A．4，3，2，1B．1，2，3，4C．1，4，3，2D．4，1，3，2

解析：

本题答案为B。

[例8-9]判断一个循环队列Q为满队列的条件是（）。

A．Q一>front==Q—>rear

B．Q一>front!

＝Q—>rear

C．