答案与解析

1．【答案】 D

【解析】本题考查物理结构。数据的存储结构包括顺序、链式、索引、散列。题目中的单链表是链式存储结构，散列表是散列存储结构，因此选择D选项。

2．【答案】 B

【解析】本题考查数据结构的效率分析。单链表的按关键字查找速度较慢，需要从头依次比较，但是插入和删除只需要改变指针的方向，速度快；顺序表的随机存取第i个元素很快，但是插入和删除需要挪动大量元素的位置，速度慢；顺序有序表由于其有序的特征，可以使用二分查找进行加速，因此查找速度比较快，但是插入和删除速度没有提升，都比较慢；散列表是一种查找、插入、删除都很快的数据结构，但由于其散列存储的特点，无法进行顺序存取。综上，本题的答案为B选项。

3．【答案】 B

【解析】本题考查存储结构。数据的存储结构包括顺序存储结构、索引存储结构、链式存储结构、散列存储结构，因此选择B选项。

知识链接

顺序存储意味着连续的存储空间存放逻辑连续的数据；索引存储意味着对每个数据元素附加索引进行存储；链式存储意味着不连续的存储空间存放逻辑连续的数据，但需要额外的数据项来指向下一个元素；散列存储意味着使用关键字直接计算出结点的存储地址。

4．【答案】 C

【解析】本题考查算法的特性。算法具有5个特性：有穷性、确定性、可行性、输入、输出，因此选择C选项。

知识链接

一个算法存在零个或多个输入，输入是取自某个特定的对象的集合；一个算法存在一个或多个输出，输出是算法运行后的集合。

5．【答案】 B

【解析】本题考查算法的特性。算法是对特定问题求解步骤的一种描述，因此A选项错误；算法的确定性指的是算法的每个步骤都不能存在二义性，可行性指的是算法中的每个步骤都可以通过基本运算实现，因此C选项错误；算法的有穷性指的是算法必须在有限的步骤内结束，因此D选项错误。

6．【答案】 D

【解析】本题考查算法的特性。算法的5个特性中，确定性指的是算法中的每个步骤不能有二义性，因此D选项错误。

7．【答案】 D

【解析】本题考查算法的定义。算法是对特定问题求解步骤的一种描述。

8．【答案】 D

【解析】本题考查时间复杂度的计算。题目中程序段的外层循环共执行n次，内层循环每次执行n−i次，因此总共执行的次数约为n+(n−1)+(n−2)+…+1 = n(n+1)/2，时间复杂度为O(n2)。

9．【答案】 D

【解析】本题考查时间复杂度的计算。O(1)复杂度指的是算法可以在常数级别时间内对任何规模的数据量进行处理，因此本题的答案为D选项。

10．【答案】 A

【解析】本题考查时间复杂度的计算。题目中程序段的while循环退出条件为i小于n，而循环中的i每次都乘2，因此时间复杂度为O(logn)。

11．【答案】 A

【解析】本题考查时间复杂度的计算。此程序段主要耗时在循环上，循环共执行了j次，需要根据n求得j。j在循环时为等差数列1, 2, 3, 4, …，s为j的累加，由等差数列求和公式可以求得s = (1+j) j/2，再根据s=n，解得j≈n1/2，所以此程序段的时间复杂度为O(n1/2)。