MOOC 数据结构与算法-北京大学 中国大学慕课答案.docx
《MOOC 数据结构与算法-北京大学 中国大学慕课答案.docx》由会员分享,可在线阅读,更多相关《MOOC 数据结构与算法-北京大学 中国大学慕课答案.docx(29页珍藏版)》请在文库网上搜索。
1、 MOOC 数据结构与算法-北京大学 中国大学慕课答案第一章 概论 测验1、问题:下列不属于线性结构的是:Which one of the followings does not belong tolinear structure:(There is only one correct answer)选项:A、队列(queue)B、散列表(hash table)C、向量(vector)D、图(graph)正确答案:【图(graph)】2、问题:以下哪种结构是逻辑结构,而与存储和运算无关:Which of the followingstructure is a logical structure
2、regardless of the storage or algorithm:(There is only onecorrect answer)选项:A、队列(queue)B、双链表(doubly linked list)C、数组(array)D、顺序表(Sequential list)正确答案:【队列(queue)】3、问题:关于算法特性描述正确的有:Which one is right about algorithmscharacterization:(there are more than one correct answers)选项:A、算法保证计算结果的正确性。Algorithm w
3、ill ensure the correctness of thecalculation results.B、组成算法的指令可以有限也可能无限。 Instructions which composite algorithmscan be infinite or finiteC、算法描述中下一步执行的步骤不确定。 The next step in the implementation of thealgorithm described is uncertain.D、算法的有穷性指算法必须在有限步骤内结束。The finite nature of algorithmsmeans algorithm
4、 must be completed within a limited step.正确答案:【算法保证计算结果的正确性。Algorithm will ensure the correctness of thecalculation results.#算法的有穷性指算法必须在有限步骤内结束。The finite nature ofalgorithms means algorithm must be completed within a limited step.】4、问题:下列说法正确的是:Which options may be correct?(there are more thanone
5、correct answers)选项:A、如果函数 f(n)是 O(g(n),g(n)是 O(h(n),那么 f(n)是 O(h(n)【 if f(n) is O(g(n) ,g(n) is O(h(n),then f(n) is O(h(n)】B、如果函数 f(n)是 O(g(n),g(n)是 O(h(n),那么 f(n)+g(n)是 O(h(n)【if f(n) isO(g(n),g(n) is O(h(n),so f(n)+g(n) is O(h(n)】C、如果 ab1,是,但不一定是【if ab1, is , may not be 】D、函数 f(n)是 O(g(n),当常数 a 足够
6、大时,一定有函数 g(n)是 O(af(n)【if f(n)是O(g(n),When constant a is big enough ,there must be g(n) is O(af(n)】正确答案:【如果函数 f(n)是 O(g(n),g(n)是 O(h(n),那么 f(n)是 O(h(n)【 if f(n) isO(g(n),g(n) is O(h(n),then f(n) is O(h(n)】#如果函数 f(n)是 O(g(n),g(n)是O(h(n),那么 f(n)+g(n)是 O(h(n)【if f(n) is O(g(n),g(n) is O(h(n),so f(n)+g(
7、n) isO(h(n)】5、问题:已知一个数组 a 的长度为 n,求问下面这段代码的时间复杂度:An arrayof a, its length is known as n. Please answer the time complexity of the following code.(There are more than one answers.)for (i=0,length=1;in-1;i+) for (j = i+1;jn aj-1=aj;j+) if(lengthj-i+1) length=j-i+1;选项:A、B、C、D、正确答案:【#】6、填空题:计算运行下列程序段后 m
8、的值:Calculate the value of m after runningthe following program segmentn = 9; m = 0;for (i=1;i=n;i+) for (j = 2*i; j=n; j+)m=m+1;求 m 的值正确答案:【20】7、填空题:由大到小写出以下时间复杂度的序列: 答案直接写标号,如:(1)(2)(3)(4)(5) (提示:系统基于字符匹配来判定答案,所以您的答案中不要出现空格)Write the following time complexity in descending sequence:Write down thean
9、swer labels such as (1)(2)(3)(4)(5). (Hint:This problem is judged by stringmatching, Please make sure your answer dont contain any blanks. ) 正确答案:【(5)(1)(2)(4)(3)】第二章 线性表测验1、问题:下面关于线性表的叙述中,正确的是哪些?Which of the followings aboutlinear list are correct?(There are more than one answers.)Select the answer
10、 thatmatches选项:A、线性表采用顺序存储,必须占用一片连续的存储单元。Linear lists usesequential storage which must occupy a continuous memory units.B、线性表采用顺序存储,便于进行插入和删除操作。Linear lists using sequentialstorage, it is easy to do insert and delete operations.C、线性表采用链接存储,不必占用一片连续的存储单元。Linear lists using thelinked storage, do not o
11、ccupy a continuous memory units.D、线性表采用链接存储,便于插入和删除操作。Linear lists using the linkedstorage, it is easy for insert and deleting operations.正确答案:【线性表采用顺序存储,必须占用一片连续的存储单元。Linear lists usesequential storage which must occupy a continuous memory units.#线性表采用链接存储,不必占用一片连续的存储单元。Linear lists using the linke
12、d storage, do notoccupy a continuous memory units.#线性表采用链接存储,便于插入和删除操作。Linear lists using the linked storage, it is easy for insert and deleting operations.】2、问题:下面的叙述中正确的是:Select the answer that matches (There are morethan one correct answers)选项:A、线性表在链式存储时,查找第 i 个元素的时间与 i 的数值无关。When the linearlist
13、 stored in linked form, the time to find the i-th element is regardless of the value of i.B、线性表在顺序存储时,查找第 i 个元素的时间与 i 的数值成正比。When thelinear list stored sequentially, the time to find the i-th element is proportional to valuewith i. C、线性表在顺序存储时,查找第 i 个元素的时间与 i 的数值无关。When the linearlist stored sequent
14、ially, the time to find the i-th element is regardless of the value of i.D、线性表在链式存储时,插入第 i 个元素的时间与 i 的数值成正比。When linearlists stored in the linked form, the time to insert the i-th element is proportional to valuewith i.正确答案:【线性表在顺序存储时,查找第 i 个元素的时间与 i 的数值无关。Whenthe linear list stored sequentially, th
15、e time to find the i-th element is regardless of thevalue of i.#线性表在链式存储时,插入第 i 个元素的时间与 i 的数值成正比。Whenlinear lists stored in the linked form, the time to insert the i-th element is proportional tovalue with i.】3、问题:完成在双循环链表结点 p 之后插入 s 的操作为:The operation to insert safter the doubly circular linked lis
16、ts node p is: (There are more than one answers.)选项:A、p-next-prev=s; s-prev=p; s-next=p-next; p-next=s;B、p-next-prev=s; p-next=s; s-prev=p; s-next=p-next;C、s-prev=p; s-next=p-next; p-next=s; p-next-prev=s;D、s-next=p-next; p-next-prev=s; s-prev=p; p-next=s;正确答案:【p-next-prev=s; s-prev=p; s-next=p-next;
17、 p-next=s;#s-next=p-next; p-next-prev=s; s-prev=p; p-next=s;】4、填空题:对于一个具有 n 个结点的单链表,在已知的结点*p 后插入一个新结点的时间复杂度为 O(_),在给定值为 x 的结点后插入一个新结点的时间复杂度为O(_)。(请依次填入,格式为(a)(b),如果您的答案中出现字母,请使用小写;后一空系统基于字符匹配来判定答案,所以您的答案中不要出现空格)For a single linkedlist with n nodes, and after a known node *p to insert a new node, the
18、 time complexity isO (_); after a given node with x value insert a new node, the time complexity is O(_). (If your answer contains letters, use lowercase one.The second blank is judged bystring matching, Please make sure your answer dont contain any blanks. )正确答案:【(1)(n)】5、填空题:设某循环链表长度为 n,并设其中一节点为 p
19、1,然后按照链表的顺序将后面的节点依次命名为 p2,p3,.,pn,那么请问 pn.next=_(答案为一个节点名,注意所有字母为小写且答案中不包含空格)正确答案:【p1】第三章 栈与队列测验1、问题:设栈 S 和队列 Q 的初始状态为空,元素 e1,e2,e3,e4,e5 和 e6 依次通过栈 S,一个元素出栈后即进队列 Q,若 6 个元素出队的序列是 e2,e4,e3,e6,e5,e1 则栈 S 的容量至少应该是_。Assume that the stack S andqueue Qs initial state is empty, the elements e1, e2, e3, e4,
20、 e5 and e6 followed throughstack S, an element out the stack means into the queue Q. If the sequence the six elements out of the queue is e2, e4, e3, e6, e5, e1 then stack S of capacity should be at least_. (There is only one correct answer)选项:A、2B、3C、4D、6正确答案:【3】2、问题:现有中缀表达式 E=(100-4)/3+3*(36-7)*2。
21、以下哪个是与 E 等价的后缀表达式?Existing infix expression E = (100-4) / 3 + 3 * (36-7) * 2. Which of thefollowing is the equivalent postfix expression of E? (There is only one correct answer)选项:A、( ( 100 4 ) 3 / 3 ( 36 7 ) * + ) 2 *B、* + / 100 4 3 * 3 36 7 2C、100 4 3 / 3 36 7 * + 2 *D、* ( + / ( 100 4 ) 3 * 3 ( 36
22、 7 ) ) 2正确答案:【100 4 3 / 3 36 7 * + 2 *】3、问题:队列的特点包括:Queue features include:(There are more than oneanswers.)选项:A、后进先出 Last-in first-out (LIFO)B、先进后出 First-in last-out (FILO)C、先进先出 First-in first-out (FIFO)D、后进后出 Last-in last-out (LILO)正确答案:【先进先出 First-in first-out (FIFO)#后进后出 Last-in last-out (LILO)
23、】4、问题:以下循环队列的实现方式中,长度为 n 的队列,所能容纳的元素个数也为 n 的有:In the following realizing ways of circular queue, the queue whose length is ncan also contain the number of n elements is:(There are more than one answers.)选项:A、只用 front 和 rear 两个指针标记队列的头和尾,两个指针均为实指 Only usefront and rear as the queues head and tail poi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- MOOC 中国大学慕课答案