数据结构试题.docx

1、设计一个算法,利用栈的基本运算返回指定栈中的栈底元素。status Getbase(Sqstack s,int &e)If(s.top=s.base) Error(no data)else e =*s.base;return e;2、利用一维数组A可以对N个整数进行排序，其中一种排序的算法的处理思想是：将N个整数分别作为数组A的N个元素的值，每次（即第i次）从元素AiAN中挑出最小的一个元素Ak(1=k=N)最后将Ak与Ai换位，这样反复N次完成排序。 selectSort (SqList &A ) for (i =1; i A.length; +i) j =SelectMinkey(A,i ); if (i ! = j) A.ri A.rj; / SelectSort3、设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。 status Nizhuan(sqstack s, int a, int b, int t)If(s.top=s.base)error(no data);for(i=0;inext;Return (n);5、修改直接选择排序,每趟从无序区中选择最大元素与当前元素进行交换。 selectSort (SqList &A ) for (i =1; i A.length; +i) j =SelectMaxkey(A,i ); if (i ! = j) A.ri A.rj; / SelectSort6、用不带头结点的单链表存储链栈,设计初始栈、判断栈是否为空、进栈和出栈等相应的算法。 （1）入栈操作【单个链栈的入栈操作】int pushLstack(SlStackType *top,ElemType x)/将元素x压入链栈top中slStacktype *p;if(p=(slStacktype*)malloc(sizeof(slStacktype)=NULL) return FALSE; /申请一个结点p-data=x; p-next=top; top=p; return TRUE;（2）出栈操作【单个链栈的出栈操作】Elemtype popLstack(slStacktype *top)/从链栈top中删除栈顶元素slStacktype *p;Elemtype x;if (top= =NULL) return NULL; /空栈p=top; top=top-next; x=p-data;free(p);return x;1、简述逻辑结构与存储结构的关系。答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。2、在什么情况下，使用顺序表比链表好？ 答： 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素。3、简述二路归并排序思想。答：将两个有序表合并为一个有序表。1个元素的表总是有序的，所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成 个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。4、在单链表和双向表中，能否从当前结点出发访问到任一结点? 答： 在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。5、简述线性表、栈和队列的异同。 答： 栈和队列是操作位置受限的线性表，即对插入和删除的位置加以限制。栈是仅允许在表的一端进行插入和删除的线性表，因而是后进先出表。队列只允许在表的一端进行插入，另一端进行删除操作的线性表，因而是先进先出表。 6、已知一组元素为(46、25、78、62、18、34、12、40、73)，试画出按元素排列顺序输入而生成的一棵二叉排序树。 答： 得到的二叉排序树如下图所示。7、画出对长度为10的有序表进行二分查找的一棵判断树,并求其等概率时查找成功的平均查找长度。 答： 判断树（略）。 ASL=（1+2+2+3+3+3+3+4+4+4）/10=2.98、数据结构与数据类型有什么区别？ 答： “数据结构”这一术语有两种含义，一是作为一门课程的名称；而是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。9、简述顺序表和链表存储方式的特点。 答： 顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。10、为什么说栈是一种后进先出表? 答： 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO-Last IN First Out表）。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)； 答: 根据堆的定义可知堆中元素满足下面中的某一个式子的关系， 因此(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 2nn1 (n1)其中，n为编号元素的个数，Cn 是可能的排列数目。14、对链表设置头结点的作用是什么?(至少说出两条好处) 答：(1)