1993年程序员级试题离散数学方面的题解及分析 耿秦云 教授 1994-05-13 ●试题一(程序员级上午试题四) 从供选择的答案中,选出应填入下面关于数据结构叙述中内的正确答案,把编号写在答卷的对应栏内。 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