《数据结构习题2》由会员分享，可在线阅读，更多相关《数据结构习题2（21页珍藏版）》请在金锄头文库上搜索。
1、第 1 章 绪1.1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1)A=(D，R)，其中，D=a1，a2，a 3，a4，R=(2)B=(D，R)，其中，D=a，b，c，d，e，R=(a，b)，(b，c)，(c，d)，(d，e)(3)C=(D，R)，其中，D=a，b，c，d，e，f，g，R=(d，b)，(d，g)，(b，a)，(b，c)，(g，e)，(e，f)(4)K=(D，R)，其中，D=1，2，3，4，5，6，R=，(1)集合(2)线性表abcde(3)树fgabcde(4)图1453621.2 设 n 为正整数，求下列各程序段中的下划线语句
2、的执行次数。(1)i=1;k=0 while(i=n-1)k+=10*i;i+;(2)for(int i=1;i=n;i+)for(int j=1;j=n;j+)cij=0;for(int k=1;k=n;k+)cij=cij+aik*bkj 解：(1)n-1(2)ninjnkn11131(3)x=0;y=0;for(int i=1;i=n;i+)for(int j=1;j=i;j+)for(int k=1;k=j;k+)x=x+y;(3)62)1)(nn(n21)(216)12)(1(2121212)1(1112111111nnnnniiiijnininiijjkniijni名师资料总结-精
3、品资料欢迎下载-名师精心整理-第 1 页，共 21 页 -1.3 指出下列个算法的功能，并求其时间复杂度。(1)int sum1(int n)int p=1,s=0;for(int i=1;i=n;i+)p*=i;s+=p;return s;(2)int sum2(int n)int s=0;for(int i=1;i=n;i+)int p=1;for(int j=1;j=i;j+)p*=j;s+=p;return s;解：(1)n1ii!,T(n)=O(n)(2)n1ii!,T(n)=O(n2)1.4 算法设计有 3 枚硬币，其中有1 枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出
4、伪币？以流程图表示算法。上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。1.设 a,b,c 为 3 个整数，求其中位于中间值的整数。开始A=B？A=C？A是伪币C是伪币B是伪币结束是是否否名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 21 页 -第 2 章 线性表1.设计算法：在顺序表中删除值为e 的元素，删除成功，返回 1；否则，返回0。int Sqlist:DeleteElem(T e)for(i=1;i=length;i+)/按值顺序查找*i 可从 0 开始if(elemi-1=e)/找到，进行删除操作 for(j=i;jlength;j+)/ai 至
5、 an 依次前移Elemj-1=elemj;length-;/表长减一return 1;/删除成功，返回1 return 0;/未找到，删除不成功，返回0 2.分析顺序表中元素定位算法int SqList:Locate(T e)的时间复杂度。解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n 定位成功第i 个元素，需比较i 次212)1(111)(11nnnnininnfnini3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点 ai；p=head;j=0;while(p&jnext;j+;(2)定位到第i 个结点的前驱ai-1；p=head
6、;j=0;while(p&jnext;j+;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 21 页 -(3)定位到尾结点；p=head;while(p-next)p=p-next;(4)定位到尾结点的前驱。p=head;while(p-next-next)p=p-next;4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。首元结点：指链表中的第一个元素结点。头结点.aa1a2n 首(元)结点尾(元)结点头指针名师资料总结-精
7、品资料欢迎下载-名师精心整理-第 4 页，共 21 页 -5.对于无头结点单链表，给出删除第i 个结点的算法描述。template T LinkList:Delete(int i)template T LinkList:Delete(int i)/在单链表上删除第i 个数据元素if(head=NULL)throw“表空!”;/空表，不能删else if(i=1)/删除第 1 个元素p=Head;x=p-data;/保存被删元素值Head=p-next;delete p;else /元素定位到第ai-1p=Head;j=1;/定位查找起始位置while p-next&jnext;j+;if(!p
8、-next|ji-1);/定位失败throw“删除位置不合理”;else /定位成功，进行结点删除q=p-next;x=pdata;p-next=q-next;delete q;retrun x;/返回被删除元素值/#6.用教材定义的顺序表的基本操作实现下列操作：template int DeleteElem(SqList L,T e)#include“SqList.h“template int DeleteElem(SqList L,T e)/i=L.LocateElem(e);/按值查找名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 21 页 -if(!i)/未找到retur
9、n 0;else/找到delete(i);/删除被找到的元素 7.已知 L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。(1)在 P 结点后插入S 结点；(2)在 P 结点前插入S 结点；(3)在表首插入S结点；(4)在表尾插入S结点.【解】(1)s-next=p-next;p-next=s;(2)q=L;while(q-next!=p)q=q-next;s-next=p 或 q-next;q-next=s;(3)s-next=L-next;L-next=s;(3)q=L;while(q-next!=NULL)q=q-next;s-next=q-
10、next;q-next=s;上机练习题要求：给出问题分析、算法描述、源程序及运行截图，在线提交。编程实现：删除单链表中值为e的元素。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 21 页 -第 3 章 栈与队列1.铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示。试问：若进站的六辆列车顺序如上所述,那么是否能够得到325641 和 154623 的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出 进栈 或出栈 的序列)。解：325641 可以154623 不可以。123456名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 21 页 -2
11、.简述以下算法的功能（栈的元素类型为 int）。(1)status algo_1(SqStack S)int i,n,A 255;n=0;while (!S.StackEmpty()n+;An=S.Pop();for (i=1;i=n;i+)S.Push(Ai);(2)status algo_2(SqStack S,int e)SqStack T;int d;while (!S.tackEmpty()d=S.Pop();if (d!=e)T.Push(d);while (!T.StackEmpty()d=T.Pop();T.Push(d);解：(1)借助一个数组，将栈中的元素逆置。(2)借助栈
12、 T，将栈 S中所有值为e 的数据元素删除之。3.编写一个算法，将一个非负的十进制整数N 转换为 B 进制数，并输出转换后的结果。当 N=248D，B 分别为 8 和 16 时，转换后的结果为多少？#include“stack.h”int NumTrans(int N,int B)/十进制整数N 转换为 B 进制数stack S;/建立一个栈while(N!=0)/N非零i=N%B;/从低到高，依次求得各位名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 21 页 -N=N/B;S.push(i);/各位入栈while(!S.StackEmpty()/栈不空 i=S.pop();I
13、f(i9)i=A+10-i;cout S.pop();/依次出栈，得到从高到低的输出结果/#4 借且栈，设计算法：假设一个算术表达式中包含“(”、“)”括号，对一个合法的数学表达式来说，括号“(”和“)”应是相互匹配的。若匹配，返回1；否则，返回0。解：以字符串存储表达式，也可以边输入边判断。顺序扫描表达式，左括号，入栈；右括号，如果此时栈空，表示多右括号，不匹配；如果栈不空，出栈一个左括号。扫描结束，如果栈空，表示括号匹配；否则，括号不匹配，多左括号。int blank_match(char*exp)用字符串存表达式SqStack s;/创建一个栈char*p=exp;/工作指针 p 指向表
14、达式首while(*p!=)/不是表达式结束符switch(p)case (:/左括号，入栈s.push(ch);break;case )/右括号if(s.StackEmpty()return 0;/栈空，不匹配，多右括号else s.Pop();break;/左括号出栈/switch p+;/取表达式下一个字符/while if(!s.StackEmpty()/表达式结束，栈不空名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 21 页 -return 0;/不匹配，多左括号else return 1;/匹配/#5.简述栈和队列的逻辑特点，各举一个应用实例。6.写出下列中缀表达式
15、的后缀表达式。(1)-A+B-C+D(2)(A+B)*D+E/(F+A*D)+C(3)A&B|!(EF)(1)A-B+C-D+(2)AB+D*EFAD*+/+C+(3)AB&EF!|7.计算后缀表达式：4 5*3 2+-的值。解：15 8.将下列递推过程改写为递归过程。void recursion(int n)int i=n;while(i1)cout1)courx;if(x=0)sum=0;else test(sum);sum+=x;coutx;while(x)S.push(x);cinx;sum=0;coutsum;while(x=S.pop()sum+=x;coutsum;/10.简述以
16、下算法的功能（栈和队列的元素类型均为 int）。解：利用栈，将队列中的元素逆置名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 21 页 -void algo(Queue&Q)Stack S;/创建一个栈int d;while (!Q.QueueEmpty()d=DeQueue(Q);S.Push(d);while (!S.StackEmpty()d=S.Pop();Q.EnQueue(d);12.假设以数组sem存放循环队列的元素，同时设变量rear 和front 分别作为队首、队尾指针，且队首指针指向队首前一个位置，队尾指针指向队尾元素处，初始时，rear=fornt=-1。写出这样设计的循环队列入队、出队的算法。解：采用教材队空与队满判别方法。为了区分队空与队满条件，牺牲一个元素空间。即：rear=front，为队空；rear=(front+1)%m，为队满。template void EnQueue(T Se,T e,int m)/入队if(rear+1)%m=fornt)/队满，不能插入throw“队满，不能插入!”else rear=(rear+1)%m;/队
