大学MOOC 数据结构(北京联合大学)1452402161 最新慕课完整章节测试答案

小测验：算法复杂度

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: 内部结构和外部结构
答案: 【 线性结构和非线性结构】

2、单选题：
‍线性表是具有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: 错误
答案: 【 错误】

8、判断题：
‍线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

9、填空题：
​一个算法的效率可分为      效率和        效率。‎
答案: 【 时间 空间】

10、填空题：
‍线性表是具有n个          有限序列。‏
答案: 【 数据元素】

小测验：堆栈

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】

第二章单元测验

1、单选题：
‌​栈和队列的共同特点是(      )。‌
选项：
A: 只允许在端点处插入和删除元素
B: 都是先进后出
C: 都是先进先出
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素】

2、单选题：
用链接方式存储的队列，在进行插入运算时(   ).​‎​
选项：
A: 仅修改头指针
B: 头、尾指针都要修改
C: 仅修改尾指针
D: 头、尾指针可能都要修改
答案: 【 头、尾指针可能都要修改】

3、单选题：
​下面关于线性表的叙述错误的是（   ）。‍
选项：
A: 线性表采用顺序存储必须占用一片连续的存储空间
B: 线性表采用链式存储不必占用一片连续的存储空间
C: 线性表采用链式存储便于插入和删除操作的实现
D: 线性表采用顺序存储便于插入和删除操作的实现
答案: 【 线性表采用顺序存储便于插入和删除操作的实现】

4、单选题：
‍设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（  ）。‍
选项：
A: R-F
B: F-R
C: (R-F+M)％M
D: (F-R+M)％M
答案: 【 (R-F+M)％M】

5、单选题：
​设用链表作为栈的存储结构则退栈操作（  ）。‌
选项：
A: 必须判别栈是否为满
B: 必须判别栈是否为空
C: 判别栈元素的类型
D: 对栈不作任何判别
答案: 【 必须判别栈是否为空】

6、单选题：
‎设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（  ）。‏
选项：
A: head==0
B:  head->next==0
C: head->next==head
D: head!=0
答案: 【 head==0】

7、单选题：
设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（  ）。‍‎‍
选项：
A:  front->next=s；front=s；
B:  s->next=rear；rear=s；
C: rear->next=s；rear=s；
D:  s->next=front；front=s；
答案: 【 rear->next=s；rear=s；】

8、单选题：
设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（  ）。‍​‍
选项：
A: top=top+1;
B: top=top-1;
C: top->next=top;
D: top=top->next;
答案: 【 top=top->next;】

9、单选题：
 队列是一种（  ）的线性表。‏‏‌‏
选项：
A: 先进先出
B: 先进后出
C: 只能插入
D: 只能删除
答案: 【 先进先出】

10、单选题：
设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（  ）个元素。‎‎‎
选项：
A: n-i
B: n+l -i
C: n-1-i
D: i
答案: 【 n-i】

11、单选题：
‏设输入序列1、2、3、…、n经过栈作用后，输出序列中的第