数据结构考试重点题

数据结构考试重点题数据结构考试重点题数据结构考试重点题资料仅供参考文件编号：2022年4月数据结构考试重点题版本号：A修改号：1页次：1.0审核：批准:发布日期：问答题：1.简述逻辑结构与存储结构的关系.答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。2.在什么情况下使用顺序表比链表好？答：若线性表的总长度基本稳定，且很少进行插入和删除操作，但要以最快的速度存取线性表中的元素。3.简述二路归并排序思想.

答：将两个有序表合并为一个有序表。1个元素的表总是有序的，所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。4.在单链表和双向表中，能否从当前结点出发访问到任一结点

答：在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。5.简述线性表，栈和队列的异同？答：栈和队列是操作位置受限的线性表，即对插入和删除的位置加以限制，栈是仅允许在表的一端进行插入和删除的线性表，因而是后进先出表，队列是只允许在表的一端进行插入，另一端进行删除的线性表，因而是先进先出表。6.已知一组元素（46,25,78,62,18,34,12,40,73），试画出按元素排列顺序输出而生成的二叉排序树？答：46781834621240737．画出对长度为10的有序表进行二分查找的一棵判断树，并求其等概率时查找成功的平均查找长度？答：判断树5813694710ASL=（1+2+2+3+3+3+3+4+4+4）/10=2.98.“数据结构”这一术语有两种含义，一是操作为一门课程的名称，二是作为一个科学的概念，作为科学概念，且目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行操作（运算），而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。9.简述顺序表和链表存储方式的特点

答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。10.为什么说栈是一种后进先出表

答：栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO--LastINFirstOut表）。11.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。(1)(100，85，98，77，80，60，82，40，20，10，66)。(2)(100，98，85，82，80，77，66，60，40，20，10)。(3)(100，85，40，77，80，60，66，98，82，10，20)。(4)(10，20，40，60，66，77，80，82，85，98，100)。答：根据堆的定义可知堆中元素满足下面中的某一个式子的关系，┌≤k2i┌≥k2i①ki或②ki└≤k2i＋1└≥k2i＋1因此(1)、(2)和(4)序列是堆。(3)不是堆。(3)调整为100,98,66,85,80,60,40,77,82,10,20后成为堆。12.有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个

答：三个：CDEBA，CDBEA，CDBAE13．试述栈的基本性质

答：由栈的定义可知，这种结构的基本性质综述如下：(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即：Ｃn＝Ｃn2n/(n＋1)其中，n为编号元素的个数，Cn是可能的排列数目。14.对链表设置头结点的作用是什么

答：(1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。(2)对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。算法题：设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。答：statusGetbase(Aqstacks,int&e){If(s.top==s.base)Error(‘nodata’)elsee=*s.base;returne;}利用一维数组A可以对N个整数进行排序，其中一种排序的算法的处理思想是：将N个整数作为数组A的N个元素的值，每次（即第一次）从元素A[1]~A[N]中挑出最小的一个元素A[K]（1<=K<=N），然后将A[K]与A[1]换位，这样反复N次完成排序，编写实现上述算法的函数？答:SelectSort(sqlist&A){For(i=1;KA.length;++i);{J=selectminkey(A,i);If(i=J)A.R[i]<-->A.R[J];}}//selectsort设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。答：statusNizhuan(sqstacks,inta,intb,intt){If(s.top==s.base)error(‘nodata’);for(i=0;i<s.stacksize/2;i++){a=*--top;b=*s.base;t=b;b=a;a=t;s.base++;}}在栈项指针为HS的链栈中，编写算法计算该链栈中结点个数？答：statussum(linkedstackHS.elemtypeN){IntN=0;While(HS!=NULL);{N++;HS=HS->next;}Return(N);}修改直接选择排序,每趟从无序区中选择最大元素与当前元素进行交换.

答：selectSort(SqList&A){for(i=1;i<A.length;++i){j=SelectMaxkey(A,i);if(i!=j)A.r[i]<-->A.r[j];}}//SelectSort用不带头结点的单链表存储链栈,设计进栈和出栈的算法。答：（1）入栈操作【单个链栈的入栈操作】intpushLstack(slStacktype*top,Elemtypex){//将元素x压入链栈top中slStacktype*p;if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL)returnFALSE;//申请一个结点p->data=x;p->next=top;to