过关练习

单项选择题

1．以下名称表示物理结构的是（  ）。【模拟题】

①线性表　②二叉树　③集合　④图　⑤单链表　⑥散列表

A．①②

B．③④

C．①⑤

D．⑤⑥

2．在各类存储结构中，（  ）查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快；（  ）查找和存取速度快，但插入、删除速度慢；（  ）查找、插入和删除速度快，但不能进行顺序存取；（  ）插入、删除和顺序存取速度快，但查找速度慢。【2016年昆明理工大学】

A．散列表；顺序有序表；顺序表；单链表

B．顺序表；顺序有序表；散列表；单链表

C．单链表；顺序有序表；散列表；顺序表

D．顺序有序表；顺序表；单链表；散列表

3．数据的4种基本存储结构是指（  ）。【2018年昆明理工大学】

A．顺序存储结构、索引存储结构、直接存储结构、链式存储结构

B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构

C．顺序存储结构、非顺序存储结构、指针存储结构、树形存储结构

D．顺序存储结构、链式存储结构、树形存储结构、图存储结构

4．一个算法具有（  ）5个重要特性。【模拟题】

A．确定性、有穷性、稳定性、输入、输出

B．易读性、稳定性、安全性、输入、输出

C．有穷性、确定性、可行性、输入、输出

D．可行性、可移植性、可扩充性、输入、输出

5．下列关于算法的说法正确的是（  ）。【模拟题】

A．算法最终必须由计算机程序实现

B．一个算法执行所花时间等于该算法中每条语句的执行时间之和

C．算法的可行性是指指令不能有二义性

D．算法的有穷性指的是程序所处理的数据量是有限的

6．下面关于算法的描述，错误的是（  ）。【2018年四川大学】

A．算法必须是正确的

B．算法必须能够结束

C．一个问题可以由多种算法解决

D．算法的某些步骤可以有二义性

7．计算机算法指的是（  ）。【2017年上海海事大学】

A．计算方法

B．排序方法

C．调度方法

D．解决问题的步骤序列

8．下面程序段的时间复杂度是（  ）。【2017年广东工业大学】

x=0;
for(i=0;i<n;i++){
    for(j=i;j<n;j++){
        x++;
    }
}

A．O(logn)

B．O(n)

C．O(nlogn)

D．O(n2)

9．时间复杂度O(1)的含义是（  ）。【2016年广东工业大学】

A．问题规模为1

B．执行时间为1s

C．问题规模为1的常数倍

D．执行时间与问题规模无关

10．下列程序段的时间复杂度为（  ）。【2015年常州大学】

i=1,x=0;
do {
    x++;
    i=2*i;
} while(i<n)

A．O(logn)

B．O(n2)

C．O(n)

D．O(1)

11．下列程序段的时间复杂度为（  ）。【2016年昆明理工大学】

j=0,s=0;
while(s<n){
    j++;
    s+=j;
}

A．O(n1/2)

B．O(n)

C．O(n2)

D．O(1)

答案与解析

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)。

上一章目录下一章