1.7例题详解一、选择题【例1】算法的时间复杂度取决于。（考点2）A）问题的规模B）待处理的数据的初态C）问题的难度D)A）和B)解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输入数据所有的可能取值范围、输入各种数据或数据集的概率有关。答案：D【例2】在数据结构中，从逻辑上可以把数据结构分成。（考点3）B）线性结构和非线性结构A）内部结构和外部结构C）紧凑结构和非紧结构D）动态结构和静态结构解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系，所以答案为B）。答案：B【例3】以下不是栈的基本运算。（考点5）A）判断栈是否为素空B）将栈置为空栈C）删除栈顶元素D）删除栈底元素解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈顶元素等，对栈的操作都是在栈顶进行的。答案：D）。（考点6)【例4】链表不具备的特点是A）可随机访问任意一个结点B）插入和删除不需要移动任何元素D）所需空间与其长度成正比C）不必事先估计存储空间解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所以答案为A)。答案：A）【例5】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是。（考点8)A)ACBEDBDEABCC)DECABD)EDBAC8解析：后序遍历的顺序是”左子树一右子树一根结点”；中序遍历顺序是”左子树一根结点一右子树”；前序遍历顺序是”根结点一左子树一右子树”。根据各种遍历算法，不难得出前序遍历序列是EDBAC。所以答案为D)。答案：D）【例6】设有一个已按各元素的值排好序的线性表（长度大于2），对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别是s和b，在查找不成功的情况下，s和b的关系是（考点9)A) s=bB)s>bC)s<bD)s≥b解析：对于顺序查找，查找不成功时和给定关键字比较的次数为n+1。二分查找查找不成功的关键字比较次数为[log2n］+1。当n≥2时，显然n+1>[log2n]+1。答案：B）【例7】在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子表，下列结论一定正确的是。（考点11)A）左、右两个子表都已各自排好序
1.7 例题详解 一、选择题 【例 1】算法的时间复杂度取决于_。（考点 2） A）问题的规模 B）待处理的数据的初态 C）问题的难度 D）A）和 B） 解析：算法的时间复杂度不仅与问题的规模有关，在同一个问题规模下，而且与输入数据有关。即与输 入数据所有的可能取值范围、输入各种数据或数据集的概率有关。 答案：D） 【例 2】在数据结构中，从逻辑上可以把数据结构分成_。（考点 3） A）内部结构和外部结构 B）线性结构和非线性结构 C）紧凑结构和非紧凑结构 D）动态结构和静态结构 解析：逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结 构表示数据元素之间为一对多或者多对一的关系，所以答案为 B）。 答案：B） 【例 3】以下_不是栈的基本运算。（考点 5） A）判断栈是否为素空 B）将栈置为空栈 C）删除栈顶元素 D）删除栈底元素 解析：栈的基本运算有：入栈，出栈（删除栈顶元素），初始化、置空、判断栈是否为空或满、提取栈 顶元素等，对栈的操作都是在栈顶进行的。 答案：D） 【例 4】链表不具备的特点是_。（考点 6） A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素 C）不必事先估计存储空间 D）所需空间与其长度成正比 解析：顺序表可以随机访问任意一个结点，而链表必须从第一个数据结点出发，逐一查找每个结点。所 以答案为 A）。 答案：A） 【例 5】已知某二叉树的后序遍历序列是 DACBE，中序遍历序列是 DEBAC，则它的前序遍历序列是 _。（考点 8） A）ACBED B）DEABC C）DECAB D）EDBAC 解析：后序遍历的顺序是"左子树－右子树－根结点"；中序遍历顺序是"左子树－根结点－右子树"；前 序遍历顺序是"根结点－左子树－右子树"。根据各种遍历算法，不难得出前序遍历序列是 EDBAC。所以答 案为 D）。 答案：D） 【例 6】设有一个已按各元素的值排好序的线性表（长度大于 2），对给定的值 k，分别用顺序查找法和 二分查找法查找一个与 k 相等的元素，比较的次数分别是 s 和 b，在查找不成功的情况下，s 和 b 的关系是 _。 （考点 9） A）s=b B）s>b C）s<b D）s≥b 解析：对于顺序查找，查找不成功时和给定关键字比较的次数为 n+1。二分查找查找不成功的关键字比 较次数为［log2n］+1。当 n≥2 时，显然 n+1>［log2n］+1。 答案：B） 【例 7】在快速排序过程中，每次划分，将被划分的表（或子表）分成左、右两个子表，考虑这两个子 表，下列结论一定正确的是_。（考点 11） A） 左、右两个子表都已各自排好序
B）左边子表中的元素都不大于右边子表中的元素C）左边子表的长度小于右边子表的长度D）左、右两个子表中元素的平均值相等解析：快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。答案：B）二、填空题【例1】问题处理方案的正确而完整的描述称为。（考点1）解析：计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。答案：算法【例2】一个空的数据结构是按线性结构处理的，则属于。（考点4）解析：一个空的数据结构是线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的，则属于线性结构，否则属于非线性结构。答案：线性结构【例3】设树T的度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数为。（考点7)解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加1。因此树的结点数为1×4十2×2十3×1十4×1十1=16。叶子结点数目等于树结点总数减去度不为0的结点数之和，即16-（4十2+1+1）=8。答案：8【例4】二分法查找的存储结构仅限于且是有序的。（考点10）解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用顺序存储结构，且表中元素必须按关键字有序（升序或降序均可）。答案：顺序存储结构第2章程序设计基础经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是结构化程序设计的原则、面向对象方法的基本概念，读者应对此部分进行重点学习。详细重点学习知识点：1.结构化程序设计方法的四个原则2.对象、类、消息、继承的概念、类与实例的区别2.1结构化程序设计考点1结构化程序设计的原则20世纪70年代提出了”结构化程序设计”的思想和方法。结构化程序设计方法引入了工程化思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。?疑难解答：如何进行自顶向下设计方法？
B） 左边子表中的元素都不大于右边子表中的元素 C） 左边子表的长度小于右边子表的长度 D） 左、右两个子表中元素的平均值相等 解析：快速排序基本思想是：任取待排序表中的某个元素作为基准（一般取第一个元素），通过一趟排 序，将待排元素分为左右两个子表，左子表元素的排序码均小于或等于基准元素的排序码，右子表的排序码 则大于基准元素的排序码，然后分别对两个子表继续进行排序，直至整个表有序。 答案：B）二、填空题 【例 1】问题处理方案的正确而完整的描述称为_。（考点 1）解析：计算机解题的过程实际上是在 实施某种算法，这种算法称为计算机算法。 答案：算法 【例 2】一个空的数据结构是按线性结构处理的，则属于_。（考点 4）解析：一个空的数据结构是 线性结构或是非线性结构，要根据具体情况而定。如果对数据结构的运算是按线性结构来处理的，则属 于线性结构，否则属于非线性结构。 答案：线性结构 【例 3】设树Ｔ的度为４，其中度为１、２、３和４的结点的个数分别为４、２、１、１，则Ｔ中叶子 结点的个数为_。（考点 7） 解析：根据树的性质：树的结点数等于所有结点的度与对应的结点个数乘积之和加１。 因此树的结点数为１×４＋２×２＋３×１＋４×１＋１＝16。叶子结点数目等于树结点总数减去度不 为０的结点数之和，即 16－（４＋２＋１＋１）＝８。 答案：8 【例 4】二分法查找的存储结构仅限于_且是有序的。（考点 10） 解析：二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用 顺序存储结构，且表中元素必须按关键字有序(升序或降序均可）。 答案：顺序存储结构 第 2 章 程序设计基础 经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是结构化程序设计的原则、 面向对象方法的基本概念，读者应对此部分进行重点学习。 详细重点学习知识点： 1．结构化程序设计方法的四个原则 2．对象、类、消息、继承的概念、类与实例的区别 2.1 结构化程序设计 考点 1 结构化程序设计的原则 20 世纪 70 年代提出了"结构化程序设计"的思想和方法。结构化程序设计方法引入了工程化思想和结构 化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为：自顶向下、逐步 求精、模块化和限制使用 goto 语句。 疑难解答：如何进行自顶向下设计方法？