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