大学MOOC 数据结构及算法(西南石油大学)1453138168 最新慕课完整章节测试答案

测验1.1

1、单选题：
‍在数据结构中，从逻辑上可以把数据结构分成（   ）‍
选项：
A: 动态结构和静态结构
B: 逻辑结构和物理结构
C: 线性结构和非线性结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】

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

第一、二章测验

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、单选题：
下面说法错误的是（    ）‏ (1）算法原地工作的含义是指不需要任何额外的辅助空间 ‏（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2^n)的算法 ‏（3）所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界‏（4）同一个算法，实现语言的级别越高，执行效率就越低‏‏‎‏
选项：
A: (1)
B: (1),(2) 
C: (1),(4) 
D: (3)
答案: 【 (1),(2) 】

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

9、单选题：
下面程序段的时间复杂度是 (      ) 。 ‏i ＝ 0；‏while（i<=n）       ‏i = i * 3；‏‏‏
选项：
A: O(2^n) 
B: O(n) 
C: O(n^2)   
D: O(log3n)
答案: 【 O(log3n)】

10、单选题：
下面程序段的时间复杂度是(       )。 ‏for( i =0; i<n; i++) ‏   for(j=0;j<m;j++) ‏      A[i][j] ＝ 0;‏
选项：
A: O(2n) 
B: O(n*m) 
C: O(n^2)
D: O(logn) 
答案: 【 O(n*m) 】

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、单选题：
一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（     ）。‎​‎
选项：
A: 确定性、可行性、有穷性
B: 易读性、确定性、有效性
C: 有穷性、稳定性、确定性
D: 可行性、易读性、有穷性
答案: 【 确定性、可行性、有穷性】

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

21、单选题：
下面关于算法说法错误的是（    ）‌‌‎‌
选项：
A: 算法最终必须由计算机程序实现
B: 为解决某问题的算法同为该问题编写的程序含义是相同的
C: 算法的可行性是指指令不能有二义性  
D:  以上几个都是错误的
答案: 【  以上几个都是错误的】

22、单选题：
程序段 FOR  i:=n-1  DOWNTO  1  DO​            FOR j:=1 TO i DO​               IF A[j]>A[j+1]​                  THEN  A[j]与A[j+1]对换；​其中 n为正整数，则最后一行的语句频度在最坏情况下是（   ）​
选项：
A: O（n） 
B:  O(nlogn)  
C: O(n^3)
D: O(n^2)
答案: 【 O(n^2)】

23、单选题：
以下属于逻辑结构的是（    ）。​
选项：
A: 顺序表
B: 循环链表
C: 有序表
D: 单链表
答案: 【 有序表】

24、单选题：
‏对于顺序表，以下说法错误的是（     ）‏
选项：
A: 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B: 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C: 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D: 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
答案: 【 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址】

25、单选题：
‏以下说法错误的是  (  ) ‍
选项：
A: 对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n）
B: 读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构
C: 在链表上实现读表元运算的平均时间复杂度为O（1）
D: 插入、删除操作在链表上的实现可在O（1）时间内完成
E: 插入、删除操作在顺序表上的实现，平均时间复杂度为O（n）
答案: 【 在链表上实现读表元运算的平均时间复杂度为O（1）】

26、单选题：
​在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（    ）‍
选项：
A: p->next=s;s->next=p->next
B: s->next=p->next;p->next=s
C: p->next=s;p->next=s->next
D: p->next=s->next;p->next=s
答案: 【 s->next=p->next;p->next=s】

27、单选题：
​对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（    ）‌
选项：
A: head==NULL 
B: head→next==NULL 
C: head→next==head
D: head!=NULL
答案: 【 head→next==NULL 】

28、单选题：
‍若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（   ）存储方式最节省时间。‌‍‌
选项：
A: 顺序表
B: 单链表
C: 双链表
D: 单循环链表
答案: 【 顺序表】

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

30、单选题：
‍在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（    ）。​
选项：
A: rear和rear->next->next
B: rear->next 和rear
C: rear->next->next和rear
D: rear和rear->next
答案: 【 rear->next 和rear】

31、单选题：
‍哪个选项不是线性表的链式存储结构（    ）‌
选项：
A: 单链表
B: 顺序表
C: 循环链表
D: 双向链表
答案: 【 顺序表】

测验2.1

1、单选题：
‎线性表是         。‍
选项：
A: 一个有限序列，可以为空
B: 一个有限序列，不可以为空
C: 一个无限序列，可以为空
D: 一个无限序列，不可以为空
答案: 【 一个有限序列，可以为空】

2、单选题：
​若数组M可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素M[8]的起始地址为_____。‎
选项：
A: x+8
B: x+28
C: x+32
D: x+64
答案: 【 x+32】

第三章测验

1、单选题：
‏在作进栈运算时,应先判别栈是否(    )‍
选项：
A: 空
B: 满
C: 上溢
D: 下溢 
答案: 【 满】

2、单选题：
​在作退栈运算时应先判别栈是否(   )‍
选项：
A: 空
B: 满
C: 上溢
D: 下溢
答案: 【 空】

3、单选题：
​当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(    )‏
选项：
A: n-1
B: n
C: n+1
D: n/2
答案: 【 n】

4、单选题：
‌若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为(   )。‎
选项：
A: 可能是2
B: 一定是2
C: 可能是1
D: 一定是1
答案: 【 可能是2】

5、单选题：
‎有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（    ） ‏‎‏
选项：
A: 5 4 3 6 1 2
B: 4 5 3 1 2 6
C: 3 4 6 5 2 1
D: 2 3 4 1 5 6
答案: 【 3 4 6 5 2 1】

6、单选题：
‌设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（    ）‏‌‏
选项：
A: 2
B: 3
C: 5
D: 6
答案: 【 3】

7、单选题：
‌若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（    ）​‌​
选项：
A: |top[2]-top[1]|=0
B: top[1]+1=top[2]
C: top[1]+top[2]=m
D: top[1]=top[2]
答案: 【 top[1]+1=top[2]】

8、单选题：
‌执行完下列语句段后，i值为：（    ）‍     int f(int x)‍     { return  ((x>0) ? x* f(x-1):2);}‍      int i  ;‍      i =f(f(1));‍
选项：
A: 2
B: 4
C: 8
D: 无限递归
答案: 【 4】

9、单选题：
‏表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（   ），其中^为乘幂。‍‏‍
选项：
A: 3,2,4,1,1；(*^(+*-
B: 3,2,8；(*^- 
C: 3,2,4,2,2；(*^(- 
D: 3,2,8；(*^(-
答案: 【  3,2,8；(*^(-