数据结构与算法(江西财经大学)中国大学mooc慕课答案2024版100分完整版

汀钱龋报赦眷歉乓疥纺溜逼呻

对应课程:点击查看
起止时间:2020-02-17到2020-06-30
更新状态:已完结

第一章 概论 第一章 概论 测验

1、 下列不属于线性结构的是：Which one of the followings does not belong to linear structure:（There is only one correct answer）

A:队列(queue)
B:散列表(hash table)
C:向量(vector)
D:图(graph)
答案: 图(graph)

2、 以下哪种结构是逻辑结构，而与存储和运算无关：Which of the following structure is a logical structure regardless of the storage or algorithm:（There is only one correct answer）

A:队列(queue)
B:双链表(doubly linked list)
C:数组(array)
D:顺序表(Sequential list)
答案: 队列(queue)

3、 关于算法特性描述正确的有：Which one is right about algorithm’s characterization:（there are more than one correct answers）

A:算法保证计算结果的正确性。Algorithm will ensure the correctness of the calculation results.
B:组成算法的指令可以有限也可能无限。 Instructions which composite algorithms can be infinite or finite
C:算法描述中下一步执行的步骤不确定。 The next step in the implementation of the algorithm described is uncertain.
D:算法的有穷性指算法必须在有限步骤内结束。The finite nature of algorithms means algorithm must be completed within a limited step.
答案: 算法保证计算结果的正确性。Algorithm will ensure the correctness of the calculation results.;
算法的有穷性指算法必须在有限步骤内结束。The finite nature of algorithms means algorithm must be completed within a limited step.

4、 下列说法正确的是：Which options may be correct?（there are more than one 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) is O(g(n))，g(n) is O(h(n))，so f(n)+g(n) is O(h(n))
C:如果a>b>1,

是

，但

不一定是

if a>b>1,

is

，

may not be

D:函数f(n)是O(g(n))，当常数a足够大时，一定有函数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) is O(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(n) is O(h(n))

5、 已知一个数组a的长度为n，求问下面这段代码的时间复杂度: An array of 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;i
B:

C:

D:

答案:

;

6、 计算运行下列程序段后m的值：Calculate the value of m after running the following program segmentn = 9; m = 0; for (i=1;i<=n;i++) for (j = 2*i; j<=n; j++) m=m+1;求m的值
答案: 20
分析：注意i从1到9全部遍历，j分别从2，4，6,…开始遍历到9，当i大于5时，循环不再对m进行操作.
i=1结束循环时，m=8；
i=2结束循环时，m=8+6=14；
i=3结束循环时，m=14+4=18；
i=4结束循环时，m=18+2=20；

7、 由大到小写出以下时间复杂度的序列： 答案直接写标号，如：(1)(2)(3)(4)(5) （提示：系统基于字符匹配来判定答案，所以您的答案中不要出现空格）Write the following time complexity in descending sequence:Write down the answer labels such as (1)(2)(3)(4)(5). （Hint：This problem is judged by string matching, Please make sure your answer don’t contain any blanks. ）

答案: (5)(1)(2)(4)(3)
分析：计算复杂度时，系数是可以忽略的。(5)和(1)是指数级复杂度，大于(2)(3)(4)多项式级复杂度，区别在于指数中是否有n。而(5)的指数里还有指数级复杂度的表达式，(1)的指数是n，为多项式级，故(5)比(1)复杂。对于(2)(3)(4)，(2)的指数最大，为2.5，(4)的指数居中，为2，(3)的指数最小，解释如下：logn的任意实数次方的复杂度都小于n，故(logn)^4比n复杂度低，故n(logn)^4比nn复杂度低，故(4)比(3)复杂，故答案为(5)(1)(2)(4)(3)

第二章 线性表 第二章 线性表测验

1、 下面关于线性表的叙述中，正确的是哪些？Which of the followings about linear list are correct?（There are more than one answers.）Select the answer that matches

A:线性表采用顺序存储，必须占用一片连续的存储单元。Linear lists use sequential storage which must occupy a continuous memory units.
B:线性表采用顺序存储，便于进行插入和删除操作。Linear lists using sequential storage, it is easy to do insert and delete operations.
C:线性表采用链接存储，不必占用一片连续的存储单元。Linear lists using the linked storage, do not occupy a continuous memory units.
D:线性表采用链接存储，便于插入和删除操作。Linear lists using the linked storage, it is easy for insert and deleting operations.
答案: 线性表采用顺序存储，必须占用一片连续的存储单元。Linear lists use sequential storage which must occupy a continuous memory units.;
线性表采用链接存储，不必占用一片连续的存储单元。Linear lists using the linked storage, do not occupy 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 more than one correct answers）

A:线性表在链式存储时，查找第i个元素的时间与i的数值无关。When the linear list stored in linked form, the time to find the i-th element is regardless of the value of i.
B:线性表在顺序存储时，查找第i个元素的时间与i的数值成正比。When the linear list stored sequentially, the time to find the i-th element is proportional to value with i.
C:线性表在顺序存储时，查找第i个元素的时间与i的数值无关。When the linear list stored sequentially, the time to find the i-th element is regardless of the value of i.
D:线性表在链式存储时，插入第i个元素的时间与i的数值成正比。When linear lists stored in the linked form, the time to insert the i-th element is proportional to value with i.
答案: 线性表在顺序存储时，查找第i个元素的时间与i的数值无关。When the linear list stored sequentially, the time to find the i-th element is regardless of the value of i.;
线性表在链式存储时，插入第i个元素的时间与i的数值成正比。When linear lists stored in the linked form, the time to insert the i-th element is proportional to value with i.

3、 完成在双循环链表结点p之后插入s的操作为：The operation to insert s after the doubly circular linked list’s 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; 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 linked list with n nodes, and after a known node p to insert a new node, the time complexity is O (); 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 by string matching, Please make sure your answer don’t contain any blanks. )
答案: (1)(n)
分析：已知结点后插入，不需要移动其他结点位置，所以为O(1) 2. 先要查找到值为x的结点，需要O(n),再插入，不需要移动其他结点位置，需要O(1)，总共需要O(n)+O(1)=O(n)

5、 带头结点head的循环链表的尾结点tail的特点是: _
（提示： 1.请使用“=” 2.系统基于字符匹配来判定答案，所以您的答案中不要出现空格）The circular linked list with a head node, its tail node’s character is: ___.(Hint:1. Please use “=” 2.This problem is judged by string matching, Please make sure your answer don’t contain any blanks. )
答案: tail->next=head
分析：循环链表尾结点的next会指向头结点

第三章 栈与队列 第三章 栈与队列测验

1、 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是___。Assume that the stack S and queue Q’s initial state is empty, the elements e1, e2, e3, e4, e5 and e6 followed through stack 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:2
B:3
C:4
D:6
答案: 3

2、 现有中缀表达式E=((100-4)/3+3(36-7))2。以下哪个是与E等价的后缀表达式？Existing infix expression E = ((100-4) / 3 + 3 * (36-7)) * 2. Which of the following is the equivalent postfix expression of E? （There is only one correct answer）

苏碎涡怠江疼门平汗妒史亥惕