1993年程序员级试题离散数学方面的题解及分析
从供选择的答案中,选出应填入下面关于数据结构叙述中内的正确答案,把编号写在答卷的对应栏内。
1.已知一棵二叉树的前序序列和中序序列分别为:ABDEGCFH和DBGEACHF,则该二叉树的后序序列为A,层次序列为B。
2.设有n个结点进行排序,不稳定的排序是C,快速排序的最大比较次数是D。
3.设有100个结点,用二分法查找时,最大比较次数是E。
供选择的答案:
A、B:①GEDHFBCA ②DGEBHFCA ③ABCDEFGH ④ACBFEDHG
C:①直接插入排序 ②冒泡排序 ③shell排序 ④归并排序
D:①nlog2n ②n2 ③n2/2 ④n
E:①25 ②50 ③10 ④7
答案:A:② B:③ C:③ D:② E:④
分析:为了寻找A,B的答案,应根据二叉树的前序序列ABDEGCFH和中序序列DBGEACHF,画出二叉树来,所画二叉树如下图所示。
按后序行遍法周游此树得序列为
DGEBHFCA,
这正是供选答案中的②,易知层次序列为
ABCDEFGH,
这正是供选答案中的③,
C的供选答案中,只有③shell排序是不稳定的,因而C的答案应为③。
快速排序的最大比较次数的数量级为n2,所以D的答案为②。
用二分法查找的,最大比较次数的数量级为log2n 〔log2100〕=7,故E的答案应为④。
●试题二(程序员级上午试题6)
从供选择的答案中选出应填入下面关于数据结构叙述中 内的正确答案。
下图是带权的有向图G的邻接表表示法。以结点V1出发深度遍历图G所得的结点序列为A;广度遍历图G所得的结点序列是B;G的一个拓扑序列是C;从V1到V8的最短路径是D;从结点V1到V8的关键路径是E。
供选择的答案:
A～C:①V1,V2,V3,V4,V5,V6,V7,V8
②V1,V2,V4,V6,V5,V3,V7,V8
③V1,V2,V4,V6,V3,V5,V7,V8
④V1,V2,V4,V6,V7,V3,V5,V8
⑤V1,V2,V3,V8,V4,V5,V6,V7
⑥V1,V2,V3,V8,V4,V5,V7,V6
⑦V1,V2,V3,V8,V5,V7,V4,V6
D、E:①(V1,V2,V4,V5,V3,V8)
②(V1,V6,V5,V3,V8)
③(V1,V6,V7,V8)
④(V1,V2,V5,V7,V8)
答案:A:⑥ B:③ C:② D:④ E:②
分析:本题要求考生掌握以下几方面的概念及运算:
(1)掌握一般图的周游问题,具体说来是掌握一般有向图按深度方向周游(或遍历)的运算和按广度方向周游(或遍历)的运算;
(2)掌握一般有向图结点的拓扑序列的概念及会求出结点的一个拓朴序列;
(3)会求有向带权图中指定两个结点之间的最短路径并求出它的权;
(4)会求无回路(数据结构中常称回路为环)有向带权图中从发点(入度为0的结点)到收点(出度为0的结点)的关键路径(其实是发点到收点的最长路径)。
本题中的有向带权图是以邻接表表示法给出的。由于图G的结点少,又题目并没要求给出具体的算法和步骤,因而采用“ 图上作业法”较为方便,所以首先将邻接表表示的图还原成图形,所得图如下图所示:
在以下的各运算中,做一个如下的规定:若结点Vi1,Vi2,……Vis(i1<i2<……<is)同时具备可被访问(或选择)的资格,规定首先访问Vi,记这种规定为(*)。
(1)从供选答案中寻找从V1出发的按深度遍历图的结点序列。
V1邻接到V2，V4，V6，按(*)的规定及深度方向遍历的规则，得序列
V1，V2，V3，V8 a
回到a中，按(*)，应访问V1邻接到的结点V4，再按深度方向遍历规则，得
V1，V2，V3，V8，V4，V5，V7 b
再回到b，按(*)的规定，访问V1邻接到的结点V6，得序列
V1，V2，V3，V8，V4，V5，V7，V6 c
至此，所有结点都访问过了，得序列c为从V1出发的按深度遍历的结点序列，供选答案中再无其它的所要求的序列，故A的答案为c，即为⑥。
(2)寻找B的答案。
先访问V1邻接到的结点V2，V4，V6，得序列V1，V2，V4，V6 a
注意到V2邻接到未被访问的结点V3，V5；V6邻接到未被访问过的结点V7，得序列
V1，V2，V4，V6，V3，V5，V7 b
V3，V5，V7中有V7邻接到未被访问的结点V8，于是得序列
V1，V2，V4，V6，V3，V5，V7，V8 c
c是从V1出发按广度遍历的结点序列，供选答案中再无其它的要求的序列了，故B的答案为c，即为③。
(3)从供选答案中寻找C的答案。
在求有向图的拓扑序列的每一步骤上，都可能遇到不仅一个入度为0的结点情况。因而一个图对应的拓扑序列是不唯一的，往往有多个拓扑序列，于是检查每个序列，找出拓扑序列来，①V1，V2，V3，V4，V5，V6，V7，V8不是拓扑序列，显然V1，V2删除后，所得图中，结点V3的入度不为0，这就导致了①不是拓扑序列，类似地讨论可知，③_⑦也都不是拓扑序列，而②是拓扑序列，因而C的答案为②。
(4)从供选答案中寻找D的答案。
为了寻找D的答案，首先用Dijkstra标号法求出V1到V8的路径(过程略)，求出的路径为 (V1，V2，V5，V7，V8)
这条路径的权为56，它正是供选择答案中的④，由于两结点之间的最短路径是不唯一的，但权应该相同，有必要再检查一下其余3条路径，经过计算知道，①的权为75，②的权为97，③的权为82，因而它们都不是V1到V8的最短路径，于是D的答案必为④。
(5)导找E的答案
发点到收点的关键路径是这两个结点之间的最长路径，在供选择的4条路径之中，②的权最大，为97，因而若②是关键路径，则它就是E的答案，而其它3条不是。
容易求出各结点的最早完成时间TE，最晚完成时间TL以及缓冲时间TS，见下表。
TS(Vi)=0当且仅当Vi在关键路径上，可见V1，V3，V5，V6，V8在关键路径上，其余结点V2，V4，V7不在关键路径上。本图中关键路径是唯一的，即为(V1，V6，V5，V3，V8)，这就保证了E的答案一定为②。
以上从不同的角度寻找A，B，C，D，E的答案，供读者参考