数据结构与算法(北京大学) 中国大学MOOC答案2024版100分完整版

 存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。There exists a binary tree with at least one node, whose preorder, infix order and post order are all the same.

3、 一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1)What is the height of a complete binary tree with 510 nodes? (the height of a tree with only a root is 1)
答案: 9

4、 一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）What is the height of a complete binary tree with 512 nodes? (the height of a tree with only a root is 1)
答案: 10

5、 在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=_ (系统根据字符串匹配来判定答案，所以您的答案中请不要包含空格) For a binary tree with at least one node, if there are n nodes with degree 0 and m nodes with degree 2, then n = _（This problem is judged by string matching, Please make sure your answer don’t contain any blanks.）
答案: m+1

6、 已知一棵树的前序遍历为ABDEGCF，中序遍历为DBGEACF，求这棵树的后序遍历。（字母和字母之间不要有空格）The preorder sequence of a tree is ABDEGCF, and its infix order sequence is DBGEACF, please write down its post order sequence. (There is no blank space between letters)
答案: DGEBFCA

7、 已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。（字母和字母之间不要有空格）The infix order sequence of a tree is DBGEACF, and its post order sequence is DGEBFCA, please write down its preorder sequence. (There is no blank space between letters)
答案: ABDEGCF

8、 请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）
Please write down the preorder sequence of the following binary tree. (There is no blank space between letters)
答案: BEXLMKCPDHQA

9、 请写出下面这棵二叉树的中序遍历（字母和字母之间不要有空格）
Please write down the infix order sequence of the following binary tree. (There is no blank space between letters)
答案: LXMECKPBQHDA

10、 请写出下面这棵二叉树的后序遍历（字母和字母之间不要有空格）
Please write down the post order sequence of the following binary tree. (There is no blank space between letters)
答案: LMXCPKEQHADB

第五章 二叉树 第五章 二叉树后半部分（5.5~5.7）测验

1、 下列关于二叉搜索树的说法正确的有Which sentences of the followings are right about binary search tree:

A:二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。If we print a binary search tree’s nodes according its infix order, the sequence will be from small to large.
B:如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在$$x$$的左子树之中。If the left child tree of a node x has a right child tree, then there exists some node whose value is between the value of node x and the value of its left child node, and this node is on the left child tree of node x.
C:当根结点没有左儿子时，根结点一定是值最小的结点。If the root node doesn’t have left child, it must be the node with the smallest value.
D: 二叉搜索树一定是满二叉树。A binary search tree must be a full binary tree.
E:二叉搜索树一定是完全二叉树。A binary search tree must be a complete binary tree.
F: 从根结点一直沿右儿子向下找不一定能找到树中值最大的结点。Along the right child of nodes all the time from the root node, it is possible that we couldn’t find out the node with the largest value.
答案: 二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。If we print a binary search tree’s nodes according its infix order, the sequence will be from small to large.;
如果结点χ的左子树有右子树，则存在某个结点的值介于结点χ的值和χ左儿子的值之间，并且这个结点在$$x$$的左子树之中。If the left child tree of a node x has a right child tree, then there exists some node whose value is between the value of node x and the value of its left child node, and this node is on the left child tree of node x.;
当根结点没有左儿子时，根结点一定是值最小的结点。If the root node doesn’t have left child, it must be the node with the smallest value.

2、 下列关于堆的说法正确的有: Which sentences of the followings are right:

A:堆一定是满二叉树。A heap must be a full binary tree.
B:最小堆中，最下面一层最靠右的结点一定是权值最大的结点。In a minimum heap, the rightest node on the nethermost layer must be the node with the largest value.
C:堆是实现优先队列的惟一方法。A heap is the only method to implement a priority queue.
D:堆一定是完全二叉树。A heap must be a complete binary tree.
E:最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。In a minimum heap, the largest value on some node’s left child tree could be possibly smaller than the smallest value of its right child tree.
F:使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screening method has a higher efficiency than inserting elements one by one while constructing a heap.
答案: 堆一定是完全二叉树。A heap must be a complete binary tree.;
最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。In a minimum heap, the largest value on some node’s left child tree could be possibly smaller than the smallest value of its right child tree.;
使用筛选法建堆要比将元素一个一个插入堆来建堆效率高。Screening method has a higher efficiency than inserting elements one by one while constructing a heap.

3、 下列关于Huffman树和Huffman编码的说法正确的有:Which sentences of the followings are right about Huffman tree and Huffman code:

A:Huffman树一定是满二叉树。A Huffman tree must be a full binary tree.
B:Huffman编码是一种前缀编码。Huffman code is a kind of prefix code.
C:Huffman树一定是完全二叉树。A Huffman tree must be a complete binary tree.
D:Huffman编码中所有编码都是等长的。All codes in a Huffman code have the same length.
E: 对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。Different content with the same group of weights can get different Huffman codes.
F:使用频率越高的字母，Huffman编码越长。The higher a letter’s frequency is, the longer its Huffman code is. 
答案: Huffman树一定是满二叉树。A Huffman tree must be a full binary tree.;
Huffman编码是一种前缀编码。Huffman code is a kind of prefix code.;
 对于同样的一组权值两两不同的内容可以得到不同的Huffman编码方案。Different content with the same group of weights can get different Huffman codes.

4、 一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应编码001,下面说法正确的有A group of letters with different weights has corresponded with Huffman codes, if a letter’s corresponding code is 001, which sentences of the followings are right:

A: 以001开头的编码不可能对应其他字母。A code beginning with 001 couldn’t correspond with other letters.
B:以000开头的编码不可能对应任何字母。Codes beginning with 000 couldn’t correspond with any letter.
C: 以01开头和1开头的编码肯定对应某个字母。Codes beginning with 01 or 1 must correspongding with some letters.
D:建好的Huffman树至少包含4个叶结点。The Huffman tree contains at least 4 leaf nodes.
E:编码0和00可能对应于其他字母。Code 0 and 00 could corresponding with other letters.
答案:  以001开头的编码不可能对应其他字母。A code beginning with 001 couldn’t correspond with other letters.;
 以01开头和1开头的编码肯定对应某个字母。Codes beginning with 01 or 1 must correspongding with some letters.;
建好的Huffman树至少包含4个叶结点。The Huffman tree contains at least 4 leaf nodes.

5、 如果按关键码值递增的顺序依次将n个关键码值插入到二叉搜索树中，如果对这样的二叉搜索树进行检索时，每次检索的字符都等概率的从这n个关键码值中选取，平均比较次数为多少？If we insert n key values to a binary search tree successively from small to large, when we search this binary search tree, each time the search character is selected from these n key values with the same possibility, then how many times will the comparison be on average?
答案: (以下答案任选其一都对)(n+1)/2;
(1+n)/2

6、 从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照前序遍历得到的序列为？（答案中每两个元素之间用一个空格隔开）From a null binary tree, insert key values {18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of preorder of this binary search tree. (There is one blank space between two elements)
答案: 18 10 5 73 68 27 25 41 32 51 99

7、 从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照后序遍历得到的序列为？（答案中每两个元素之间用一个空格隔开）From a null binary tree, insert key values {18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25} successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. Please write down the sequence of post order of this binary search tree. (There is one blank space between two elements)
答案: 5 10 25 32 51 41 27 68 99 73 18

8、 从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码构造出一棵二叉树，以怎样的顺序插入关键码集合{14，32，47，6，9，12，78，63，29，81}可以使得树的深度最小？请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。如果有多组满足要求的方案，请使得你的答案中先插入的元素尽可能的小。From a null binary tree, insert key values successively according to the insertion algorithm of a binary search tree strictly (no rotation and balance) to construct a binary search tree. What is the insertion sequence that could make the tree have a smallest depth with a key value set {14，32，47，6，9，12，78，63，29，81}? Please write down the elements successively, and there is one blank space between two elements. If there are more than one answer that meet the condition, please make the element which needs to be inserted first as small as possible in your answer.
答案: 12 6 9 47 29 14 32 78 63 81

9、 对于关键码序列{38，64，52，15，73，40，48，55，26，12}，用筛选法建最小值堆，若一旦发现逆序对就进行交换，共需要交换元素多少次？For the key value sequence {38，64，52，15，73，40，48，55，26，12}, use the screening method to constuct a minimum heap, if we exchange them when we find reversed order, then how many times should we exchange them?
答案: 6

10、 对于如下图所示的最大堆，删除掉最大的元素后，堆的前序遍历结果是For the following maximum heap, after deleting the maximum element, the preorder traversal sequence is请依次写出插入到树中的元素，每两个元素之间用一个空格隔开。Please write down the elements successively, and there is one blank space between two elements.
答案: 59 43 24 12 23 37 28 5 57 48 3

11、 对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是For the following maximum heap, after deleting the maximum element, the post order traversal sequence is
答案: 12 23 24 28 5 37 43 48 3 57 59

12、 下表展示了在一段文本中每个字母出现的次数。The frequencies that each letter appears in a paragraph is represented as follow.对于这段文本使用Huffman编码相较使用等长编码能够节约多少比特的空间？Comparing to use codes that have the same length, how many bits of space could be saved when we use Huffman code for the paragraph?
答案: 36

13、 对于给定的一组权W={1,4,9,16,25,36,49,64,81,100}，构造一棵具有最小带权外部路径长度的三叉树，写出这棵树的带权外部路径长度。For a given group of weights W={1, 4, 9, 16, 25, 36, 49, 64, 81, 100}, please construct a ternary tree with a minimum weighted route length and write down this weighted route length.
答案: 705

14、 请阅读下面一段代码 Please read the following codeC++：Python：若此段代码的作用是用来进行前序遍历，那么应该在几号访问点进行访问？（只需要填写数字）if this code is used to do a preorder traversal, which visiting point should be visited? (You only need to write down the number)
答案: 1

15、 请阅读下面一段代码Please read the following codeC++：Python：若此段代码的作用是用来进行中序遍历，那么应该在几号访问点进行访问？（只需要填写数字）if this code is used to do an infix order traversal, which visiting point should be visited? (You only need to write down the number)
答案: 2

16、 请阅读下面一段代码Please read the following code C++：Python：若此段代码的作用是用来进行后序遍历，那么应该在几号访问点进行访问？（只需要填写数字）if this code is used to do an post order traversal, which visiting point should be visited? (You only need to write down the number)
答案: 3

第四章 字符串 第四章 字符串测验

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;int f(char s[])
{    
    int i=0,j=0;
    while(s[j])
        (1)++;
    for(j–; i < j && s[i] == s[j]; i++, j–);
    return((2)>=(3)__);
}注：(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