2020 数据结构–刘浩(桂林理工大学博文管理学院) 最新满分章节测试答案

文章目录[隐藏]

【作业】第1周：绪论（时长：56分11秒）第1周作业
第4周：栈和队列（时长：1小时4分4秒）第4周测验

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-03-02到2020-06-17
本篇答案更新状态:已完结

【作业】第1周：绪论（时长：56分11秒）第1周作业

1、问题:有以下用C/C++语言描述的算法，说明其功能：void fun(double &y,double x,int n){ y=x; while (n>1) { y=y*x; n–; }}
评分规则: 【参考答案：本算法的功能是计算y=。
】

2、问题:一个算法的空间复杂度是O(1)，那么执行该算法时不需要任何空间，这个说法正确吗？为什么？
评分规则: 【参考答案：这个说法是错误的。一个算法的空间复杂度是O(1)只是表明执行该算法时所需临时分配的空间大小是个常量，与问题规模无关，并不是不需要任何空间。回答是正确的，给0分。
】

3、问题:一个算法的执行频度为，其时间复杂度多少？
评分规则: 【参考答案：当n足够大时，T(n)®3n/10=0.3n，其时间复杂度为O(n)
】

4、问题:设有算法如下：int Find(int a[], int n, int x){ int i; for (i=0;i 参考答案1：在最好情况下，a[0]=x，比较1次，所以最好时间复杂度为O(1)。
参考答案2：在最坏情况下，a[n-1]=x，比较n次，所以最坏时间复杂度为O(n)。
】

第4周：栈和队列（时长：1小时4分4秒）第4周测验

1、问题:栈的“先进后出”特性是指（）。
选项：
A:最后进栈的元素总是最先出栈
B:同时进行进栈和出栈操作时，总是进栈优先
C:每当有出栈操作时，总要先进行一次进栈操作
D:每次出栈的元素总是最先进栈的元素
答案: 【最后进栈的元素总是最先出栈】

2、问题:给定一个足够大的空栈，有4个元素的进栈次序为A、B、C、D，则以C、D开头的出栈序列的个数为（）。
选项：
A:1
B:2
C:3
D:4
答案: 【1】

3、问题:若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是（）。
选项：
A:dcebfa
B:cbdaef
C:bcaefd
D:afedcb
答案: 【afedcb】

4、问题:一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。
选项：
A:edcba
B:decba
C:dceab
D:abcde
答案: 【dceab】

5、问题:当用一个数组data[0..n-1]存放栈中元素时，栈底最好（）。
选项：
A:设置在data[0]处
B:设置在data[n-1]处
C:设置在data[0]或data[n-1]处
D:设置在data数组的任何位置
答案: 【设置在data[0]或data[n-1]处】

6、问题:若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是（）。
选项：
A:top++; data[top]=x;
B:data[top]=x; top++;
C:top–; data[top]=x;
D:data[top]=x; top–;
答案: 【top–; data[top]=x;】

7、问题:若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进栈的正确操作是（）。
选项：
A:top++; data[top]=x;
B:data[top]=x; top++;
C:top–; data[top]=x;
D:data[top]=x; top–;