大学MOOC 2017春数据结构（大连东软信息学院）(中国高校计算机教育大学MOOC联盟)1002004003 最新慕课完整章节测试答案

MOOC第一章单元测试题

1、单选题：
执行下面的程序段的时间复杂度为           。‏for(int i=0;i<m;i++)‏for(int j=0;j<n;j++)‏     a[i][j]=i*j;‏‌‏
选项：
A: O(m2)
B: O(n2)
C: O(m*n)
D: O(m+n)
答案: 【 O(m*n)】

2、单选题：
执行下面程序段时，语句S的执行次数为          。‍for(int i=0;i<=n;i++)‍  for(int j=0;j<=i;j++)‍    S;‍‌‍
选项：
A: n2       
B:   n2/2
C:   (n+1) (n+2)/2 
D:   n(n+1)/2
答案: 【   (n+1) (n+2)/2 】

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、单选题：
‍某算法的时间复杂度是O（n2）,表明该算法的            。‍‍‍
选项：
A: 问题规模是n2 
B: 问题规模与n2成正比    
C: 执行时间与n2成正比 
D: 执行时间等于n2
答案: 【 执行时间与n2成正比 】

9、单选题：
‏以下不属于算法特性的是‍‏‍
选项：
A: 可行性
B: 有输入     
C: 确定性  
D: 健壮性
答案: 【 健壮性】

10、单选题：
‎若需要利用形式参数直接访问修改实参值，则应将形参说明为           参数。​
选项：
A: 指针
B: 值参数
C: 实地址
D: 地址参数
答案: 【 指针】

11、判断题：
‍线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。‏‍‏
选项：
A: 正确
B: 错误
答案: 【 错误】

12、判断题：
‍算法就是程序。​‍​
选项：
A: 正确
B: 错误
答案: 【 错误】

13、判断题：
‍在高级语言（如C或 PASCAL）中，指针类型是原子类型。‍‍‍
选项：
A: 正确
B: 错误
答案: 【 错误】

14、判断题：
‏算法的优劣与算法描述的语言无关。‎‏‎
选项：
A: 正确
B: 错误
答案: 【 正确】

15、判断题：
‎算法的可行性是指指令不能具有二义性‌‎‌
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
‌健壮的算法不会因为非法输入数据而出现莫名的执行结果‎‌‎
选项：
A: 正确
B: 错误
答案: 【 正确】

17、判断题：
‍高效率和低存储是算法设计的首要要求。​‍​
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
‏数据类型就是变量。‍‏‍
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
​数据结构的存储结构分为顺序存储和非顺序存储。‏​‏
选项：
A: 正确
B: 错误
答案: 【 正确】

20、判断题：
​数据结构的顺序存储优于非顺序存储。‌​‌
选项：
A: 正确
B: 错误
答案: 【 错误】

21、填空题：
‏变量的作用域是指   ‌
答案: 【 变量的有效范围】

22、填空题：
‌抽象数据类型具有数据抽象、    的特点。‍‌‍
答案: 【 信息隐蔽】

23、填空题：
‏一种抽象类型包括数据对象、     和基本操作。‌‏‌
答案: 【 结构关系】

24、填空题：
‏当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为____。‏
答案: 【 指针类型##%_YZPRLFH_%##指针参数##%_YZPRLFH_%##指针类型参数##%_YZPRLFH_%##指针】

25、填空题：
‎数据结构的逻辑结构分为集合结构  线性结构  树形结构 和____ 四种。‏
答案: 【 图结构##%_YZPRLFH_%##网状结构】

26、填空题：
‍数据结构的存储结构分为   和 链式存储结构两种。‏
答案: 【 顺序存储结构##%_YZPRLFH_%##顺序##%_YZPRLFH_%##顺序结构】

27、填空题：
‎在线性结构、树形结构和图结构中，数据元素之间分别存在着 ____、 一对多和多对多的联系。 ‌
答案: 【 一对一】

28、填空题：
​算法是规则的有限集合，是为解决特定问题而规定的     。‌
答案: 【 操作序列】

29、填空题：
‍算法具有有限性、可行性     、输入、输出五大特性。‌
答案: 【 确定性】

30、填空题：
如下程序段:for(i=1;i<=n-1;i++)‏             for(j=i+1;j<=n;j++) x=x+1;‏其中语句x=x+1执行的语句频度为        。‏‌‏
答案: 【 n(n-1)/2##%_YZPRLFH_%##​n*(n-1)/2】

数据结构的基础概念随堂测验

1、单选题：
​一个抽象类型包括数据对象、              和一组处理数据的操作。‏
选项：
A: 数据对象中各元素间的结构关系
B: 数据元素集
C: 接口
D: 数据对象集
答案: 【 数据对象中各元素间的结构关系】

2、填空题：
‏抽象数据类型具有             、信息隐蔽的特点。​‏​
答案: 【 数据抽象】

3、填空题：
‎一个抽象类型包括              、              和              。‏‎‏
答案: 【 数据对象、数据对象中各元素间的结构关系 一组处理数据的操作】

第2讲数据结构的内容随堂测验

1、判断题：
线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）​​​​​
选项：
A: 正确
B: 错误
答案: 【 错误】

2、填空题：
​1、数据结构的逻辑结构分为集合、线性、层次和         四种。‏​‏
答案: 【 网状】

3、填空题：
‎2、数据结构的存储结构分为              和非顺序 两种。​‎​
答案: 【 顺序】

4、填空题：
3、在线性结构、树形结构和图结构中，数据元素之间分别存在着一对一、一对多和          联系。‍‌‍
答案: 【 多对多】

第3讲数据结构与C语言表示随堂测验

1、单选题：
若需要利用形式参数直接访问修改实参值，则应将形参说明为           参数。‍              ‍​‍​‍
选项：
A: 同类型指针参数
B: 值参数
C: 无参数
D: 同类型变量参数
答案: 【 同类型指针参数】

2、判断题：
​在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ）‌
选项：
A: 正确
B: 错误
答案: 【 错误】

3、填空题：
​当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为        。‍
答案: 【 与实参同类型的指针变量参数】

第4讲算法性能评价随堂测验

1、单选题：
1、执行下面的程序段的时间复杂度为           。​for(int i=0;i<m;i++)​     for(int j=0;j<n;j++)​     a[i][j]=i*j;​‎​
选项：
A: O()     
B: O() 

C: O(m*n) 
D: O (m+n)
答案: 【 O(m*n) 】

2、单选题：
2、执行下面程序段时，语句S的执行次数为          。‏for(int i=0;i<=n;i++)‏  for(int j=0;j<i;j++)‏    S;‏‏‎‏
选项：
A:

B:
C: n(n+1)
D:

答案: 【 
】

第5讲算法与算法描述随堂测验

1、填空题：
​算法具有 有限性、确定性、              、输入、输出五大特性。‌​‌
答案: 【 可行性】

2、填空题：
‍算法设计的要求是：正确性、可读性 、                    和高效率和低存储  。‍
答案: 【 健壮性】

第1讲线性表的概念随堂测验

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

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

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

第2讲线性表的顺序存储随堂测验

1、单选题：
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（  ）(1<=i<=n+1)。‍‍‍‍‍
选项：
A: O(1)
B: O(n)
C: O(n*n)
D: O（）
答案: 【 O(n) 】

2、单选题：
若长度为n的线性表采用顺序存储结构，删除第i个位置的元素，需要移动的元素个数为（   ）。‏‍‏‍‏
选项：
A: i
B: n-i
C: n-i+1
D: n-i-1
答案: 【 n-i 】

第3讲随堂测验

1、单选题：
‍对一个长度为n的顺序表，假设在任何位置上插入一个元素的概率是相等的，那么插入一个元素时要移动表中的（   ）个元素。​‍​‍​‍​
选项：
A: n 
B: n+1
C:
D:
答案: 【 】

2、判断题：
‏线性表的顺序存储是指将表中元素按照从大到小或从小到大存储。​
选项：
A: 正确
B: 错误
答案: 【 错误】

第4讲线性表的链式存储随堂测验

1、判断题：
单链表中必须设有头结点。（）‌​‌
选项：
A: 正确
B: 错误
答案: 【 错误】

2、填空题：
‎通过表达式           可以获取带头结点的单链表L中首元素结点的数据值。‌
答案: 【 (L->next)->data】

第5讲单链表的基本运算随堂测验

1、单选题：
下列选项中，      项是链表不具有的特点。‌‌​‌
选项：
A: 插入和删除运算不需要移动元素
B: 所需要的存储空间与线性表的长度成正比
C: 不必事先估计存储空间大小
D: 可以随机访问表中的任意元素
答案: 【 可以随机访问表中的任意元素】

2、单选题：
有一个带头结点的单链表HEAD，则判断其是否为空链表的条件是                ‍‎‍‎‍
选项：
A: HEAD==NULL 
B: HEAD-〉NEXT==NULL
C: HEAD-〉NEXT==HEAD 
D: HEAD！=NULL
答案: 【 HEAD-〉NEXT==NULL】

3、填空题：
‌在带头结点的非空单链表中，头结点的存储位置由       指示。‎
答案: 【 头指针】

4、填空题：
在一个单链表中P所指结点后插入一个S所指结点时，‎应执行语句：              和 P->next=S。‎‌‎
答案: 【 S->next=P->next##%_YZPRLFH_%##s->next=p->next】

第6讲随堂测验

1、单选题：
设指针变量p指向单链表中结点A的直接前驱，若删除单链表中结点A，则需要修改指针的操作序列为（  ）。‍   ‍‌ ‍‌‍
选项：
A: q=p->next；p->next=q->next；free(q)；
B: q=p->next； p->next=q->next；
C: p->next=p-> next->next；
D: q=p->next；p->data=q->data；free(q)；
答案: 【 q=p->next；p->next=q->next；free(q)；】

2、判断题：
‍对链表进行插入和删除操作时不必移动链表中结点。(  )​
选项：
A: 正确
B: 错误
答案: 【 正确】

3、判断题：
‌在单链表中，可以从头结点开始查找到表中所有结点。（ ）‎
选项：
A: 正确
B: 错误
答案: 【 正确】

第二章第一次单元测验

1、单选题：
​在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，其算法时间复杂度为（  ）。‏
选项：
A: O(logn)(以2为底)
B: O(1)  
C: O(n)   
D: O(n*n)
答案: 【 O(n)   】

2、单选题：
​在长度为n的顺序表中的第i个位置上插入一个元素，需要移动的元素个数为（   ）。‍
选项：
A: n-i
B: i
C: n-i+1
D: n-i-1
答案: 【 n-i+1】

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

4、单选题：
‎在一单链表中，删除指针p所指的后继结点，以下语句正确的是（   ）。‍‎‍
选项：
A: p->next=p->next->next;  free(p->next);
B: free(p->next);p->next=p->next->next;
C:  p=p->next;
D: s=p->next;p->next=s->next;free(s);
答案: 【 s=p->next;p->next=s->next;free(s);】

5、单选题：
‌假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（  ）。‌‌‌
选项：
A: n
B: (n+1)/2
C: (n-1)/2
D: n/2
答案: 【 (n-1)/2】

6、单选题：
‌设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。‎
选项：
A: Base+(i-1)×m              
B: Base+i×m          
C: Base-i×m              
D: Base+(i+1)×m 
答案: 【 Base+(i-1)×m              】

7、单选题：
‏长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（  ）。‏
选项：
A: i>0    
B: 1≤i≤n+1 
C: 1≤i≤n-1
D: 0≤i≤n+1
答案: 【 1≤i≤n+1 】

8、判断题：
‏单链表中增加头结点的目的是存储链表的长度。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

9、判断题：
‎静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。​
选项：
A: 正确
B: 错误
答案: 【 错误】

10、判断题：
‌线性表在链式存储时，查找第i个元素的时间同i的值无关。​
选项：
A: 正确
B: 错误
答案: 【 错误】

11、判断题：
​线性表在顺序存储时，查找第i个元素的时间同i 的值成正比。‎
选项：
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、判断题：
‌顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。​
选项：
A: 正确
B: 错误
答案: 【 正确】

21、填空题：
‏若某线性表经常做插入、删除操作，易采用     结构存储。【请填 顺序 或 链式】‏
答案: 【 链式】

22、填空题：
‏在长度为n的顺序表中删除第i个位置上的元素，需要移动的元素个数为              。‎
答案: 【 n-i】

23、填空题：
‏非空单链表结点结构为【data,next】，指针p所指结点是尾结点的条件是          。‎
答案: 【 p-->next==NULL##%_YZPRLFH_%##p-->next= =NULL##%_YZPRLFH_%##p-->next为空】

24、填空题：
‎某顺序表的第一个元素的存储地址是500，每个元素占4个单元，则第8个元素的起始地址是     。‎
答案: 【 528】

25、填空题：
‍顺序表的存储密度     1。【请填大于、小于或等于】‍
答案: 【 等于】

26、填空题：
‌链表的存储密度      1。【请填大于、小于或等于】‎‌‎
答案: 【 小于】

总结与提高随堂测验

1、单选题：
某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用         存储方式时间性能最好。‏‏
选项：
A: 双向链表
B: 双向循环链表  
C: 单向循环链表
D: 顺序表
答案: 【 顺序表】

2、单选题：
已知一个带头结点的非空循环单链表，其尾指针是R，则其首元素结点的地址为：‎
选项：
A:  R->next     
B:  *( R->next->next ) 
C: &( R->next->next )
D:  R->next->next
答案: 【  R->next->next】

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

4、填空题：
​在带头结点的非空单链表中，头结点的存储位置由       指示‏
答案: 【 头指针】

第10讲链式结构小结--随堂检测

1、单选题：
已知单链表的头指针为head且该链表不带头结点，则该单链表为空的条件是    。‌‌
选项：
A: head== NULL
B: head->next==NULL
C: head->next==head
D: head!=NULL
答案: 【 head== NULL】

2、单选题：
设指针变量p指向单链表中结点A的直接前驱，若删除单链表中结点A，则需要修改指针的操作序列为              。‏  ‏‏‏
选项：
A:  q=p->next； p->next=q->next；free(q)；
B:  q=p->next； free(q)；
C:  p->next=p->next->next；free(p->next)；
D: q=p->next； free(q)；
答案: 【  q=p->next； p->next=q->next；free(q)；】

3、单选题：
设带有头结点的单向循环链表的头指针变量为head，则其判空条件是     。‏‍‏
选项：
A: head==NULL         
B: head->next==NULL
C: head->next==head
D: head!=NULL
答案: 【 head->next==head】

4、判断题：
‍在双向循环链表中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）‏
选项：
A: 正确
B: 错误
答案: 【 正确】

第12讲随堂测验

1、单选题：
下列选项中，      项是链表不具有的特点。‍‍
选项：
A: 插入和删除运算不需要移动元素
B: 所需要的存储空间与线性表的长度成正比
C: 不必事先估计存储空间大小
D: 可以随机访问表中的任意元素
答案: 【 可以随机访问表中的任意元素】

2、单选题：
在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用             存储方式最省时间？‍‍
选项：
A: 顺序表 
B: 带头指针的双向循环链表
C: 带头指针的单向循环链表
D: 带头指针的单向链表
答案: 【 顺序表 】

3、单选题：
下面关于线性表的叙述错误的是（   ）。‌‌‌‌
选项：
A:  线性表采用顺序存储必须占用一片连续的存储空间  
B: 线性表采用链式存储不必占用一片连续的存储空间
C: 线性表采用链式存储便于插入和删除操作的实现
D: 线性表采用顺序存储便于插入和删除操作的实现
答案: 【 线性表采用顺序存储便于插入和删除操作的实现】

第7讲循环链表随堂测验

1、单选题：
‏有一个带头结点的循环单链表HEAD，则判断其是否为空链表的条件是         。     ‎‏‎
选项：
A: HEAD==NULL  
B: HEAD-〉NEXT==NULL
C: HEAD-〉NEXT==HEAD 
D: HEAD！=NULL
答案: 【 HEAD-〉NEXT==HEAD 】

2、判断题：
‍在单向循环链表中，从表中任意结点出发都可以顺着next域访问到表中所有元素（）​
选项：
A: 正确
B: 错误
答案: 【 正确】

第8讲双向链表--随堂测验

1、单选题：
‎‍‎与单链表相比，双向链表的优点之一是           。‍‎‍‎‍‎‍
选项：
A: 插入删除操作更加方便　
B: 可以进行随机访问
C: 可以省略表头指针和表尾指针　
D: 访问前后相邻结点更方便。
答案: 【 访问前后相邻结点更方便。】

2、判断题：
​在双向链表中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）‏
选项：
A: 正确
B: 错误
答案: 【 错误】

第9讲静态链表--随堂测验

1、判断题：
‏静态链表中与动态链表的插入和删除运算类似，不需要做元素的移动。（）​
选项：
A: 正确
B: 错误
答案: 【 正确】

2、判断题：
​静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中第ｉ个元素的时间与位置序号ｉ无关，可以实现随机存取。（）‏
选项：
A: 正确
B: 错误
答案: 【 错误】

第二章第二次单元测试

1、单选题：
‌非空循环单链表L中，p指针指向尾结点，则以下表达式成立的是（  ）。‌
选项：
A: p->next==NULL
B: p==NULL
C: p->next==L
D: p==L
答案: 【 p->next==L】

2、单选题：
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（   ）存储方式最节省时间。‏
选项：
A: 顺序表    
B: 双向链表
C: 带头结点的双循环链表
D: 单循环链表
答案: 【 顺序表    】

3、单选题：
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（   ）存储方式最节省运算时间。 ‎
选项：
A: 单链表  
B: 仅有头指针的单循环链表 
C: 双链表
D: 仅有尾指针的单循环链表
答案: 【 仅有尾指针的单循环链表】

4、单选题：
‏对于双向循环链表，在两个结点之间插入一个新结点需修改的指针共（  ）个。‎
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 4】

5、单选题：
‍将带头指针的长度为m的单链表，链接到同样带都指针的长度为n的单链表末尾。该算法的时间复杂度为(   )。​
选项：
A: O(m)
B: O(n)
C: O(m+n)
D: O(m*n)
答案: 【 O(n)】

6、判断题：
‎静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

7、判断题：
‏循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。​
选项：
A: 正确
B: 错误
答案: 【 错误】

8、判断题：
‌静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

9、判断题：
‏静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

10、判断题：
‌线性表在顺序存储时，查找第i个元素的时间同i的值无关。‏
选项：
A: 正确
B: 错误
答案: 【 正确】

11、判断题：
‌线性表在顺序存储时，删除第i个元素的时间同i的值无关。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

12、判断题：
‍静态链表因为采用的是一段连续的空间来存储元素，因此查找第i个元素的时间和i无关。‎
选项：
A: 正确
B: 错误
答案: 【 错误】

13、填空题：
‏在双向循环链表的末尾插入一个元素，其时间复杂度为O(   )。‏
答案: 【 1】

14、填空题：
‎某双向链表中，结点结构为【prior,data,next】。那么删除p指针所指结点时，需要执行语句：p->next->prior=p->prior;                                 ; free(p);‍
答案: 【 p->prior->next=p->next】

15、填空题：
‏在某双向链表中删除一个结点，需要改动       个指针域​
答案: 【 2】

第1讲随堂测验

1、单选题：
 栈操作的特性是（ ）​‌​
选项：
A: FIFO
B: LIFO
C: FCFS
D: 插入和删除操作限制在表的两端进行
答案: 【 LIFO】

2、单选题：
‏栈中，允许进行插入和删除的一端称为（）‍
选项：
A: 栈顶
B: 栈底
C: 栈头
D: 栈尾
答案: 【 栈顶】

3、判断题：
栈是线性结构，是操作受限制的线性表。（）‌‏‌
选项：
A: 正确
B: 错误
答案: 【 正确】

第2讲随堂测验

1、多选题：
1、  已知顺序栈的地址为s,此时栈不满且栈顶指示器top指向真实栈顶,执行元素x进栈操作正确的语句是（ ）​​​​​​​​​​​
选项：
A: s->top++;s->elem[s->top]=x;
B: s->top= s->top+1;s->elem[s->top]=x;
C: s->elem[++s->top]=x;
D: s->elem[s->top]=x;s->top++;
答案: 【 s->top++;s->elem[s->top]=x;;
s->top= s->top+1;s->elem[s->top]=x;;
s->elem[++s->top]=x;】

2、多选题：
2、 已知顺序栈的地址为s ,此时栈不空且栈顶指示器top指向真实栈顶，执行出栈操作并将出栈元素赋值给x所指向的单元，则下列语句中，正确的是（ ）‏‍‏
选项：
A: s->top--; *x= s->elem[s->top];
B: *x= s->elem[s->top]; s->top= s->top-1;
C: *x =s->elem[s->top--];
D: *x= s->elem[s->top];s->top--;
答案: 【 *x= s->elem[s->top]; s->top= s->top-1;;
*x =s->elem[s->top--];;
*x= s->elem[s->top];s->top--;】

3、判断题：
1、  已知顺序栈的地址为s ,此时栈不空且栈顶指示器top指向真实栈顶，执行取栈顶操作的语句是‎*x= s->elem[s->top--];( )‎​‎
选项：
A: 正确
B: 错误
答案: 【 错误】

第3讲随堂测验

1、单选题：
​已知一个双端栈的地址为dS，则该双端栈不满时，，元素x进1号栈（高端栈）操作的语句是（）​​​​​​​​​​ ​​​
选项：
A: dS->stack[--dS->top[1]]=x;
B: dS->stack[dS->top[1]]=x;dS->top[1]--;
C: dS->top[1]--; dS->stack[dS->top[1]]=x;
D: dS->stack[++dS->top[1]]=x;
答案: 【 dS->top[1]--; dS->stack[dS->top[1]]=x;】

2、多选题：
‏已知一个双端栈dStack ,则判断该双端栈栈满的条件是（）‎‏ ‎‏‎‏‎‏‎‏‎‏ ‎‏‎
选项：
A: dStack.top[0]+1= = dStack.top[1]
B: dStack.top[0] = = dStack.top[1]
C: dStack.top[0]-1= = dStack.top[1]
D: dStack.top[0] = = dStack.top[1]-1
答案: 【 dStack.top[0]+1= = dStack.top[1];
dStack.top[0] = = dStack.top[1]-1】

3、判断题：
‏已知一个双端栈的地址为dS，则该双端栈不空时，1号栈（高端栈）出栈操作的语句是*x= dS->stack[dS->top[1]--]（）​‏​
选项：
A: 正确
B: 错误
答案: 【 错误】

第4讲随堂测验

1、单选题：
​已知带头结点的链栈top, 则该链栈不空时, 出栈操作的语句是( )‍​‍​‍​‍​‍
选项：
A: top->next=top->next->next; *x=top->next->data;
B: *x=top->next->data; top->next=top->next->next; free(top->next);
C: *x=top ->data;p=top;top =p->next;free(p);
D: *x=top->next->data;p=top->next;top->next=p->next;free(p);
答案: 【 *x=top->next->data;p=top->next;top->next=p->next;free(p);】

2、单选题：
‍已知带头结点的链栈top, 则该链栈为空的条件是( )‌‍‌‍‌‍‌‍‌‍‌
选项：
A: top==NULL
B: top->next= =NULL
C: top->next->next= =NULL
D: top->next= =top
答案: 【 top->next= =NULL】

3、单选题：
‍已知带头结点的链栈top, 则元素x对应的新结点s进栈操作的语句是（）‏‍‏‍‏‍‏‍‏
选项：
A: s->next=top->next;top->next=s;
B: top->next=s; s->next=top->next;
C: s->next=top;top =s;
D: top =s; s->next=top;
答案: 【 s->next=top->next;top->next=s;】

第5讲栈的应用

1、单选题：
‌在括号匹配算法中，当正扫描检测的符号是右括号，此时的栈是空栈，则（）。‏‌‏‌‏‌‏‌‏‌‏
选项：
A: 右括号进栈；
B: 继续向下扫描；
C: 取出栈顶元素做匹配检查；
D: 此时出现“右括号多了”的不匹配现象。
答案: 【 此时出现“右括号多了”的不匹配现象。】

2、单选题：
​在算术表达式求值的算法中，若当前正扫描的符号是运算符s，且s的优先级比运算符栈栈顶元素的优先级高，则（ ）​​​​​​​​​​​
选项：
A: 运算符栈出栈，运算数出栈，做运算；
B: s 进运算符栈；
C: 取运算符栈栈顶，运算数栈顶，做运算；
D: s 进运算数栈；
答案: 【 s 进运算符栈；】

3、填空题：
‏在括号匹配算法中，当正扫描的符号是左括号时，则该做左括号（ ）。​‏​
答案: 【 进栈】

第6讲随堂测验

1、多选题：
‌递归进层（i→i +1层）系统需要做三件事是（  ）‎‎‎
选项：
A: 保留本层参数与返回地址；
B: 保留下层参数和函数地址；
C: 为被调用函数的局部变量分配存储区，给下层参数赋值；
D: 将程序转移到被调函数的入口。
答案: 【 保留本层参数与返回地址；;
为被调用函数的局部变量分配存储区，给下层参数赋值；;
将程序转移到被调函数的入口。】

2、多选题：
‏从被调用函数返回调用函数之前，递归退层（i←i +1层）系统也应完成三件工作是（ ）‎‎
选项：
A: 保存被调函数的计算结果；
B: 释放被调函数的数据区，恢复上层参数；
C: 保存返回上层函数的地址；
D: 依照被调函数保存的返回地址，将控制转移回调用函数。
答案: 【 保存被调函数的计算结果；;
释放被调函数的数据区，恢复上层参数；;
依照被调函数保存的返回地址，将控制转移回调用函数。】

3、判断题：
‏递归是指在定义自身的同时又出现了对自身的引用。（ ）‍
选项：
A: 正确
B: 错误
答案: 【 正确】

4、填空题：
‎系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个（ ）。​‎​
答案: 【 工作记录】

第三章单元测验

1、单选题：
‌栈的特点是（     ）。​
选项：
A: 先进先出
B: 先进后出
C: 后进后出
D: 没有顺序
答案: 【 先进后出】

2、单选题：
‏队列的特点是（     ）。‎
选项：
A: 先进先出             
B: 先进后出  
C: 后进先出  
D: 没有顺序
答案: 【 先进先出             】

3、单选题：
‏栈之说以叫限定性线性表，是因为（  ）。​
选项：
A: 栈的操作位置受限制
B: 栈中的元素类型受限制 
C: 栈的应用范围受限制
D: 栈的存储结构受限制
答案: 【 栈的操作位置受限制】

4、单选题：
​输入序列为123，若进栈出栈可以交替进行，则不能可以得到的出栈序列是（   ）。‏
选项：
A: 321
B: 312
C: 123
D: 132
答案: 【 312】

5、单选题：
‍以下会用到栈的应用的是（   ）。‌
选项：
A: 递归
B: 子程序调用
C: 括号匹配
D: 其他选项均有可能
答案: 【 其他选项均有可能】

6、单选题：
‌循环队列存储在数组A[0..m-1]中，则入队时rear应该变化为（    ）​
选项：
A: rear++  
B: rear=(rear+1) mod (m-1)
C: rear=(rear+1) mod m       
D: rear=(rear+1) mod (m+1) 
答案: 【 rear=(rear+1) mod m       】

7、单选题：
​循环队列A[0..n-1]存放其元素值，用F和R分别表示队头和队尾，则当前队列中的元素数是(    )。‏​‏
选项：
A: (R-F+n)%n
B: R-F+1
C: R-F-1    
D: R-F
答案: 【 (R-F+n)%n】

8、单选题：
‏栈和队列的共同点是（    ）。‌
选项：
A: 都是先进先出
B: 都是先进后出
C: 只允许在端点处插入和删除元素
D: 它们没有共同点
答案: 【 只允许在端点处插入和删除元素】

9、单选题：
当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则每次向这个栈插入一个元素时，首先应执行（    ）语句修改top指针。‍‌‍
选项：
A: top++;
B: top--;
C: top=0;
D: top=n;
答案: 【 top--;】

10、单选题：
设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,e,f,c,a,g，则栈S的容量至少是（ )。‍‍‍
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 3】

11、单选题：
​以下属于递归求解问题的前提条件的是（    ）。​
选项：
A: 原问题可层层分解为子问题，且子问题比原问题规模小
B: 子问题的解法与原问题解法相同
C: 最小的子问题有解
D: 其他选项均是
答案: 【 其他选项均是】

12、单选题：
‏以下属于消除递归的主要原因是（  ）。‏
选项：
A: 递归程序不容易理解
B: 递归程序时空效率较差
C: 递归程序容易写错
D: 其他选项均是
答案: 【 递归程序时空效率较差】

13、单选题：
‎一个栈的输入序列为123……n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（    ）‍
选项：
A: i
B: n-i
C: n-i+1
D: 不确定
答案: 【 n-i+1】

14、判断题：
​消除递归肯定要用到栈，否则无法完成。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

15、判断题：
‏若输入序列为1234,则通过一个栈可以得到输出序列3124。‍
选项：
A: 正确
B: 错误
答案: 【 错误】

16、判断题：
‍若输入序列为1234,则通过栈只能得到4321的输出序列。‏‍‏
选项：
A: 正确
B: 错误
答案: 【 错误】

17、判断题：
‏有些问题，比如汉诺塔问题等，只能用递归来解，无法转换成非递归算法。‌
选项：
A: 正确
B: 错误
答案: 【 错误】

18、判断题：
‎顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

19、判断题：
​两顺序栈共享空间，也存在空间溢出问题。‎​‎