大学MOOC 数据结构(海南热带海洋学院)1450329430 最新慕课完整章节测试答案

小测验：算法复杂度

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、单选题：
‏借助堆栈将中缀表达式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++】

3、判断题：
​‏下列函数试图求链式存储的线性表的表长，是否正确？‏int  Length ( List  *PtrL )‏​‏{    List  *p = PtrL;      ‏​‏     int  j = 0;‏​‏     while ( p ) { ‏​‏           p++; ‏​‏           j++;                 ‏​‏     }   ‏​‏     return  j;‏​‏}‏​‏
选项：
A: 正确
B: 错误
答案: 【 错误】

小测验：队列

1、单选题：
‍在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：  ​
选项：
A: f->next=s; f=s;
B: r->next=s; r=s;
C: s->next=r; r=s;
D: s->next=f; f=s;
答案: 【 r->next=s; r=s;】

2、单选题：
​现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？ ​​​
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 4】