《算法与数据结构习题答案》由会员分享，可在线阅读，更多相关《算法与数据结构习题答案（15页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构习题答案算法与数据结构习题答案3.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动 n/2 个结点。删除一个结点需平均移动(n-1)/2 个结点。具体的移动次数取决于顺序表的长度 n 以及需插入或删除的位置 i。i 越接近 n 则所需移动的结点数越少。3.12 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：要解决这样
2、的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：/设已建立三个带头结点的空循环链表 A,B,C 且 A、B、C 分别是尾指针.void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)ListNode *p=L-next, *q;while ( p )if ( p-data=a p=p-next;/指向下一结点q-next=A-next;/将字母结点链到 A 表中A-next=q;A=q;else if( p-data=0 p=p-ne
3、xt;/指向下一结点q-next=B-next;/将数字结点链到 B 表中B-next=q;B=q;else /分出其他字符结点q=p-next; p=p-next;/指向下一结点q-next=C-next;/将其他结点链到 C表中C-next=q;C=q;/结束3.13 设有一个双链表，每个结点中除有 prior、data 和 next 三个域外，还有一个访问频度域 freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次 LocateNode(L,x)运算时，令元素值为 x 的结点中 freq 域的值加 1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是
4、靠近表头。试写一符合上述要求的 LocateNode 运算的算法。 解：LocateNode 运算的基本思想就是在双向链表中查找值为 x 的结点，具体方法与单链表中查找一样。找到结点*p 后给 freq 域的值加 1。由于原来比*p 结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p 结点频度的结点*q 后，将*p 结点从原来的位置删除，并插入到*q 后就可以了。算法如下：/双向链表的存储结构typedef struct dlistnodeDataType data;struct dlistnode *prior,*next;int freq;DListNo
5、de;typedef DListNode *DLinkList;void LocateNode( LinkList L, DataType x)ListNode *p, *q;p=L-next; /带有头结点while( pif (!p) ERROR(“x is not in L“);/双链表中无值为 x的结点else p-freq+;/freq 加 1 q=p-prior;/以 q 为扫描指针寻找第一个频度大于或等于*p 频度的结点while(q!=Lif (q-next!=p)/若* q 结点和*p 结点不为直接前趋直接后继关系，/则将*p 结点链到* q 结点后p-prior-next=
6、p-next;/将*p 从原来位置摘下p-next-prior=p-prior;q-next-prior=p;/将*p 插入*q 之后。p-next=q-next;q-next=p;p-prior=q;4.1 设将整数 1，2，3，4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为 Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示 i 进栈，Pop( )表示出栈)?(2) 能否得到出栈序列 1423 和 1432?并说明
7、为什么不能得到或者如何得到。(3)请分析 1，2 ，3 ，4 的 24 种排列中，哪些序列是可以通过相应的入出栈操作得到的。答：(1)出栈序列为：1324(2)不能得到 1423 序列。因为要得到 14 的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3 在栈顶，2 在栈底，所以不能得到 23 的出栈序列。能得到 1432 的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在 1，2 ，3 ，4 的 24 种排列中，可通过相应入出栈操作
8、得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43124.3 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的“假上溢“现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的“空“或“满“不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合
9、，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。4.5 回文是指正读反读均相同的字符序列，如“abba“和“abdba“均是回文，但“good“不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)解：根据提示，算法可设计为：/ishuiwen.h 存为头文件int IsHuiwen( char *S)SeqStack T;int i , l;char t;InitStack( l=strlen(S); /求向量长度for ( i=0; iPush( while( !EmptyStack( if( t!=Sl-
10、i) return 0 ;/ 不等则返回 0i-;return -1 ; / 比较完毕均相等则返回 -1/ 以下程序用于验证上面的算法/以下是栈定义( 存为 stack.h)/出错控制函数#include#includevoid Error(char * message)fprintf(stderr, “Error: %sn“,message);exit(1);/ 定义栈类型#define StackSize 100typedef char Datatype;typedef structDatatype dataStackSize;int Top; SeqStack;void InitStac
11、k( SeqStack *S)/初始化(置空栈)S-Top=-1;int EmptyStack(SeqStack *S) /判栈空return S-Top = -1;int FullStack (SeqStack *S) / 判栈满return S-Top=StackSize-1;void Push (SeqStack *S , Datatype x) /进栈if(FullStack(S)Error(“Stack overflow“);S-data+S-Top=x;Datatype Pop(SeqStack *S) / 出栈(退栈)if (EmptyStack( S) )Error( “Sta
12、ck underflow“);return S-dataS-Top-;/取栈顶元素(略)/-/以下是主程序#include#include#include “stack.h#include “ishuiwen.h“void main( )char Str100=“;printf(“输入一个字符串:n“);scanf(“%s“,Str);if( IsHuiwen(Str)printf(“ n 这个字符串是回文。“);else printf(“n 这个字符串不是回文。“);4.6(类似题) 利用栈的基本操作， 写一个返回 S 中结点个数的算法 int StackSize( SeqStack S),
13、并说明 S 为何不作为指针参数?解：算法如下：int StackSize (SeqStack S)/计算栈中结点个数int n=0;if(!EmptyStack(n+;return n;类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能“数“得出来，那如果用指针做参数的话，就会把原来的栈中元素“弹“光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。4.8 一个双向栈 S 是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化 In
14、itStack ( S ) 、入栈 Push( S , i , x) 和出栈 Pop( S , i )等算法， 其中i 为 0 或 1， 用以表示栈号。解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：/双向栈的栈结构类型与以前定义略有不同#define StackSize 100 / 假定分配了 100 个元素的向量空间#define char Datatypetypedef structDatatype DataStackSizeint top0; /需设两个指针int top1;DblStackvoid In
15、itStack( DblStack *S ) /初始化双向栈S-top0 = -1;S-top1 = StackSize; /这里的 top2 也指出了向量空间，但由于是作为栈底，因此不会出错4.10 对于循环向量中的循环队列，写出求队列长度的公式。解：公式如下：Queuelen= 0 当 EmptyQueueQueuelen= rear - front 当 rearfrontQueuelen= rear+QueueSize-front 当 rearQueuelen= QueueSize 当 FullQueue4.11 假设循环队列中只设 rear 和 quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下：int FullQueue( CirQueue *Q)/判队满,队中元素个数等于空间大小return Q-quelen=QueueSize;void EnQueue( CirQueue *Q, Datatype x)/ 入队if(FullQue
