您好,欢迎访问三七文档
第一章绪论1、简述下列术语:数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。数据:所有能被输入到计算机中并被计算机处理的符号的总称。数据元素:数据的最小单位,在计算机程序中通常作为一个整体进行考虑和处理。有时一个数据元素可由若干个数据项组成,数据项是数据不可分割的最小单位。数据对象:性质相同的数据元素的集合,是数据的一个子集。数据结构:相互之间存在一种或多种特定关系的数据元素的集合。存储结构:数据结构在计算机中的表示(又称映像)成为数据的物理结构,又称存储结构。数据类型:一个值的集合和定义在这个值集上的一组操作的总称。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。抽象数据类型:一个数据模型以及定义在该模型上的一组操作。2、数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等;非线性结构包括树、图等、这两类结构各自的特点是什么?线性结构:数据逻辑结构中的一类。它的特征是若结构为非空集,则该结构有且只有一个开始结点和一个终端结点,并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。非线性结构:数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。3、什么是算法?算法的5个特性是什么?试根据这些特性解释算法与程序的区别。算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每条指令表示一个或多个操作。特性:有穷性、确定性、可行性、输入、输出。4、什么叫算法的时间复杂度?怎样表示算法的时间复杂度?随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法是时间量度记作T(n)=O(f(n))。5、两个数据结构的逻辑结构和存储结构都相同,但是它们的运算集合中有一个运算的定义不一样,它们是否可以认作是同一个数据结构?为什么?不可以。因为数据结构是定义在运算上的,而与它们的逻辑结构和存储结构无关。6、试画出与下列程序段等价的框图(1)product=1;i=1;while(i=n){product*=i;i++;}(2)i=0;do{i++;}while((i!=n)&&(a[i])!=x);7、已知如下程序段for(i=n;n=1;n--){语句1}{x++;{语句2}for(j=n;j=i;j--)FORj:=n{语句3}y++;{语句4}};求语句1到语句4的频度。语句1:n;语句2:n;语句3:n!;语句4:n!8、按增长率从小到大的顺序排列下列各组函数:2100,(3/2)n,(2/3)n,(4/3)n,n,n3/2,n2/3,n!,nn,log2n,n/log2n,log2(log2n),nlog2n(2/3)n,2100,log2(log2n),log2n,n2/3,n/log2n,n,n3/2,(4/3)n,(3/2)n,nlog2n,n!,nn,9、试写一算法,自大至小依次顺序读入三个整数X,Y,Z的值。voidDescending(){scanf(x,y,z);if(xy){temp=x;x=y;y=temp;}if(yz){temp=z;z=y;if(x=temp)y=temp;else{y=x;x=temp;}}printf(x,y,z);}Descending12、设n为已在算法前边定义的整数类型,并已知n为正整数,分析下列各算法中语句的执行次数,并给出各算法的时间复杂度T(n)。(1)inti=1,k=0;while(in-1){k=k+10*i;i=i+1;}解析:i=1;//1k=0;//1while(in-1)//n-1{k=k+10*i;//n-2i++;//n-2}由以上列出的各语句的频度,可得该程序段的时间消耗:T(n)=1+1+(n-1)+(n-2)+(n-2)=3n可表示为T(n)=O(n)(2)inti=1,k=0;do{k=k+10*i;i=i+1;}while(i!=n);解析:i=0;//1k=0;//1do{//nk=k+10*i;//ni++;//n}while(i!=n);//n由以上列出的各语句的频度,可得该程序段的时间消耗:T(n)=1+1+n+n+n+n=4n+2可表示为T(n)=O(n)(3)inti=1,j=1;while(i=n&&j=n){i=i+1;j=j+1;}解析:inti=1;//1j=1;//1while(i=n&&j=n)//n{i=i+1;//nj=j+1;//n}由以上列出的各语句的频度,可得该程序段的时间消耗:T(n)=1+1+n+n+n=3n+2可表示为T(n)=O(n)(4)intx=n;/*n1*///1inty=0;//1while(x=(y+1)*(y+1))//n1/2y++;//n1/2由以上列出的各语句的频度,可得该程序段的时间消耗:T(n)=1+1+n1/2+n1/2=2+2n1/2可表示为T(n)=O(n1/2)5※习题二第二章线性表1、描述以下基本概念:线性表、顺序存储结构、链式存储结构、给出线性表的抽象数据类型定义。线性表:n个数据元素的有限序列。顺序存储结构:用相邻存储位置存储相邻数据元素的存储结构。链式存储结构:用一组任意的存储单元存储线性表的数据元素的存储结构。2、说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素,以及插入操作和删除操作各自移动数据元素的方向。因为在线性表的顺序存储结构中,由于逻辑上相邻的数据元素在物理位置上也是相邻的,所以,除非i=n+1,,否则必须移动元素才能反映这个逻辑关系的变化。一般情况下,在第i(1=i=n)个元素之前插入一个元素时,需将第n至第i(共n-i+1)个元素向后移动一个位置;删除第i(1=i=n)个元素时,需将第n至第i+1(共n-i)个元素向前移动一个位置。3、对比顺序表和单链表,说明顺序表和单链表的主要优点和主要缺点。顺序表优点:可随机存取表中任一元素,存储位置可用一个简单、直观的公式来表示;缺点:插入、删除一个结点需要移动大量元素;单链表优点:插入、删除一个结点不需要移动大量元素;缺点:不能随机存取。4、已知L是无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。A.在P结点后插入S结点的语句序列是(4,1);B、在P结点前插入S结点的语句序列是(7,11,8,4,1);C、在表首插入S结点的语句序列是(5,12);D、在表尾插入S结点的语句序列是(9,1,6);(1)P-next=S;(2)P-next=S-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;5、已知L是带表头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。A、删除P结点的直接后继结点的语句序列是(3);B、删除P结点的直接前驱结点的语句序列是(10,12,8,11,3,14,);C、删除P结点的语句序列是(10,12,7,3,14);D、删除首元结点的语句序列是(12,11,3,14);E、删除尾元结点的语句序列是(12,9,11,3,14);(1)P=P-next;(2)P-next=P;(3)P-next=P-next-next;(4)P=P-next-next;(5)while(P-next!=NULL)P=P-next;(6)while(Q-next!=NULL){P=Q;Q=Q-next};(7)while(P-next!=Q)P=P-next;(8)while(P-next-next!=Q)P=P-next;(9)while(P-next-next!=NULL)P=P-next;(10)Q=P;(11)Q=P-next;(12)P=L;(13)L=L-next;(14)free(Q);5※习题三第三章栈和队列1、什么叫堆栈?什么叫队列?堆栈:限定只在表尾进行插入或者删除操作的线性表。队列:只允许在表的一端进行插入,而在另一端删除元素的线性表。2、线性表、堆栈和队列这三种抽象数据类型有什么相同之处和不同之处?从数据结构角度看,堆栈和队列也是线性表,它们的基本操作是线性表操作的子集,是操作受限的线性表。但从数据类型角度看,它们都是互不相同的抽象数据类型。3、在顺序队列中,什么叫真溢出?什么叫假溢出?为什么顺序队列通常都采用顺序循环队列结构?在顺序队列中,由于数组空间不够而产生的溢出叫真溢出;顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出;假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的,解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列,因此,顺序队列通常都采用顺序循环队列结构。4、什么叫优先级队列?优先级队列和队列有什么相同之处和不同之处?优先队列(priorityqueue)是0个或多个元素的集合,每个元素都有一个优先权或值。优先队列中元素出队列的顺序由元素的优先级决定,从优先队列中删除元素是根据优先权高或低的次序,而不是元素进入队列的次序。5.(1)什么是递归程序?一个直接调用自己或者通过一系列的调用语句间接调用自己的程序。(2)递归程序的优、缺点是什么?递归程序的优点是程序结构简单、清晰,易证明其正确性。缺点是执行中占内存空间较多,运行效率低。(3)递归程序在执行时,应借助于什么来完成?递归程序执行中需借助栈这种数据结构来实现。(4)递归程序的入口语句、出口语句一般用什么语句实现?递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口,即不再递归即可求出结果的部分;归纳项是将原来问题化成简单的且与原来形式一样的问题,即向着“基本项”发展,最终“到达”基本项。6、设有4个数据元素a1、a2、a3和a4,对他们分别进行栈操作或队操作。在进栈或进队操作时,按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次,出栈一次,再进栈两次,出栈一次;这时,第一次出栈得到的元素是A②,第二次出栈得到的元素是B③;类似地,考虑对这四个数据元素进行的队操作是进队两次,出队一次,再进队两次,出队一次;这时,第一次出队得到的元素是C①,第二次出队得到的元素是D②。经操作后,最后在栈中或队中的元素还有E②个。供选择的答案:A~D:①a1②a2③a3④a4E:①1②2③3④07、栈是一种线性表,它的特点是A②。设用一维数组A[1,…,n]来表示一个栈,A[n]为栈底,用整型变量T指示当前栈顶位置,A[T]为栈顶元素。往栈中推入(PUSH)一个新元素时,变量T的值B①;从栈中弹出(POP)一个元素时,变量T的值C②。设栈空时,有输入序列a,b,c,经过PUSH,POP,PUSH,PUSH,POP操作后,从栈中弹出的元素的序列是D⑥,变量T的值是E①。供选择的答案:A:①先进先出②后进先出③进优于出④出优于进⑤随机进出B,C:①加1②减1③不变④清⑤加2⑥减2D:①a,b②b,c③c,a④b,a⑤c,b⑥a,cE:①n+1②n+2③n④n-1⑤n-28、在做进栈运算时,应先判别栈是否A②;在做退栈运算时,应先判别栈是否B①。当栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大
本文标题:精简数据结构习题
链接地址:https://www.777doc.com/doc-4755563 .html