大学MOOC 数据结构(南京森林警察学院)1450316233 最新慕课完整章节测试答案

小测验：算法复杂度

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、单选题：
‌在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（   ）。‍
选项：
A: 数据元素的类型
B: 数据的操作方法
C: 数据元素之间的关系
D: 数据的存取方法
答案: 【 数据元素之间的关系】

3、单选题：
‎以下关于数据结构的说法中，正确的是（   ）。‎
选项：
A: 数据的逻辑结构独立于其存储结构
B: 数据的存储结构独立于其逻辑结构
C: 数据的逻辑结构唯一决定了其存储结构 数据结构仅由其逻辑结构和存储结构决定
D: 数据结构仅由其逻辑结构和存储结构决定
答案: 【 数据的逻辑结构独立于其存储结构】

4、单选题：
‌一个算法应该是（   ）。​
选项：
A: 程序
B: 问题求解步骤的描述
C: 要满足五个基本特性
D: 程序且满足五个基本特性
答案: 【 问题求解步骤的描述】

5、单选题：
‌可以用（   ）定义一个完整的数据结构。‍
选项：
A: 数据元素
B: 数据对象
C: 数据关系
D: 抽象数据类型
答案: 【 抽象数据类型 】

6、判断题：
‌线性表中的每个结点最多只有一个前驱和一个后继。（  ）‏
选项：
A: 正确
B: 错误
答案: 【 正确】

7、判断题：
‌线性表的逻辑顺序与物理顺序总是一致的。​
选项：
A: 正确
B: 错误
答案: 【 错误】

8、判断题：
‏顺序表的空间利用率高于链表。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

9、判断题：
‍在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为O(1)。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

10、判断题：
‌线性表就是顺序存储的表。​
选项：
A: 正确
B: 错误
答案: 【 错误】

11、判断题：
​线性表的顺序存储优于链式存储。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

12、判断题：
‎数据的逻辑结构是数据结构在计算机中的表示。​
选项：
A: 正确
B: 错误
答案: 【 错误】

2.1节单元测试

1、单选题：
‎与单链表相比，双链表（   ）。‌
选项：
A: 可随机访问表中结点
B: 访问前后结点更为便捷
C: 执行插入、删除操作更为简单
D: 存储密度等于 1
答案: 【 访问前后结点更为便捷】

2、单选题：
‍设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（   ）最节省时间。‌
选项：
A: 单链表
B: 单循环链表
C: 带尾指针的单循环链表
D: 带头结点的双循环链表
答案: 【 带头结点的双循环链表】

3、单选题：
​线性表（a1，a2，…，an）以链接方式存储时，访问第 i 位置元素的时间复杂度为（   ）。‏
选项：
A: O(i)
B: O(1)
C: O(n)
D: O(i-1)
答案: 【 O(n)】

4、单选题：
‌假定顺序表中的第一个数据元素的存储地址为第200个存储单元，若每个数据元素占用6个存储单元，则第4个数据元素的地址是第（   ）个存储单元。‌
选项：
A: 218
B: 224
C: 230
D: 212
答案: 【 218】

5、单选题：
‌若将某一数组A中的元素，通过头插法插入至单链表B中（单链表初始为空），则插入完毕后，B中结点的顺序（   ）。‏
选项：
A: 与数组中元素的顺序相反
B: 与数组中元素的顺序相同
C: 与数组中元素的顺序无关
D: 与数组中元素的顺序部分相同、部分相反
答案: 【 与数组中元素的顺序相反】

6、单选题：
‍顺序表比链表的存储密度更大，是因为（   ）。‌
选项：
A: 顺序表的存储空间是预先分配的
B: 顺序表不需要增加指针来表示元素之间的逻辑关系
C: 链表的所有结点是连续的
D: 顺序表的存储空间是不连续的
答案: 【 顺序表不需要增加指针来表示元素之间的逻辑关系】

7、单选题：
‏下面关于线性表的叙述中，错误的是（   ）。​
选项：
A: 线性表采用顺序存储，必须占用一片连续的存储单元
B: 线性表采用顺序存储，便于进行插入和删除操作
C: 线性表采用链接存储，不必占用一片连续的存储单元
D: 线性表采用链接存储，便于插入和删除操作
答案: 【 线性表采用顺序存储，便于进行插入和删除操作】

8、单选题：
‏链表不具有的特点是（   ）。‍
选项：
A: 插入、删除不需要移动元素
B: 可随机访问任一元素
C: 不必事先估计存储空间
D: 所需空间与线性长度成正比
答案: 【 可随机访问任一元素】

9、单选题：
‎单链表中，增加一个头结点的目的是为了（   ）。​
选项：
A: 使单链表至少有一个结点
B: 标识表结点中首结点的位置
C: 方便运算的实现
D: 说明单链表是线性表的链式存储
答案: 【 方便运算的实现】

10、单选题：
‍线性表的顺序存储结构是一种（   ）的存储结构。‌
选项：
A: 随机存取
B: 顺序存取
C: 索引存取
D: 散列存取
答案: 【 随机存取】

11、单选题：
‍线性表是具有n个（   ）的有限序列。‎
选项：
A: 数据表
B: 字符
C: 数据元素
D: 数据项
答案: 【 数据元素】

12、单选题：
‏一个顺序表所占用的存储空间大小与（   ）无关。‌
选项：
A: 表的长度
B: 元素的存放顺序
C: 元素的类型
D: 元素中各字段类型
答案: 【 元素的存放顺序】

13、单选题：
‍若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（   ）的存储方式。‌
选项：
A: 单链表
B: 双向链表
C: 单循环链表
D: 顺序表
答案: 【 顺序表】

14、单选题：
‍在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动(   )个元素。‎
选项：
A: n
B: i-1
C: n-i    
D: n-i-1 
答案: 【 n-i    】

15、单选题：
‎对于顺序表，访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为（   ）。‌
选项：
A: O(n),O(n)
B: O(n),O(1)
C: O(1),O(n)
D: O(1),O(1)
答案: 【 O(1),O(n)】

16、判断题：
​单链表可以实现随机存取。​
选项：
A: 正确
B: 错误
答案: 【 错误】

17、判断题：
‎链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
​顺序存储方式的优点是存储密度大，且插入、删除运算效率高。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
‍循环链表不是线性表。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

20、判断题：
‏线性表的特点是每个元素都有一个前驱和一个后继。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

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

22、判断题：
‌线性表若采用链式存储表示,在删除时不需要移动元素。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

23、判断题：
​在线性链表中删除中间结点时，只需将被删结点释放。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

24、判断题：
‍链表中的头结点仅起到标识的作用。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

25、判断题：
​一个顺序表所占用的存储空间大小与元素的存放顺序无关。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

26、填空题：
‎在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度是O(__)。‏
答案: 【 1】

27、填空题：
‍当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。​
答案: 【 顺序】

28、填空题：
‎链接存储的特点是利用________来表示数据元素之间的逻辑关系。‌
答案: 【 指针】

29、填空题：
‎将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度是O(     )。‏
答案: 【 m】

30、填空题：
‍一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为O(    ) 。‌
答案: 【 n】

2.2节单元测试

1、单选题：
‍栈是（   ）。​
选项：
A: 顺序存储的线性结构
B: 链式存储的非线性结构
C: 限制存取点的线性结构
D: 限制存储点的非线性结构
答案: 【 限制存取点的线性结构】

2、单选题：
‌（   ）不是栈的基本操作。‌
选项：
A: 删除栈顶元素
B: 删除栈底元素
C: 判断栈是否为空
D: 将栈置为空栈
答案: 【 删除栈底元素】

3、单选题：
‏假定利用数组a[n]顺序存储为一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（   ）。‎
选项：
A: a[--top]=x
B: a[top--]=x
C: a[++top]=x
D: a[top++]=x
答案: 【 a[++top]=x】

4、单选题：
‎和顺序栈相比，链栈有一个比较明显的优势是（   ）。‎
选项：
A: 通常不会出现栈满的情况
B: 通常不会出现栈空的情况
C: 插入操作更容易实现
D: 删除操作更容易实现
答案: 【 通常不会出现栈满的情况】

5、单选题：
​设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是（   ）。 ​
选项：
A: 只有表头结点指针，没有表尾指针的双向循环链表
B: 只有表尾结点指针，没有表头指针的双向循环链表
C: 只有表头结点指针，没有表尾指针的单向循环链表
D: 只有表尾结点指针，没有表头指针的单向循环链表
答案: 【 只有表头结点指针，没有表尾指针的单向循环链表】

6、单选题：
‍设有一个空栈，栈顶指针为1000H，每个元素需要1个存储单元，在执行Push、Push、Pop、Push、Pop、Push、Pop、Push操作，栈顶指针的值为（   ）。‎
选项：
A: 1002H
B: 1003H
C: 1004H
D: 1005H
答案: 【 1002H】

7、单选题：
‏若一个栈的输入序列是1, 2, 3,……, n，输出序列的第一个元素是n，则第i个输出元是（   ）。‌
选项：
A: 不确定
B: n-i
C: n-i-1
D: n-i+1
答案: 【 n-i+1】

8、单选题：
​下列关于栈的描述中错误的是( )。‎
选项：
A: 栈是先进后出的线性表
B: 栈只能顺序存储
C: 栈具有记忆作用
D: 对栈的插入与删除操作中，不需要改变栈底指针
答案: 【 栈只能顺序存储】

9、单选题：
‏若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，则不可能得到的出栈序列是（   ）。‌
选项：
A: dcebfa
B: cbdaef
C: bcaefd
D: afedcb
答案: 【 afedcb】

10、单选题：
​用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234, 为了得到1342的出栈顺序，相应的S和X的操作序列为（   ）。‏
选项：
A: SXSXSSXX
B: SSSXXSXX
C: SXSSXXSX
D: SXSSXSXX
答案: 【 SXSSXSXX】

11、单选题：
‍采用共享栈的好处是（   ）。‏
选项：
A: 减少存取时间，降低发生上溢的可能
B: 节省存储空间，降低发生上溢的可能
C: 减少存取时间，降低发生下溢的可能
D: 节省存储空间，降低发生下溢的可能
答案: 【 节省存储空间，降低发生上溢的可能】

12、判断题：
‏任何一个递归过程都可以转换成非递归过程。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

13、判断题：
​若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。‏
选项