大学MOOC 数据结构-胡文彬(江苏海洋大学)1451417167 最新慕课完整章节测试答案

小测验算法复杂度

1、单选题：
‍下列函数中，哪个函数具有最快的增长速度：‏
选项：
A:
B:
C:
D:
答案: 【 】

2、单选题：
‌下面一段代码的时间复杂度是？if ( A > B ) {
    for ( i=0; i<N; i++ )
        for ( j=N*N; j>i; j-- )
            A += B;
}
else {
    for ( i=0; i<N*2; i++ )
        for ( j=N*2; j>i; j-- )
            A += B;
}‏
选项：
A:
B:
C:
D:
答案: 【 】

第1章单元测试

1、单选题：
执行下面的程序段的时间复杂度为（   ）。‍for(int i=0;i<m;i++)‍   for(int j=0;j<n;j++)‍     a[i][j]=i*j‍‎‍
选项：
A: O(n2)
B: O(m+n)
C: O(m2)
D: O(m*n)
答案: 【 O(m*n)】

2、单选题：
执行下面程序段时，语句S的执行次数为（   ）。‎for(int i=0;i<=n;i++)‎  for(int j=0;j<=i;j++)‎    S;‎‍‎
选项：
A: n*n
B: n*n/2
C: n(n+1)/2
D: (n+1)*(n+2)/2 
答案: 【 (n+1)*(n+2)/2 】

3、单选题：
‌算法的时间复杂度与（    ）有关。​
选项：
A: 问题规模 
B: 计算机硬件性能 
C: 编译程序质量 
D: 程序设计语言
答案: 【 问题规模 】

4、单选题：
‍某算法的时间复杂度是O（n^2）,表明该算法的（   ）。‎
选项：
A: 问题规模与n^2正比 
B: 执行时间等于n^2
C: 执行时间与n^2正比
D: 问题规模是n^2
答案: 【 执行时间与n^2正比】

5、单选题：
在数组A[0..n-1]中查找给定值K的算法大致如下：   ‎i=n-1;            ‎while(i>=0&&(A[i]!=k))       ‎      i--;        ‎return i;  ‎该算法的时间复杂度为（    ）。‎‌‎
选项：
A: O(n-i+1)
B: 无法确定
C: O(n)
D: O(n-i)
答案: 【 O(n)】

6、单选题：
‍下面的算法是判断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: O（n-i）
B: O(n)
C: O(1)
D: O(sqrt(n))    sqrt表示对n取根方
答案: 【 O(sqrt(n))    sqrt表示对n取根方】

7、多选题：
‎一个抽象数据类型包括（    ）。‍
选项：
A: 一组基本操作
B: 数据
C: 数据对象中各元素间的关系
D: 数据对象
答案: 【 一组基本操作;
数据对象中各元素间的关系;
数据对象】

8、多选题：
‌以下属于算法特性的是（    ）。‍
选项：
A: 0个或多个输入
B: 可行性
C: 正确性和有限性
D: 至少一个输出
答案: 【 0个或多个输入;
可行性;
正确性和有限性;
至少一个输出】

9、多选题：
‍数据元素在计算机的存储映像包括（   ）。‏
选项：
A: 顺序存储
B: 图结构
C: 树结构
D: 非顺序存储
答案: 【 顺序存储;
非顺序存储】

10、多选题：
‌具有线性结构的数据元素只能顺序存储，非线性结构的元素只能非顺序存储。​
选项：
A: 正确
B: 不正确
C: 说法不正确
D: 确定
答案: 【 不正确;
说法不正确】

11、判断题：
​算法就是程序。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

12、判断题：
‎算法的可行性是指每一条指令具有明确含义。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

13、判断题：
​高效率和低存储是衡量一个算法的唯一标准。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

14、判断题：
‏健壮的算法不会因为非法输入而出现莫名的执行结果。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

15、判断题：
‍数据类型就是一组性质相同的值的集合和在该集合上的一组操作的总称。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

小测验堆栈

1、单选题：
​借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：‏​‏
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 4】

2、单选题：
‎‌设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：‌‎‌
选项：
A: 3
B: n-2
C: n-3
D: 任何元素均可能
答案: 【 n-2】

3、单选题：
‍‌若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？‌‍‌          （1）4->2->3    (2)  1->2->4‌‍‌
选项：
A: 只能是（1）
B: 只能是（2）
C: （1）和（2）都有可能
D: （1）和（2）都不可能
答案: 【 只能是（1）】

4、单选题：
‌如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。​‌​
选项：
A: PPPOOPOPOO
B: POOPPPOPOO
C: POPPOPPOOO
D: PPOPPOOOPO
答案: 【 POPPOPPOOO】

小测验线性表

1、单选题：
​对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？‌
选项：
A: 都是O(1)
B: 都是O(k)
C: O(1)和O(k)
D: O(k)和O(1)
答案: 【 O(1)和O(k)】

2、单选题：
‏在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：‍‏‏for (___________ )‍‏            PtrL->Data[j-1]=PtrL->Data[j];  ‍‍‏其中空缺部分的内容应该是‍
选项：
A:  j = i; j< = PtrL->Last; j++
B:  j =PtrL->Last; j>= i;  j--
C:  j = i-1; j< = PtrL->Last; j++
D: j =PtrL->Last; j>= i-1;  j--
答案: 【  j = i; j< = PtrL->Last; j++】