对应课程:点击查看
起止时间:2020-03-02到2020-06-12
更新状态:已完结
第一周 绪论 第一周 绪论 单元测验
1、 某算法的时间复杂度为
。若该算法在规模为n的数据集上，运行时间为10秒；如果数据规模扩大为2n，该算法大约需要运行（ ）。
A:10秒
B:100秒
C:6-7分钟
D:以上都不对
答案: 以上都不对
2、 以下函数中时间复杂度最小的是（ ）。
A:
B:
C:
D:
E:
F:
G:
答案:
;
3、 下列程序段的时间复杂度是（ ）。count=0;for (k=1;k<=n;k*=2) for (j=1;j<=n;j+1) count++;
A:
B:
C:
D:
答案:
4、 下列程序段的时间复杂度是（ ）。int k=0,j=0;while (j<=n) {
k++; j+=k;
}
A:
B:
C:
D:
E:
答案:
5、 下面的数据结构是（ ）。DS=(D,R)，其中D={a,b,c,d,e}，R={r}，r={ , , , }。注：“<>”表示有序对。
A:集合
B:线性结构
C:树形结构
D:图状结构
E:顺序存储结构
F:链式存储结构
答案: 图状结构
6、 下列关于算法的叙述正确的是（ ）。
A:算法的有穷性是指算法必须能在执行有限个步骤之后终止。
B:算法的时间复杂度与空间复杂度紧密相关。
C:算法的效率只与问题规模有关，而与数据的存储结构无关。
D:用不同算法求解同一问题的时间复杂度不同。
E:算法的优劣与算法描述语言无关，与所用计算机也无关。
F:算法原地工作的含义是指该算法不需要任何额外的辅助空间。
G:对于相同规模的n，时间复杂度O(n)的算法运行时间总是小于时间复杂度
的算法的运行时间。
H:所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
答案: 算法的有穷性是指算法必须能在执行有限个步骤之后终止。;
算法的优劣与算法描述语言无关，与所用计算机也无关。;
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。
7、 下列叙述正确的是（ ）。
A:数据元素是数据项中不可分割的最小可标识单位。
B:从逻辑上可以把数据结构分为顺序结构、链式结构等类别。
C:研究数据结构就是研究数据的逻辑结构和存储结构。
D:数据类型可看成是程序设计语言中已实现的数据结构。
E:数据元素之间的关联关系在数据的逻辑结构中体现。
F:数据对象是由有限个类型相同的数据元素构成的。
G:逻辑结构不相同的数据，必须采用不同类型的存储方法。
H:如果数据元素值发生改变，则数据的逻辑结构也随之改变。
I:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
答案: 数据类型可看成是程序设计语言中已实现的数据结构。;
数据元素之间的关联关系在数据的逻辑结构中体现。;
数据对象是由有限个类型相同的数据元素构成的。;
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
第三周 栈和队列 第三周 栈和队列 单元测验
1、 循环队列 Q 采用数组空间 Q.base[0,n-1] 存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是（ ）。
A:rear-front
B:rear-front+1
C:rear-front+n
D:(rear-front+n)%n
E:rear-front-1
F:(rear-front)%n
答案: (rear-front+n)%n
2、 已知操作符包括 “+”，“-”，“/”，“(” 和 “)”。将中缀表达式 a+b-a((c+d)/e-f)+g 转换为等价的后缀表达式ab+acd+e/f--g+后再计算表达式的结果，这时仅需用一个栈来存放参加运算的数据，在计算过程中，遇见数据进栈，遇见运算符号出栈计算，结果再进栈，若栈初始时为空，为计算该表达式值，该栈的的最大容量是( )。
A:4
B:5
C:7
D:8
答案: 4
3、 在宾馆的客房管理中，为了保证每间客房硬件设施的磨损率尽可能均等，可以利用（ ）这种数据结构来管理空闲的客房，以使得每间客房的使用率尽可能均等。
A:线性表
B:栈
C:队列
D:双端队列
答案: 队列
4、 下列链表中最不适合用作链栈的是（ ）。
A:只有表头指针没有表尾指针的双向循环链表。
B:只有表尾指针没有表头指针的双向循环链表。
C:只有表尾指针没有表头指针的单循环链表。
D:只有表头指针没有表尾指针的单循环链表。
答案: 只有表头指针没有表尾指针的单循环链表。
5、 以下方法中，（ ）不能区分循环队列的满与空。
A:牺牲一个存储单元
B:设置一个标志变量
C:判断头尾指针相等
D:使用一个计数器
答案: 判断头尾指针相等
6、 设进栈的字符序列为dcba，则哪一种是不可能的出栈序列( )
A:abcd
B:dcba
C:abdc
D:dcab
答案: abdc
7、 下列关于栈的叙述中，错误的是（ ）。
A:采用非递归方式重写递归程序是必须使用栈。
B:函数调用时，系统要用栈保存必要的信息。
C:只要确定了入栈次序，即可确定出栈次序。
D:栈是一种受限的线性表，允许在其两端进行操作。
E:消除递归不一定需要使用栈。
F:进栈和出栈操作的算法时间复杂度均为 O(n)。
G:两个栈共享一片连续的内存空间时，为了提高内存利用率、减少溢出，应当把两个栈的栈底分别设置在整篇内存空间的两端。
答案: 采用非递归方式重写递归程序是必须使用栈。;
只要确定了入栈次序，即可确定出栈次序。;
栈是一种受限的线性表，允许在其两端进行操作。;
进栈和出栈操作的算法时间复杂度均为 O(n)。
8、 下列关于循环队列的叙述中，正确的是（ ）。
A:循环队列不会产生假溢出。
B:循环队列也存在空间溢出问题。
C:循环队列比非循环队列节省空间。
D:循环队列一定优于非循环队列。
E:循环队列入队操作的复杂度比非循环队列高。
F:循环队列是一种顺序存储的线性结构。
答案: 循环队列不会产生假溢出。;
循环队列也存在空间溢出问题。;
循环队列是一种顺序存储的线性结构。
9、 银行柜台有2个服务窗口，客户可以在其中任意一个窗口排队办理业务，一旦开始排队，就不能够再进入到另一个队列中。客户x的业务办理完成后，银行系统会在今日流水记录的尾部新增一条流水记录 x。已知在某日银行开门营业后，依次有 a,b,c,d,e,f,g 共7位客户前来办理业务，且每人只办理一次。以下四个流水记录中，一定错误的是（ ）。
A:abcdefg
B:abdcfeg
C:abfcgde
D:gfedcba
E:adcbgef
F:afbgcde
G:dacbegf
H:eabdfcg
答案: gfedcba;
adcbgef;
dacbegf;
eabdfcg
10、 设计一个判别表达式中左、右括号是否匹配的算法，采用（ ）数据结构最佳。
答案: 栈
分析：早期的高级语言中，表达式中的括号有3种，大括号，中括号和小括号，因此上为了检测表达式中的括号匹配，必须用栈结构来完成，现在我们的表达式中只有圆括号，因此除了栈还可以通过设置一个计数器来完成。遇见左括号计数器+1，遇见右括号计数器减1，最后我们看计数器的值来判定是否匹配。
11、 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是多少？
答案: 3
分析：这个题目综合了栈和队列，栈先进后出，队列先进先出
第五周 数组和广义表 第五周 数组和广义表 单元测验
如需购买完整答案，请点击下方红字：
获取更多中国大学mooc慕课答案，请点击这里，进入mooc.mengmianren.com
京腑焚仙零蹈峡庞灿俺斥赁膜