《数据结构与算法徐凤生习题答案1.doc》由会员分享，可在线阅读，更多相关《数据结构与算法徐凤生习题答案1.doc（65页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法习题答案目录 第1章 2 第2章 7 第3章 13 第4章 21 第5章 26 第6章 32 第7章 42 第8章 54 第9章 60 第10章 64 习题11.解释下列术语：数据、数据元素、数据对象、数据结构。解：数据是用于描述客观事物的数值、字符以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合，是计算机操作的对象的总称。数据元素是数据的基本单位，它是数据中的一个“个体”。有时，一个数据元素可有若干数据项组成，。数据项是数据的不可分割的最小单位。数据对象是具有相同性质的数据元素的集合，是数据的一个子集。数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合
2、。2.数据类型和抽象数据类型是如何定义的？两者有何异同？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？解：数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如，C语言中的整型变量，其值为某个区间上的整数(依赖于机器)，定义在其上的操作为加、减、乘、除和取模等算术运算。抽象数据类型(Abstract Data Type，简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，“整数”是一个抽象数据类型，其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。抽象数据类型和数据类型实质上是一个概念，只是抽象数据类型的范围更广，除了已有的数
3、据类型外，抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。ADT的定义取决于它的一组逻辑特性，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部的使用。抽象数据类型的最重要的特点是抽象和信息隐蔽。抽象的本质是抽取反映问题本质的东西，忽略非本质的细节，从而使所设计的数据结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐蔽数据存储和操作实现的细节，使用者仅需了解抽象操作，或界面服务，通过界面中的服务来访问这些数据。一个含抽象数据类型的软件模块通常应包含定义、表示和实现三部分。3.数据元素之间的关系在计算机中有几种表示方法？各有什么
4、特点？解：数据元素之间的关系在计算机中有四种不同的表示方法：(1)顺序存储方法。数据元素顺序存放，每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作(如插入、删除)效率较差。(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续，便于进行插入和删除等操作，但存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。(3)索引存储方法。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态特性。 (4)哈希
5、(或散列)存储方法。通过哈希函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存储，也不能折半存取。4.简述数据结构的三个层次、五个要素。解：数据结构的三个层次是指抽象、实现和评价三个层次，五个要素是指逻辑结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面。5.举一个数据结构的例子，说明其逻辑结构、存储结构及其运算三个方面的内容。并说明数据的逻辑结构、存储结构及其运算之间的关系。解：例如复数数据结构，其逻辑结构是复数的表示，而存储结构是指复数在计算机内的表示，运算是指对复数初
6、始化、相加等操作。数据的逻辑结构反映数据元素之间的逻辑关系。数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。6.设为整数，试给出下列各程序段中标号为的语句的频度。（1）i=1; while(in) i=i+2;（2）i=1;k=0; while(i=n-1) k+=10*i; i+; （3）i=1;k=0; while(i=n-1) i+; k+=10*i; （4）i=1;j=0; while(i+jj)j+;else i+; （5）x=n;y=0;/n是不小于
7、1的常数 while(x=(y+1)*(y+1) y+; （6）x=91;y=100; while(y0) if(x100)x-=10;y-;else x+; 解：（1）；（2）n-1；（3）n-1；（4）；（5）；（6）1007.调用下列C函数，回答下列问题：（1）试指出值的大小，并写出值的推导过程。（2）假定=5，试指出值的大小和执行时的输出结果。int f(int n) int i,j,k,sum=0; for(i=1;ii-1;j-) for(k=1;kj+1;k+)sum+; printf(sum=%dn,sum); return (sum);解：第一层for循环判断n+1次，往下执
8、行n次，第二层for执行次数为(n+(n-1)+(n-1)+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：i= 1 2 3 nj=n n n n nj=n-1 n-1 n-1 n-1 j=3 3 3 3 j=2 2 2j=1 1执行次数为(1+2+n)+(2+3+n)+n=n*n(n+1)/2-n(n*n-1)/6。在n=5时，=55，执行过程中，输出结果为：sum=15，sum=29，sum=41，sum=50，sum=55(每个sum占一行)。8.试写一算法，从小到大依次输出顺序读入的3个整数、和的值。解：void print_descending(int x,int
9、 y,int z)/按从大到小顺序输出三个数int temp;scanf(%d,%d,%d,&x,&y,&z); if(xy)temp=x;x=y;y=temp; if(yz)temp=y;y=z;z=temp; if(xy)temp=x;x=y;y=temp; printf(%d %d %d,x,y,z);9.将下列各函数，按它们在时的无穷阶数，从小到大排序：，。解：从大到小排列为：，。10.已知阶裴波那契序列的定义为，=，+1，试编写求阶裴波那契序列的第项值的函数算法，和均以值调用的形式在函数参数表中出现。解：int fib(int k,int m,int &f)/求k阶斐波那契序列的第m
10、项的值fint tempMAX,i,j,sum; if(k2|m0) return 0;if(mk-1) f=0;else if (m=k-1) f=1;elsefor(i=0;i=k-2;i+) tempi=0;tempk-1=1; /初始化for(i=k;i=m;i+)/求出序列第k至第m个元素的值sum=0;for(j=i-k;jnext。（1）while(p!=NULL& p-data!=x)p=p-next;if(p=NULL)return NULL;/查找失败else return p;/查找成功（2）while(p!=NULL& p-datanext;if(p=NULL| p-d
11、atax)return NULL;/查找失败else return p;/查找成功（3）while(p!=NULL& p-datax)p=p-next;if(p=NULL| p-datanext;/L是一带头结点的单链表，结点有数据域data和指针域nextif(pre!=NULL)while(pre-next!=NULL)p=pre-next;if(p-data=pre-data) pre=p;else return(FALSE);return(TUURE);解：该算法的功能是判断链表L是否非递减有序，若是则返回TRUE，否则返回FALSE。pre指向当前结点，p指向pre的后继。7.设、分
12、别指向两个带头结点的有序（从小到大）单链表。阅读下列程序，并回答问题：（1）程序的功能；（2）、2中的值的含义；（3）、中值的含义。void exam(LinkList pa, LinkList pb)p1=pa-next;p2=pb-next;pa-next=NULL;s1=0;s2=0;while(p1&p2)switchcase(p1-datadata):p=p1;p1=p1-next;s2+;delete p;case(p1-datap2-data):p2=p2-next;case(p1-data=p2-data):p=p1;p1=p1-next;p2-next=p2-next;pa-
13、next=p;p2=p2-next;s1+;while(p1)p=p1;p1=p1-next;delete p;s2+;解：本程序的功能是将pa和pb链表中值相同的结点保留在pa链表中（pa中与pb中不同的结点删除），pa是结果链表的头指针。链表中结点值与从前逆序。s1记结果链表中结点个数（即pa与pb中相等的元素个数），s2记原pa链表中删除的结点个数。8.假设长度大于1的循环单链表中，既无头结点也无头指针，为指向该链表中某一结点的指针，编写一算法删除该结点的前驱结点。解：int Delete_Pre(LNode *p) LNode *q,*temp; q=p; while(q-next-n
14、ext!=p)q=q-next; temp=q-next; q-next=p; delete temp; return OK;9.已知两个单链表La和Lb分别表示两个集合，其元素递增排列。编写一算法求其交集Lc，要求Lc以元素递减的单链表形式存储。解：void Inter_set(LinkList La, LinkList Lb, LinkList &Lc) LNode *pa,*pb,*pc; pa=La-next; pb=Lb-next; Lc=new LNode; Lc-next=NULL; while(pa&pb)if(pa-data=pb-data)pc=new LNode; pc-
15、data=pa-data;pc-next=Lc-next;Lc-next=pc;pa=pa-next;pb=pb-next;else if(pa-datadata) pa=pa-next;else pb=pb-next; 10.已知单链表是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点（若表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。解： void Delete_Between(LinkList &L, int min, int max) LNode *p,*q,*s; p=L; while(p-next-
16、datanext; if(p)q=p-next;while(q&q-datanext;delete s;p-next=q; 11.已知非空单链表的头指针为，试写一算法，交换所指结点与其下一个结点在链表中的位置（设指向的不是链表最后那个结点）。解：void Exchange(LinkList &L, LNode *p) LNode *q,*pre;q=L-next; pre=L; while(q!=NULL&q!=p)pre=q;q=q-next; if(p-next=NULL)printf(p无后继结点n); else q=p-next; pre-next=q;p-next=q-next;q-
17、next=p; 12.线性表中有n个元素，每个元素是一个字符，现存于数组Rn中，试写一算法，使R中元素的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的空间，元素移动次数最小。解：void process(char R,int n) int low,high; char k; low=0;high=n-1; while(lowhigh)/将字母放在前面while(lowhigh&fch(Rlow)low+;while(lowhigh&!fch(Rhigh)high-;if(lowhigh)k=Rlow; Rlow=Rhigh;Rhigh=k; high=n-1; while(low
18、high)/将数字放在字母后面，其它字符前面while(lowhigh&!fnum(Rlow)low+;while(lowhigh&fnum(Rhigh)high-;if(lownext;pre=L;q=p; while(p-next!=NULL)if(p-next-datadata)pre=p; q=p-next;p=p-next; pre-next=q-next; delete q; 14.已知两个单链表La和Lb，其元素递增排列。编写一算法，将La和Lb归并成一个单链表Lc，其元素递减排列（允许表中有相同的元素），要求不另辟新的空间。解：void interaction(LinkList
19、 &La, LinkList Lb) LNode *pa,*pb,*s; pa=La-next; pb=Lb-next; La-next=NULL; delete Lb; while(pa&pb)if(pa-datadata)s=pa;pa=pa-next;s-next=La-next;La-next=s;else s=pb;pb=pb-next;s-next=La-next;La-next=s; while(pa)s=pa;pa=pa-next;s-next=La-next;La-next=s; while(pb)s=pb;pb=pb-next;s-next=La-next;La-next=
20、s;15.设以带头结点的双向循环链表表示的线性表。试写一时间复杂度为的算法，将改造为。解：void OEReform(CirDuLinkList &L) DuLNode *p; p=L-next; while(p-next!=L&p-next-next!=L) p-next=p-next-next;p=p-next; if(p-next=L)p-next=L-prior-prior; else p-next=L-prior; p=p-next; while(p-prior-prior!=L)p-next=p-prior-prior;p=p-next; p-next=L; for(p=L; p-
21、next!=L; p=p-next)p-next-prior=p; L-prior=p;16.设有一双向循环链表，每个结点除有prior、data和next三个域外，还有一个访问频度域frep。在链表被起用之前，频度域frep的值为0，而每当对链表进行一次LocateElem(L，e)的操作后，被访问的结点的频度域frep的值增1，同时调整链表中结点之间的顺序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试写出符合上述要求的LocateElem操作的算法。解：void LocateElem(CirDuLinkList &L,int x)DuLNode *p
22、=L-next,*q;while(p-data!=x&p)p=p-next;if(p)p-frep+;q=p-prior;while(q-frepfrep&q!=L) q=q-prior; if(q!=p-prior)p-prior-next=p-next;p-next-prior=p-prior;q-next-prior=p;p-next=q-next;q-next=p;p-prior=q; 习题31.名词解释：栈、队列、循环队列。解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。队列是允许在一端插入而在另一端
23、删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最后插入的元素最先删除，故栈也称先进先出表。最先入队的元素最先删除，故队列也称先进先出表。用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；
24、请说明为什么不能或如何才能得到。解：输入序列为1，2，3，4，5，6，不能得到4，3，5，6，1，2，其理由是：输出序列最后两个元素是1，2，前面四个元素（4，3，5，6）得到后，栈中元素剩下1，2，且2在栈顶，栈底元素1不可能在栈顶元素2出栈之前出栈。得到序列1，3，5，4，2，6的过程是：1入栈并出栈；然后2和3依次入栈，3出栈，部分输出序列是1，3；紧接着4和5入栈，5，4和2依次出栈，此时输出序列为1，3，5，4，2；最后6入栈并出栈，得到最终结果序列是1，3，5，4，2，6。3.试证明：若借助栈由输入序列1，2，得到序列，(它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形
25、：存在着，使得。解：如果的情况，则说明要将压到之上，也就是在出栈之后才能出栈。这说明，对于，不可能出现的输出序列。4.当函数递归调用自身时，函数内定义的局部变量在函数的2次调用期间是否占用同一数据区？为什么？解：函数递归调用自身时，函数内定义的局部变量在函数的2次调用期间不占用同一数据区。每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。5.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值。解：循环队列的数据结构略。typedef structElemType *elem;int front;int rear;SqQueue,Q;（1
26、）初始状态: Q.front=Q.rear=0;（2）队列空: Q.front=Q.rear=0;（3）队列满: Q.front=(Q.rear+1)%MAXSIZE;6.设一个双端队列，元素进入该队列的次序为1，2，3，4.求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。解：既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是：4，2，3，1。7.简述以下算法的功能。(1)void algo1(Stack S) int i,n,A255; n=0; while(!StackEmpty(S)n+;Pop(S,An); for(i=1;i=n;i
27、+)Push(S,Ai);(2)void algo2(Stack S,int e) Stack T;int d;InitStack(T); while(!StackEmpty(S)Pop(S,d);if(d!=e)Push(T,d); while(!StackEmpty(T)Pop(T,d);Push(S,d);(3)void algo3(Queue &Q)/栈和队列的元素类型均为int Stack S;int d;InitStack(T); while(!QueueEmpty(Q)DeQueue(Q,d);Push(S,d); while(!StackEmpty(S)Pop(S,d);EnQ
28、ueue(Q,d);解：（1）将栈中元素逆置。（2）将栈中的0元素删除。（3）将队列中元素逆置。8.试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中不含字符，且序列2是序列1的逆序列。解：int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0 SqStack s; char c,x; InitStack(s); while(c=getchar()!=&)Push(s,c); while(c=getchar()!=)if(StackEmpty(s)return 0;Pop(s,x);
29、if(x!=c)return 0; if(!StackEmpty(s)return 0; return 1;9.在火车调度站的入口处有节硬席或软席车厢(分别以H和S表示)等待调度，试写一算法，输出对这节车厢进行调度的操作(即入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。解：typedef char SSMAX; void Train_arrange(SS &train)/这里用字符串train表示火车,H表示硬席,S表示软席 SqStack s; char *p,*q,c; p=train; q=train; InitStack(s); while(*p)if(*p=H)Pu
30、sh(s,*p);/把H存入栈中else *(q+)=*p; /把S调到前部p+; while(!StackEmpty(s)Pop(s,c);*(q+)=c;/把H接在后部 10.试写出求递归函数的递归算法，并消除递归：解：int F_recursive(int n,int &s)/递归算法 if(n0) return ERROR; if(n=0) s=n+1; elseF_recursive(n/2,s);s=n*s; return OK;/F_recursive typedef struct ElemType a; ElemType b;node;typedef struct node *
31、data; int top;/栈顶指针 int stacksize;SqStack;void F_nonrecursive(int n,int &s)/非递归算法SqStack T; node x,t; if(n-1)sum+=stop-; printf(sum=%dn,sum);12.设整数列，给出求解最大值的递归程序。解：int MaxValue(int a,int n) int max; if(n=1)max=a0; else if(an-1MaxValue(a,n-1)max=an-1; else max=MaxValue(a,n-1); return max;13.假设以带头结点的循
32、环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队和出队的算法。解：(1)void InitQueue(CirLinkList &rear) rear=new LNode; rear-next=rear;(2) void EnQueue(CirLinkList &rear, ElemType x) LNode *s; s=new LNode; s-data=x; s-next=rear-next; rear-next=s; rear=s;(3)void DnQueue(CirLinkList &rear,ElemType &x) LNode *s;
33、 if(rear-next=rear)printf(队空n);exit(0); s=rear-next-next;/s指向队头元素 rear-next-next=s-next;/队头元素出队 x=s-data; if(s=rear)rear=rear-next;/空队 delete s;14.假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个亿为结束符的字符序列是否是“回文”。解：int Test()/判别输入的字符串是否回文序列,是则返回1,否则返回0 SqStack S; SqQueue Q; char c; ElemType a,b; InitStack(S);Ini
34、tQueue(Q); while(c=getchar()!=)Push(S,c);EnQueue(Q,c); /同时使用栈和队列两种结构 while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR; return OK;15.写一算法，借助于栈将一个单链表逆序输出。解：void process(LinkList &L) LNode *p; SqStack s;ElemType x; p=L-next; InitStack(s); while (p)Push(s,p-data);p=p-next; while (!StackEm
35、pty(s)Pop(s,x);printf(%d ,x);16.假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：typedef struct ElemType *base;/动态分配存储空间 int length;/队列长度int rear;/尾指针，指向队列尾元素SqQueue;int EnQueue(SqQueue &Q,ElemType x) /带length域的循环队列入队算法 if(Q.length=MAX)return ERROR;/队列满 Q.rear=(Q.rear+1)%MAX; Q.baseQ.rear=x; Q.length+; return OK;int DeQueue(SqQueue &Q,ElemType &x) /带length域的循环队列出队算法 int head; if(Q.length=0)return ERROR;/队列空 head=(Q.rear-Q.length+1)%MAX; x=Q.basehead; Q.length-; return OK;