数据结构章习题课课件.ppt

1、1习习 题题 课课（13章）章）2一、填空题一、填空题1.数据的逻辑结构被分为数据的逻辑结构被分为 、和和 4种种.2.数据的存储结构被分为数据的存储结构被分为 、2种种.3.在线性结构、树形结构和图形结构中，直接前驱和在线性结构、树形结构和图形结构中，直接前驱和 直接后继结点之间分别存在着直接后继结点之间分别存在着 、和和 的联系。的联系。4.一个算法应具有一个算法应具有 、输输 入和输出特性入和输出特性.5.一个算法的效率主要由一个算法的效率主要由 和和 来度量。来度量。6.抽象数据类型包括抽象数据类型包括_和和_。37.在顺序表中插入一个元素，需要平均移动在顺序表中插入一个元素，需要平均

2、移动 元素，具体移动的元素个数与元素，具体移动的元素个数与 有关。有关。8.在顺序表中逻辑上相邻的元素的物理位置在顺序表中逻辑上相邻的元素的物理位置 紧邻。紧邻。单链表中逻辑上相邻的元素的物理位置单链表中逻辑上相邻的元素的物理位置 紧邻。紧邻。9.在单链表中，除了首元结点外，任一结点的存储位在单链表中，除了首元结点外，任一结点的存储位 置由置由 指示。指示。10.在单链表中设置头结点的作用是在单链表中设置头结点的作用是 。11.11.栈的特点是栈的特点是 。12.12.队列的特点是队列的特点是 。13.13.在能存放在能存放m m个元素的循环队列中，允许最多存放个元素的循环队列中，允许最多存放

3、 个元素。个元素。414.从一维数组从一维数组An中顺序找出一个最大值元素的时间复杂度中顺序找出一个最大值元素的时间复杂度 为为 ,输出一个二维数组输出一个二维数组Bmn中所有元素值的时中所有元素值的时 间复杂度为间复杂度为 .15.在下面的程序中在下面的程序中,s=s+p语句的执行次数为语句的执行次数为 ,p*=j语句的执行次数为语句的执行次数为 ,该程序段的时间复杂度为该程序段的时间复杂度为 .int i=0;s=0;while(+i=n)int p=1;for(int j=1;jlink=S;(2)p-link=p-link-link;(3)P-link=S-link;(4)S-link

4、=P-link;(5)S-link=L;(6)S-link=NULL;(7)Q=P;(8)while(P-link!=Q)P=P-link;(9)while(P-link!=NULL)P=P-link;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;9四、四、设有一个设有一个10*10的对称矩阵的对称矩阵A1010，采取按行压缩存，采取按行压缩存储的方式存放于一个一维数组储的方式存放于一个一维数组B 中，则数组中，则数组B 的容量应的容量应有多大？若设有多大？若设A00为第一个元素，存放于为第一个元素，存放于B0，且数组，且数组A 的每一个数组元素在数组的每一个数组元素在数组B

5、 中占一个数组元素位置，中占一个数组元素位置，则则A85在数组在数组B 中地址是多少？中地址是多少？答案：答案：数组数组B应有应有55个元素，对于下三角矩阵，个元素，对于下三角矩阵，LOC(A85)=1+8+5=41 对于上三角矩阵，对于上三角矩阵，LOC(A85)=LOC(A58)=10+9+8+7+6+(8-5)=4310五、五、（1）画出执行下列各行语句后各指针及链表的示意图。）画出执行下列各行语句后各指针及链表的示意图。ListNode*L=new ListNode();P=L;for(i=1;ilink=Q;P=P-link;P-data=2*i-1;P-link=NULL;for(

6、i=4;i=1;i-)Insert(2*i,i+1);for(i=1;ilink)Q=L;L=L-link;P=L;while(P-link)P=P-link;P-link=Q;Q-link=NULL;12(2)void BB(ListNode*s;ListNode*q)p=s;while(p-link!=q)p-p-link;p-link=s;void AA(ListNode*pa;ListNode*pb)BB(pa,pb);/pa和和pb分别指向单循环链表中的两个结点。分别指向单循环链表中的两个结点。BB(pb,pa);13(3)void exam1(Stack S)int i,n=0,A

7、255;while(!S.IsEmpty()n+;An=S.Pop();for(i=1;i=n;i+)S.Push(Ai);将栈将栈S中元素自栈底到栈顶的内容进行颠倒存放中元素自栈底到栈顶的内容进行颠倒存放.14(4)void exam2(Stack S,Type e)Stack T;Type d;while(!S.IsEmpty()d=S.Pop();if(d!=e);T.Push(d);while(!T.IsEmpty()d=T.Pop();S.Push(d);删去栈删去栈S中值为中值为e的元素的元素15(5)void exam3(Queue&Q)Stack S;int d;while(!

8、Q.IsEmpty()d=Q.Leave();S.Push(d);while(!S.IsEmpty()d=S.Pop(S);Q.Enter(d);把队列中的元素颠倒把队列中的元素颠倒.16八、写出下列程序段的输出结果（栈中元素类型为八、写出下列程序段的输出结果（栈中元素类型为char）(1)void main()Stack S;x=c;y=k;S.Push(x);S.Push(a);S.Push(y);x=S.Pop();S.Push(t);S.Push(x);x=S.Pop();S.Push(s);while(!S.IsEmpty()y=S.Pop();couty;coutx;结果：结果：s

9、tack17(2)void main()Queue Q;char x=e;y=c;Q.Enter(h);Q.Enter(r);Q.Enter(y);x=Q.Leave();Q.Enter(x);x=Q.Leave();Q.Enter(a);while(!Q.IsEmpty()y=Q.Leave();couty;coutnext=NULL)return;p=head-next;head-next=NULL;while(p!=NULL)q=p-next;p-next=head-next;head-next=p;p=q;262-10 设计一个算法，将数组设计一个算法，将数组An中的元素循环右移中的元

10、素循环右移k位，位，假设原数组序列为假设原数组序列为a0,a1,an-2,an-1；移动后的序列为；移动后的序列为 an-k,an-k+1,a0,a1,an-k-1。要求只用一个元素大小。要求只用一个元素大小的附加存储，元素移动或交换次数为的附加存储，元素移动或交换次数为O(n)。void youyi(int a,int n,int k)int b;for(int i=0;i=0;j-)aj+1=aj;a0=b;27补充题补充题1.数组置逆数组置逆 void inverse(DataType A,int n)for(i=0;in/2;i+)temp=Ai;Ai=An-1-i;An-1-i=te

11、mp;282:求鞍点求鞍点:二维数组中行最小二维数组中行最小,列最大的元素列最大的元素 void minmax(int A ,int m,int n)for(i=0;im;i+)row=Ai0;k=0;for(j=1;jn;j+)if(Aijrow)k=j;row=Aij;tag=1;h=0;while(tag&hrow)tag=0;else h+;if(tag)couti“”j“”rowendl;29练习题：练习题：3.设数组设数组An中有多个零元素，是写一函数，将中有多个零元素，是写一函数，将A中中 所有非零元素依次移动数组所有非零元素依次移动数组A的前端。的前端。4.设计一个算法，找单链

12、表中值最大的结点。设计一个算法，找单链表中值最大的结点。303：设数组：设数组An中有多个零元素，是写一函数，将中有多个零元素，是写一函数，将A中中所有非零元素依次移动数组所有非零元素依次移动数组A的前端。的前端。void compact(int A，int n)k=0;for(i=0;in;i+)if(Ai!=0)if(i!=k)Ak=Ai;k+;for(i=k;in;i+)Ai=0;31 int Max(List head)if(!head-next)return-1;maxvalue=-9999;p=head-next;while(p)if(p-datamaxvalue)maxvalue

13、=p-data;p=p-next;return maxvalue;4.设计一个算法，找单链表中值最大的结点。设计一个算法，找单链表中值最大的结点。32习题习题p68:2-6 void inverse(Type A,int n)for(i=0;in/2;i+)temp=Ai;Ai=An-1-i;An-1-i=temp;332-4：template void Array:compact()k=0;for(i=0;iArraySize;i+)if(elementsi!=0)if(i!=k)elementsk=elementsi;k+;for(i=k;iArraySize;i+)elementsi=0

14、;342-6:求鞍点求鞍点 void minmax(int A ,int m,int n)/行最小行最小,列最大的元素列最大的元素 for(i=0;im;i+)row=Ai0;k=0;for(j=1;jn;j+)if(Aijrow)k=j;row=Aij;tag=1;h=0;while(tag&hrow)tag=0;else h+;if(tag)couti“”j“”rowendl;352-7:解解：LOC(A22)=LOC(A00)+2*n+2=644+2*n+2=676 n=15 LOC(A33)=LOC(A00)+3*n+3=692362-9：(1)数组数组B中共有中共有n*(n+1)/2

15、个元素个元素(2)LOC(Aij)=n+n-1+n-2+n-(i-1)+1+j-i=(2n-i)*(i-1)/2+j-1(3)LOC(Aij)=1+2+i-1+j-1=i*(i-1)/2+j-1 372-13:0346770122115136141-45 33 81-94 2行二元组表行二元组表 col value行指针数组行指针数组 row012345012345678383-3 void Merge(List&ha,List&hb)pa=ha-link;pb=hb-link;ha-link=NULL;delete hb;while(pa&pb)if(pa-datalink)q=pa;pa=

16、pa-link;else q=pb;pb=pb-link;q-link=ha-link;ha-link=q;/while p=pa?pa:pb;while(p)q=p;p=p-link;q-link=ha-link;ha-link=q;393-4:temlateviod List:Inverse()if(first-link=NULL)return;p=first-link;first-link=NULL;while(p!=NULL)q=p-link;p-link=first-link;first-link=p;p=q;404-2 (1)1234，1243，1342，1324，1432，213

17、4，2143，2314，2341，2431，3214，3421，3241，4321 (2)325641和和135426能得到出站序列；能得到出站序列；435612和和154623得不到出站序列；得不到出站序列；414-4(p92)/两个栈共享一个连续空间两个栈共享一个连续空间 int top2,bot2;int IsEmpty(int i)return topi=boti;int IsFull()return top0+1=top1;42int pop(int i)/出栈出栈 if(IsEmpty(i)return-1;if(i=0)return top0-;else return top1+

18、;void push(Type x,int i)/入栈入栈 if(IsFull()return NULL;if(i=0)element+top0=x;else element-top1=x;4-4(p92)434-5:(1)ABC*(2)A-B+CD+(3)AB-*C+(4)AB+D*EFAD*+/+C+444-10:templatevoid Queue :EnQueue(Type&item)/入队入队 if(tag=1&front=rear)return;/队满队满 rear=(rear+1)%m;Qrear=item;tag=1;454-10:templatevoid Queue :DeQ

19、ueue(Type&item)/出队出队 if(tag=0&fornd=rear)return;/队空队空 front=(front+1)%m;tag=0;return(Qfront);465-1:(1)int MaxKey(int n)if(n=1)return(element0);temp=MaxKey(n-1);if(elementn-1temp)return elementn-1;else return temp;475-1:(2)int Sum(int n)if(n=1)return(element0);else return(elementn-1+Sum(n-1);485-7练习：

20、练习：利用广义表的利用广义表的Head和和Tail操作，写出函数操作，写出函数表达式，把以下各题中单元素表达式，把以下各题中单元素banana从广义表中分从广义表中分离出来：离出来：(4)L4(apple),(pear),(banana),orange)(5)L5(apple),pear),banana),orange)(6)L6(apple,(pear,(banana),orange)答案：答案：(4)H(H(T(T(L4)(5)H(T(H(L5)(6)H(H(T(H(T(L6)49练习题：练习题：（1）设计一个算法，找单链表中值最大的节点。）设计一个算法，找单链表中值最大的节点。（2）设计

21、一个算法，在非递减的单链表中删除值相同的多余设计一个算法，在非递减的单链表中删除值相同的多余 节点。节点。50Type Max(List head)/找单链表中值最大的节点找单链表中值最大的节点 if(!head-link)return-1;maxvalue=-9999;p=head-link;while(p)if(p-datamaxvalue)maxvalue=p-data;p=p-link;return maxvalue;51 void delete(List head)/删除值相同的多余节点删除值相同的多余节点 ListNode *p=head-link,q;while(p&p-link)if(p-data=p-link-data)q=p-link;p-link=p-link-link;delete q;else p=p-link;