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

《《数据结构与算法》(清华)典型例题》由会员分享，可在线阅读，更多相关《《数据结构与算法》(清华)典型例题（119页珍藏版）》请在装配图网上搜索。

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 算法指的是( ) ，它必须具备( )这三个特性。A

2、 .计算方法 B.排序方法C.解决问题的步骤序列D.调度方法A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性解析 ：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本题答案为：B。 例 6-4 在下面的程序段中，对 x 的赋值语句的执行频度为 ()。for(i=0 ； in ； i+)for( j=0 ； jn ； j+)x=x+l ：A O(2n)B O(n)C O(n 2)D O(1bn)解析：语句的执行频度即语句重复执行的次数

3、，属于算法的时间复杂度类题目。本题中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环 n次，显然此语句的执行次数为nxn=n2次。由此可知，本题答案为：C。二、填空题例6-5 是数据的基本单位，通常由若干个 组成，是数 据的最小单位。解析：本题是基本概念题，知识点为数据结构的相关概念。本题答案为：数据元素；数 据项；数据项。三、应用题例6-6 简述数据结构的定义。解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上定义的运算。用集合的观点可以把数据结构表示为一个二元组DS

4、 = (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)+(2n 2+n) = 4n 2+5n

5、+1 =O(n2)。实际上， 可以用算法中基本操作重复执行的频度作为度量标准， 而被视为基本操作的一般是最深层循环内的语句。在上例中，语句为基本操作，其执行频度为2n2+n ,因此，该算法的时间复杂度 T(n) =2n2+n = O(n 2)。 例 6-8分析以下程序段的时间复杂度。i=1 ；while(inext = = NULLC. head next = = headD. head! = NULL解析： 在不带头结点的单链表head 中， head 指向第一个数据结点。空表即该表没有点，head = NULL表示该单链表为空。本题答案为:A。 例 7-4 带头结点的单链表head 为空的

6、判定条件是()。结点。本题答案为：A. head = NULLB. head next = NULLC. head next = = headD. head! = NULL解析 ： 在带头结点的单链表head 中， head 指向头结点。 空表即该表只有头结点， headnext = = NULL表不该单链表为空。本题答案为： B。 例 7-5 带头结点的循环单链表head 中， head 为空的判定条件是()。A. head = NULLB. head next = NULLC. head next = = headD . head! = NULL解析： 在带头结点的循环单链表head 中，

7、 head 指向头结点。 空表即该表只有头结点，head next = head表示该单链表为空。本题答案为：C。 例 7-6 线性表采用链式存储时其存储地址 () 。A 必须是连续的B 部分地址必须是连续的C. 一定是不连续的D.连续不连续都可以解析 ：链式存储采用动态存储，地址一般不连续。本题答案为： D 。 例 7-7在双向链表的 * p 结点前插入新结点 *s 的操作为 ()。A pprior=s；snext=p；p prior next=s； sprior=p prior；Bp prior=s；p prior next=s；snext=p； sprior=p prior；Csnext

8、=p；sprior=pprior；pprior=s；pprior next=s ；D snext=p；sprior=pprior；pprior next=s ； pprior=s ；解析 ：在双向链表的 * p 结点前插入新结点 * s 的操作如图 7.12 所示，图中虚线为所作的操作，序号为操作顺序。本题答案为： D 。图7.12双向链表插入结点的过程示意图（例7-8）若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用（）存储方式最节省运算时间。A.单链表B.双向链表C.给出表头指针的循环单链表D .给出尾指针的循环单链表解析：在链表中插入或删除一个结点，需修改相邻结点

9、的指针域。上述四个选项中， 只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案 为：Do例7-9若线性表中有2n个元素，算法（）在单链表上实现要比在顺序表上实现效率更高。A.删除所有值为x的元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换其中某两个元素的值解析：对于选项 A,在单链表上和顺序表上实现的时间复杂度都为O（n），但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：Ao（例7-10）在长度为门的（）上，删除第一个元素，其算法复杂度为O（n）。A.只有表头指针的不带头结点的循环单链表B.只有尾指针的不带表头结点的循环单链表C

10、.只有表尾指针的带头结点的循环单链表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的后继结点 八、5* s则成为* p的后继结点。操作指令序列为：s

11、next =pnext ; p next =s。例7-12在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为 _和;而根据指针的链接方式，链表又可分为 和。解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。例7-13 在单链表中，要删除某一个指定的结点，必须找到该结点的 结 点。解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指向该结点的后继结点。本题答案为：前驱。例7-14在一个长度为n的顺序表中删除第i(0 4wn 1)个元素，需向前移动 个元素。解析：需将第i个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个

12、元素。本题答案为：n-i-1。例7-15在一个具有n个结点的单链表，在* p结点后插入一个新结点的时间复杂度是;在给定值为x的结点后插入一个新结点的时间复杂度是 。解析：在* p结点后插入一个新结点* s的操作是：s next = p next ; p next s;其时间复杂度为 0(1)。在给定值为x的结点后插入一个结点，首先要找到该结点，然后再进行插入。找到该结点的时间复杂度为O(n),插入的时间复杂度为 0(1)。本题答案为:0(1) ; O(n)。三、应用题(例7-16) 设A是一个线性表(a。, a1，a,，an-1),采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的

13、元素个数是多少？若元素插在ai和ai+1之间(0iprior =p prior ; p prior next =s;snext =p; p prior =s;(2)(L = = L next)&(L = = L prior) 例 7-20 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的 ?有序表的有序性又如何理解?解析 ： 链表所表示的元素是有序的， 其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。 有序表的有序性不仅在逻辑结构上有序， 而且在物理结构上也有序。四、算法设计题(例 7-21) 编写一个算法，将一个

14、带头结点的单链表逆转。要求在原链表空间上进行逆转，即不允许构造新的链表结点；解析： 从单链表的一种构造方法头插法中可以得知，该方法构造的线性表中结点的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表， 所构造的单链表即为原表的逆转。具体算法如下：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 ；return h

15、 ；（例 7-22） 已知一个顺序表La 的元素按值非递减有序， 编写一个算法将元素x 插人后保持该表仍然按值非递减有序。解析： 要让插入新元素后的顺序表仍然按值非递减有序，必须把x 插入到表中第一个La last+ ；（例7-23） 用顺序表A、B表示集合B 表内无重复元素） 。解析：求C = AnB, C中元素是A、B中的公共元素。对于表中扫描，若有与它相同的元素，则为交集元素，将其放到具体算法如下：/ 后移所有大于等于x 的元素/ 将 x 插入/ 表长度加 1编写算法求集合A和集合B的交集C（假设AA 中的每个元素，在表C 中。大于等于 x 的元素之前。应先在表中找到该位置，然后后移该元

16、素，空出一个位置，再将插入。具体算法如下：insert(sqlist *La ， datatype x)int i=0 ， j ；while(ilast)if(xdatai)break ；i+ ；for( j=La last+1 ； ji ； j-)La dataj=La data j-1 ；La datai =x；然后后移该元素，空出一个位置，再将/La 为指向顺序表的指针/ 查找插入位置 iintersection(sqlist A ， sqlist B ， sqlist * C)int i , j, k = 0 ;for(i =0; i =A. last ; i+)j=0 ；while(

17、 j=B.1ast& A.darai! = B.datajj+ ；if(jdatak+ = A.dataiC last=k l；/ 修改表长度 例 7-24 编写一个算法，计算在头指针为head 的单链表中数据域值为 x 的结点个数。解析： 先设一计数器 n ，初值为 0 。然后遍历链表中的每个结点，每遇到一个结点都需要判断其数据域值是否为 x ，如果是，计数器n 加 1 。遍历完成后计数器n 的值就是所求的结点数。具体算法如下：int count(linklist * head, datatype x)int n=0 ；linklist * p ；p = head ；while(p ! =

18、NULL)if(p data = = x)n+;p=p next ；return n ；(例 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,

19、 * pa, *pb, * s, * r ；pa= La nextLc = (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 ；return Lc ；(例 7-26

20、)已知两个头指针分别为 La 和 Lb 的单链表，它们的元素按值递增有序。编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。解析 ： 由于题目要求不开辟另外的链表空间， 所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。从头到尾逐个比较La 和 Lb 表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。当 La 或 Lb 为空后，把另一个链表余下的结点链接到新表的末尾。具体算法如下：linklist * union(linklist * La, linklist * Lb)linklist *

21、pa, * pb, * r ；pa = La next ；pb= Lb next ；r=La ；/ 以 *La 为新表头结点， r 为新表尾指针free(Lb);/ 释放 Lb 表头结点while(pa! =NULL & pb! =NULL)if ( pa data data)r=pa;pa= pa next ；else if(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 ；p

22、b = pb next ；free(s) ；if(pa=NULL)/ 将 Lb 表剩余结点链到新表r next=pb ；return La ；/ 返回新表头结点地址(例 7-27) 设计个将循环双链表中结点 *p 与其后继结点交换位置的算法。解析：本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。具体算法如下：int swap(dlinklist * p)dlinklist * q ；if(p next= = p prior)/ 只有一个数据结点，不能交换return 0 ；/ 交换失败q=p next ；p next=q next ；q next prior= p ；q prior

23、= p prior ；q next=p ；p prior next=q ；/q 指向 * p/ 删除 * q/ 把 *q的后继*p 前p prior=q ；return 1 ；/ 交换成功8.3 典型例题一、单项选择题 例 8-1 在一个具有n 个单元的顺序栈中， 假设以地址高端作为栈底， 以 top 为栈顶指针，则向栈中压入一个元素时top 的变化是 () 。A top 不变 B top=n C top=top-1 D top=top+1解析 ：本题答案为：C。(例 8-2) 一个栈的进栈序列是a， b ， c， d ， e ，则不可能的出栈序列是()。A edcba B decba C。

24、dceab D abcde解析 ：栈的特点是先进后出。在选项C 中， a 、 b 、 c 、 d 进栈， d 出栈， c 出栈， e 进栈，e出栈，此时栈中从栈顶到栈底应该是b、a,不可能a先出栈。本题答案为：C。例8-3 若已知一个栈的进栈序列是 1, 2, 3,，n,其输出序列为pi, p2, p3, pn,若 pi = 3,则 p2为()。A.可能是2B.不一定是2C.可能是1D. 一定是1解析：当pi= 3时，表示3最先出栈，前面l、2应该在栈中。此时若出栈，则p2为2;此时若进栈，则p2可能为3, 4, 5,，n的任何一个。本题答案为：Ao 例 8-4 若一个栈的输入序列为 1则第

25、i 个输出元素是() 。A n iB n i 1解析 ：本题答案为： D 。(例 8-5) 栈和队列的共同点是(A 都是先进后出2, 3, 4,，n,输出序列的第一个元素是 nC iD ni+1)。B 都是先进先出C.只允许在表端点处插入和删除元素D 没有共同点解析： 栈和队列都是操作受限的线性表，只允许在表端点处进行插入和删除操作。本题答案为： C 。(例 8-6) 向一个栈顶指针为top 的链栈中插入一个s 所指的结点时， 操作语句序列为()。A top next=top ；B s next=top next ； top next=s；C.snext =top ; top=s;D. sne

26、xt=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， 4 C 1 ， 4， 3， 2 D 4， 1， 3，2解析 ：本题答

27、案为 B 。 例 8-9 判断一个循环队列 Q 为满队列的条件是()。A Q 一 front= =Q rearB. Q 一front! =QrearC. Q -front= =(Q-rear+1) %MaxSizeD. Q front! =(Q rear+1) % MaxSize解析 ：由循环队列的结构可知，本题答案为：C。例 8-10 循环队列用数组 A0 ， MaxSize-1 存放其元素，已知其头尾指针分别是front 和 rear ，则当前队列元素个数为 () 。A (rear front + MaxSize) MaxSizeB rear front+1C rear front lD

28、rear front解析： 本题答案为： A 。(例8-11)在一个链队列中，假设f和r分别是队头指针和队尾指针，则插入 s所指结点的运算是()。A. f next =s; f=s;B. r next =s; r=s;C. s next =r; r=s;D. s next =f; f=s;解析 ：向链队列插入一个结点即在单链表表尾插入一个结点。本题答案为： B 。二、判断题例 8-12栈是一种先进先出的线性结构。解析：错误。栈是一种先进后出的线性结构。例 8-13栈和队列都是线性表。解析：正确。栈和队列都是操作受限的线性表。例 8-14 即使对不含相同元素的同一输入序列进行两组不同的但合法的人

29、栈和出栈组合操作，所得的输出序列也一定相同。解析：错误。根据栈的特性，不同的人栈和出栈组合操作所得的输出序列是不相同的。例 8-15 循环队列也存在空间溢出问题。解析：正确。循环队列的引入只是解决了一般顺序队列的假溢问题，并没有解决溢出问题。例8-16循环队列通常用指针来实现队列的头尾相接。解析：错误。循环队列的首尾相接是假想的，事实上并没有实质上的相接，只是在指针时实现了从最大下标向最小下标的过渡。三、填空题例8-17栈的特点是 ,队列的特点是 ,栈和队列都是 c解析：本题答案为：先进后出/FILO（或后进先出/ LIFO）;先进先出/ FIFO;操作受限的线性表。例8-18一个栈的输入序列

30、是：1, 2, 3,则不可能的栈输出序列是 。解析：在栈的操作中，如果输入序列按递增排序号，则在输出序列中，某一个元素后所有比它序号小的元素序号肯定是逆序的。本题答案为：3, 1, 2。例8-19队列是限制了插入操作只能在表的一端，而删除操作只能在表的另一端进行的线性表，其特点是。解析：本题答案为：先进先出。（例8-20）若用不带头结点的单链表来表示链栈s,则创建一个空栈所要执行的操作解析：由链栈的运算过程可知，本题答案为：s=NULL。（例8-21） 在链队列Q中，判定其只有一个结点的条件是 。解析：只有一个结点时，队头指针和队尾指针都指向链表头结点。本题答案为： Qfront =Qrear

31、 。四、应用题例8-22为什么说栈是一种先进后出表 ？解析：栈是一种线性表，如果把所有元素都放人栈中再出栈，则最后插入栈中的那个元素总是最先从栈中移出，因此说栈是一种先进后出表。(例8-23)对于一个栈，按顺序输入 A, B, Co如果不限制出栈时机(即栈中元素不必等所有输入元素都进栈再输出 ) ，试给出全部可能的输出序列。解析 ：本题利用栈的后进先出的特点，有如下几种情况：(1)A进，A出，B进，(2)A进，A出，B进，(3)A进，B进，B出，(4)A进，B进，C进，(5)A进，B进，B出，不可能产生的序列为：ABC 。ACB 。BAC。CBA。BCA。B 出，C进，C 出，产生输出序列C

32、进，B出，C 出，产生输出序列A 出，C进，C 出，产生输出序列C 出，B出，A 出，产生输出序列C 进，C出，A 出，产生输出序列CAB 。(例8-24)有一字符串次序为-3 * y - a/yA2，试利用栈将该字符串次序改为3y-ayA2/* -,写出操作步骤。(可用X代表扫描该字符串并顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈操作)解析 ：实现上述转换的进、出栈操作如下：-进3进3出*进 y进 y出-进-出a进a 出进y 进y 出 A 进 A 出2 进2 出/ 出*出 -出所以操作步骤为： XXSXXSXSXSXXSXSXSSSS 。( 例 8-25) 什么是顺

33、序队列的上溢现象?什么是假溢现象?解决假溢现象的方法有哪解析 ：在队列的顺序存储结构中，设队头指针为 front ，队尾指针为 rear ，队的容量为MaxSize。当有元素加入队列时，若 rear = = MaxSize-1(初始时rear = = -1),则发生队列 的上溢现象，该元素不能加入队列。队列的假溢现象是指队列中尚有空余空间，但此时rear = MaxSize-1 ,元素不能入队。解决队列假溢的方法如下：(1) 建立一个足够大的存储空间，但这样做会造成空间浪费。(2) 采用循环队列方式。原理参照 8.2.5 中的介绍。(3) 采用平移元素的方法，即每当队列中删除一个元素肘，依次移

34、动队中元素，始终使front = = - 1。(例8-26)假设Q0 . 11是一个循环队列，初始状态为 front =rear=0,画出做完下列操作后队列的头、 尾指针的状态变化情况。 若不能人队， 请指出其元素， 并说明理由。d， e， b ， g ， h 入队d ， e 出队1 ， j ， k， l ， m 人队b 出队n ， o ， p ， q 人队解析 ：本题入队和出队的变化如图 8.7 所示。队列没有产生上溢。mJic)元由屏元IK* 4 data) ；/ 元素进栈p=p 一 next ；i+ ；if(n % 2! =0)/n 为奇数p=p next ；while(p!=NULL)

35、x=pop(s) ；/ 元素出栈if(x!=p data)/ 若不相等，则不对称return 0 ；p=p next ；return 1 ；/ 中心对称并与链表中字符从前，方法二： 将字符串中的全部字符进栈， 然后将栈中字符逐个出栈，往后逐个比较。字符串不对称时，返回值为 0；反之，返回值为 1 。int match(1inklist * h)linklist * p ；datatype x ；sqstack s ；initstack(&s) ；/ 初始化p=h next ；/p 指向链表第一个数据结点while(p!=NULL)push(s ， p data) ；/ 元素进栈p=p next

36、 ；p=h next ；/P 重新指向链表第一个数据结点while(p!=NULL)x=pop(s) ；/ 元素出栈if(x!=p data)/ 若不相等，则不对称return 0 ；p=p next ；return 1 ；/ 中心对称 例 8-29 编写一个算法，利用队列的基本运算返回队列中的最后一个元素。解析 ： 假设队列为循环顺序队列。 建立一个临时队列， 将指定队列中所有元素出队并入队到临时队列中，这样指定队列为空，再将临时队列中所有元素出队并入队到指定队列 ( 因 为不能破坏原队列结构，所以需要恢复元素)，最后一个元素即为所求。具体算法如下：datatype lastelem (qu

37、eue * Q)datatype x ；queue tmp Q ；initqueue(& tmp Q)while(! emty (Q)/ 将 Q 中元素放入 tmpQ x=dequeue(Q) enqueue(&tmpQ ， x) ； while (! empty (& tmpQ)/ 将 tmpQ 中元素恢复回 Q x=dequeue ( & tmpQ) ； enqueue(Q ， x) ； return x ； (例 8-30) 假定用一个循环单链表表示队列 (循环链队， 带头结点 ) ， 该队列只设一个队尾指针 rear ，不设队头指针，试编写算法实现下列要求：(1) 向循环链队中插入一个

38、元素x 。(2) 从循环链队中删除一个结点。解析 ：定义本题队列类型如下：typedef structlinklist * rear; Queue2(1) 队列中人队操作是在队尾进行，即在链尾插入一个新结点。void enqueue (Queue2 * Q ， datatype x)linklist * s ；s= (linklist * )malloe (sizeof (linklist) ；/ 建立新结点5 datda=x ；6 next=Q rear next ；/ 将新结点插入队尾q rear next = s ；q rear = s ；(2) 队列中出队操作是在队头进行，即删除链表第

39、一个数据结点。datatype dequeue (Queue2 * Q)datatype x ；linklist * p ；if (Q rear next= =Q rear)/ 队列为空return NULL ；p = Q -rear -next -next ;/p 指向队头结点x=p 一 data ；Q -rear -next -next =p-next删除 * p 结点free (p)/ 返回原队头元素return x ；注意 ：队列和栈都是线性表，它们是操作受限的线性表。在考虑它们的性质、算法的时候可以结合上一章中有关线性表的内容。(3) 典 型 例 题一、单项选择题例 9-1 下列操作

40、中， ()是数组的基本运算。A.插入B.删除C.修改 D.排序解析 ：数组的基本运算只有两种，一种是给定一组下标，存取相应的元素；另一种是给定一组下标，修改相应数据元素中某个数据项的值。本题答案为： C 。(例 9-2) 一维数组和线性表的区别是() 。A.前者长度固定，后者长度可变 B.后者长度固定，前者长度可变C.两者长度均固定D.两者长度均可变解析： 由数组和线性表的定义可知，数组的长度是固定的，而线性表的长度是可变的。本题答案是： A 。例9-3 二维数组A的每个元素是由6个字符组成的字符串， 其行下标i = 0,1, 8,列下标j=1, 2,，10。当A按行存储时，元素 A8 , 5

41、的起始地址与当 A按列存储 时的元素 () 的起始地址相同(设每个字符占一个字节)。A A8 ， 5 B A3 ， 10 C A5 ， 8 D A0 ， 9解析：当A按行存储时，元素A8, 5前共有(8 0)X(10 1+1)+(5 1) = 84个元素。对侯选答案进行类似计算可知，本题答案为： B 。(例9-4) 有一个100 X90的稀疏矩阵，有非零元素(整型)10个。设每个整型数占2个字节，则用三元组表表示该矩阵时，所需的字节数为 ()。A 60B 66C 18 000D 33解析 ：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行数、列数和非零元素个数；主表用手存放

42、非零元素三元组，每个三元组由三个域组成， 分别表示该元素的行号、列号和值。本题答案为：Bo例9-5 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上的所有元素)依次存放于一维数组B0.(n(n+1)/21)中,则在 B中确定ai, j(i(d 1-C 1+1)M+(i 1-C1) xi(例9-12)设上三角矩阵 AnM,将其上三角元素逐行存于数组Bm中，使得Bk=aij,且k=f 1+f 2 (j) +c。试推导出函数f1 (i)、f2和常数Co解析：由前面内容的分析可得k和i、j之间的关系为:i(2n i 1)2n(n 1)2当i w j时当ij时，存放常数c当iwj时，

43、有f1(1)= n 产f2(j)=jC=0当ij时，有3(i尸f2(j)=0n(n 1)C 2四、算法设计题(例913)已知一个nxn矩B$ B按行优先顺序存储在一个一维数组A0.n Xn 1)中，试给出一个算法将原矩阵转置后仍存于数组 A 中。解析 ：矩阵转置是将矩阵中第i 行第 j 列的元素与第j 行第 i 列的元素位置互换。因此，先确定矩阵与一维数组的映射关系：bi, j在一维数组 A中的下标为ixn+j , bi, j在一维数组A中的下标为jxn+i。具体算法如下：void trans （ datatype A， int n）int i ， j ；datatype temp ；for（i=0 ； in ； i+）for（ j=0; jm=A n ；/B 的行数为 A 的列数B n=A m ；/B 的列数为 A 的行数B t=At ；/ 转置前后非零元素个数不变if(B t!0)/ 非 0 矩阵k=0 ；/B 表元素计数器，作当前放置元素指针for(col=0 ； coln ； col+)for(p = 0 ; pt ; p+)if(A datap.j = col)B datak i=A datap.j ；B datak.j=A datap.iBdatak.v = A datap.v ;K+