1、数据结构与算法清华典型例题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 算法指的是(
2、)，它必须具备( )这三个特性。 A计算方法 B排序方法 C解决问题的步骤序列 D调度方法 A可执行性、可移植性、可扩充性 B可执行性、确定性、有穷性 C确定性、有穷性、稳定性 D易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本题答案为：B。 例6-4 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；in；i+) for(j=0；jn；j+) x=x+l： AO(2n) BO(n) CO(n2) DO(1bn) 解析：语句的执行频度即语句重复执
3、行的次数，属于算法的时间复杂度类题目。本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次，显然此语句的执行次数为nnn2次。由此可知，本题答案为：C。二、填空题例6-5 是数据的基本单位，通常由若干个 组成， 是数据的最小单位。 解析：本题是基本概念题，知识点为数据结构的相关概念。本题答案为：数据元素；数据项；数据项。三、应用题 例6-6 简述数据结构的定义。 解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。用集合的观点可以把数据结构表示为一个二元
4、组DS(D，R)。其中，D是数据元素的有穷集合，R是D上关系的有限集合。 例6-7 分析以下程序段的时间复杂度。 for(i=0；in；i+) /语句 x=x+1； /语句for(j=0；j2*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+1O(n2)。 实际上，可以用算法中
5、基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。在上例中，语句为基本操作，其执行频度为2n2+n，因此，该算法的时间复杂度T(n)2n2+nO(n2)。 例6-8 分析以下程序段的时间复杂度。 i=1； while(inextNULL Chead_nexthead Dhead!NULL 解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结点，headNULL表示该单链表为空。本题答案为：A。 例7-4 带头结点的单链表head为空的判定条件是( )。 AheadNULL BheadnextNULL Chead nexthead Dh
6、ead!NULL 解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，headnextNULL表示该单链表为空。本题答案为：B。 例7-5 带头结点的循环单链表head中，head为空的判定条件是( )。 AheadNULL BheadnextNULL Chead nexthead Dhead!NULL 解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，headnexthead表示该单链表为空。本题答案为：C。 例7-6 线性表采用链式存储时其存储地址( )。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续不连续都可以
7、解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。例7-7 在双向链表的* p结点前插入新结点*s的操作为( )。 Apprior=s；snext=p；ppriornext=s；sprior=pprior； Bpprior=s；ppriornext=s；snext=p；sprior=pprior； Csnext=p；sprior=pprior；pprior=s；ppriornext=s； Dsnext=p；sprior=pprior；ppriornext=s；pprior=s； 解析：在双向链表的 * p结点前插入新结点 * s的操作如图7.12所示，图中虚线为所作的操作，序号为操作
8、顺序。本题答案为：D。图7.12 双向链表插入结点的过程示意图 (例7-8) 若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。 A单链表 B双向链表 C给出表头指针的循环单链表 D给出尾指针的循环单链表 解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。上述四个选项中，只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案为：D。 例7-9 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。 A删除所有值为x的元素 B在最后一个元素的后面插入一个新元素 C顺序输出前k个元素 D交换其中
9、某两个元素的值 解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：A。 (例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。 A只有表头指针的不带头结点的循环单链表 B只有尾指针的不带表头结点的循环单链表 C只有表尾指针的带头结点的循环单链表 D只有尾指针的带表头结点的循环单链表 解析：本题答案为：A。具体算法如下： linklist * delfirst(linklist * h) Linklist * ph； while(p next!h) /找到表尾结点 ppnext； pnext
10、=h next； free(h)； returnp一next； /返回头指针 二、填空题 例7-11 在单链表中结点 * p后插入结点 * s的指令序列为 ； 。 解析：在单链表中结点 * p后插入结点 * s，即将 * p 的后继结点变为 * s 的后继结点，* s 则成为 * p的后继结点。操作指令序列为：snextpnext；pnexts。 例7-12 在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为 和 ；而根据指针的链接方式，链表又可分为 和 。 解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。 例7-13 在单链表中，要删除某一个指定的结点，必
11、须找到该结点的 结点。 解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指向该结点的后继结点。本题答案为：前驱。 例7-14 在一个长度为n的顺序表中删除第i(0in一1)个元素，需向前移动 个元素。 解析：需将第i个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。本题答案为：n-i-1。 例7-15 在一个具有n个结点的单链表，在 * p结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。 解析：在 * p结点后插入一个新结点 * s的操作是：s nextp next；pnexts；其时间复杂度为0(1
12、)。 在给定值为x的结点后插入一个结点，首先要找到该结点，然后再进行插入。找到该结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。本题答案为：O(1)；O(n)。三、应用题 (例7-16) 设A是一个线性表(a0，a1，ai，an-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在ai和ai+1之间(0in-1)的概率为，则平均每插入一个元素所需要移动的元素个数是多少? 解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：若元素插在ai和ai+l之间(0in-1)的概率为，则平均每插入一个元素所需要移动的元素个数为： (例7-17)
13、简述线性表采用顺序存储方式和链式存储方式的优缺点。 解析：顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。 例7-18 若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?为什么? 解析：应采用链式结构来存储该线性表。采用链式存储结构来存储线性表，在进行插入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平均移动指针域的次数为表长的一半；而采用顺序存储
14、结构存储线性表，在进行插入和删除操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。因为指针域的移动操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。 (例719) (1)写出在双向链表中的结点 * p前插入一个结点 *s的语句序列。 (2)写出判断带头结点的双向循环链表L为空表的条件。 解析：(1)spriorpprior；pprior nexts； snextp；ppriors； (2)(LLnext)&(LLprior) 例7-20 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理
15、解? 解析：链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。 四、算法设计题 (例7-21) 编写一个算法，将一个带头结点的单链表逆转。要求在原链表空间上进行逆转，即不允许构造新的链表结点； 解析：从单链表的一种构造方法头插法中可以得知，该方法构造的线性表中结点 的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表， 所构造的单链表即为原表的逆转。 具体算法如下： linklist * reverse(1inklist * h) linklist * p，*q
16、，*r； phnext； hnext=NULL； /构造空表 while(p!NULL) q=p； /拆下结点 p=p next； qnext=hnext； /用头插法插入 hnext=q； return h； (例7-22) 已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。 解析：要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个大于等于x的元素之前。应先在表中找到该位置，然后后移该元素，空出一个位置，再将x插入。 具体算法如下： insert(sqlist *La，datatype x) /La为指向顺序表的指针 int i=
17、0，j； while(ilast) /查找插入位置i if(xdatai) break； i+； for(j=Lalast+1；ji；j-) /后移所有大于等于x的元素 Ladataj=Ladataj-1； Ladataix； /将x插入 Lalast+； /表长度加1 (例7-23) 用顺序表A、B表示集合，编写算法求集合A和集合B的交集C(假设A、B表内无重复元素)。 解析：求CAB，C中元素是A、B中的公共元素。对于表A中的每个元素，在表B中扫描，若有与它相同的元素，则为交集元素，将其放到C中。 具体算法如下： intersection(sqlist A，sqlist B，sqlist
18、* C) int i，j，k0； for(i0；iA1ast；i+) j=0； while(jB.1ast& A.darai!B.dataj j+； if(jdatak+A.datai Clast=kl； /修改表长度 例7-24 编写一个算法，计算在头指针为head的单链表中数据域值为x的结点个数。 解析：先设一计数器n，初值为0。然后遍历链表中的每个结点，每遇到一个结点都需要判断其数据域值是否为x，如果是，计数器n加1。遍历完成后计数器n的值就是所求的结点数。具体算法如下：int count(linklist * head, datatype x) int n=0； linklist *
19、p； p = head； while(p ! = NULL) if(p data = = x) n+; p=pnext； return n； (例7-25) 用单链表La、Lb表示集合A、B，编写算法求集合A和集合B的差集C，并用链表Lc表示(假设A、B内无重复元素)。 解析：根据集合运算规则可知，集合AB中包含所有属于集合A而不属于集合B的元素。具体做法是：从头到尾扫描单链表La，并判断当前元素是否在单链表Lb中；若不在，则将其插入单链表Lc中。具体算法如下：linklist * difference(linklist * La, linklist * Lb) linklist *Lc, *
20、 pa, *pb, * s, * r； pa= Lanext Lc = (linklist * ) malloc (sizeof (linklist) ; r=Lc; while(pa! = NULL) pb=Lb next; while (phb! = NULL & & pb data ! = pa data) pb= pbnext； if(pb = = NULL) s= (linklist * )malloe(sizeof(linklist); s data= padata； rnext=s； rs； pa= panext； rnext = NULL； return Lc； (例7-26)
21、 已知两个头指针分别为La和Lb的单链表，它们的元素按值递增有序。编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。 解析：由于题目要求不开辟另外的链表空间，所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。从头到尾逐个比较La和Lb表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。当La或Lb为空后，把另一个链表余下的结点链接到新表的末尾。 具体算法如下：linklist * union(linklist * La, linklist * Lb) linklist * pa, * pb, *
22、 r； pa = La next； pb= Lbnext； r=La； /以*La为新表头结点，r为新表尾指针 free(Lb); /释放Lb表头结点 while(pa! =NULL & pb! =NULL) if ( pa data data) r=pa; pa= panext； else if(padatadata) r next = pb； r=pb； pb = pb next; rnext= pa； else /pa-data = = Pbdata的情况 r=pa； /将原La表结点插入，原Lb表结点删除 pa = pa next； s=pb； pb = pbnext； free(s)
23、； if(pa=NULL) /将Lb表剩余结点链到新表 rnext=pb； return La； /返回新表头结点地址 (例7-27) 设计个将循环双链表中结点*p与其后继结点交换位置的算法。解析：本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。具体算法如下： int swap(dlinklist * p) dlinklist * q； if(pnext= = pprior) /只有一个数据结点，不能交换 return 0； /交换失败 q=pnext； /q指向 * p的后继 pnext=qnext； /删除 * q qnextprior= p； qprior= pprior；
24、/把*q插入*p前 qnext=p； ppriornext=q； pprior=q； return 1； /交换成功 8.3 典型例题一、单项选择题例8-1 在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top为栈顶指针，则向栈中压入一个元素时top的变化是( )。 Atop不变 Btop=n Ctop=top-1 Dtop=top+1 解析：本题答案为：C。 (例8-2) 一个栈的进栈序列是a，b，c，d，e，则不可能的出栈序列是( )。 Aedcba Bdecba C。dceab Dabcde 解析：栈的特点是先进后出。在选项C中，a、b、c、d进栈，d出栈，c出栈，e进栈，e出
25、栈，此时栈中从栈顶到栈底应该是b、a，不可能a先出栈。本题答案为：C。 例8-3 若已知一个栈的进栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若pl3，则p2为( )。 A可能是2 B不一定是2 C可能是1 D一定是1 解析：当p13时，表示3最先出栈，前面l、2应该在栈中。此时若出栈，则p2为2；此时若进栈，则p2可能为3，4，5，n的任何一个。本题答案为：A。 例 8-4 若一个栈的输入序列为1，2，3，4，n，输出序列的第一个元素是n，则第i个输出元素是( )。 Ani Bni1 Ci Dni+1 解析：本题答案为：D。 (例8-5) 栈和队列的共同点是( )。 A都是先
26、进后出 B都是先进先出 C只允许在表端点处插入和删除元素 D没有共同点 解析：栈和队列都是操作受限的线性表，只允许在表端点处进行插入和删除操作。本题答案为：C。 (例8-6) 向一个栈顶指针为top的链栈中插入一个s所指的结点时，操作语句序列为( )。 Atopnext=top； Bsnext=topnext；topnext=s； Csnexttop；tops； Dsnext=top；toptopnext； 解析：向链栈中插入一个结点，就是在不带头结点的单链表的表头插入一个结点。本题答案为：C。 例8-7 在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据进行打印。该缓冲区应该是一个( )结构。 A栈 B队列 C数组 D线性表 解析：本题答案为：B。 (例8-8) 一个队列的入队序列是1，2，3，4，则队列的输出序列是( )。 A4，3，2，1 B1，2，3，4 C1，4，3，2 D4，1，3，2 解析：本题答案为B。 例8-9 判断一个循环队列Q为满队列的条件是( )。 AQ一front= =Qrear BQ一front!QrearC
