二级公共基础课件2013.ppt

本章内容 1.1 算法基本特征 [2008.4]算法的有穷性是指 A)算法程序的运行时间是有限的 B)算法程序所处理的数据是有限的 C)算法程序的长度是有限的 D)算法只能被有限的用户使用 1.2 时间和空间复杂度 1.2 时间和空间复杂度 [2010.3]算法的时间复杂度是指 A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数 1.2 时间和空间复杂度 [2009.9]算法的空间复杂度是指 A)算法在执行过程中所需要的计算机存储空间 B)算法在执行过程中所需要的临时工作单元数 C)算法所处理的数据量 D)算法程序中的语句或指令条数 1.2 时间和空间复杂度 [2011.9]下列叙述中正确的是 A)算法就是程序 B)设计算法时只需要考虑数据结构的设计 C)设计算法时只需要考虑结果的可靠性 D)以上三种说法都不对 1.2 时间和空间复杂度 [2006.9]下列叙述中正确的是 A)一个算法的空间复杂度大，时间复杂度必定大 B)一个算法的空间复杂度大，时间复杂度必定小 C)一个算法的时间复杂度大，空间复杂度必定小 D)以上三种说法都不对 2 数据的逻辑结构 数据的逻辑结构包含两个要素： ①数据元素的集合，记为 D ②D中各数据元素之间的前后件关系，记为 R 数据结构 B 表示为：B = (D, R) 2 数据的存储结构 数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。一种数据结构的逻辑结构根据需要可以表示成多种存储结构。 采用不同的存储结构，其数据处理的效率是不同的。 2 数据结构 [2005.4]数据的存储结构是指 A)存储在外存中的数据 B)数据所占的存储空间量 C)数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表示 2 数据结构 [2007.4]下列叙述中正确的是 A)算法的效率只与问题的规模有关，与数据的存储结构无关 B)数据的逻辑结构与存储结构是一一对应的 C)算法的时间复杂度与空间复杂度一定相关 D)算法的时间复杂度是指执行算法所需要的计算工作量 2 数据结构 [2007.9]下列叙述中正确的是 A)程序执行的效率与数据的存储结构密切相关 B)程序执行的效率只取决于程序的控制结构 C)程序执行的效率只取决于所处理的数据量 D)以上三种说法都不对 3.2 线性表 3.3 顺序线性表的插入 3.3 顺序线性表的删除 [2012.3]在长度为 n 的顺序存储的线性表中删除一个元素，最坏情况下需要移动表中的元素个数为 。 3.4 顺序查找 顺序查找：对于长度为 n 的线性表，平均要进行n/2 次比较，在最坏情况下进行 n 次比较。 3.4 顺序查找 [2006.9]在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为 A)63 B)64 C)6 D)7 3.5 求极值 3.5 求极值 [2010.9]在长度为n的线性表中，寻找最大项至少需要比较 次。 3.6 二分查找 二分查找：适用于顺序存储的有序表，对长度为 n 的线性表，在最坏情况下进行 log2n 次比较。 3.6 二分查找 [2011.3]有序线性表能进行二分查找的前提是该线性表必须是 存储的。 3.6 二分查找 [2005.9]下列数据结构中，能用二分法查找的是 A)顺序存储的有序线性表 B)线性链表 C)二叉链表 D)有序线性链表 3.6 二分查找 [2005.4][2008.9][2010.3]在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是 A)O(n) B)O(n2) C)O(log2n) D)O(n log2n) 3.7 线性链表 线性链表：即线性表的链式存储结构。在线性链表中，各数据结点的存储空间可以不连续，各数据元素的存储顺序与逻辑顺序可以不一致。 3.7 线性链表的操作 在线性链表中进行插入与删除，不需要移动链表中的元素。 3.7 线性链表 [2010.9]下列叙述中正确的是 A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D)上述三种说法都不对 3.7 线性链表 [2005.4][2011.9]关于线性链表的叙述，正确的是