软件基础知识试题精解(编辑修改稿)

软件基础知识试题精解(编辑修改稿)内容摘要：

结果就是题中问题 E 的 答案 【答案】： A： ③ B： ③ C： ② D： ① E： 试题 3(1999 年 试题 从供选择的答案中，选出应填入下面叙述中 { }内的最确切的解答，把相应编号 给定数据结构 (V， E)， V为结点的有限集合， V={V1， V2， V3， V4， V5， V6， V7，V8}， E 是 V 上 E={＜ V1， V2＞，＜ V3， V4＞，＜ V5， V8＞，＜ V6，＜ V1， V3＞， V4＜， V5＞，V6＜，＜ V1 ， V3＞， V4＜， V5＞，＜ V2， V4＞， V4＜， V6＞＝它所 对应的图表是 { A }， 这就是 { B }。 图的存储 结构主要有邻接表和 { C }，若用 邻接表来存储一个图，则需要保存一个 { D }存 储的结点表和若干个 { E }存 储的关系 (又 称边表 )。 供 A： B： ①树 ②无向图 ③有向图 中国 最庞大的下资料库 (整理 . 版权归原作者所有 ) 第 15 页 共 34 页 C： ①转称矩阵 ②邻接矩阵 ③状态矩阵 D： ①顺序 ②链接 ③散列 【解析】 本 题是一道关于图的试题，应该说是比较简单的 在 数据结构 (V， E)中，有 关系＜ V1， V2＞和＜ V1， V3＞， 这样很快就答案案③和④排除了， 然后再看答案 ①②。 在数据结构 (V， E)中， 还有关系＜ V2， V4＞， 这在答案②中没有反映出 来，所以又排除了答案②。 既然确定了答案①就是正确的答案，仔细观察该图形，由于关系 ＜ V1， V2＞、＜ V1， V3＞、＜ V2， V4＞，＜ V3， V4＞以及 关系＜ V4， V6＞、＜ V6，V5＞、＜ V4， V5＞的特殊性，我 们排除了该图是树、有向图、无回路图的可能性，数据结构 (V， E)是 图的存储结构主要有邻接表和邻接矩两种。 邻接矩阵是表示结点间的相邻关系的矩阵，若 G 是一 个具有 n 个结点的图，则 G 的 临界阵是如下定义的 nn 矩 A［ ij］ =0，表示 (Vi， Vj)或者 (Vj， Vi)是 G 的 A［ ij］ =1，表示 (Vi， Vj)或者 (Vj， Vi)不是 G 的 用 邻接表来存储一个图，需要保存一个顺序存储的结点表和 n个链接存储的边表。 结点表的 每 个表目对应于图的一个结点，每个表目包括两个字段：一个是结点的数据或指向结点数据 的指 针，另一个是指向此结点的边表的指针。 图的每一个结点都有一个边表，一个结点的边 表的每 个表目对应于与该 结点相关联的一条边。 它的每个表目也包括两个字段：一个是与此 相 边相关联的另一个结点的序号，另一个是指向边表的下一个表目的指针。 对于有向图来说 ，用 【答案】： A： ① B： ② C： ② D： ① E： 试题 4(1998 年 试题 中国 最庞大的下资料库 (整理 . 版权归原作者所有 ) 第 16 页 共 34 页 从供选择的答案中，选出应填入下面叙述中 { }内的最确切的答案，把相应编号 在 内部排序中，通常要对被排序数据序列进行多趟扫描。 各种排序方法有其不同的排序实施 过程和 (时间 )复 对给定的整数序列 (541， 132， 984， 746， 518， 181， 946， 314， 205， 827)进行从小到大的 排序 时，采用冒泡排序和直接选择排序时，若先选出大元素，则第一趟扫描结果分别是 { A }和 { B }；采用快速排序 (以中 间元素 518 为基准 )的第一趟 扫描结果是 { C }。 设被排序数据序列有 n 个元素，冒泡排序和直接选择排序的复杂性是 { D }；快速排序的复 杂性是 { E }。 供 A～ C： ① (181， 132， 314， 205， 541， 518， 946， 827， 746， ② (541， 132， 827， 746， 518， 181， 946， 314， 205， ③ (205， 132， 314， 181， 518， 746， 946， 984， 541， ④ (541， 132， 984， 746， 827， 181， 946， 314， 205， ⑤ (132， 541， 746， 518， 181， 946， 314， 205， 827， ⑥ (132， 541， 746， 984， 181， 518， 314， 946， 205， D、 E： ① O(nlog2n) ② O(n) ③ (nc) ④ O(n2 ⑤ O(log2n)2 ⑥ O(n2log2 【解析】 冒泡排序：冒泡排序的 过程很简单。 首先将第 1 个数与第 2个数相比较，若为逆序则交换两数 ，然后比 较每两个数与第 3个数，依次类推，直到第 n1 个数与第 n个数进行过比较为止。 上 述 过程称为一趟冒泡排序，结果是最大的数被称鲐了最后。 然后进行第 2 趟， 对前面 n1个数 进行冒泡排序，结果是次大的数被移到了 n1的位置上。 一般 来说，第 i 趟冒泡排序是 从第 1 个数到第 ni+1 的位置上，整 个排序过程需进行 k(1≤k≤n) 趟。 分析冒泡排序的效率，若初始序列 为正序，则只进行一次排序。 在排序过程中只进行 n1次 比 较，不交换数据。 若为逆序，则需进行 n1 趟排序，需 进行 n(n1)/2 次比 较，交换数据的数量组也相同。 因此，冒泡排序的复杂性是 O(n2)。 中国 最庞大的下资料库 (整理 . 版权归原作者所有 ) 第 17 页 共 34 页 快速排序是 对冒泡排序的一种改进，其基本思想是通过一趟排序将待排序的数据分成两部分 ，其中一部分的 关键字均比另一部分的关键字小，然后再对这两部分分别进行快速排序，最 后 达到整个序列有序。 快速排序的复杂是 O(nlog2n)。 直接 选择排序，又称简单选择排序，其基本思想是每一趟在 ni+1(i=1， 2， … ，n1)个数据 中 选择最小的数据作为有序序列中的第 i 个 数据。 一趟直接选择排序的基本操作为通过 ni次 关键字的比较，从 ni+1 个数据中选出关键字最小的数据，并和第 i 个数据交换。 直接选择排 序 过程中，所需交换数据的次数较少，最小值为 0，最大值 为 3(n1)。 然而，无论数 据的初始次序如何，它所需 进行的关键字的比较次数相同，均为 n(n1)/2，因此，直接 选择 排序的复 杂性是 O(n2)。 对于题中给定的整数序列 (541， 132， 984， 746， 518， 181， 946， 314， 205， 827)进行从小 到大排序，若先 选出较大的元素，则对于冒泡排序，第 1 趟操 作 为 541←→132 ，984←→746 ， 984←→518 ， 984←→181 ， 984←→946 ， 984←→314 ， 984←→205 ， 984←→827 ，其 结果 得到的序列 为 (132， 541， 746， 518， 181， 946， 314， 205， 827， 984)； 对于直接选择排序 ，第 1 趟操作 为 984←→827 ，其 结果得到的序列为 (541， 132， 827， 746， 518，181， 946， 3 14， 205， 984)。 采用快速排序 (以中 间元素 518 为基准 )的第 1趟 扫描结果是 (205， 132， 314， 181，518， 746 ， 946， 984， 827)。 【答案】： A： ⑤ B： ② C： ③ D： ④ E： 试题 5(1997 年 试题 从供选择的答案中，选出应填入下面的叙述中 { }内的最确切的解答，把相应编号写在答卷 的 设数据结构 (D， R)由 数据结点集合 D={di|1≤i≤7} 及其上的 关系 R R={＜ di1， d|di1， di∈D ， 2≤i≤7} ， 这个数据结构对应于 A。 中国 最庞大的下资料库 (整理 . 版权归原作者所有 ) 第 18 页 共 34 页 R={＜ d4， d2＞， d1＞，＜ d2， d3＞，＜ d4， d6＞，＜ d6， d5＞，＜ d6， d7＞ }， 这个结构的图形是 B， 用 C 遍 历法可以得到 A 的 R={＜ d1， d2＞，＜ d1， d3＞，＜ d2， d4＞，＜ d4， d5＞，＜ d4， d5＞，＜d4， d6＞， ＜ d4， d7＞ }， 这个结构的图形是 D。 用 E 遍 历法可以得到 A 的 供 A、 B、 D： ①二叉树 ②队列 ④线性表 ⑤无向图 C、 E： ①前序 ②中序 ④深度优先 【解析】 该题要求考生熟练掌握数据结构中常用的线性表、二叉树、树、图的结构及其遍历方法。 数 据 结构 (D， R)中， D 由 7个数据组成， R决定这 7 (1)R={＜ di1， d|di1， di∈D ， 2≤i≤7 } 其 对应的数据结构可以表示为 d1→d2→d3→d4→d5→d6→d7 ，它 对应一个线性表。 (2)R={＜ d4， d2＞，＜ d2， d1＞，＜ d2， d3＞，＜ d4， d6＞，＜ d6， d5＞，＜ d6，d7＞ 其 这棵 二叉树利用中序遍历法得到序列为 d1d2d3d4d5d6d7。 中国 最庞大的下资料库 (整理 . 版权归原作者所有 ) 第 19 页 共 34 页 (3)R={＜ d1， d2＞，＜ d1， d3＞，＜ d2， d4＞，＜ d3， d4＞，＜ d4， d5＞，＜ d4，d6＞，＜ d4， d7＞ }， 对应的数据结构为一个有向无回路图，利用广度优先遍历法得到的序列为 d1d2d 3d4d5d6d7，正好 对应 (1)中的 【答案】： A④ B① C② D⑥ E 试题 6(1996 年 试题 从供选择的答案中，选出应填入下面叙述中 { }内的最确切的解答，把相应编号写在答卷的 一棵二叉排序 树可顺序存放在一组物理上相邻的存储区中，每个结点及左、右针依次分别放 在 该存储区的 3 个连续单元中。 现对一棵结点按字母的字典顺序构成的二叉排序树从根结点 P 开始顺序放在一个存储区中，结果如图 22所示。 其中 Li 为第 i个结点的左指针， R为第 i 个结点的右指针，则 L2 应为 A， L4 应为 B， R1 应为 C。 该二叉排序树的前序遍历序列为 D，后序遍 历序列为 E。 供 中国 最庞大的下资料库 (整理 . 版权归原作者所有 ) 第 20 页 共 34 页 A～ C： ① 1003 ② ③ 100A… ④ ⑤ 1006 ⑥ ⑦ 100C ⑧ ⑨ D、 E： ① PBQHCJ ② ③ BCHJPQ ④ CJHBQP ⑤ 【解析】 二叉 树或者为空，或者由一个根结点加上左子树和右子树 (互不相交的 两棵二叉树 )构成，因 此，若依次 遍 历根、左子树、右子树，就有 6种遍 历方法，即 DLR、 DRL、 LDR、RDL、 LRD 和 RL D。 限定先左后右的 顺序，则有常用的前序遍历、中序遍历和后序遍历 3种情 况。 基于二叉 (1)先序遍 历 (DLR)算法：若二叉 树为空，则进行的是空操作，否则访问根结点： 前序遍 前序遍 (2)中序遍 历 (LDR)算法：若二叉 树为空，则进行的是空操作，否则 中序遍。