大学MOOC 数据结构（邓育林）(南宁师范大学)1452231171 最新慕课完整章节测试答案

小测验：算法复杂度

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: 一对多
C: 多对多
D: 无关系
答案: 【 多对多】

7、单选题：
‏数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称为（                ）。‏
选项：
A: 存储结构
B: 逻辑结构
C: 顺序存储结构
D: 链式存储结构
答案: 【 顺序存储结构】

8、单选题：
‌非线性结构中的每个结点（                ）。​
选项：
A: 无直接前驱结点
B: 无直接后继结点
C: 只有一个直接前驱结点和一个直接后继结点
D: 可能有多个直接前驱结点和多个直接后继结点
答案: 【 可能有多个直接前驱结点和多个直接后继结点】

9、单选题：
‎链式存储结构所占存储空间‏
选项：
A: 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B: 只有一部分，存放结点的值
C: 只有一部分，存储表示结点间关系的指针
D: 分两部分，一部分存放结点的值，另一部分存放结点所占单元
答案: 【 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针】

10、单选题：
​算法分析的两个主要方面是（                ）。‎
选项：
A: 正确性和简单性
B: 可读性和文档性
C: 数据复杂性和程序复杂性
D: 时间复杂度和空间复杂度
答案: 【 时间复杂度和空间复杂度】

11、单选题：
‌算法的计算量大小称为算法的（                ）。‎
选项：
A: 现实性
B: 难度
C: 时间复杂性
D: 效率
答案: 【 时间复杂性】

12、单选题：
‌每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（        ）。‏
选项：
A: 顺序存储
B: 链式存储
C: 索引存储
D: 散列存储
答案: 【 顺序存储】

13、单选题：
​每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（            ）存储方式。​
选项：
A: 顺序
B: 链式
C: 索引
D: 散列
答案: 【 链式】

14、单选题：
‎以下任何两个结点之间都没有逻辑关系的是（            ）。‌
选项：
A: 图形结构
B: 线性结构
C: 树形结构
D: 集合
答案: 【 集合】

15、单选题：
‏在数据结构中，与所使用的计算机无关的是（                ）。‍
选项：
A: 物理结构
B: 存储结构
C: 逻辑结构
D: 逻辑和存储结构
答案: 【 逻辑结构】

16、单选题：
‌下列四种基本逻辑结构中，数据元素之间关系最弱的是（                ）。‎
选项：
A: 集合
B: 线性结构
C: 树形结构
D: 图形结构
答案: 【 集合】

17、单选题：
‍与数据元素本身的形式、内容、相对位置、个数无关的是数据的（                ）‍
选项：
A: 逻辑结构
B: 存储结构
C: 逻辑实现
D: 存储实现
答案: 【 逻辑结构】

18、单选题：
‍每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（                ）。‍
选项：
A: 顺序
B: 链式
C: 索引
D: 散列
答案: 【 索引】

19、单选题：
‌算法能正确的实现预定功能的特性称为算法（                ）。‌
选项：
A: 正确性
B: 易读性
C: 健壮性
D: 高效性
答案: 【 正确性】

20、单选题：
‏算法在发生非法操作时可以做出处理的特性称为算法的（                ）。‍
选项：
A: 正确性
B: 易读性
C: 健壮性
D: 高效性
答案: 【 健壮性】

21、单选题：
‌下列时间复杂度中最坏的是（                ）。​
选项：
A: O（1）
B: O（n）
C: O（ n）
D: O（）
答案: 【 O（）】

22、单选题：
‍在下面的程序段中，对 x 的赋值语句的频度为（                ）。​‍for(i=1;i<n;i++)
    for(j=1;j<n;j++)
        x++;​
选项：
A: O（2n）
B: O（n）
C: O（）
D: O（ n）
答案: 【 O（）】

23、判断题：
‌数据的逻辑结构与数据元素本身的内容和形式无关。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

24、判断题：
‎一个数据结构是由一个逻辑结构和这个逻辑结构上一个基本运算集构成的整体。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

25、判断题：
​数据元素是数据的最小单位。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

26、判断题：
‎数据的逻辑结构和数据的存储结构是相同的。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

27、判断题：
‎程序和算法原则上没有区别，所以在讨论数据结构时可以通用。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

28、判断题：
​从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

29、判断题：
​数据的存储结构是数据的逻辑结构的存储映像。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

30、填空题：
‍常见的数据结构有集合、线性结构、                      结构、图形结构。‍
答案: 【 树形】

31、填空题：
‍算法的5个重要特性是有穷性、                                 、可行性、输入、输出。‌
答案: 【 确定性】

32、填空题：
‎算法是一个                          的集合。‌
答案: 【 有穷指令】

33、填空题：
‎算法效率的度量可以分为：                                        和空间复杂度。‌
答案: 【 时间复杂度】

34、填空题：
​线性结构中元素之间存储一对一关系；树形结构中元素之间存在一对多关系，图形结构中元素之间存在                   关系。​
答案: 【 多对多】

35、填空题：
‏数据的存储结构又称为                                         。‌
答案: 【 物理结构】

36、填空题：
​数据结构定义为（D, R），其中 D 是数据的有限集合，R 是 D 上的                         的有限集合。‏
答案: 【 关系】

37、填空题：
‍算法的空间复杂度是指该算法所耗费的                                 ，它是该算法求解问题规模 n 的函数。‍
答案: 【 存储空间】

38、填空题：
​设有一组数据元素需存储，为了方便查找某元素，数据宜采用顺序存储结构；为了方便插入与删除某元素，数据宜采用                    存储结构。‎
答案: 【 链式】

小测验：堆栈

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
答案: 【&nb