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