大学MOOC 数据结构s1(南京邮电大学)1003118002 最新慕课完整章节测试答案

第1章 单元测验

1、单选题：
‏对包含n个元素的数组进行顺序搜索时，若搜索每个元素的概率相同，则平均搜索长度是‎
选项：
A: n/2
B: n
C: (n-1)/2
D: (n+1)/2
答案: 【 (n+1)/2】

2、单选题：
‎下面说法正确的是____。‍
选项：
A: 健壮的算法不会因为非法的输入数据而出现莫名其妙的状态
B: 算法的优劣与算法的描述语言无关，但与所用计算机环境因素有关
C: 数据的逻辑结构依赖于数据的存储结构
D: 以上几个都是错误的
答案: 【 健壮的算法不会因为非法的输入数据而出现莫名其妙的状态】

3、单选题：
‎从逻辑上可以吧数据结构分为______两大类。‎
选项：
A: 初等结构和构造性结构
B: 顺序结构和链式结构
C: 线性结构和非线性结构
D: 动态结构和静态结构
答案: 【 线性结构和非线性结构】

4、单选题：
‍数据结构采用链式存储时，存储单元的地址_______________。‍
选项：
A: 一定连续
B: 一定不连续
C: 不一定连续
D: 部分连续，部分不连续
答案: 【 不一定连续】

5、单选题：
​算法的时间复杂度取决于______________。‌
选项：
A: 问题规模
B: 计算机的软硬件配置
C: 两者都是
D: 两者都不是
答案: 【 问题规模】

6、单选题：
下面程序段的时间复杂度为________________。‍for(i=0;i<n;i++）‍    for(j=0;j<i;j++)‍         x++;‍‎‍
选项：
A:
B:
C:
D:
答案: 【 】

7、单选题：
下列函数的时间复杂度是（）‌           int func（Int  n）｛‌                    int i=0,sum=0;‌                    while(sum<n)   sum+=++i;‌                    return i;‌                 ｝‌‏‌
选项：
A: O(logn)
B: O(n^1/2)
C: O(n)
D: O(nlogn)
答案: 【 O(n^1/2)】

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

9、单选题：
‍计算机算法必须具备如下三个基本特征_____________.‏
选项：
A: 可执行性、可移植性、可扩充性
B: 可执行性、确定性、有穷性
C: 确定性、有穷性、稳定性
D: 易读性、稳定性、安全性  
答案: 【 可执行性、确定性、有穷性】

10、单选题：
‍从逻辑上可以把数据结构分为__________两大类‏
选项：
A: 动态结构、静态结构
B: 顺序结构、链式结构 
C: 线性结构、非线性结构
D: 初等结构、构造型结构
答案: 【 线性结构、非线性结构】

11、判断题：
​程序步越少的算法执行效率越高。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

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

13、判断题：
‏数据的逻辑结构是指数据的各数据项之间的逻辑关系。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

14、判断题：
​算法的优劣与算法描述语言无关，但与所用计算机有关。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
‏健壮的算法不会因非法的输入数据而出现莫名其妙的状态。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

16、判断题：
‏程序一定是算法。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

17、判断题：
‌数据的物理结构是指数据在计算机内的实际存储形式。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

18、判断题：
‍数据结构的抽象操作的定义与具体实现有关。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

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

20、填空题：
求该方法的渐近时间复杂度为__________.‍(注意填写答案时不要有空格，用x^y的方式表达x的y次方)‍void aFunc(int n) {‍    for (int i = 0; i < n; i++) {‍        for (int j = i; j < n; j++) {‍            printf("Hello Worldn");‍        }‍    }‍}‍‎‍
答案: 【 O(n^2)】

21、填空题：
求aFunc方法的时间复杂度为____________。（注意答案中不要有空格）‏void aFunc(int n) {‏    for (int i = 2; i < n; i++) {‏        i *= 2;‏        printf("%in", i);‏    }‏}‏​‏
答案: 【 O(logn)】

22、填空题：

已知算法关键步骤的执行次数,则算法的渐近时间复杂度为_______。

​

（请用x^y表示x的y次方）

​

‍

​答案: 【 O(n^2)】

23、填空题：

已知算法关键步骤的执行次数,则算法的渐近时间复杂度为_______。

‎

（logn默认以2为底，答案不要有空格，请注意此题表示问题特征的变量有m和n两个）

‎

‎答案: 【 O(mlogn+m^3)##%_YZPRLFH_%##O(m^3+mlogn)】

24、填空题：
‌四种基本的逻辑结构包括集合结构、_______结构、图形结构和树形结构‌
答案: 【 线性】

25、填空题：
‌四种基本的逻辑结构包括线性结构、_______结构、图形结构和树形结构‌
答案: 【 集合】

26、填空题：
‎四种基本的逻辑结构包括集合结构、_______结构、线性结构和树形结构‍
答案: 【 图形##%_YZPRLFH_%##图】

27、填空题：
‏四种基本的逻辑结构包括集合结构、_______结构、线性结构和图形结构‎
答案: 【 树形##%_YZPRLFH_%##树】

第2章 单元测验

1、单选题：
‌如果线性表最常用的操作是读取第i个元素的值，则采用______存储方式最高效。‌
选项：
A: 顺序表
B: 有序表
C: 单链表
D: 双向链表
答案: 【 顺序表】

2、单选题：
‌对于线性表，下列说法正确的是_______________。‎
选项：
A: 每个元素都有一个直接前驱和一个直接后继
B: 线性表中至少要有一个元素
C: 表中元素必须有序排列
D: 除第一个元素与最后一个元素，其他每个元素都有一个直接前驱和一个直接后继
答案: 【 除第一个元素与最后一个元素，其他每个元素都有一个直接前驱和一个直接后继】

3、单选题：
‌已知顺序表中每个元素占2个存储单元，第一个元素存储地址为100，则表中第6个元素的存储地址是_______。‎
选项：
A: 112
B: 120
C: 110
D: 140
答案: 【 110】

4、单选题：
‏线性表采用链式存储结构所具有的特点是________。​
选项：
A: 所需空间地址必须连续
B: 可随机存取
C: 插入、删除操作不必移动元素
D: 需要事先估计所需存储空间
答案: 【 插入、删除操作不必移动元素】

5、单选题：
‎在带表头结点的单链表中，设指针first指向表头结点，当______时，表示链表为空。‏
选项：
A: first==NULL
B: first->link==NULL
C: first->link==first
D: first!=NULL
答案: 【 first->link==NULL】

6、单选题：
‏在循环单链表中，设指针first指向头结点，当_____时表示链表为空。‍
选项：
A: first==NULL
B: first->link==NULL
C: first->link==first
D: first->link->link==first
答案: 【 first==NULL】

7、单选题：
‌在单链表中添加表头结点的目的是_______。‍
选项：
A: 使得单链表至少存在一个结点
B: 避免断链现象
C: 方便插入和删除操作的实现
D: 说明单链表是线性表的链式存储
答案: 【 方便插入和删除操作的实现】

8、单选题：
​循环链表的主要优点是_______。‌
选项：
A: 不再需要头指针
B: 访问某个结点时，可以快速访问它的直接前驱
C: 进行插入和删除操作时避免断链现象
D: 从表中任意结点出发都能扫描整个链表
答案: 【 从表中任意结点出发都能扫描整个链表】

9、单选题：
‍在包含n个结点的单链表上进行元素查找操作，平均时间复杂度是_______。‍
选项：
A: O(1)
B: O(n)
C: O(n/2)
D: O(n^2)
答案: 【 O(n)】

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

11、单选题：
在一个以 first为头指针的单循环链表中，p 指针指向尾结点的条件是__________。‌
选项：
A: p->link=first
B: p->link=NULL
C: p->link->link=first 
D: p->element=-1
答案: 【 p->link=first】

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

13、单选题：
‍以下选项__________不是链表结构所具备特征。‍
选项：
A: 插入、删除操作不需要移动元素
B: 可随机存取任意位置元素
C: 不必预先估计和申请连续存储空间
D: 所需存储空间与线性表长度呈正比
答案: 【 可随机存取任意位置元素】

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

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

16、判断题：
‎顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

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

18、判断题：
‌取线性表的第i个元素的时间与i值的大小有关.​
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
‎取顺序表的第i个元素的时间与i值的大小有关.‎
选项：
A: 正确
B: 错误
答案: 【 错误】

20、判断题：
‍取单链表的第i个元素的时间与i值的大小有关.‏
选项：
A: 正确
B: 错误
答案: 【 正确】

21、判断题：
‌在顺序表上进行查找操作，最好情况的时间复杂度为O(n)。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

22、判断题：
‍在单链表上进行查找操作，最好情况的时间复杂度为O(1)。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

23、判断题：
​在顺序表上，逻辑上相邻的两个数据元素 ，在物理存储位置上不一定相邻‍
选项：
A: 正确
B: 错误
答案: 【 错误】

24、判断题：
‍在顺序表上，物理上相邻的两个数据元素之间存在逻辑关系。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

25、判断题：
‏链表方式实现的线性表中，存在逻辑关系的两个数据元素不一定存储在相邻的地址上。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

26、判断题：
‌顺序存储实现的线性表上，元素的插入操作需要移动的元素个数，与元素插入位置有关。‍
选项：
A: 正确
B: 错误
答案: 【 正确】

27、判断题：
‎链表存储实现的线性表上，元素的插入操作需要移动的元素个数，与元素插入位置有关。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

28、填空题：

‍线性表，删除需要移动______个元素（提示：答案不唯一，写出一个答案即可）。

‍答案: 【 50##%_YZPRLFH_%##0】

29、填空题：

‎线性表，在前插入一个元素，需要移动______个元素（提示：答案不唯一，写出一个答案即可）。

‏答案: 【 51##%_YZPRLFH_%##0】

30、填空题：

‍

​

‍指针r的指向如上图所示，现在需要在r后插入一个由指针p指向的新结点，请完成如下算法填空（答案中请不要包含空格和分号）：

​

‍p->llink=r;

​

‍p-rlink=r->rlink;

​

‍r->rlink=p;

​

‍___________;

​答案: 【 p->rlink->llink=p】

31、填空题：

‌

‌

‌指针r的指向如上图所示，现在需要在r后插入一个由指针p指向的新结点，请完成如下算法填空（答案中请不要包含空格和分号）：

‌

p->llink=r;

‌

p-rlink=r->rlink;

‌

r->rlink->llink=p;

‌

__________________;

‌答案: 【 r->rlink=p】

第3章 单元测验

1、单选题：
‎堆栈和队列的主要区别是_______。‍
选项：
A: 逻辑结构不同
B: 存储结构不同
C: 限定元素插入和删除的位置不同
D: 名字不同
答案: 【 限定元素插入和删除的位置不同】

2、单选题：
‎在移动营业厅通过“取号、叫号”办理业务的服务模式符合______特征。​
选项：
A: 集合
B: 堆栈
C: 队列
D: 线性表
答案: 【 队列】

3、单选题：
‏若元素入栈序列为a, b, c, d，则不可能得到的出栈序列为_________（提示：元素可以入栈后立刻出栈）。‏
选项：
A: c, b, a, d 
B:  c, b, d, a 
C:  d, b, c, a
D: b, c, d, a
答案: 【  d, b, c, a】

4、单选题：
​设数组data[m]作为循环队列SQ的存储空间，front指向队头，rear指向队尾，则执行出队操作时对front执行的操作是______。‎
选项：
A: front=front+1 
B: front=(front+1)%(m-1)   
C: front=(front-1)%m   
D: front=(front+1)%m   
答案: 【 front=(front+1)%m   】

5、单选题：
‎已知某多项式的中缀表达式为(a+b*c)/d+e*f，则其后缀表达式为_______。‌
选项：
A: abc*+d/ef*+ 
B: abc*+d/+ef* 
C: abc*+def/*+ 
D: ab+c*d/ef*+
答案: 【 abc*+d/ef*+ 】

6、单选题：
‌在具有m个存储单元的循环队列中，队满时共有个           数据元素。‎
选项：
A: m
B: m-1
C: m-2
D: m+1
答案: 【 m-1】

7、单选题：
‌设有一顺序栈，元素3,2,1依次进栈，进栈后可立即出栈，共可得到________种不同的出栈序列。‏
选项：
A: 5
B: 6
C: 4
D: 3
答案: 【 5】

8、单选题：
​算术表达式的后缀形式为264－×2/，每个操作数均为一位数，此表达式的值为_____。‎
选项：
A: 2
B: 1
C: 3
D: 4
答案: 【 2】

9、单选题：
​设数组data[20]作为循环队列SQ的存储空间，front指向队头，rear指向队尾，当front==4，rear==15时，以下说法正确的是_______。‍
选项：
A: data数组中下标从4到15的位置存储的是队列元素
B: data数组中下标从5到14的位置存储的是队列元素
C: 该循环队列当前存储的队列元素个数是11个
D: 该循环队列当前存储的队列元素个数是10个
答案: 【 该循环队列当前存储的队列元素个数是11个】

10、单选题：
‍设数组data[20]作为循环队列SQ的存储空间，front指向队头，rear指向队尾，当front==4，rear==15时，以下说法正确的是_______。‎
选项：
A: 队列中还能存放数据元素的空闲位置数量为8个
B: 队列中还能存放数据元素的空闲位置数量为7个
C: 队列中还能存放数据元素的空闲位置数量为9个
D: 队列中还能存放数据元素的空闲位置数量为6个
答案: 【 队列中还能存放数据元素的空闲位置数量为8个】

11、单选题：
‌设数组data[m]作为循环队列SQ的存储空间，front指向队头，rear指向队尾，则执行入队操作时对rear执行的操作是______。‏
选项：
A: rear=(rear+1)%m
B: rear=(rear+1)%(m-1)
C: rear=rear+1
D: ++rear
答案: 【 rear=(rear+1)%m】

12、单选题：
‏设数组data[100]作为循环队列SQ的存储空间，front指向队头，rear指向队尾，当front==80，rear==15时，以下说法正确的是_______。​
选项：
A: data数组中下标从16到79的位置都为空闲位置
B: 队列元素个数为36
C: data数组中下标从16到80的位置都为空闲位置
D: 队列元素个数为34
答案: 【 data数组中下标从16到79的位置都为空闲位置】

13、单选题：
‌设计一个判别表达式中左右括号是否配对出现的算法，采用_______实现最佳。​
选项：
A: 线性表的顺序存储结构
B: 队列
C: 线性表的链式存储结构
D: 堆栈
答案: 【 堆栈】

14、单选题：
‌设a,b,c,d,e,f依次进栈，允许入栈后立刻出栈，则下面得不到的出栈序列为______。‍
选项：
A: f,e,d,c,b,a  
B: b,c,a,f,e,d
C: d,c,e,f,b,a
D: c,a,b,d,e,f
答案: 【 c,a,b,d,e,f】

15、单选题：
​递归过程或函数调用时，处理参数及返回地址，要用一种称为______的数据结构。​
选项：
A: 堆栈
B: 队列
C: 数组
D: 线性表
答案: 【 堆栈】

16、单选题：
​最多可存储n个数据元素的循环队列，rear指向队尾,  front指向队头, 则队空的条件是  (   )‌
选项：
A: rear==front
B: front+1==rear
C: (rear+1)%n==front
D: (rear+1)%(n+1)==front
答案: 【 rear==front】

17、单选题：
‎最多可存储n个数据元素的循环队列，rear指向队尾,  front指向队头, 则队满的条件是  (   )‏
选项：
A: (rear+1)%(n+1)==front
B: (front+1)%(n+1)==rear
C: (rear+1)%n==front
D: (front+1)%n==rear
答案: 【 (rear+1)%(n+1)==front】

18、单选题：
用链接方式存储的队列，在进行删除运算时_______。‌‍‌
选项：
A: 仅修改头指针
B: 仅修改尾指针
C: 头、尾指针都要修改  
D: 头、尾指针可能都要修改
答案: 【 头、尾指针可能都要修改】

19、单选题：
‌若用一个大小为6的数组来实现循环队列，且当前rear 和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?‏
选项：
A: 1和5  
B: 2和4  
C: 4和2
D: 5和1
答案: 【 2和4  】

20、单选题：
‎假设以数组A[m] 存放循环队列的元素，front指向队头，rear指向队尾，则当前队列中的元素个数为______。‎
选项：
A: (rear- front)%m
B: front-rear
C: (front- rear) %m
D: rear- front
答案: 【 (rear- front)%m】

21、单选题：
‎栈和队列的共同点是__________。‍
选项：
A: 都是先进先出
B: 都是先进后出
C: 都是线性结构
D: 没有共同点
答案: 【 都是线性结构】

22、单选题：
‏设栈S初始状态为空，元素e1,  e2，e3，e4,e5和e6依次进入栈S，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是__________。​
选项：
A: 6
B: 5
C: 4
D: 3
答案: 【 3】

23、单选题：
​9 3 1 - 3 * + 10 2 / +（表达式中相邻数字以空格相隔）的计算结果是______。‍
选项：
A: 20
B: 18
C: 22
D: 16
答案: 【 20】

24、单选题：
‍3 2+5*4-（表达式中相邻数字以空格相隔）的计算结果是______.‌
选项：
A: 21
B: 20
C: 19
D: 18
答案: 【 21】

25、单选题：
‍为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的数据结构应该是_____.​
选项：
A: 队列
B: 堆栈
C: 有序表
D: 数组
答案: 【 队列】

26、判断题：
‎已知某长度为maxSize的循环队列,front指向队头元素，rear指向队尾元素，则rear==front时表示该队列为满队列。​
选项：
A: