数据结构复习题目.docx

第 1 章 概论 练习题 一、单项选择题 在数据结构中，从逻辑上可以把数据结构分为 A．紧凑结构和非紧凑结构 B．线性结构和非线性结构 C．内部结构和外部结构 D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构 算法分析的两个主要方面是 A．正确性和简明性 B．时间复杂性和空间复杂性 C．可读性和可维护性 D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址 A．不一定连续的 B．部分地址必须是连续的 C．必须是连续的 D．一定是不连续的 算法指的是 A．计算机程序 B．解决问题的计算方法 C．解决问题的有限运算序列 D．排序算法 二、填空题 数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容． 数据的逻辑结构可分为线性结构、非线性结构两大类．  （B） （D） （B） （A） （C） 数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储 结构等四种存储方法表示． 在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要 的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。 设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储． 三、应用题 设 n 为正整数，利用大“O”记号，写出下列各程序段的时间复杂度． 11．for (i = 1; i = n; i++){ y = y + 1; for (j = 1; j = 2 * n; j++) x = x + 1; } 分析：语句 “y = y + 1;”执行n次，语句“x = x + 1;”各执行 2n2次，故该程序段的时间复杂度为O( n2)． 12．s = 0; while (n = (s + 1) * (s + 1)) s = s + 1; nn分析：语句 “s = s + 1;”执行 次，故该程序段的时间复杂度为O( )． n n 13．x = 1; sum = 0; for (i = 0; i = n; i++){ x = x * i; sum = sum + x; } 分析：语句 “x = x * i”和“sum = sum + x;”各执行n次，故该程序段的时间复杂度为O(n)． 14．for (i = 1; i = n; i++) if (3 * i =n) for (j = 3 * i; j = n; j++){ x++; y = 3 * x + 2; } 分析：语句 “x++”和“y = 3 * x + 2;”各执行 1 n(n ?1) 次，故该程序段的时间复杂度为O( n2 )． 6 15．for (i = 1; i = n; i++) for (j = 1; j = i; j++){ x = x + 1; } 分析：语句 “x = x + 1;”执行 1 n(n ?1) 次，故该程序段的时间复杂度为O( n2 )． 2 16．sum = 0; i = 0; while (i = 100){ sum = sum + i; i++; } 分析：语句 “sum = sum + i;”和“i++;”各执行100次，故该程序段的时间复杂度为O(1)． 17．x = 1; s = 0; for (i = 1; i = n; i++){ ++x; s += x; } for (j = 1; j = n; j++) for (k = 1; k = n; k++){ x++; s = s + x; } 分析：语句 “++x;”执行n次，语句“x++;”和“s = s + x;”各执行 n2 次，故该程序段的时间复杂度为O( n2 )． 第 2 章 线性表 练习题 一、单项选择题 在长度为 n 的顺序表的第 i (1? i ? n ?1) 个位置上插入一个元素，元素的移动次数为 （A） A． n ? i ?1 B． n ? i C． i D． i ?1 2．若一个顺序表中第一个元素的存储地址为1000，每个元素占4 个地址单元，那么，第6 个元素的存 储地址应是 （A） A．1020 B．1010 C．1016 D．1024 带头结点的单链表（以 head 为头指针）为空的判断条件是 （C） A．head != NULL B．head ? next == head C．head ? next == NULL D．head == NULL 在单循环链表中，p 指向表任一结点，判断表不是访问结束的条件是 （B） A．p != NULL B．p != hea