大学MOOC 数据结构(湖南科技大学)1207523807 最新慕课完整章节测试答案

数据结构基础测试

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、单选题：
设n是描述问题规模的非负整数，下面程序段的时间复杂度是（  ）。​x=2;​while(x<n/2)​    x=2*x;​
选项：
A:
B: O(n)
C:
D:  
答案: 【 】

8、单选题：
下面程序段的时间复杂度是（  ）。‎count=0;‎for(k=1;k<=n;k*=2)‎    for(j=1;j<=n;j++)‎        count++;‎
选项：
A: O(log2n)
B: O(n)
C: O(nlog2n)
D:
答案: 【 O(nlog2n)】

9、单选题：

‏某算法的语句执行频度为，其时间复杂度表示（  ）。

‌选项：
A: O(n)
B:
C:
D:
答案: 【 】

10、单选题：
以下程序段中语句"x++;"的语句频度为（  ）。‎for(i=1;i<=n;i++)‎    for(j=1;j<=i;j++)‎        for(k=1;k<=j;k++)‎            x++;‎
选项：
A: n(n+1)(2n+1)/ 2
B: n(n+1)(n+1)/ 2
C: n(n+1)(2n+1)/ 6
D: n(n+1)(n+2)/ 6
答案: 【 n(n+1)(n+2)/ 6】

11、单选题：
以下程序中的语句"m++;"的语句频度为（  ）。‌int m=0, i, j;‌for(i=1; i<=n; i++)‌ for(j=1; j<=2*i; j++)‌    m++;‌
选项：
A: n(n+1)
B: n
C: n+1
D:
答案: 【 n(n+1)】

12、单选题：
​下面说法错误的是（  ）。​
选项：
A: 算法原地工作的含义是指不需要任何额外的辅助空间
B: 在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2^n）的算法
C: 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
D: 某算法的时间复杂度为，表明该算法的执行时间与成正比
答案: 【 算法原地工作的含义是指不需要任何额外的辅助空间】

13、单选题：
‏下列叙述中正确的是（  ）。‏
选项：
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: 大于1
B: 等于1
C: 小于1
D: 不能确定
答案: 【 小于1】

6、单选题：
‏创建一个包括n个结点的有序单链表的时间复杂度是（    ）。​
选项：
A: O(1) 
B: O(n)
C:

O()
D: O(nlog2n)
答案: 【 

O()】

7、单选题：
​以下说法错误的是（   ）。‌
选项：
A: 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低。
B: 顺序存储的线性表可以随机存取。
C: 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。
D: 线性表的链式存储结构优于顺序存储结构
答案: 【 线性表的链式存储结构优于顺序存储结构】

8、单选题：
​在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（   ）。‏
选项：
A: s->next=p+1; p->next=s;
B: (*p).next=s; (*s).next=(*p).next;
C: s->next=p->next; p->next=s->next;
D: s->next=p->next; p->next=s;  
答案: 【 s->next=p->next; p->next=s;  】

9、单选题：
‌在双向链表存储结构中，删除p所指的结点时须修改指针（   ）。‎
选项：
A: p->next->prior=p->prior; p->prior->next=p->next;
B: p->next=p->next->next; p->next->prior=p;
C: p->prior->next=p; p->prior=p->prior->prior;
D: p->prior=p->next->next; p->next=p->prior->prior;
答案: 【 p->next->prior=p->prior; p->prior->next=p->next;】

10、单选题：
‏在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（   ）。‎
选项：
A: p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B: p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C: q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D: q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
答案: 【 q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;】

11、单选题：
‍已知两个长度分别为m和n的升序链表，若将它们合并成为一个长度为 m+n 的降序链表，则最坏情况的时间复杂度是（  ）。‌
选项：
A: O(n) 
B: O(m×n) 
C: O(min(m，n))    
D: O(max(m，n))
答案: 【 O(max(m，n))】

12、单选题：
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，至少需要进行关键字比较（  ）次。‌
选项：
A: 2
B: n-1
C: n
D: 2n
答案: 【 n】

13、单选题：
‎将长度为n的单链表接在长度为m的单链表之后的算法的时间复杂度为（  ）。‌
选项：
A: O(1) 
B: O(n)
C: O(m)
D: O(m+n)
答案: 【 O(m)】

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

15、单选题：
‌在线性表的下列运算中，不改变数据元素之间结构关系的运算是（  ）。‌
选项：
A: 插入
B: 删除
C: 排序
D: 定位
答案: 【 定位】

16、单选题：
‏对于一个头指针为head的带头结点的单链表，判断该表为空表的条件是（  ）。‎
选项：
A: head==NULL
B: head->next=NULL
C: head->next==head
D: head!=NULL
答案: 【 head->next=NULL】

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

18、单选题：
‍访问单链表中当前结点的后继和前驱的时间复杂度分别是（  ）。‎
选项：
A: O（n）和O（1）
B: O（1）和O（1）
C: O（1）和O（n）
D: O（n）和O（n）
答案: 【 O（1）和O（n）】

19、单选题：
‍在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（  ）。​
选项：
A: O（1）
B: O(n)
C: O(nlog2n)
D: O()
答案: 【 O(n)】

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

顺序表测验

1、单选题：
​设一维数组中有n个数组元素，则取第i个数组元素的平均时间复杂度为（  ）。‎
选项：
A: O(n) 
B: O(nlogn) 
C: O(1) 
D: O()
答案: 【 O(1) 】

2、单选题：
下面算法将一维数组a中的n个数逆序存放到原数组中空间复杂度为（  ）。​for（i=0;i<n；i++）​     b[i]=a[n-i-1];​for(i=0;i<=n;i++)​     a[i]=b[i]​‍​
选项：
A: O(1)
B: O(n)
C: O(log2n)
D: O()
答案: 【 O(n)】

3、单选题：
下面算法将一维数组a中的n个数逆序存放到原数组中空间复杂度为（  ）。‍for(i=0;i<n/2;i++)‍{‍        t=a[i];‍        a[i]=a[n-i-1];‍        a[n-i-1]=t‍}‍‎‍
选项：
A: O(1)
B: O(n)
C: O(log2n)
D: O()
答案: 【 O(1)】

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、单选题：
顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（  ）。‎
选项：
A: 110
B: 108
C: 100
D: 120
答案: 【 108】

11、单选题：
‏在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（   ）。‎
选项：
A: 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B: 在第i个结点后插入一个新结点（1≤i≤n）
C: 删除第i个结点（1≤i≤n）
D: 将n个结点从小到大排序
答案: 【 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）】

12、单选题：
‍向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（   ）。‎
选项：
A: 8
B: 63.5
C: 63
D: 7
答案: 【 63.5】

13、单选题：
‏在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（   ）个元素。‌
选项：
A: n-i
B: n-i+1
C: n-i-1
D: i
答案: 【 n-i+1】

14、单选题：
‌线性表L=(a1，a2,……an)，下列说法正确的是（   ）。‍
选项：
A: 每个元素都有一个直接前驱和一个直接后继
B: 线性表中至少有一个元素
C: 表中诸元素的排列必须是由小到大或由大到小
D: 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
答案: 【 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。】

栈和队列测验

1、单选题：
若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（  ）种情况。‌
选项：
A: 5,4,3,2,1
B: 2,1,5,4,3
C: 4,3,1,2,5
D: 2,3,5,4,1
答案: 【 4,3,1,2,5】

2、单选题：
‍若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（  ）。‌
选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i+1】

3、单选题：
‎数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（  ）。‎
选项：
A: r-f
B: (n+f-r)%n
C: n+r-f
D: (n+r-f)%n
答案: 【 (n+r-f)%n】

4、单选题：
‏链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（  ）。​
选项：
A: x=top->data;top=top->link；
B: top=top->link;x=top->link；
C: x=top;top=top->link；
D: x=top->link；
答案: 【 x=top->data;top=top->link；】

5、单选题：
‌设有一个递归算法如下​‌int fact(int n) {  //n大于等于0​‌{​‌             if(n<=0)   return 1;​‌             else   return n*fact(n-1);       ​‌}​‌则计算fact(n)需要调用该函数的次数为（  ）。 ​
选项：
A: n+1
B: n-1
C: n
D: n+2
答案: 【 n+1】

6、单选题：
‎栈在 （  ）中有所应用。‏
选项：
A: 递归调用
B: 函数调用
C: 表达式求值
D: 前三个选项都有
答案: 【 前三个选项都有】

7、单选题：
‍为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（  ）。‍
选项：
A: 队列
B: