MOOC 数据结构与算法(东莞市教育局)1205988810 最新慕课完整章节测试答案
第一章 概论
文章目录
第一章 概论 测验
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<n-1;i++){ for (j = i+1;j<n && a[j-1]<=a[j];j++) if(length<j-i+1) length=j-i+1;}
选项：
A: 
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】
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)】
第二章 线性表
第二章 线性表测验
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 insert 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)】
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】
第三章 栈与队列
第三章 栈与队列测验
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）
选项：
A: ( ( 100 4 – ) 3 / 3 ( 36 7 – ) * + ) 2 *
B: * + / – 100 4 3 * 3 – 36 7 2
C: 100 4 – 3 / 3 36 7 – * + 2 *
D: * ( + / ( – 100 4 ) 3 * 3 ( – 36 7 ) ) 2
答案: 【 100 4 – 3 / 3 36 7 – * + 2 *】
3、多选题：
队列的特点包括：Queue’ features include:（There are more than one answers.）
选项：
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)】
4、多选题：
以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有:In the following realizing ways of circular queue, the queue whose length is n can also contain the number of n elements is:（There are more than one answers.）
选项：
A: 只用front和rear两个指针标记队列的头和尾，两个指针均为实指Only use front and rear as the queue’s head and tail pointers and the two pointers are actually referring to.
B: 用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数With the queue’s head and tail pointers marked as front and rear, use the integer variable len to record the number of elements.
C: 用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空With the queue’s head and tail pointers marked as front and rear, use Boolean variable empty record whether the queue is empty.
D: 只用front和rear两个指针标记队列的头和尾，两个指针均为虚指Only use front and rear as the queue’s head and tail pointers and the two pointers are virtually referring to.
答案: 【 用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数With the queue’s head and tail pointers marked as front and rear, use the integer variable len to record the number of elements.;
用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空With the queue’s head and tail pointers marked as front and rear, use Boolean variable empty record whether the queue is empty.】
5、填空题：
编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；则开出车站的顺序有______种可能。 注释：例如 1, 2, 3, 4 或 4, 3, 2，1 就是其中两种可能出站序列；而 4, 3, 1, 2 是 非法序列。Numbered 1,2,3,4 four trains, orderly entered a stack structure station. How many possible leaving sequences of that four trains ? ______ . Note: For instance, the leaving sequence could be 1,2,3,4 or 4,3,2,1 these two possibilities, but 4, 3, 1, 2 is not a possible sequence.
答案: 【 14】
6、填空题：
双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_____种不同的排列。double-ended queue can insert and delete operations on both ends of the queue. That it can insert / delete at its tail, but also at the head. Existing 4 different elements sequentially input to the double-ended queue, you can get _____ different permutations.
答案: 【 8】
第四章 字符串
第四章 字符串测验
1、单选题：
设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )（单选）There are two strings p q, q is p’s substring. The algorithm to search the first time q appeared in p is called ( )（There is only one correct answer）
选项：
A: 求子串 Seeking substring
B: 联接 Concatenation
C: 匹配 Matching
D: 求串长 Seeking length
答案: 【 匹配 Matching】
2、单选题：
下列说法正确的是：（单选） Which of the following statements is correct? （There is only one correct answer）
选项：
A: 空串就是空白串“Empty string” is blank string.
B: 空串是任意字符串的子串 Empty string is a substring of arbitrary string.
C: 串只可以采用顺序存储，不可以采用链式存储 String only can be stored in sequential method and cannot be stored in linked method.
D: 在C++标准中，char S[M]最多能表示长度为M的字符串 In C ++ standards, char S[M] can represent up to a string of length M.
答案: 【 空串是任意字符串的子串 Empty string is a substring of arbitrary string.】
3、单选题：
若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))注意：substr(S,i,j)是对字符串S的下标为i开始取j个字符，这里的下标是从0开始的(单选)If the string S1 = 'ABCDEFG', S2 = '9898', S3 = '###', S4 = '012345', execute concat (replace (S1, substr (S1, length (S2), length (S3)), S3), substr (S4, index (S2, '8'), length (S2))) Note substr (S, i, j) is the operation to take string S’s j characters from subscript i. Subscript here is starting from 0.（There is only one correct answer）
选项：
A: ABC###G0123
B: ABCD###2345
C: ABCD###1234
D: ABC###G2345
答案: 【 ABCD###1234】
4、单选题：
下面关于串的的叙述中，哪一个是不正确的:（单选） Which of the following descriptions about string is not correct? （There is only one correct answer）
选项：
A: 串是字符的有限序列 String is a finite sequence of characters.
B: 模式匹配是串的一种重要运算 Pattern matching is an important operation.
C: 串是一种数据对象和操作都特殊的线性表 String is a linear list whose data objects and operations both special
D: 空串是由空格构成的串 Empty string is a string consisting of spaces.
答案: 【 空串是由空格构成的串 Empty string is a string consisting of spaces.】
5、单选题：
Seek the string "BAAABBBAA" ‘s feature vector, where the feature vector is defined as follows:（There is only one correct answer）
选项：
A: {-1, 0, 0, 0, 0, 0, 0, 1, 2}
B: {-1, 0, 0, 0, 0, 1, 1, 1, 2}
C: {-1, 0, 0, 0, 0, 0, 1, 1, 2}
D: {-1, 0, 0, 0, 1, 1, 1, 1, 2}
答案: 【 {-1, 0, 0, 0, 0, 1, 1, 1, 2}】
6、多选题：
在字符{A, C, G, T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。下面DNA序列中存在互补回文串的是：（多选）In the DNA sequences consisting of character {A, C, G, T}, A and T, C and G are complementary pairs. Judging whether there is a complementary palindrome sequence in a DNA sequence (e.g., ATCATGAT’s complement strings is TAGTACTA, it is complementary palindrome sequence with the original sequence). Which of the following DNA sequences have complementary palindrome string? （There are more than one answers.）
选项：
A: CTGATCAG
B: AATTAATT
C: TGCAACGT
D: CATGGTAC
E: GTACGTAC
F: AGCTAGCT
答案: 【 CTGATCAG;
AATTAATT;
GTACGTAC;
AGCTAGCT】
7、填空题：
若字符串s=“software”，则其子串个数为： If the string s = "software", then the number of its sub-string is:
答案: 【 37】
8、填空题：
若字符串s=”algorithm”，则其子串个数为： If the string s = "algorithm", then the number of its sub-string is:
答案: 【 46】
9、填空题：
设有字符串变量String A ＝“”，B＝“MULE”，C＝“OLD”，D＝“MY” ; 请计算下列表达式 （3个答案本身不要出现空格，答案之间用空格分开） Assume that there is a string variable String A = "", B = "MULE", C = "OLD", D = "MY"; Please calculate the following expression: (1) D+C+B(2) B.substr(3，2) (3) A.strlength()
答案: 【 MYOLDMULE E 0】
10、填空题：
一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：
A text string can be encrypted by the given letters mapping table. For example, the letters mapping table is:
比如字符串"encrypt"被加密为"tkzwsdf"。则字符串 “algorithm”，被加密为________________（Hint： 1. 答案不需要加引号 2. 系统基于字符匹配来判定答案，所以您的答案中不要出现空格）。
As the string "encrypt" is encrypted as "tkzwsdf", then the "algorithm" is encrypted as ________ (Hint：1. please don’t include any quotes in your answer 2. This problem is judged by string matching, Please make sure your answer don't contain any blanks.).
答案: 【 neopwmfbl】
11、填空题：
S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。S = "S1S2 ... Sn" is a string of length n, and stored in an array, output S after its programmable transformation.
1.将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分； 1.All the even-numbered characters of S should be placed in accordance with their subscript descending order in the second half of S;2.将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；2.All the odd-numbered characters of S should be placed in accordance with their subscript ascending order in the first half of S.例如：S=‘ABCDEFGHIJKL’，则改造后的S为‘ACEGIKLJHFDB’。则 S=’algorithm’, 改造后为____________（Hint： 1. 答案不需要加引号 2. 系统基于字符匹配来判定答案，所以您的答案中不要出现空格）。For example: S = 'ABCDEFGHIJKL', then after the transformation S is 'ACEGIKLJHFDB'. If S = 'algorithm', then after the transformation S is ____________ (Hint:1. please don’t include any quotes in your answer. 2.This problem is judged by string matching, Please make sure your answer don't contain any blanks ).
答案: 【 agrtmhiol】
12、填空题：
下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；
Use the following procedures to determine whether the string s is symmetry, symmetry returns 1, otherwise return 0; such as f ("abab") returns 0;
注：(1)和(2)和(3)三个答案之间用空格分隔，每个答案是一个字符,不要加空格
答案: 【 j i j】
13、填空题：
上一题中的字符串"BAAABBBAA"，与目标"BAAABBBCDDDCCHHHHBBBAAABBBAADD"进行匹配，至少需要多少次字符匹配（提示：利用优化后的Next数组):
The string in question above "BAAABBBAA" matches with "BAAABBBCDDDCCHHHHBBBAAABBBAADD". How many times character matching will need at least? (Hint: Use “Next” arrays ):
答案: 【 31】
第五章 二叉树
第五章 二叉树前半部分（5.1~5.4）测验
1、多选题：
下列关于二叉树性质的说法正确的有：（多选）Which sentences of the followings are right about a binary tree's characterization:（There are more than one correct answers）
选项：
A: 非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.
B: 非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。Sequential storing structure can also be used to store an incomplete binary tree just like to store a complete binary tree.
C: 当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.
D: 完全二叉树最多只有最下面的一层结点度数可以小于2。For a complete binary tree, only the degrees of nodes on the nethermost layer could be less than 2.
E: 一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.
F: 满二叉树的所有结点的度均为2。All degrees of nodes in a full binary tree are 2.
答案: 【 非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.;
当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.;
一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.】
2、多选题：
下列关于二叉树遍历的说法正确的有:Which sentences of the followings are right about traversal of a binary tree:
选项：
A: 前序和中序遍历的顺序恰好一样的二叉树，只能是空二叉树或者独根二叉树这两种情况。Only the sequences of preorder and infix order of the binary tree with no nodes or only one