数据结构复习题：绪论问答题1、当你为解决某一问题而选择数据结构时,应从哪些方面考虑? 答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及 以下三点：(1) 程序运行时所需输入的数据总量。(2) 计算机执行每条指令所需的时间。(3) 程序中指令重复执行的次数。2、简述逻辑结构与存储结构的关系. 答：数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关联方式或“邻接关系”)，数据的存储 结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。3、数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于 运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的.答：栈和队列的逻辑结构相同，其存储表示也可相同(顺序存储和链式存储)，但由于其运算集合不同而成为 不同的数据结构。数据结构复习题：线性表问答题1、线性表有两种存储结构：一是顺序表，二是链表。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自 动地改变。在此情况下，应选用哪种存储结构?为什么?(3) 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那 么，应采用哪种存储结构?为什么? 答：(1)顺序存储是按索引(隐含的)直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元 素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域 存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素， 这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移 动元素，仅修改指针即可。所以很容易实现表的容量扩充。(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元 素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所 以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么? 不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、扩充和删除各种信息，才 能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。3、在单链表和双向表中，能否从当前结点出发访问到任一结点? 在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有 指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。4、对链表设置头结点的作用是什么?(至少说出两条好处)答：(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结 点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插 入结点或删除该结点时操作会复杂些。(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。5、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的 链表中删去？若可以，其时间复杂度各为多少？答：1.单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指 针，所以无法访问到 p 指针指向的结点的直接前趋。因此无法删去该结点。2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以 删除该结点。其时间复杂度为0(1)。3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表， 所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为0(n)。6、简述顺序表和链表存储方式的特点。答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因 而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不 如顺序表方便，但结点的插入、删除操作较简单。数据结构复习题：栈和队列问答题1 、试述栈的基本性质?答：由栈的定义可知，这种结构的基本性质综述如下：(1) 集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；(2) 线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；(3) 受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4) 数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好 满足卡塔南数列的计算，即：Cn =Cn 2n /(n+1)其中， n 为编号元素的个数， Cn 是可能的排列数目。4、为什么说栈是一种后进先出表?栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一 端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH), 删除则称为退栈(POP)。栈也称为后进先出表(LIFO-Last IN First Out表)。5、对于一个栈，给出输入项A,B,C。如果输入项序列由A,B,C所组成，试给出全部可能的输出序列。ABC，BAC，CBA6、有字符串次序为3*y-a/yf2,试利用栈给出将次序改变为3y-*ay2f/-的操作步骤。(可用X代表扫描该字符串 函数中顺序取一字符进栈的操作，用S代表从栈中取出一个字符加到新字符串尾的出栈的操作)。例如:ABC变 为BCA,则操作步骤为XXSXX。X:进栈 S:出栈 XSXXXSSSXXSXXSXXSSSS7、跟踪以下代码,显示每次调用后队列中的内容。InitQueue(qu);EnQueue(qu,A);EnQueue(qu,B); EnQueue(qu,C); EnQueue(qu,x; EnQueue(qu,x;EnQueue(qu,D); EnQueue(qu,E); EnQueue(qu,F); EnQueue(qu,x)EnQueue(qu,G);EnQueue(qu,X) EnQueue(qu,X)EnQueue(qu,X) 答：InitQueue(qu); EnQueue(qu,A); EnQueue(qu,B); EnQueue(qu,C);EnQueue(qu,x; EnQueue(qu,x; EnQueue(qu,D); EnQueue(qu,E); EnQueue(qu,F); EnQueue(qu,x) EnQueue(qu,G); EnQueue(qu,X) EnQueue(qu,X) EnQueue(qu,X)队列为空队列为A队列为AB队列为ABC队列为 ABCx队列为 ABCxx队列为ABCxxD队列为ABCxxDE队列为ABCxxDEF队列为ABCxxDEFx 队列为 ABCxxDEFxG 队列为 ABCxxDEFxGX 队列为 ABCxxDEFxGXX 队列为 ABCxxDEFxGXXX&假设Q0.10是一个线性队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化 情况,若不能入队,请指出其元素,并说明理由。d,e,b,g,h 入队 d,e 出队 i,j,k,l,m 入队 n,o,p 入队解答： d,e,b,g,h 入队debghFrd,e 出队bghFri,j,k,l,m 入队bghij k l mFrn,o,p 入队bghij k l m n o pFr所有元素均正好能入队，共有11个存储空间，恰好11个元素9、假设CQO.1O是一个环形队列，初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化 情况,若不能入队,请指出其元素,并说明理由。d,e,b,g,h 入队d,e 出队i,j,k,l,m 入队b出队n,o,p 入队解答： 图略 。p不能入队，共有11个地址，p为第12个元素，故不能入队10、有5个元素，其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一 个且D第一个出栈)的次序有哪几个？答：三个：CDEBA，CDBEA，CDBAE11、设输入元素为1、2、3、P和A,入栈次序为123PA,元素经过栈后到达输出序列，当所有元素均到达输出 序列后,有哪些序列可以作为高级语言的变量名？答：一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是:AP321,PA321,P3A21,P32A1,P321A。12、简要叙述栈和队列的特点.答：栈和队列都是插入和删除操作的位置受限制的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表数据结构复习题：树和二叉树问答题1、对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。其特点是只有最下面的二层结点可以小于2,其它结点的度数必须为23、已知一组元素为(46、 25、 78、 62、 18、 34、 12、 40、 73)，试画出按元素排列顺序输入而生成的一棵二 叉排序树。解答：得到的二叉排序树如下图所示。4625781834 621240734、已知一棵树的边的集合表示为： (L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G), (D,H),(D,I),(D,J),(A,B),(A,C),(A,D)画出这棵树，并回答下列问题：(1) 树根是哪个结点？哪些是叶子结点？哪些是非终端结点？(2) 树的度是多少？各个结点的度是多少？(3) 树的深度是多少？各个结点的层数是多少？以结点G为根的子树的深度是多少？(4) 对于结点G,它的双亲是哪个结点？它的祖先是哪些结点？它的孩子是哪些结点？它的子孙是哪些 结点？它的兄弟和堂兄弟分别是哪些结点？解答：树的根是A,而E、F、C、H、I、J、K、M、N是叶子结点，其它为非终端结点。(2) 树的度为 4。deg(A)=3,deg(B)=2,deg(D)=4,deg(G)=3,deg(L)=1,其它各叶子结点的度均为0。(3) 树的深度为 5(设根结点的深度为 1)level(A) = 1,level(B)=2,level(C)=2,level(G)=3,level(K) =4,., level(N)=5。(4) D是G的双亲；A、D是G的祖先；K、L、M是G的孩子；K、L、M和N是G的子孙；H、I、J 是G的兄弟；E、F是G的堂兄弟。5、设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。 解答：最大值(高度为h的满二叉树)20 +21 +22 +2h-1 =2h 1最小值：第一层只有一个结点，其余的h-1层各有2个结点，所以最小值