中央电大-&-数据结构---复习题----综合复习资料.doc(简答题).docx

电大数据结构复核习题（简答题）
1、 简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现?
答:若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构.可见，数据的逻辑结构是反映数据之间的固有关系,而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同,逻辑上相邻的结点,其物理地址未必相同,但可通过结点的内部信息,找到其相邻的结点,从而保留了逻辑结构的特点.采用的存储结构不同,对数据的操作在灵活性,算法复杂度等方面差别较大.
2、 解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。
答：顺序结构存储时，相邻数据元素的存放地址也相邻,即逻辑结构和存储结构是统一的,，要求内存中存储单元的地址必须是连续的。优点:一般情况下,存储密度大,存储空间利用率高。缺点：（1)在做插入和删除操作时,需移动大量元素;(2）由于难以估计,必须预先分配较大的空间，往往使存储空间不能得到充分利用;(3）表的容量难以扩充。
链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针.优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低.
3、 什么情况下用顺序表比链表好?
答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作,则采用链表.
4、 解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？
答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。
5、 解释带头结点的单链表和不带头结点的单链表的区别.
答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。
在结构上，带头结点的单链表,不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。
在操作上,带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点,算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点.因为两种情况的算法步骤不同.
6、 与单链表相比，双向循环链表有哪些优点?
答：双向循环链表设置了指向前驱和后继的指针，所用的地址空间增加,以空间复杂度代价换取时间复杂度的提高。双向循环链表可以从任一结点开始遍历整个链表。在动态内存管理中，应用双向循环链表可以从上次查找过的 结点开始继续查找可用结点，而单链表却每次都需要从表头开始查找。相比之下，双向循环链表的时间效率更高.
7、 简述栈和一般线性表的区别。
答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作.
8、 简述队列和一般线性表的区别。
答：队列是一种先进先出的线性表,队列的插入只能在队尾进行,队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作.
9、 链栈中为何不设头结点?
答：因为链栈只在链头插入和删除结点,不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。
10、 利用一个栈，则:
（1)如果输入序列由A,B，C组成,试给出全部可能的输出序列和不可能的输出序列。
（2)如果输入序列由A,B，C，D组成,试给出全部可能的输出序列和不可能的输出序列.
答：（1）栈的操作特点是后进先出，因此输出序列有：
A入，A出，B入,B出，C入C出,输出序列为ABC.
A入，A出,B入,C入，C出，B出，输出序列为ACB.
A入，B入，B出，A出，C入，C出，输出序列为BAC。
A入，B入，B出，C入，C出,A出，输出序列为BCA。
A入，B入，C入,C出，B出，A出,输出序列为CBA。
由A,B，C组成的数据项,除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，(A不在栈顶位置),最后把B出栈,所以序列CAB不可能由输入序列A，B，C 通过栈得到。
（2）按照上述方法,可能的输出序列有：ABCD，ABDC，ACBD,ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD,CBDA，CDBA，DCBA。不可能的输出序列有：DABC,ADBC，DACB，DBAC，BDAC,DBCA,DCAB，CDAB，CADB，CABD
11、 用S表示入栈操作,X表示出栈操作,若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么?
答:应是SXSSXSXX。各操作结果如下：
S 1入栈
X 1出栈 输出序列:1
S 2入栈
S 3入栈
X 3出栈 输出序列：13
S 4入栈
X 4出栈 输出序列:134
X 2出栈 输出序列:1342
12、 有5个元素,其入栈次序为：A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先的次序有哪几个?
答:从题中可知，要使C第一个且D第二个出栈,应是A入栈,B入栈，C入栈,C出栈，D入栈.之后可以有以下几种情况:
（1）B出栈,A出栈,E入栈，E出栈，输出序列为：CDBAE。
（2)B出栈，E入栈，E出栈,A 出栈,输出序列为CDBEA。
（3)E入栈，E出栈,B出栈，A出栈，输出序列为CDEBA
所以可能的次序有:CDBAE，CDBEA，CDEBA
13、 写出以下运算式的后缀算术运算式
（1）3x2+x-1/x+5 （2）（A+B）＊C—D/(E+F）+G
答；对应的后缀算术运算式：(1）3x2^＊x+1x/—5+ （2)AB+C＊DEF+/-G+
14、 在什么情况下可以用递归解决问题?在写递归程序时应注意什么?
答：该问题必须可以被分解为和该问题具有相同逻辑结构的子问题,即具有递归性质。书写递归程序的要点如下：
（1）问题与自身的子问题具有类同的性质，被定义项在定义中的应用具有更小的尺度.
(2）被定义项在最小尺度上有直接解。
递归算法设计的原则是用自身的简单情况来定义自身，一步比一步简单,确定递归的控制条件非常重要,设计递归算法的方法是：
（1）寻找方法，将问题化为原问题的子问题求解（例如n！=n＊（n-1）！）.
（2）设计递归出口，确定递归终止条件（例如求解n！时，当n=1时,n!=1）.
15、 简述广义表和线性表的区别和联系.
答：广义表是线性表的的推广，它也是n（n>0）个元素a1 ，a2…ai… an的有限序列,其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构,而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。
16、 写出如下图所示的二叉树的先序、中序和后序遍历序列。
答:二叉树的定义是递归的,所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树,又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…。.,这样划分一直进行到树叶结点。
(1）先序为“根左右”,先序序列为:fdbacegihl
（2)中序为“左根右”，中序序列为：abcdefghij
（3)后序为“左右根"，后序序列为：acbedhjigf
17、 已知某二叉树的先序遍历结果是:A，B,D，G,C，E，H，L,I,K,M，F和J,它的中序遍历结果是：G,D，B，A,L,H,E，K，I，M，C，F和J，请画出这棵二叉树,并写出该该二叉树后序遍历的结果。
答：二叉树图形表示如下:
该二叉树后序遍历的结果是：G D B L H K M I E J F C A
18、 已知一棵完全二叉树共有892个结点,求
(1）树的高度
(2）叶子结点数
(3)单支结点数
(4）最后一个非终端结点的序号
答：(1）已知深度为k的二叉树最多有2k—1个结点(K≥1），
　 29-1〈892< 210—1，故树的高度为10
(2)对于完全二叉树来说,度为1的结点只能是0或1
　因为n=n0+n1+n2和n0=n2+1
　 得：设n1=0，892=n0+0+n2=2n2+1　得n2不为整数出错
　　　 设n1=1,892=n0+1+n2=2n2+2　
　　　 得n2 =445→ n0=n2+1=446
　 叶子结点数为446.
（3)由⑵得单支结点数为1
（4)对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结点　 即为最后一个非终端结点，
序号为892/2=446。
19、 给出满足下列条件的所有二叉树.
（1）先序和中序相同
（2）中序和后序相同
（3）先序和后序相同
答：（1）先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树
（2)中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树
（3）先序和后序序列相同的二叉树为空树或仅有一个结点
20、 假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I组成,它们出现的频率分别是:10、20、5、15、8、2、3、7和30。请请用这9个字母出现的频率作为权值求:
（1)设计一棵哈夫曼树;
（2）计算其带权路径长度WPL；
(3）写出每个字符的哈夫曼编码。
答:(1)哈夫曼树如图B—4所示.
图B—4
（2）其带权路径长度WPL值为270。
(3）每个字符的哈夫曼编码为：A:100， B：11， C：1010， D:000， E：0010, F:10110, G:10111, H:0011， I：01
21、 请根据以下带权有向图G
（1）给出从结点v1出发分别按深度优先搜索遍历G和广度优先搜索遍历G所得的结点序列；
（2）给出G的一个拓扑序列；
(3）给出从结点v1到结点v8的最短路径.
答：(1）深度优先遍历：v1，v2,v3，v8,v5，v7，v4，v6 广度优先遍历：v1,v2，v4,v6,v3，v5，v7,v8
（2）G的拓扑序列为：v1,v2，v4，v6，v5，v5，v3,v5，v7，v8
(3）最短路径为:v1,v2,v5,v7，v8
22、 已知无向图G描述如下：
G=（V，E）
V=｛V1，V2,V3，V4，V5}
E=｛（V1，V2），（V1，V4），（V2,V4），(V3,V4），（V2，V5），（V3，V4），(V3,V5）｝
（1)画出G的图示；
（2)然后给出G的邻接矩阵和邻接表；
(3)写出每个顶点的度.
答：(1)g1的图示和图g1的邻接表如下图所示.
图G
（2)图G的邻接矩阵如下图所示：
0 1 0 1 0
1 0 0 1 1
0 0 0 1 1
1 1 1 0 0
0 1 1 0 0

图G的邻接矩阵 图G的邻接表
(3）V1、V2、V3、V4、V5的度分别为：2，3，2，3,2
23、 回答下列问题：
（1）对于存储结构采用邻接矩阵的无向图,如何判断下列有关问题？
①图中有多少条边？
答：矩阵中所有非0元素的个数的一半.
②任意两顶点间是否有边相连？
答：若第i行第j列的元素非0，则说明i顶点和j顶点间有边，否则说明其没边。
③任意一个顶点的度是多少？
答：第i行（列）中非0元素的个数即为第i个顶点的度。
(2)对于存储结构采用邻接表的有向图，如何判断下列有关问题?
①图中有多少条边？
答：邻接表中边（弧）结点的个数。
②图中是否存在从Vi到Vj的边?
答:若在第i个单链表中存在值域为j的弧结点,则说明存在从Vi到Vj的边，否则说明不存在从Vi到Vj的边。
③如何求顶点Vi的入度和出度？
答：第i个单链表中边（弧)结点的个数为顶点Vi的出度.所有单链表中值域为i的边（弧)结点的个数为顶点Vi的入度。
24、 已知序列(70,83,100，65，10，32，7，9)，请写出对此序列采用插入排序法进行升序排序时各趟的结果.
答：原始序列：（70),83，100,65，10,32,7，9
第1趟： (70，83),100,65，10,32，7,9
第2趟：（70，83，100）,65，10，32，7，9
第3趟:（65，70，83，100)，10，32，7，9
第4趟：（10，65,70，83,100)，32，7，9
第5趟:（10,32，65,70,83，100),7,9
第6趟：(7,10，32，65，70，83，100）,9
第7趟:（7，9，10，32，65，70，83，100)
25、 已知序列（10,18,4，3，6，12，1，9，15,8）,请写出对此序列采用归并排序法进行升序排序时各趟的结果.
答：原始序列：10,18，4，3，6，12，1，9，15，8
第1趟： ［10,18］［ 3，4］[6，12］［1，9]［ 8,15］
第2趟： ［3，4，10，18，]［ 1，6，9，12］［ 8，15]
第3趟： [3,4，10，18，］［ 1，6，8，9,12,15]
第4趟: ［1，3，4，6,8，9，10，12，15，18］
26、 已知序列（256，301,751,129，937，863，742，694，076，438）请给出采用冒泡排序法对该序列作升序排列时的每一趟结果。
答：原始序列：256，301，751，129，937，863，742，694，076，438
第1趟: 256，301,129，751,863，742,694,076，438，937
第2趟： 256，129,301，751，742，694，076,438，863，937
第3趟: 129，256，301，742，694，076,438，751，863，937
第4趟： 129，256,301,694,076，438,742，751,863，937
第5趟: 129,256，301，076,438，694，742，751,863，937
第6趟: 129，256，076，301，438,694，742，751,863，937
第7趟： 129，076，256，301，438，694，742，751，863，937
第8趟： 076，129，256，301,438,694,742，751,863，937
第9趟： 076,129，256，301，438，694,742，751，863,937
27、 已知序列（503,87，512，61，908,170，897，275，653，462)请给出采用快速排序法对该序列作升序排列时的每一趟结果。
答:原始序列：503，87，512，61，908,170，897，275，653，462
第1趟: ［462，87，275，61，170]503［897，908，653，512］
第2趟: ［170,87，275，61］ 462,503[897，908，653，512］
第3趟: ［87，61］170［275］ 462，503［897,908,653，512］
第4趟: 61 [87]170［275] 462，503[897,908,653，512］
第5趟: 61 ，87，170，［275］ 462，503［897，908,653,512］
第6趟: 61 ，87，170,275，462,503［897,908，653,512］
第7趟: 61 ，87，170,275，462,503［512，653］897［908]
第8趟： 61 ，87，170,275，462,503,512，［653］ 897［908]
第9趟： 61 ,87，170,275，462，503,653，897[908］
第10趟： 61 ，87,170,275,462,503,653，897，908
28、 设一组记录的关键字序列为（51，85，61，43，45，49）,采用堆排序算法完成以下操作：（要求小根堆,并画出中间过程)
(1）以二叉树描述6个元素的初始堆;
（2）以二叉树描述逐次取走堆顶元素后,经调整得到的5个元素、4个元素的堆;
答：（1)6个元素的初始堆:
51
61
85
43
45
49
85
49
43
45
61
51
51
85
43
49
45
61
49
85
45
61
51
43
45
49
85
51
61
43

（2)经调整得到的5个元素、4个元素的堆：
61
49
43
51
85
45
45
49
43
61
85
51
61
49
43
45
85
51
49
43
85
61
45
51
49
43
45
85
51
61

29、 设查找表为（20，19，24，57,68，11)
30、 （1)用冒泡对该表进行排序，要求写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？
31、 (2）在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）；
32、 （3）求在等概率条件下，对上述有序表成功查找的平均查找长度。
答：（1）原序列16 15 20 53 64 7
15 16 20 53 7 64 n—1趟
7
15
20
64
16
535
15 16 20 7 53 64 n-j次
15 16 7 20 53 64
15 7 16 20 53 64
7 15 16 20 53 64
(2)其进行折半查找所对应的判定树（如右图）：
(3)平均查找长度=（1＊1+2＊2+3＊3）/6=14/6
33、 （1）设有查找表｛8,17，5，9，21，10，7，19，6｝,依次取表中数据，构造一棵二叉排序树。
(2）说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
2
4
6
16
7
3
18
5
145
答:（1）二叉排序树：
34、 （2）中序遍历：2，3，4,5,6，7，14，16,18