乡挥举囱稳佛恃疼镁杆缕劫靠
第一周数据结构概述时长24分42秒
数据结构概述测试
1、单选题:
计算机算法指的是()
A: 计算机程序
B: 解决问题的有限运算序列
C: 排序方法
D: 检索方法
答案: 解决问题的有限运算序列
2、单选题:
下面程序段的算法复杂度是()min=A[0];
for(i=1;i<n;i++)
if( min>A[i]) min=A[i]其中 n为正整数。
A:
B:
C:
D:
答案:
3、单选题:
在数据结构中,数据的( )的结构是与计算机无关的。
A: 物理
B: 存储
C: 逻辑
D: 逻辑和存储
答案: 逻辑
4、单选题:
数据的最小单位是( )。
A: 数据项
B: 数据元素
C: 结点
D: 记录
答案: 数据项
5、单选题:
数据结构是指( )的集合以及它们之间的关系。
A: 数据
B: 数据的逻辑结构
C: 算法
D: 数据元素
答案: 数据元素
6、单选题:
数据的逻辑结构可以分为() 。
A: 内部结构和外部结构
B: 链式结构和顺序结构
C: 动态结构和静态结构
D: 线性结构和非线性结构
答案: 线性结构和非线性结构
7、单选题:
数据结构在计算机内存中的表示是指( )。
A: 数据元素之间的关系
B: 顺序结构
C: 数据的存储结构
D: 数据的逻辑结构
答案: 数据的存储结构
8、单选题:
算法分析的主要任务之一是分析( )。
A: 算法的执行时间和问题规模之间的关系
B: 算法的正确性
C: 算法的可读性
D: 算法的功能是否符合用户需求
答案: 算法的执行时间和问题规模之间的关系
9、单选题:
若某算法的时间复杂度为O(n^2),则表明该算法的( )。
A: 执行时间与n^2成正比
B: 问题规模是n^2
C: 问题规模与n^2成正比
D: 执行时间等于n^2
答案: 执行时间与n^2成正比
10、单选题:
下列函数中时间复杂度是O(n)的是()。
A:
B: T(n)=500n
C:
D: T(n)=2n^2
答案: T(n)=500n
11、单选题:
下面代码段的时间复杂度为()。{ int i=1;
while (i<=n) i=i*2;
}
A: O(1)
B: O(n)
C:
D:
答案:
12、单选题:
下面代码段的时间复杂度为()。{ int i=0, s=0;
while (i<n) { s=s+a[i];i=i+2;}
}
A: O(1)
B: O(n)
C:
D:
答案: O(n)
13、单选题:
以下说法正确的是()。
A: 数据结构是带结构的各数据项的集合
B: 一些表面上很不相同的数据可以有相同的逻辑结构
C: 数据元素是数据的最小单位
D: 数据项是数据的基本单位
答案: 一些表面上很不相同的数据可以有相同的逻辑结构
14、单选题:
通常要求同一逻辑结构中的所有数据元素具有相同的特性,这说明()。
A: 每个数据元素所包含的数据项的个数要相等
B: 每个数据元素都一样
C: 数据元素具有同一特点
D: 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致
答案: 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致
15、单选题:
在决定选取何种存储结构时,一般不考虑()。
A: 所用编程语言实现这种结构是否方便
B: 结点个数的多少
C: 各结点的具体值如何
D: 对数据有哪些运算
答案: 各结点的具体值如何
16、单选题:
下面的算法是判断n是否为素数,其算法时间复杂度为( )。void prime(int n)
{ /* 判断n是否是素数 */
for (i=2; i<sqrt(n) && (n % i)!=0; i++) ;
if (i>sqrt(n))
printf(“%d is a prime number”, n);
else
printf(“%d is not a prime number”, n);
}
A:
B:
C:
D:
答案:
17、单选题:
下面算法的时间复杂度为( )。x=100; y=100;
while(y>0)
if(x>100)
{x=x-10; y–;}
else
x++;
A:
B:
C:
D:
答案:
18、单选题:
如下程序段:for(i=1;i<=n-1;i++)
for(j=i+1;j<=n;j++) x=x+1;其中语句x=x+1执行的语句频度为( )。
A: n*n
B: n*(n-1)
C: n*(n-1)/2
D: n*(n+1)/2
答案: n*(n-1)/2
19、单选题:
评价一个算法性能好坏的重要标准是( )。
A: 算法是否易于理解
B: 算法是否易于调试
C: 算法的时间复杂度
D: 算法的正确性
答案: 算法的时间复杂度
20、多选题:
算法的时间复杂度取决于( )。
A: 问题的规模
B: 待处理数据的初态
C: 实现算法所使用的的语言
D: 数据采用的存储结构
答案: 问题的规模;
待处理数据的初态
21、多选题:
数据结构包括数据的()、数据的()和数据的()这三个方面的内容。
A: 逻辑结构
B: 存储结构
C: 运算
D: 输入输出
答案: 逻辑结构;
存储结构 ;
运算
22、多选题:
常见的逻辑结构有集合 ,(),(),()四种。
A: 顺序表
B: 线性结构
C: 树形结构
D: 图形结构
答案: 线性结构;
树形结构;
图形结构
23、多选题:
计算机中算法指的是解决某一问题的有限运算序列,它必须具备0或多个输入、1或多个输出、( )、()、()。
A: 确定性
B: 有穷性
C: 可移植性
D: 可行性
答案: 确定性;
有穷性;
可行性
24、多选题:
一个抽象数据类型包括()。
A: 一组基本操作
B: 数据
C: 数据对象
D: 数据对象中各元素间的关系
答案: 一组基本操作;
数据对象;
数据对象中各元素间的关系
25、判断题:
数据的物理结构是指数据的各数据项之间的逻辑关系。
A: 正确
B: 错误
答案: 错误
26、判断题:
数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。
A: 正确
B: 错误
答案: 错误
27、判断题:
某算法的时间复杂度是O(n^3),表明该算法的执行时间与n^3成正比。
A: 正确
B: 错误
答案: 正确
28、判断题:
顺序存储的优点是逻辑上相邻的元素,物理上也是相邻的,因此可以实现随机存储。
A: 正确
B: 错误
答案: 正确
29、判断题:
数据元素是数据的基本单位
A: 正确
B: 错误
答案: 正确
30、判断题:
在存储数据时,通常不仅要存储各数据元素的值,而且还要存储数据元素之间的关系。
A: 正确
B: 错误
答案: 正确
31、判断题:
健壮的算法不会因为非法输入而出现莫名的执行结果。
A: 正确
B: 错误
答案: 正确
32、判断题:
算法的可行性是指每一条指令具有明确含义。
A: 正确
B: 错误
答案: 错误
33、判断题:
算法的优劣与算法描述的语言无关。
A: 正确
B: 错误
答案: 正确
34、判断题:
程序一定是算法。
A: 正确
B: 错误
答案: 错误
35、判断题:
算法可以用不同的语言描述,如果用C或Java或Python等高级语言来描述,则算法实际上就是程序了。
A: 正确
B: 错误
答案: 错误
36、判断题:
任何数据结构都具备3个基本运算:插入、删除、和查找。
A: 正确
B: 错误
答案: 错误
37、判断题:
数据的逻辑结构与数据元素在计算机中如何存储有关。
A: 正确
B: 错误
答案: 错误
38、判断题:
如果数据元素值发生改变,则数据的逻辑结构也随之改变。
A: 正确
B: 错误
答案: 错误
39、判断题:
数据的逻辑结构时指数据的各数据项之间的逻辑关系。
A: 正确
B: 错误
答案: 错误
课堂小测验
1、单选题:
关于算法复杂度说法正确的是( )
A: 算法复杂度指时间复杂度
B: 算法复杂度指空间复杂度
C: 算法复杂度包含时间复杂度、空间复杂度
D: 算法复杂度通常与数据规模无关
答案: 算法复杂度包含时间复杂度、空间复杂度
第二周线性表上时长74分54秒
线性表单元测试上
1、单选题:
线性表是( )
A: 一个有限序列,不可以为空
B: 一个有限序列,可以为空
C: 一个无限序列,可以为空
D: 一个无限序列,不可以为空
答案: 一个有限序列,可以为空
2、单选题:
对于长度为n的顺序表(下标范围0..n-1),在第i个位置插入一个元素需要移动( )个元素。其中,0≤i≤n。
A: n-i
B: n-i-1
C: n-i+1
D: i
答案: n-i
3、单选题:
若数组A可存放100个元素,每个元素占4个字节,从首地址1000开始按顺序连续存放,那么,元素A[16]的起始地址为( )。
A: 1128
B: 1064
C: 1032
D: 1016
答案: 1064
4、单选题:
对于顺序存储的长度为n的线性表,删除第i个位置的元素需要移动( )个元素。其中,0≤i<n。
A: i
B: n-i+1
C: n-i-1
D: n-i
答案: n-i-1
5、单选题:
对于线性表,下列说法正确的是()。
A: 表中元素必须是有序的
B: 每个元素有且仅有一个直接前驱和一个直接后继
C: 除第一个元素与最后一个元素,其他每个元素有且仅有一个直接前驱和一个直接后继
D: 线性表不允许为空
答案: 除第一个元素与最后一个元素,其他每个元素有且仅有一个直接前驱和一个直接后继
6、单选题:
线性表采用顺序存储结构,下列说法不正确的是( )。
A: 插入、删除操作不必移动元素
B: 需要事先估计所需存储空间,可能出现顺序表满的情况
C: 内容空间地址必须是连续的
D: 可以进行随机存取
答案: 插入、删除操作不必移动元素
7、单选题:
线性表的顺序存储最适合于实现 ( )运算。
A: 将x插入第i个位置
B: 查找值为x
C: 删除第i个位置元素
D: 取第i个位置元素
答案: 取第i个位置元素
8、单选题:
在长度为n的顺序表中,查找值为x的数据元素的时间复杂度为()
A: O(1)
B: O(n)
C: O(n^2)
D:
答案: O(n)
9、单选题:
在长度为n的顺序表中,查找第i个位置的数据元素的时间复杂度为()
A: O(1)
B: O(n)
C: O(n^2)
D:
答案: O(1)
10、单选题:
对顺序存储的长度为n的线性表,假设在任何位置上进行删除操作是等概率的。则删除一个元素时平均要移动表中的( )个元素。
A: n
B: (n+1)/2
C: n/2
D: (n-1)/2
答案: (n-1)/2
11、单选题:
对顺序存储的长度为n的线性表,假设在任何位置上进行插入操作是等概率的。则插入一个元素时平均要移动表中的( )个元素。
A: n
B: n/2
C: (n+1)/2
D: (n-1)/2
答案: n/2
12、单选题:
在长度为n的顺序表的运算中,算法的时间复杂度是O(1)的操作是( )。
A: 在第i个位置上插入一个新元素(0≤i≤n)
B: 求第i个位置的元素的直接前驱(1≤i<n)
C: 删除第i个位置上的元素(0≤i<n)
D: 以上都不对
答案: 求第i个位置的元素的直接前驱(1≤i<n)
13、单选题:
下面关于线性表的叙述错误的是 ()。
A: 线性表采用链式存储便于插入和删除操作的实现
B: 线性表采用顺序存储必须占用一片连续的存储空间
C: 线性表采用链式存储不必占用一片连续的存储空间
D: 线性表采用顺序存储便于插入和删除操作的实现
答案: 线性表采用顺序存储便于插入和删除操作的实现
14、单选题:
在单链表中,要删除某一指定的结(节)点,必须找到该结点的 ()结点。
A: 头结点
B: 尾结点
C: 前驱
D: 后继
答案: 前驱
15、单选题:
求一个单链表长度的算法的时间复杂度为()。
A:
B:
C:
D:
答案:
16、单选题:
已知一个长度为n的单链表中所有结点是递增有序的,以下叙述中正确的是 ()。
A: 删除最大值结点使之有序的算法的时间复杂度为 O(1)
B: 都不对
C: 找最小值结点的算法的时间复杂度为 O(1)
D: 插入一个结点使之有序的算法的时间复杂度为O(1)
答案: 找最小值结点的算法的时间复杂度为 O(1)
17、单选题:
将长度为m的单链表(A)链接在长度为n的单链表(B)之后的算法时间复杂度为()。
A: O(n)
B: O(m+n)
C: O(m)
D: O(1)
答案: O(n)
18、单选题:
将长度为m的顺序表(A)链接在长度为n的顺序表(B)之后的算法时间复杂度为()。
A: O(m)
B: O(n)
C: O(m+n)
D: O(1)
答案: O(m)
19、单选题:
在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 ()。
A:
B:
C:
D:
答案:
20、单选题:
在单链表中查找指定值的结点的时间复杂度是()。
A:
B:
C:
D:
答案: