数据结构1-3章习题课.ppt

1,习 题 课（13章）,2,一、填空题数据的逻辑结构被分为、和 4种.数据的存储结构被分为、2种.在线性结构、树形结构和图形结构中，直接前驱和 直接后继结点之间分别存在着、和 的联系。4.一个算法应具有、输 入和输出特性.5.一个算法的效率主要由 和 来度量。6.抽象数据类型包括_和_。,3,在顺序表中插入一个元素，需要平均移动 元素，具体移动的元素个数与 有关。8.在顺序表中逻辑上相邻的元素的物理位置 紧邻。单链表中逻辑上相邻的元素的物理位置 紧邻。9.在单链表中，除了首元结点外，任一结点的存储位 置由 指示。10.在单链表中设置头结点的作用是。11.栈的特点是。12.队列的特点是。13.在能存放m个元素的循环队列中，允许最多存放 个元素。,4,从一维数组An中顺序找出一个最大值元素的时间复杂度 为,输出一个二维数组Bmn中所有元素值的时 间复杂度为.,15.在下面的程序中,s=s+p语句的执行次数为,p*=j语句的执行次数为,该程序段的时间复杂度为.int i=0;s=0;while(+i=n)int p=1;for(int j=1;j=i;j+)p*=j;s=s+p;,5,16.一维数组逻辑结构是,存储结构是.对于二维数组有 和 两种不同的存储方式.对于一个二维数组Amn,若采用行优先顺序存储的方式,则任一数组元素Aij相对于A00的地址为.17.栈的插入和删除操作是在 进行.当利用大小为 n 的 数组顺序存储一个栈时,假定top=n表示栈空,则向这个栈插 入一个元素时,首先应执行 语句修改 top 指针.18.队列的插入操作在 进行,删除操作在 进行.19.在循环队列中,队头指针指向队头元素的 位置,队尾指针指向队尾元素的 位置.20.在一个顺序栈中,判断队空的条件为,判断队满的条件 为.,6,补充题:按增长率由小到大的顺序排列下列各函数：2100，(3/2)n，(2/3)n，(4/3)n，nn，n2/3，n1/2，n!，n，log2n，n/logn2，log22n，log2(log2n)，nlog2n，nlog2n,7,补充题答案:答:按增长率由小到大的顺序各函数为：(2/3)n，2100，log2(log2n)，log2n，log22n，n1/2，n2/3，n/log2n，n，nlog2n,(4/3)n，(3/2)n，n!，nn,8,二、已知L是无表头结点的单链表，且P结点既不是首 元结点，也不是尾结点，试从下列提供的答案中选 择合适的语句序列。,在P结点后插入S结点的语句序列是。在P结点前插入S结点的语句序列是。在表首插入S结点的语句序列是。在表尾插入S结点的语句序列是。P-link=S;(2)p-link=p-link-link;P-link=S-link;(4)S-link=P-link;S-link=L;(6)S-link=NULL;Q=P;while(P-link!=Q)P=P-link;while(P-link!=NULL)P=P-link;P=Q;(11)P=L;(12)L=S;(13)L=P;,9,四、设有一个10*10的对称矩阵A1010，采取按行压缩存储的方式存放于一个一维数组B 中，则数组B 的容量应有多大？若设A00为第一个元素，存放于B0，且数组A 的每一个数组元素在数组B 中占一个数组元素位置，则A85在数组B 中地址是多少？,答案：数组B应有55个元素，对于下三角矩阵，LOC(A85)=1+8+5=41 对于上三角矩阵，LOC(A85)=LOC(A58)=10+9+8+7+6+(8-5)=43,10,五、（1）画出执行下列各行语句后各指针及链表的示意图。ListNode*L=new ListNode();P=L;for(i=1;ilink=Q;P=P-link;P-data=2*i-1;P-link=NULL;for(i=4;i=1;i-)Insert(2*i,i+1);for(i=1;i=3;i+)Remove(i);,11,六、简述以下算法的功能。（1）void A(Link L)/L是无表头结点的单链表 if(L,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,void exam1(Stack S)int i,n=0,A255;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,把队列中的元素颠倒.,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;,结果：stack,17,(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;coutx;,结果：char,18,试说明基本数据类型、数据结构和抽象数据类型的联系与差异。,基本数据类型（Data Type）：在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。高级语言中都有基本数据类型。例如在C、C+和Java语言中，有基本类型int（整型）、float（浮点型）和char（字符型），有构造类型数组、结构、联合、指针、枚举型和自定义等。数据类型仅局限于计算机中定义并实现了的数据类型;,第一章习题,一个值的集合以及定义在该值集合上的一组操作的总称.,19,数据结构:所研究内容的着重点主要体现在三个方面：第一是数据间的逻辑关系，即数据元素之间的关系。第二是数据的存储关系，即数据在计算机中的存储结构。第三是算法，即定义在逻辑关系上的一组操作。因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学科。,20,抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用。抽象数据类型除了计算机中定义并实现了的数据类型；还包括用户在设计软件系统时自己定义的数据类型。,21,1-5 试说明数据的逻辑结构、存储结构和算法三者之间的关系。,1个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是基于存储结构对算法的实现，是程序；,答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个 方面。,22,1-6 请给出下列函数的大O和表示：,O(n1/2logn),O(n),O(n1.5),O(n1/2),23,2-1描述以下三个概念的区别：头指针、头结点、首结点（第一个元素结点）。在单链表中设置头结点的作用是什么？,答：首结点就是存放数据元素的第一个元素结点，头结点是为了插入和删除的方便说增设的一个结点，头指针是指向链表中第一个结点的存储位置，在没有头结点的链表中，头指针指向链表中的首结点，在有头结点的链表中，头指针指向链表中的头结点。,习 题 2（p55）,24,2-4 已知二维数组Amm采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a00)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？,答：行优先顺序存放时:Loc(aij)=Loc(a00)+(i*m+j)*K 列优先顺序存放时:Loc(aij)=Loc(a00)+(j*m+i)*K,25,2-5 在链表类的实现中增加一个成员函数实现对表中元素置逆的操作（设原链表为 a0,a1,an-2,an-1；则置逆后的序列为 an-1,an-2,a1,a0）。对于有n个元素的线性表，你的算法的运行时间应为O(n)。void LinkList:Inverse()if(head-next=NULL)return;p=head-next;head-next=NULL;while(p!=NULL)q=p-next;p-next=head-next;head-next=p;p=q;,26,2-10 设计一个算法，将数组An中的元素循环右移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=temp;,28,2:求鞍点:二维数组中行最小,列最大的元素 void minmax(int A,int m,int n)for(i=0;irow)tag=0;else h+;if(tag)couti“”j“”rowendl;,29,练习题：3.设数组An中有多个零元素，是写一函数，将A中 所有非零元素依次移动数组A的前端。4.设计一个算法，找单链表中值最大的结点。,30,3：设数组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=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;,33,2-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;,34,2-6:求鞍点 void minmax(int A,int m,int n)/行最小,列最大的元素 for(i=0;irow)tag=0;else h+;if(tag)couti“”j“”rowendl;,35,2-7:解：LOC(A22)=LOC(A00)+2*n+2=644+2*n+2=676 n=15 LOC(A33)=LOC(A00)+3*n+3=692,36,2-9：(1)数组B中共有n*(n+1)/2个元素(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,37,2-13:,行二元组表 col value,行指针数组 row,38,3-3 void Merge(List,39,3-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;,40,4-2(1)1234，1243，1342，1324，1432，2134，2143，2314，2341，2431，3214，3421，3241，4321(2)325641和135426能得到出站序列；435612和154623得不到出站序列；,41,4-4(p92)/两个栈共享一个连续空间,int top2,bot2;int IsEmpty(int i)return topi=boti;int IsFull()return top0+1=top1;,42,int pop(int i)/出栈 if(IsEmpty(i)return-1;if(i=0)return top0-;else return top1+;,void push(Type x,int i)/入栈 if(IsFull()return NULL;if(i=0)element+top0=x;else element-top1=x;,4-4(p92),43,4-5:(1)ABC*(2)A-B+CD+(3)AB-*C+(4)AB+D*EFAD*+/+C+,44,4-10:templatevoid Queue:EnQueue(Type,45,4-10:templatevoid Queue:DeQueue(Type,46,5-1:(1)int MaxKey(int n)if(n=1)return(element0);temp=MaxKey(n-1);if(elementn-1temp)return elementn-1;else return temp;,47,5-1:(2)int Sum(int n)if(n=1)return(element0);else return(elementn-1+Sum(n-1);,48,5-7练习：利用广义表的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）设计一个算法，在非递减的单链表中删除值相同的多余 节点。,50,Type 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,