数据结构辅导习题.doc

第一章 绪论 1．数据结构是按照某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个________的集合。 A．逻辑结构 B．物理结构 C．算法 * D．运算 2．数据结构在形式上可定义为一个二元组：D=（K，R），其中K是________的有限集合，R是K上关系的有限集合。 A．数据操作 B．逻辑结构 C．算法 * D．数据元素 3．在数据结构中，从逻辑上可以把数据结构分为________。 * A．线性结构和非线性结构 B．内部结构和外部结构 C．动态结构和静态结构 D．紧凑结构和非紧凑结构 4．算法的时间复杂度与________有关。 　 *Ａ．求解问题的规模和所处理数据集的初始状态 　 B．算法本身的难度和执行算法所耗费的存储空间 C．求解问题的规模和执行算法所耗费的存储空间 D．算法本身的难度和所处理数据集的初始状态 5．分析下面程序段的时间复杂度。 for (i=1; i=n; i++) for (j=1; j=i; j++) x++; 解答：第一个语句执行n+1次，第二个语句执行n(n+3)/2次，第三个语句执行n(n+1)/2次，总共执行次数为n+3n+1，其时间复杂度为O（n）。 6．分析下面程序段的时间复杂度。 for (i=1; i=n; i++) for (j=1; j=i; j++) for (k=1; k=j; k++) x++; 解答：第一个语句执行n+1次，第二个语句执行n(n+3)/2次，第三个语句执行 次，第四个语句执行次，共执行次数为这四个语句执行次数之和，其时间复杂度为O（n3）。该程序段中执行频度最大的语句是x++。为了简单起见，只考虑第四个语句执行次数，因此可以从内层循环向外层循环分析语句x++的执行次数，也可以用下式表示： ＝ 7．分析下面程序段的时间复杂度。 for (i=1; i＝n; i++) { j=i; while (j=2) j=j/2; } 解答：对于for循环而言，循环次数为n次，while循环的执行次数与i有关，对于每个i，while循环执行log2i次，因此，算法的时间复杂度为 O(nlog2n) 8． 有如下递归函数fact(n)，分析其时间复杂度。 void fact(int n) { if (n=1) ① fact=1; ② else fact=n*fact(n-1); } 解答：设fact（n）的运行时间函数为T（n），该函数中语句①的运行时间是O（1），语句②的运行时间是T（n-1）+O（1），因此，有 则， T(n) ＝O(1)+T(n-1) ＝2*O(1)+T(n-2) …… ＝(n-1)*O(1)+T(1) ＝n*O(1) ＝O(n) 因此，递归函数fact(n)的时间复杂度为O(n)。 第二章 线性表 一．基本知识 1．________是一个线性表。 A．由n个实数组成的集合 * B．由100个字符组成的序列 C．由所有整数组成的序列 D．一维数组 2．线性表采用顺序存储结构，其特点是可以用物理位置上的邻接关系来表示结点间的________关系。 A．*逻辑 B．物理 C．运算 D．连接 3．线性表采用链式存储时，其地址________。 A.必须是连续的 B.有一部分必须是连续的 C.一定是非连续的 * D.连续与否均可以 4.在单链表中查找元素的时间复杂度为_______