第１章数据结构导论
一、选择题
1．算法的时间复杂度取决于 A 。
A．问题的规模 B．变量的多少 C．问题的难度 D．A和B
2. 算法能正确的顺利结束的特性为算法的 B 。
A. 有效性
B.有限性
C.健壮性
D. 高效性
3. 数据的物理结构主要包含 A 这几种结构。
A．顺序结构和链表结构 B．线性结构和非线性结构
C．动态结构和静态结构 D．集合、线性结构、树形结构、图形结构4．数据在计算机内存中的表示是指 A 。
A. 数据的存储结构
B. 数据结构
C. 数据的逻辑结构
D. 数据元素之间的关系
5．数据结构被形式化定义为二元组（D，S），其中D是 B 的有限集合。
A．算法B．数据元素C．数据操作D．数据关系6．算法效率的度量是 D
A．正确度和简明度B．数据复杂度和程序复杂度
C．高的速度和正确度D．时间复杂度和空间复杂度
7. 在存储数据时，通常不仅要存储各数据元素的值，还要存储 D 。
A．数据的存储方法B．数据处理的方法
C．数据元素的类型D．数据元素之间的关系
8. 以下叙述不正确的是 C 。
A. 数据结构是指数据以及数据相互之间的联系
B. 数据结构主要指数据的逻辑结构，与计算机的存储和处理无关
C. 数据的存储结构是指数据在计算机中的存储方式，主要包括线形和非线性
D. 对于给定的n个元素，可以构造出的逻辑结构有多种
9. 下列程序段违反了算法 B 特征。
count=0
while count!=3:
print(count)
A．明确性B．有限性
C．有效性D．功能性
10. 下列程序的时间复杂度为 D 。
for i in range(1,n+1):
j=i
for k in range(j+1,n+1):
x=x+1
A．O(i*j) B．O(n(n-1)/2)
C．O(n2/2) D．O(n2)
二、解答题
1．下列程序段中，函数my_fun(i,k)的执行次数是 n(n+1)/2 ，该程序的时间复杂度为O(n^2) 。
for k in range(1,n+1):
for i in range(0,k):
if i!=k:
my_fun(i,k)
2．求下列程序段中有数字标号的各语句的执行次数，然后求出该程序段的时间复杂度。
def fun (n) :
①i=s=1
②while s i=i+1 ③s=s+i ④return i 答： ① 1次 ②（2n）^1/2次 ③（2n）^1/2 - 1次 ④ 1次 ⑤ O（n^1/2） 第２章数组结构 一、选择题 1．线性表是一个 A 。 A. 有限序列，可以为空 B. 有限序列，不能为空 C. 无限序列，可以为空 D. 无限序列，不能为空 2．下面关于线性表的叙述中，错误的是 B 。 A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链接存储，不必占用一片连续的存储单元 D. 线性表采用链接存储，便于进行插入和删除操作 3．某线性表采用顺序存储结构，每个元素占4个存储单元，首地址为100，则第12个元素的存储地址为 A 。 A. 144 B. 145 C. 147 D. 148 4．若长度为n的顺序存储结构线性表，删除第i个数据元素，需要向前移动 A 个数据元素。 A. n-i B. n+i C. n-i-1 D. n-i+1 5．若长度为n的顺序存储结构线性表，在第i个位置插入一个元素，需要依次向后移动 D 个元素。 A. n-i B. n+i C. n-i-1 D. n-i+1 6．一个顺序表所占存储空间的大小与 D 无关。 A．顺序表长度 B．结点类型 C．结点中个数据域的类型 D．结点的存放次序 7. 以下叙述不正确的是 D 。 A. 数据的逻辑结构包括线性和非线性结构，非线性结构包括树和图两种。 B. 数据的逻辑结构主要指元素间的关系，与计算机的存储和处理无关 C. 数据的存储结构是指数据在计算机中的存储方式，主要包括顺序和链式两种 D. 对于给定的n个元素，可以构造出的逻辑结构有顺序表和链表两种 8. 某线性表采用顺序存储结构，则下列叙述正确的是 B 。 A．删除顺序表第i个元素和在第i位置插入一个元素所需移动的元素个数一样 B．删除顺序表第i个元素和在第i位置插入一个元素的时间复杂度一样 C．删除顺序表第i个元素和取第i元素的值的时间复杂度一样 D．在顺序表表头插入和表尾插入的时间复杂度一样 9. 对线性表，在下列情况下应当采用顺序表表示的是 A 。 A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 C. 表中每个元素需要的字节数比较大 D. 表中的元素个数不变 10．在含有n个元素的顺序表中，算法的时间复杂度是O（1）的操作是___A___。 A．访问第i个元素（1≤i≤n）和求第i个元素的直接前驱（2≤i≤n） B．在第i个元素后插入一个新元素（1≤i≤n） C．删除第i个元素（1≤i≤n） D．将n个元素从小到大排序 二、填空题 1.一个一维数组（列表）A的长度为500，起始（A[0]）地址为2000，每个元素占4个字 节，则A[80]的地址是 2320 。 2.一个4*6的二维数组A，每个元素占4个字节，假设该数组起始元素A(1,1)的地址是110， 若以行为主存储，则A(3,5)的地址是 174 ；若以列为主存储，A(3,5)的地址是 182 。 3.以顺序存储结构实现的线性表简称为顺序表，它要求存储空间必须是 连续的，并以下标来体现元素之间的关系，在顺序表中访问第i个元素的时间复杂度为 O(1) ，因此，顺序表也称为随机存取的数据结构。以链式存储结构实现的线性表称为链表。其存储空间可以是不连续的，以指针来体现元素之间的关系。在链表中访问第i个元素的时间复杂度为 O(n) ，因此，链表也称为顺序访问的数据结构。 三、算法设计题 1．设有一个顺序表L，其元素为整型数据，编写一个要求时间复杂度为O(n)、空间复杂度为O(1)的算法，将L中所有小于0的整数放在前半部分，大于0的整数放在后半部分。提示：从L的两端查找，前端找大于0的数据，后端找小于0的数据，然后将两位置的数据交换。 L = [1,2,3,4,5,6,7,8,9,10,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10] n = len(L) print("原顺序表：\n{}".format(L)) j = 0 k = 0 for i in range(n): if L[i] < 0: k = L[i] L[i] = L[j] L[j] = k j += 1 else: continue print("排序后顺序表：\n{}".format(L)) 2. 在一个有序列表中查找元素x，当被查元素x小于列表中某个元素时就可停止。请编写一个函数实现上述查找，并分析此查找在最好情况、最坏情况以及平均情况下的性能。 def found(L,x): print("查找元素") for i in L: if x > i or x == i: print("元素x大于或等于{},程序继续".format(i)) continue else: print("元素x小于{},程序停止".format(i)) break if __name__ == "__main__": x = eval(input("请输入要查找的元素x:")) L=[1,2,3,4,5,6,7,8,9] found(L,x) 3. 已知一个n*n的二维数组a已经以行为主存放在一个大小为n2的一维数组b中，编写一个函数计算此二维数组的主对角线元素之和。count(b,n) def count(b,n): x=0 i=0 while True: x += b[i] i += n+1 if i > len(b): break print("主对角线元素之和为:%d"%x) if __name__ == "__main__": a = [[1,2,3],[4,5,6],[7,8,9]] b = [] n = len(a) print("二维数组A为：") for i in range(n): for j in range(n): b.append(a[i][j]) print("%d"%a[i][j],end='\t') print() print("存放在一维数组b中为：") print(b) count(b,n) 4. 有一值为整型、长度为n的顺序表（列表），写一个函数，计算该顺序表所有元素的平均值，并输出所有大于平均值的元素。 def Average(L,n): nsum = 0 for i in range(n): nsum += L[i] average = nsum / n print("平均数为:%d"%average) print("所有大于平均值的元素为：") for i in L: if i > average: print(i,end=' ') else: continue if __name__ == "__main__": L = [1,354,56,57,2,8,9,46,767,678] n = len(L) Average(L,n) 第３章链表 一、选择题 1．以下关于链式存储结构的叙述中， C 是不正确的。 A．结点除自身信息外还包括指针域，因此空间利用率小于顺序存储结构 B．逻辑上相邻的结点物理上不必邻接 C．可以通过计算直接确定第i个结点的存储地址 D．插入、删除运算操作方便，不必移动结点 2. 在下列存储结构中，最适合实现在线性表中进行随机访问的是 A 。 A. 数组 B. 双向链表 C. 单向链表 D. 循环链表
相关主题
文本预览