下载掌阅APP，畅读海量书库
立即打开
1. 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
2. 算法的时间复杂度取决于（ ）。
A. 问题的规模
B. 待处理数据的初态
C. A和B
3. 计算机算法指的是（ ① ），它必须具备（ ② ）这3个特性。
①A. 计算方法
B. 排序方法
C. 解决问题的步骤序列
D. 调度方法
②A．可执行性、可移植性、可扩充性
B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性
D. 易读性、稳定性、安全性
4. 下面说法错误的是（ ）。
①算法原地工作的含义是指不需要任何额外的辅助空间
②在相同的规模 n 下，复杂度 O ( n )的算法在时间上总是优于复杂度 O (2 n )的算法
③所谓时间复杂度是指在最坏情况下，估算算法执行时间的一个上界
④同一个算法，实现语言的级别越高，执行效率就越低
A. ①
B. ①；②
C. ①；④
D. ③
5. 从逻辑上可以把数据结构分为（ ）两大类。
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
6. 以下数据结构中，（ ）是线性结构。
A. 广义表
B. 二叉树
C. 稀疏矩阵
D. 串
7. 在下面的程序段中，对 x 的赋值语句的频度为（ ）
FOR i := 1 TO n DO
FOR j: = 1 TO n DO
x: = x + 1;
A.
O
(2
n
)
B.
O
(
n
)
C.
O
(
n
2
)
D.
O
(log
2
n
)
8. 以下数据结构中，（ ）是非线性数据结构。
A. 树
B. 字符串
C. 队
D. 栈
9. 下列数据中，（ ）是非线性数据结构。
A. 栈
B. 队列
C. 完全二叉树
D. 堆
1. 数据元素是数据的最小单位。（ ）
2. 记录是数据处理的最小单位。（ ）
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
4. 算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）
5. 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
6. 数据的物理结构是指数据在计算机内的实际存储形式。（ ）
7. 数据结构的抽象操作的定义与具体实现有关。（ ）
8. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。（ ）
9. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
10. 数据的逻辑结构表示数据元素之间的顺序关系，它依赖于计算机的存储结构。（ ）
1. 对于给定的 n 个元素，可以构造出的逻辑结构有____________、____________、____________、____________4种。
2. 一个算法具有5个特性：____________、____________、____________、有0个或多个输入、有一个或多个输出。
3. 下面程序段的时间复杂度为____________。( n >1)
sum=1； for ( i=0;sum<n;i++) sum+=1;
1. 什么是数据？什么是数据元素？什么是数据项？
2. 什么是数据的逻辑结构？什么是数据的存储结构？什么是数据的操作？
3. 分别画出线性结构、树形结构和图形结构的逻辑结构。
4. 什么是数据类型？什么是抽象数据类型？
5. 基本的存储结构有几种？分别画出数据元素序列 a 0 , a 1 ,..., a n −1 的顺序存储结构示意图和链式存储结构示意图。
6. 评判一个算法的优劣主要有哪几条准则？
7. 什么是算法的时间复杂度？怎样表示算法的时间复杂度？
8. 设求解同一个问题有3种算法，3种算法的空间复杂度相同，各自的时间复杂度分别为 O ( n 2 )、 O (2 n )、 O ( n lg n )，哪种算法最可取？为什么？
9. 按增长率从小到大的顺序排列下列各组函数。
①2 100 ，(3/2) n ，(2/3) n ，(4/3) n 。
② n ， n 3/2 ， n 2/3 ， n !， n n 。
③log 2 n ， n log 2 n ， n log2 n ， n 。
1. 设 n 为在算法前面定义的整数类型已赋值的变量，分析下列各算法中加下画线语句的执行次数，并给出各算法的时间复杂度 O ( n )。
（1）算法1
int i = 1,k = 0;
while(i < n - 1){
k = k + 10 * i;
i = i + 1;
}
（2）算法2
int i = 1,k = 0;
do {
k = k + 10 * i;
i = i + 1;
}while(i != n);
（3）算法3
int i = 1,j = 1;
while(i <= n && j <= n){
i = i + 1;
j = j + 1;
}
（4）算法4
int x = n;
int y = 0;
while(x >= (y + 1) * (y + 1)){
y ++;
}
（5）算法5
int i,j,k,x=0;
for(i = 0;I < n;I ++)
for(j = 0;j < i;j ++)
for(k = 0;k < j;k ++)
x = x + 2;
2. 如下算法实现了将数组a中的 n 个整数类型的数据元素从小到大进行排序，求该算法的时间复杂度。
void bubbleSort(int a[]){
int n = a.length;
int i,j,temp,flag = 1;
for(i = 1;i < n&&flag == 1;I ++){
flag = 0;
for(j = 0;j < n - i;j ++){
if(a[j] > a[j + 1]){
flag = 1;
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
3. 下面的算法是在一个有 n 个数据元素的数组a中删除第pos个位置的数组元素，求该算法的时间复杂度。
boolean delete(int a[],int pos){
int n = a.length;
if(pos < 0|| pos >= n)
return false; //删除失败返回
for(int j=pos + 1;j < n;j ++){
a[j - 1]=a[j]; //顺次移位填补
return true; //删除成功返回
}
}
4. 分析以下算法的空间复杂度。
static void reverse1(int[] a,int[] b){
int n = a.length;
for(int i = 0;i < n;i ++){
b[i] = a[n – 1 - i];
}
}