c语言
果采用链式存储结构,也只能用顺序查找。 考点 10 二分法查找 考试链接:
考点 10 在笔试考试中考核几率为 30%,一般出现填空题中,分值为 2 分,考核比较多查找 的比较次数,读者应该具体掌握二分查找法的算法。 二分法只适用于顺序存储的,按非递减排列的有序表,其方法如下: 设有序线性表的长度为 n,被查找的元素为 i, (1)将 i 与线性表的中间项进行比较; (2)若 i 与中间项的值相等,则查找成功; (3)若 i 小于中间项,则在线性表的前半部分以相同的方法查找; (4)若 i 大于中间项,则在线性表的后半部分以相同的方法查找。 疑难解答:二分查找法适用于哪种情况? 二分查找法只适用于顺序存储的有序表。 在此所说的有序表是指线性表中的元素按值非递减 排列(即从小到大,但允许相邻元素值相等) 。 这个过程一直进行到查找成功或子表长度为 0 为止。 对于长度为 n 的有序线性表,在最坏情况下,二分查找只需要比较 log2n 次。 1.6 排序技术 考点 11 交换类排序法 考试链接: 考点 11 属于比较难的内容,一般以选择题的形式考查,考核几率为 30%,分值约为 2 分, 读者应该熟练掌握几种排序算法的基本过程。 冒泡排序法和快速排序法都属于交换类排序法。 (1)冒泡排序法 首先,从表头开始往后扫描线性表,逐次比较相邻两个元素的大小,若前面的元素大于后面 的元素,则将它们互换,不断地将两个相邻元素中的大者往后移动,最后最大者到了线性表 的最后。 然后,从后到前扫描剩下的线性表,逐次比较相邻两个元素的大小,若后面的元素小于前面 的元素,则将它们互换,不断地将两个相邻元素中的小者往前移动,最后最小者到了线性表 的最前面。 对剩下的线性表重复上述过程,直到剩下的线性表变空为止,此时已经排好序。 在最坏的情况下,冒泡排序需要比较次数为 n(n-1)/2。 (2)快速排序法 它的基本思想是:任取待排序序列中的某个元素作为基准(一般取第一个元素) ,通过一趟 排序, 将待排元素分为左右两个子序列, 左子序列元素的排序码均小于或等于基准元素的排 序码,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序, 直至整个序列有序。 疑难解答:冒泡排序和快速排序的平均执行时间分别是多少? 冒泡排序法的平均执行时间是 O(n2) ,而快速排序法的平均执行时间是 O(nlog2n) 。 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〔log2n〕+1。 答案:B) 【例 7】在快速排序过程中,每次划分,将被划分的表(或子表)分成左、右两个子表,考 虑这两个子表,下列结论一定正确的是。 (考点 11) A)左、右两个子表都已各自排好序 B)左边子表中的元素都不大于右边子表中的元
2010最新计算机二级c公共基础知识 很全很新的二级公共知识很全很新的二级公共...同一个算法用不同的语言实现,或者用不同的编译程序进行编译,或者在不同 同一...
计算机二级公共基础知识... 73页 免费 计算机二级C语言(重要知... 38页 ...一个算法所占用的存储空间包括算法程序所占的空间、 一个算法所占用的存储空间...
2010年计算机二级C语言编程公共基础知识 隐藏>> 特别说明此资料来自百度文库(http://wenku.baidu.com/) 您目前所看到的文档是使用的抱米花百度文库下载器所生成...
二级公共基础知识总结 12页 1财富值 计算机二级C公共基础知识题... 7页 2...同一个算法用不同的语言实现, 或者用不同的编译程序进行编译, 或者在不同的...
全国计算机二级C语言公共基础知识_IT认证_资格考试/认证_教育专区。二级公共基础知识辅导 知识点分布第一章 数据结构与算法 第二章 程序设计基础 第三章 软件工程...
全国计算机二级C语言公共基础知识_IT认证_资格考试/认证_教育专区。二级公共基础知识辅导 知识点分布第一章 数据结构与算法 第二章 程序设计基础 第三章 软件工程...
2010计算机二级c公共基础知识(最新最全2010计算机二级c公共基础知识(最新最全隐藏>> 二级公共基础知识辅导 知识点分布第一章 数据结构与算法 第二章 程序设计...
计算机二级公共基础知识20... 145页 1财富值 2010年最新计算机二级C语言......其中最关键的是,肯定以提高程序清晰性为目标的结构化方法。 二、结构化程序的...
全国计算机等级考试二级C语言公共基础知识题例_其它考试_资格考试/认证_教育专区...算法程序中的指令条数 (12) 下列叙述中正确的是___。(A) A. 线性表是线性...
热门文档