《数据结构》题库章节练习题

《数据结构》题库章节练习题-第1章绪论////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B计算机算法指的是（1），它必须具备（2）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.4、以下的算法时间复杂度中，算法速度最快的是（）。A.O(N)B.O(Nlog2N)C.O(N2)D.O(2N)下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8、如下程序算法的时间复杂度是（）。voidlink(intarr[N]){inti,j,k;for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)if(arr[i]>arr[j]){k=arr[i];arr[i]=arr[j];arr[j]=k;}}A.O(N) B.O(N2) C.O(log2N) D.O(2N)以下数据结构中，（

）是非线性数据结构。

A．树

B．字符串

C．队

D．栈

连续存储设计时，存储单元的地址（

）。A．一定连续

B．一定不连续

C．不一定连续

D．部分连续，部分不连续二、填空题1、数据的物理结构包括数据元素的表示和数据元素间关系的表示。2、根据数据元素之间的逻辑关系，一般可以构造出四种逻辑结构分别是：集合、线性结构、树形结构、图状或网状结构。3、数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。4、一个数据结构在计算机中表示（又称映像）称为存储结构。5、如果一个算法的时间复杂度是(N3+4N2log2N+3N)/N，那么用数量级表示的时间复杂度应该是O(N2)。6、抽象数据类型的定义仅取决于它的一组逻辑特性_，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。7、数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。8、算法设计应考虑4种质量要求：正确性、可读性、健壮性、高效率与低存储量要求。9、数据结构是研讨数据的逻辑结构和物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的操作（运算），设计出相应的算法_。10、一个算法具有5个重要特性：有穷性、确定性、可行性、输入、输出。11、请分析如下程序代码的时间复杂度，填写其中的空格：

voiddeleteAll(intarray[],intN,inttarget)

{inti=0;while(i<N){if(array[i]!=target)i++;else{intj;for(j=i+1;j<N;j++){array[j-1]=array[j];}N--;}}

}函数deleteAll之中，作为关键操作的一个语句是：_array[j-1]=array[j]__函数deleteAll的算法时间复杂度是：___O(N2)___12、计算机执行下面的语句时，语句s的执行次数为__(n+3)(n-2)/2_____。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;13、下面程序段的时间复杂度为___O(n)_____。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;14、在有n个选手参加的单循环赛中，总共将进行__n(n-1)/2__场比赛。15、将数据结构可定义为一个二元组（D，R），其中D表示的是数据元素的有限集合，则S表示的是D上数据元素之间关系的有限集合。16、抽象数据类型的定义包括数据对象的定义、数据关系的定义和基本操作的定义。17、数据对象是性质相同的数据元素的集合。数据元素是数据的基本单位，有时一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位。三、简答题1、数据结构是一门研究什么内容的学科？数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。2、顺序存储方式和链式存储方式各有什么特点？（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。3、数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义包括：数据对象的定义、数据关系的定义和基本操作的定义。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。4、在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。5、若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。6、在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。7、评价各种不同数据结构的标准是什么？数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征；二是是否容易实现（如对数据分解是否恰当；逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现；基本运算的选择是否恰当。）8、评价一个好的算法，您是从哪几方面来考虑的？评价好的算法有四个方面。一是算法的正确性；二是算法的可读性；三是算法的健壮性；四是算法的时空效率（高效率与低存储量需求）。9、解释：算法、算法的时间复杂度、频度（1）算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有五个重要特性：有穷性、确定性、可行性、输入和输出。（2）算法的时间复杂度是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。（3）在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。10、当你为解决某一问题而选择数据结构时，应从哪些方面考虑？通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。11、数据结构与数据类型有什么区别？“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面：（1）数据的逻辑结构，（2）数据的存储结构，（3）对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。12、在编制管理通讯录的程序时,什么样的数据结构合适?为什么?应从两方面进行讨论：如通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；若通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况作为一个元素（即一个结点存放一个人），设姓名作关键字，链表安排成有序表，这样可提高查询速度。13、算法的时间复杂度、算法的空间复杂度如何计算和表示？答案:（略）（请大家认真看和分析教材P14-P17的内容！）四、算法分析题调用下列C函数f(n)回答下列问题:（1）试指出f(n)值的大小，并写出f(n)值的推导过程;（2）假定n=5，试指出f(5)值的大小和执行f(5)时的输出结果。C函数：intf(intn){inti,j，k,sum=0;for(i=l;i<n+1;i++){for(j=n;j>i-1;j--)for(k=1;k<j+1;k++)sum++;printf("sum=%d\n",sum)；}return(sum);}参考答案：第一层for循环判断n+1次，往下执行n次，第二层for执行次数为(n+(n-1)+(n-2)+„+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：执行次数为(1+2+。。。+n)+(2+3+。。。+n)+。。。+n=n*n(n+1)/2-n(n2-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15sum=29sum=41sum=50sum=55《数据结构》期末复习题及参考答案-第2章线性表////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。2、线性表是具有n个（）的有限序列（n>0）。A．表元素B．字符C．数据元素D．数据项E．信息项3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表4、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表5、长度为N的线性表，如果是顺序存储，则访问、删除某个结点的时间复杂度分别是（）和（）。A.O(N),O(1)B.O(N),O(1)C.O(1),O(1)D.O(1),O(N)6、链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比7、长度为N的线性表，如果是链式存储，则访问、删除某个结点的时间复杂度分别是（）和（）。A.O(1),O(N)B.O(N),O(1)C.O(N),O(1)D.O(N),O(1)8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)9、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)10、线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）11、在双向链表指针p的结点前插入一个指针q的结点操作是（）。A.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;12、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;13、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL二、填空题1、O(n)O(1)2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___顺序____存储结构。在长度为N的线性表中插入一个结点，对于顺序存储和链式存储的线性表，其插入操作的时间复杂度分别是O(N)和O(1)。3、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____（n-1）/2___。在已有n个结点顺序存储的线性表中，插入一个新结点平均需要移动数据n/2次。4、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:py->next=px->next;px->next=py；5、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动___n-i+1___个元素。6、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为___O(1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为____O(n)____。7、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成___单链表_____和___多重链表____；而又根据指针的连接方式，链表又可分成__（动态）链表______和___静态链表_____。8、顺序存储结构是通过___物理上相邻_____表示元素之间的关系的；链式存储结构是通过____指针____表示元素之间的关系的。9、一个顺序存储的线性表，第1、第2个元素的存储地址分别是16进制的16A、17A，那么第10个元素的存储地址是16进制的1FA。10、对于双向链表,在两个结点之间插入一个新结点需修改的指针共___4___个，单链表为____2___个。11、循环单链表的最大优点是：___从任一结点出发都可访问到链表中每一个元素。_____。12、在单链表L中，指针p所指结点有后继结点的条件是：__p->next!=NULL13、线性表的存储结构分为__顺序存储结构____和__链式存储结构____。14、采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。15、设单链表结点指针域为next，则删除链表中指针p所指结点的直接后继的的操作是：q=p->next;p->next=q->next;free(q);16、设单链表的头结点的头指针为head,且pre=head，单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，则在p结点之前插入s结点的操作是：while(pre->next!=p)pre=pre->next;s->next=p;pre->next=s;17、在单链表p结点之后插入s结点的操作是：s->next=p->next;p->next=s;三、简答题1、已知顺序表La和Lb中数据元素按值非递减有序排列，归并La和Lb得到新的顺序表Lc，使Lc中的数据元素也按值非递减有序排列-这种操作称为顺序表的归并操作。请阅读下列顺序表的归并操作算法代码，分析该算法的时间复杂度，并作简要解释。voidMergeList(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存储分配失败pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;//将La的剩余元素插入while(pb<=pb_last)*pc++=*pb++;//将Lb的剩余元素插入}参考答案：上述算法将归并后的数据元素存放在新的顺序表Lc中，顺序表La和Lb不用变化，只是把顺序表La和Lb中的数据元素一个个新插入到顺序表Lc的末尾，最多有La.length+Lb.length个数据元素要插入到顺序表Lc中，所以该算法的时间复杂度是O(La.length+Lb.length)。2、已知顺序表La和Lb，现在将存在于顺序表Lb中而不存在于顺序表La中的数据元素插入到顺序表La中去（如果发现顺序表La的空间不够，则需要扩大顺序表La）。具体做法是从顺序表Lb中依次取得每个数据元素，并依值在顺序表La中进行查访，若不存在，则插入之-这种操作称为顺序表的合并操作。请阅读下列顺序表的合并操作算法代码，分析该算法的时间复杂度，并作简要解释。voidunion(List&La,ListLb){ElemTypee;intLa_len,Lb_len,i;La_len=ListLength(La);//求顺序表的长度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//依次取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal)//依值e在顺序表La中进行查访ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则在La的最后面插入}}参考答案：在顺序表La中查访是否存在和Lb中第i个数据元素（值为e）相同的数据元素的方法是:令e和La中的数据元素逐个比较。若La中存在和e相同的数据元素ai，则比较次数为i(1≤i≤La.length),否则为La.length，即算法LocateElem的时间复杂度为O(La.length)。而最多有Lb.length个数据元素要插入到顺序表La中，由此，算法union的时间复杂度为:O(La.length×Lb.length)。3、线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。参考答案：链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。4、对于单向链表、单向循环链表、双向链表、双向循环链表，在链表中或者链表的尾部插入或删除元素的操作各有什么特点，相应算法的时间复杂度各是怎样的情况？参考答案:（略）（请大家认真看和分析教材的相关内容！）5、静态链表是一种链式存储的线性表。静态单链表是用一维数组来存储线性链表的结点数据，并且用一维数组的下标表示指针。已知一个静态单链表SLinkList定义如下：#defineMAXSIZE200//静态链表的最大长度typedefstruct{DataTypedata;//数据域intnext;//指针域}NodeType;//静态单链表的结点类型NodeTypeSLinkList[MAXSIZE];//静态单链表SLinkList，头结点是SLinkList[0]上述静态单链表的结点中的指针域next保存的是静态单链表SLinkList的下标值。请写出插入结点、删除结点的算法所对应的函数的定义。参考答案:（略）（请大家认真看和分析教材P31-P34相关内容，并写出相应的函数以实现静态单链表的插入、删除结点的操作！）注意，教材中，SLinkList是被定义为一个一维数组类型，本题SLinkList则是一维数组名。四、算法分析题linklist_NULLq=p2、下面的结构体定义了双向链表的节点结构。请分析如下程序代码，填写其中缺少的语句代码：typedefstructnode{intdata；structnode*last;structnode*next;}Node;voiddeleteOne(Node*head,inttarget){Node*p=headnext;while(p!=NULL){if(pdata!=target)____p=pnext_____;else{if(pnext!=NULL)pnextlast=____plast_____;plastnext__=pnext;free(p);}}}3、说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首结点的关系。参考答案：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了使插入和删除等操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。首结点也就是第一元素结点，它是头结点后边的第一个结点。五、算法描述题设有一带头结点的单链表,编程将链表颠倒过来。要求不用另外的数组或结点完成。参考答案：要实现带头结点的单链表的逆置，通常作法是：将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。typedefstructnode{intdata；∥假定结点数据域为整型。structnode*next；}node,*LinkedList；LinkedListcreat（）{LinkedListhead，pintx；head=（LinkedList）malloc（sizeof（node））；head->next=null；/*设置头结点*/scanf（“%d”，&x）；while（x!=9999）/*约定输入9999时退出本函数*/{p=（LinkedList）malloc（sizeof（node））；p->data=x；p->next=head->next；/*将新结点链入链表*/head->next=p；scanf（“%d”，&x）；}return（head）；}∥结束creat函数。LinkedListinvert1（LinkedListhead）/*逆置单链表*/{LinkedListp=head->next;/*p为工作指针*/head->next=null；while（p!=null）{r=p->next；/*暂存p的后继*/p->next=head->next；head->next=p；p=r；}return（head）；}/*结束invert1函数*/voidmain（）{LinkedListla；la=creat(）；/*生成单链表*/la=invert1（la）；/*逆置单链表*/}《数据结构》期末复习题及参考答案-第3章栈和队列////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题对于栈，操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序2、要求数据遵循FIFO（先进先出）原则的数据结构是（）。A.线性表 B.链表 C.队列 D.栈3、若进栈的序列为1,2,3,4，则以下哪一个不可能是一个出栈序列。A.3,2,4,1 B.3,2,1,4 C.4,2,3,1 D.1,3,2,4有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.234156设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154328、数字1、2依次入栈，则出栈的顺序可能有（）种情况；数字1、2依次进入队列，则出队列的顺序可能有（）种情况。A.1,2B.2,1C.2,2D.1,1设一个栈的输入序列是1，2，3，4，5，则下列序列中，是栈的合法输出序列的是（）。A.51234B.45132C.43125D.32154某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是()。A．XYZB.YZXC.ZXYD.ZYX一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分14、如下四个选项中，那个选项是能够正确判断循环队列是否排满元素的操作（其中MAXQSIZE表示队列的容量）（）：A．if(Q.rear==Q.front)… B．if(Q.rear==(Q.front+MAXQSIZE))C．if(Q.rear==(Q.front+1)%MAXQSIZE)D．if(Q.front==(Q.rear+1)%MAXQSIZE)假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和117、利用栈进行十进制数1348转换成八进制数，则入栈的数依次是（）。A.1,3,4,8B.8,4,3,1C.2,5,0,4D.4,0,5,2最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点二、填空题栈是___操作受限（或限定仅在表尾进行插入和删除操作）的线性表，其运算遵循___后进先出____的原则。，其特点是__先进先出__。用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为___S×SS×S××__。表达式求值是___栈____应用的一个典型例子。5、栈和队列在本质上都是同一种基本数据结构的特例，这种基本的数据结构就是线性表。在作进栈运算时，应先判别栈是否.满，在作退栈运算时应先判别栈是否空。当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为n。三、简答题1、简要叙述循环队列的数据结构，分析循环队列的队头指针和队尾指针与循环队列元素之间的关系，写出InitQueue()、QueueLength()、EnQueue()、DeQueue()等循环队列的基本操作算法，并举例说明循环队列的操作函数的应用。参考答案：（1）队列：是一种先进先出(firstinfirstout，简称FIFO表)的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端称为队头(front)。假设队列为q=（a1,a2,…an），则a1为队头元素，an为队尾元素。队列的顺序存储结构称为顺序队列。顺序队列用一组地址连续的存储单元依次存放从队列头到队列尾的元素。由于队列的队头和队尾的位置是变化的，因而需要附设两个指针front和rear以指示队头和队尾元素在队列中的位置。在C语言中为了方便描述，约定：初始化创建空队列时，令front=rear=0(头尾指针相等)。每当插入新的队尾元素时，rear指针增1。每当删除队头元素时，front指针增1。因此，在非空队列中，头指针front始终指向队头元素，而尾指针rear始终指向队尾元素的下一位置。循环队列：用顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即:队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。为了解决循环队列上述“假溢出”现象，可采用牺牲一个存储单元（即少用了队列的一个元素空间）的方法解决“队满”和“队空”的判定问题，并规定:队空时：front==rear；队满时：(rear+1)%MAXQSIZE==front。循环队列的数据结构#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//指向初始化的动态分配存储空间intfront;//头指针,若队列不空，指向队列头元素intrear;//尾指针,若队列不空，指向队列尾元素的下一个位置}SqQueue;（2）循环队列的队头指针和队尾指针与循环队列元素之间的关系见如下示意图：循环队列为了克服“假溢出”现象，少用了队列的一个元素空间。在循环队列中，指针和队列元素之间的关系不变。每当插入新的队尾元素时，rear指针增1。每当删除队头元素时，front指针增1。并规定:队空时：front==rear；队满时：(rear+1)%MAXQSIZE==front。（3）基本操作的算法描述StatusInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;returnOK;}intQueueLength(SqQueueQ){//返回队列Q的元素个数，即队列的长度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue&Q,ElemType&e){//若队列不空，则删除Q的队头元素，//用e返回其值，并返回OK;否则返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}注意:上述函数代码要很好掌握！（4）循环队列的操作函数的应用举例（略）注意:上述操作要很好理解和掌握,能灵活应用！2、若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D和D、B、A、C、E？为什么？答案：能得到出栈序列B、C、A、E、D，不能得到出栈序列D、B、A、C、E。其理由为：若出栈序列以D开头，说明在D之前的入栈元素是A、B和C，三个元素中C是栈顶元素，B和A不可能早于C出栈，故不可能得到D、B、A、C、E出栈序列。3、有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS。答案：XSXXXSSSXXSXXSXXSSSS四、算法分析1、简要叙述顺序栈的数据结构，分析顺序栈的栈顶指针和栈底指针与顺序栈元素之间的关系，写出Push(&S,e)，Pop(&S,&e)，StackEmpty(S)，GetTop(S,&e)，InitStack(&S)等顺序栈的基本操作算法，并举例说明顺序栈的操作函数的应用。参考答案：（1）顺序栈：用一片地址连续的存储空间来存储栈的元素。顺序栈的数据结构#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{SElemType*base;//栈底指针SElemType*top;//栈顶指针inttacksize;//当前分配量,以元素为单位}SqStack;规定top永远指向下一次要插入的位置，非空栈中，top栈顶指针始终指在栈顶元素的下一个位置上。（2）顺序栈的栈顶指针和栈底指针与顺序栈元素之间的关系见如下示意图：首先说明：当base=NULL时，说明栈不存在。如图所示，栈空时：base=top，此时,栈顶指针top，栈底指针base都指向栈底；每当插入新元素，指针top加1，删除栈顶元素时，指针top减1。栈的长度：top-base的值。（3）基本操作的算法描述StatusInitStack(SqStack&S){//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZEsizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusGetTop(SqStackS,SElemType&e){//若栈不空，则用e返回S的栈顶元素，并//返回OK，否则返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}StatusPush(SqStack&S,SElemTypee){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize)//当前存储空间已满，增加分配{S.base=(SElemType*)realloc(S.base，(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;//top指针位置S.stacksize+=STACKINCREMENT//存储容量增加}*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回//ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusDestroyStack(SqStack*S){/*销毁栈S，S不再存在*/free((*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;returnOK;}StatusClearStack(SqStack*S){/*把S置为空栈*/(*S).top=(*S).base;returnOK;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;}intStackLength(SqStackS){/*返回S的元素个数，即栈的长度*/returnS.top-S.base;}注意:上述函数代码要很好掌握！（4）顺序栈的操作函数的应用举例（略）注意:上述操作要很好理解和掌握,能灵活应用！2、一个栈的输入序列为123，则栈的输出序列有哪几种？答案：共有以下5种情况：1进栈,1出栈,2进栈,2出栈,3进栈,3出栈,栈的输出序列是1231进栈,2进栈,2出栈,1出栈,3进栈,3出栈,栈的输出序列是2131进栈,2进栈,2出栈,3进栈,3出栈,1出栈,栈的输出序列是2311进栈,2进栈,3进栈,3出栈,2出栈,1出栈,栈的输出序列是3211进栈,1出栈,2进栈,3进栈,3出栈,2出栈,栈的输出序列是132五、算法描述题编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。【算法分析】利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。【算法源代码】reverse(SqStack*s){SqStack*s1,*s2;

/*s,s1,s2均为栈类型

ElemTypex;

/*栈中元素的类型，用于存储从栈中取出元素的临时变量*/

initstack(s1);/*栈的初始化*/

initstack(s2);while(!stackempty(s))

/*如果栈不空，将s栈中的内容移到s1栈中*/

{pop(s,x);

/*取栈顶元素放入变量x中*/

push(s1,x);

/*将变量x入栈*/

}

while(!stackempty(s1))/*如果栈不空，将s1栈中的内容移到s2栈中*/

{pop(s1,x);

push(s2,x);

}

while(!stackempty(s2))/*如果栈不空，将s2栈中的内容移到s栈中*/

{pop(s2,x);

push(s,x);

}}《数据结构》期末复习题及参考答案-第6章树和二叉树////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、在二叉树的第I层(I≥1)上最多含有结点数为（）A.2IB.2I-1-1C.2I-1D.2I-12、深度为6的二叉树最多有()个结点A．64B.63C.32D.313、一棵树高为K的完全二叉树至少有()个结点A.2k–1B.2k-1–1C.2k-1D.2k4、有关二叉树下列说法正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为25、n个结点的线索二叉树上含有的线索数为（）A.2nB.n－lC.n＋lD.n6、线性表和树的结构区别在于（）A．前驱数量不同，后继数量相同 B．前驱数量相同，后继数量不同C．前驱和后继的数量都相同 D．前驱和后继的数量都不同7、已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，则其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE8、设有一表示算术表达式的二叉树（见下图），EEFDGAB/++*-C*它所表示的算术表达式是（）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G9、一棵具有n个结点的完全二叉树的树高度（深度）(符号表示取不大于x的最大整数)是（）A.B.C.D.10、利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这一结果。A.3 B.4 C.5 D.614、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前序遍历是（）。A.acbedB.decabC.deabcD.cedba15、线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性二、填空题1、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=___N2+1_________。2、具有256个结点的完全二叉树的深度为___9___。3、一个深度为4的二叉树，其结点至少有4个，至多有15个：4、深度为H的完全二叉树至少有_2H-1__个结点；至多有2H-1_个结点；H和结点总数N之间的关系是H=ëlog2Nû+1。5、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，N个结点的二叉树共有__2N__个指针域，其中有_N-1__个指针域是存放了地址，有__N+1_____个指针是空指针。6、设一棵赫夫曼树有6个叶子结点，权值分别为3、4、7、14、15、20，则根结点的权值是__63____7、已知二叉树的先序遍历次序是abdcef，中序遍历次序是bdaecf，则它的后序遍历次序是：dbefca。8、对一棵完全二叉树，设一个结点的编号为i，若它的左孩子结点存在，则其编号为2i；若右孩子结点存在，则其编号为2i+1；而双亲结点的编号为。9、赫夫曼树是带权路径长度最小的二叉树，又称最优二叉树，路径上权值较大的结点离根较近。10、structnode*rchildT=NULL11、二叉树由_根结点__，__左子树_，_右子树__三个基本单元组成。12、树的链表存储结构常用的有三种，其中，双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。//P135-13613、利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。14、在二叉树中，指针p所指结点为叶子结点的条件是_p->lchild==NULL&&p->rchlid==NULL_____。15、树的孩子兄弟表示法和二叉树的二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。16、树和二叉树逻辑上都是树形结构，但是二叉树不是树的特例，二叉树与树是两个不同的概念。二叉树的度至多为2，树无此限制；二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制。17、8层的完全二叉树至少有_128(第七层满，加第八层１个)_个结点，拥有100个结点的完全二叉树的最大层数为__7__。18、对于树的孩子表示法，由于树中每个结点可能有多棵子树，则可用多重链表表示其存储结构。假设多重链表中的结点结构相同，则一棵结点数为n的d叉树中必有n(d-1)+1个空链域。三、简答题1、已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ,试画出这棵二叉树，并写出后序遍历结果。答案：当前序序列为ABKCDFGHIJ，中序序列为KBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：这棵二叉树的后序遍历结果是：KDCBIHJGFA2、某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的次数（权值）分别是16，5，7，3，8，1。试画出其哈夫曼树，确定其对应的哈夫曼编码，并计算其带权路径长度。为使结果唯一，请将权值较小的结点作为其双亲的左孩子，而将权值较大的结点作为其双亲的右孩子。答案：哈夫曼树如下：对应的哈夫曼编码如下：A:0B:101C:110D:1001E:111F:1000带权路径长度为:WPL=(1+3)*4+(5+7+8)*3+16*1=923、对下图所示二叉树分别按前序﹑中序﹑后序遍历，给出相应的结点序列，同时给二叉树加上中序线索。答案：（1）前序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA（4）中序线索见图中虚线箭头所示。4、试评述二叉树的顺序存储表示法、二叉链表表示法、三叉链表表示法和双亲链表表示法这四种二叉树的存储结构表示法的优、缺点。答案：略（p126-p128，自己看书总结）。5、满二叉树和完全二叉树有什么特点？答案：略（p124，自己看书）。6、试评述树的双亲表示法、孩子表示法、孩子兄弟表示法这三种树的存储结构表示法的优、缺点。答案：略（p135-p137，自己看书总结）。四、算法分析题1、已知二叉树的存储结构为二叉链表，阅读下面算法，之后，对于如下所示的二叉树：（1）画出执行下面算法后所建立的结构；（2）说明该算法的功能。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；voidInorder(BinTreeT){LinkLists；If(T){Inorder(T－>lchild)；If((!T－>lchild)&&(!T－>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－>data=T－>data；s－>next=Leafhead；Leafhead=s；}Inorder(T－>rchild);}}答案：2、已知二叉树中的结点类型BinTreeNode定义为:

structBinTreeNode{ElemTypedata;

structBinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右孩子结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。

structBinTreeNode*BTF(

structBinTreeNode*BT，ElemTypex)

{

if(BT==NULL)_returnNULL__;

else{if(BT->data==x)_returnBT

_;

else{

structBinTreeNode*t;

if(t=BTF(BT->left,x))returnt;

___if(t=BTF(BT->right,x))returnt

_____;

returnNULL;

}

}

}3、由二叉树的前序序列和中序序列能否唯一确定一棵二叉树？由二叉树的中序序列和后序序列能否唯一确定一棵二叉树？由二叉树的前序序列和后序序列能否唯一确定一棵二叉树？请分别进行论述。答案：(1)给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。(2)由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。证明如下：当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。最后，当1<i<m时，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树。(3)由二叉树的前序序列和后序序列不能唯一确定一棵二叉树。因为无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。五、算法描述题试写出复制一棵二叉树的递归函数的算法。BiTreeCopy(BiTreet)//复制二叉树t{BiTreebt;if(t==null)bt=null;else{bt=(BiTree)malloc(sizeof(BiNode));bt->data=t->data;bt->lchild=Copy(t->lchild);bt->rchild=Copy(t->rchild);}return(bt);}《数据结构》期末复习题及参考答案-第7章图////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、以下数据结构中，哪种具有非线性结构？A．栈B．队列C．双向链表D．十字链表2、下面关于图的存储的叙述中正确的是（）。A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历4、图的广度优先遍历算法类似于树的（）。A.中根遍历 B.先根遍历 C.后根遍历 D.按层次遍历5、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．06、设有n个结点的无向图，该图至少应有()条边才能确保是一个连通图。A．n-1