# 2020学堂在线（学堂云3.0、Pro）数据结构(上)慕课答案，学堂在线数据结构(上)慕课答案单元章节答案、期末考试答案

## For computing the Hailstone sequence (a.k.a. 3n+1 problem), the Hailstone(n) program 视频中提到的Hailstone问题（又名3n+1问题）中Hailstone(n)的计算程序是

• won't terminate for any value of n. 对于所有的n都是无穷的
• won't terminate for some values of n (but will terminate otherwise). 对于部分n是无穷的
• We don't know if it termiates for any value of n. 不能确定是否存在n，使程序无法终止
• always terminate for any value of n. 对于所有的n都是有穷的

## What is the foremost criterion for a "good algorithm"? 判断一个算法是否是一个“好算法”，最重要的一条性质是

• correctness 正确
• robustness 健壮
• efficiency 效率

## Which of the following is NOT a component of a Turing machine? 以下哪项不是图灵机的组成要件？

• A tape of finite length 有限长的纸带
• A finite alphabet 有限的字母表
• A finite set of states 有限种状态

• True 对
• False 错

## Which one of the following is equivalent to $O({n}^{3})$ in the sense of big-O? (m is not a constant) 在大O记号的意义下，以下哪一项与$O({n}^{3})$ 相等？(m不是常数)

• $O({3}^{n})$
• $O({n}^{3}+2000{n}^{2}+1000{n})$
• $O({n}^{3}+m)$
• $O(2000{n}^{3}+{n}^{4})$

## Which of the following equations is wrong? 下列对应关系中错误的是

• ${1}^{2}+{2}^{2}+{3}^{2}+...+{n}^{2}=O({n}^{3})$
• $1+2+4+...+{2}^{n}=O({2}^{n})$
• $log1+log2+log3+...+logn=O(nlogn)$
• $1+1/2+1/3+...+1/n=O(nlogn)$

## $x=n;$$y=1;$$while(x>=(y-1)*(y-1))$$\quad \quad y++;The complexity of the program above is 以上程序的时间复杂度为 • O(logn) • O(\sqrt{n}) • O(nlogn) • O({n}^{2}) ## True or false: In bubble sort, the size of the problem is reduced to k after k rounds of sweep & swap.判断：经过k轮扫描交换后，起泡排序程序会将问题规模缩减至k。 • True 对 • False 错 ## True or false: To apply decrease-and-conquer, we divide the original problem into two degenerated sub-problems, solve them, and merge their solutions. 判断：减而治之的思想是：将问题划分为两个平凡的子问题，分别求解子问题，来得到原问题的解。 • True 对 • False 错 ## Li Lei and Han Meimei have different opinions regarding the linear time complexity in the video lecture.对于视频中线性递归的时间复杂度，A、B两位同学有不同的看法。Li Lei aggrees to the video, the complexity is O(n) because there are n instances each requiring O(1) execution time. A同学赞同视频中的算法，由于单个递归实例需要O（1）时间完成，共有n个实例，所以整个算法的复杂度是O（n）。However, Han Meimei believes the time for sum（A,n) to be O(n) instead of O(1), since it's still executing even when calling sum(A,n-1), leading to a total time complexity of n+n-1+...+3+2+1=O（{n}^{2}. You agree with 但B同学认为，当sum（A,n）函数中调用sum(A,n-1)时，sum(A,n)仍在执行，因此sum（A,n）的完成时间不是O(1)而是O（n），依此计算，整个算法的复杂度应该为n+n-1+...+3+2+1=O（{n}^{2}）。请问哪位同学对了？ • Li Lei A同学 • Han Meimei B同学 ## In the video lecture we see a comment in the code: "Two base cases are required". What does it refer to? 视频里代码注释中“需要两个递归基”的含义是 • We need two functions handling different cases (when n is even or odd). 问题需要按照“n为奇数”、“n为偶数”两种情况分别设计两个函数 • The sequence of recursive callls is terminated when the problem size is reduced to either 0 or 1. 在问题规模缩减为0或1时，停止递归 • The program returns to the main function when the problem size is reduced to either 0 or 1. 在问题规模缩减为0或1时，返回main函数（或递归函数被调用的函数） • Two sub-instances are generated from every instance of the recursive calls. 递归函数在执行过程中将每次创建两个递归实例 ## 判断：用分而治之的思想来解决长度为n的数组的求和问题（n足够大），递归实例的数目会比用减而治之的方法少。 ## The naive way of computing fib(n) recursively leads to a time complexity of 直接用定义以递归的方式计算fib(n)的时间复杂度是： • \Theta({n}^{2}) • O({2}^{n}) • \Theta({2}^{n}) • O(n) ## With a regular computer, computing fib(100) naively using recursion would cost (no need to consider overflow). 以现在普通计算机的速度，直接用定义以递归的方式计算fib(100)需要多少时间（不考虑溢出）: • less than an hour 一小时之内 • about a day 大约一天 • ten years 十年 • much longer than your lifetime. 这辈子看不到啦 ## For the staircase problem in the video lecture, how many different ways can get you from the first step to the eighth. 对于视频中的上台阶问题（从第一层开始），上到第8层共有多少种不同的走法： • 21 • 13 • 17 • 34 ## The time and space complexities for computing fib(n) with dynamic programming are 用动态规划计算fib(n)的时间、空间复杂度分别为 • \Theta(n^2),\Theta(n^2) • \Theta(n^2),\Theta(n) • \Theta(n),\Theta(n) • \Theta(n),\Theta(1) ## The length of the LCS between "program" and "algorithm" isprogram 和 algorithm的LCS长度为: • 1 • 2 • 3 • 4 ## LCS(x,y) is defined to be the length of the LCS between strings x and y. LCS("program", "algorithm") = LCS(x,y)表示字符串x,y最长公共子序列长度，则LCS（“program”, “algorithm”）= • LCS（“progra”, “algorith”） + 1 • LCS（“progra”, “algorithm”） • LCS（“program”, “algorith”） • max{ LCS（“progra”, “algorithm”）, LCS（“program”, “algorith”）} ## Checkout the Demo in the video lecture (the download link is on the right side of the "Course" page, or in 01-f-6). Which tool was used to write the demo? 下载并使用视频中的Demo（下载链接在“课程信息”右侧，01-f-6里也有），它是用什么做的？ • Visual Basic • VC++ • X window • MS Excel ## Computing the LCS using dynamic programming leads to a time complexity of (m and n are the lengths of the input strings) 用动态规划求解输入序列长度分别为m,n的LCS问题，时间复杂度为： • \Theta(mn) • \Theta(n\log_2(m)) • \Theta(m+n) • \Theta(n^2) ## Given non-negative functions f(n), g(h) and h(n), which of the following statements about O,\Theta,\Omega is correct? 设函数f(n),g(n),h(n)非负，以下关于O,\Theta,\Omega记号的命题，正确的有： • If f(n)=O(h(n)) and g(n)=O(h(n)), then f(n)=g(n) 已知f(n)=O(h(n)) 且g(n)=O(h(n))，则f(n)=g(n) • \Theta(n)+\Theta(n)>\Theta(n) • \Theta(n)+\Theta(n/2)+\Theta(n/4)+\ldots+\Theta(1)=\Theta(n^2) • if f(n)=O(h(n)) and f(n)=Ω(h(n)), then f(n)=\Theta(h(n)) 已知f(n)=O(h(n))且f(n)=Ω(h(n))，则f(n)=\Theta(h(n)) ## Which of the following functions grows fastest asymptotically? 下列函数渐进增长速度最快的是： • n^{2/3} • \frac{n}{\log_2(n)} • \log_2{(\log_2(n))} • \log_2^2{n} ## Given the following three functions: 以下是三个函数：Their time complexities are: 它们的时间复杂度分别为： • \Theta(n),\Theta(n^2),\Theta(n) • \Theta(n\log_2(n)), \Theta(n\log_2(n)), \Theta(n) • \Theta(n), \Theta(n^2), \Theta(n\log_2(n)) • \Theta(n^2), \Theta(n), \Theta(n\log_2(n)) ## The following recursive function is for reversing array A[lo, hi] 以下递归函数实现数组A[lo, hi]的倒置：What is the time complexity of reverse(A, 0, n-1), for reversing an array of length n? 调用reverse(A, 0, n-1)以倒置长度为n的数组，算法的时间复杂度为： • \Theta(n) • \Theta(n\log_2(n)) • \Theta(n^2) • \Theta(\log_2(n)) ## V={11, 23, 19, 7, 17, 5, 3, 13, 2, 29}When sorting V using bubble sort, what is the value of V[8] after two rounds of sweep & swap? 对V进行起泡排序，两趟扫描交换后V[8] = • 17 • 19 • 23 • 29 ## Which of the following options is correct:下列说法中正确的是： • The abstract data type is an advanced data type provided by C++ for implementing data structures. 抽象数据类型是C++提供的一种高级的数据类型，用于实现数据结构。 • The abstract data type determines how data is stored. 抽象数据类型决定了数据的存储方式。 • The same abstract data type may be implemented using multiple data structures. 同一个抽象数据类型可能用多种数据结构实现。 • Data structure is an abstract data type. 数据结构即抽象数据类型。 ## On an initially empty vector, what's the result of executing insert(0, 2), insert(1, 6), put(0, 1), remove(1) and insert(0, 7):在一个初始为空的向量上依次执行：insert(0, 2), insert(1, 6), put(0, 1), remove(1), insert(0, 7) 后的结果是： • {6, 2, 7} • 2, 6, 0, 7} • {7, 1} • {2, 1, 7} ## The following code is a variant of the vector copy code with the same semantics. The space should be filled with: 以下代码是向量复制代码的一个变体且语义与其相同，空格处应填入的内容为： • --hi • hi-- • ++lo • lo++ ## On an empty vector with an initial maximum capacity of 10, the load factor after executing insert(0, 2), insert(1, 6), put(0, 1), remove(1) and insert(0, 7) is: 在一个初始最大容量为10的空向量上依次执行：insert(0, 2), insert(1, 6), put(0, 1), remove(1), insert(0, 7) 后的装填因子是： • 10% • 20% • 30% • 40% ## Is it possible to replace:是否可以将视频里向量扩容代码中的：for (int i = 0; i < _size; i++) _elem[i] = oldElem[i]; in the vector expansion code in the video with: 替代为： memcpy(_elem, oldElem, _size * sizeof(T));P.S.This question involves the relevant knowledge of C++ P.S.本题涉及C++的相关知识 • Yes, they are equivalent and there will be no problem. 是，二者是等价的，不会有任何问题。 • No, because the range of elemental intervals for the two copies is different. 否，因为二者复制的元素区间范围不同。 • No, because their efficiency are different. 否，因为二者的效率不同。 • No, because whether the latter can achieve the purpose is related to element type T. 否，因为后者能否达到目的与元素类型T有关。 ## Using the expansion strategy of appending fixed memory space each time, the amortized time complexity of inserting element of vector of size n is: 采用每次追加固定内存空间的扩容策略，规模为n的向量插入元素的分摊时间复杂度为： • \Theta(nlog_2n) • \Theta(n) • \Theta(log_2n) • \Theta(1) ## By using two expansion strategies, one for each additional fixed memory space and one for double up memory space, the amortized time complexity of inserting elements of vector of size n is: 分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，规模为n的向量插入元素的分摊时间复杂度分别为： • \Theta(n),\Theta(1) • \Theta(n),\Theta(n) • \Theta(1),\Theta(1) • \Theta(n),\Theta(log_2n) ## With regard to the average complexity and the amortized complexity, which of the following statement is wrong: 关于平均复杂度和分摊复杂度，下列说法中错误的是： • The sequence of operations considered by the amortized complexity must be realistic and feasible 分摊复杂度所考量的一串操作序列一定是真实可行的 • The average complexity depends on the assumption of the probability of occurrence of each operation, while the amortized complexity is not 平均复杂度依赖于对各操作出现概率的假设，而分摊复杂度则不是如此 • Amortized complexity results in lower than average complexity 分摊复杂度得到的结果比平均复杂度低 • The conclusion of Θ(1) in the double up expansion strategy refers to the amortized complexity 加倍扩容策略中Θ(1)的结论是指分摊复杂度 ## What is the meaning of the return value of T & Vector::operator[](Rank r) { return _elem[r]; }? T & Vector::operator[](Rank r) { return _elem[r]; } 中的返回值T&是什么意义？ • This is a pointer of type T because it is more efficient 这是类型T的指针，使用它是因为效率更高 • This is a reference to type T because it is more efficient 这是类型T的引用，使用它是因为效率更高 • This is a pointer of type T because its return value can be used as an left value 这是类型T的指针，使用它是因为返回值可以作为左值 • This is a reference to the type T because its return value can be used as an left value 这是类型T的引用，使用它是因为返回值可以作为左值 ## What happens if the FOR loop in the insert() function changes to the following form？for (int i = r; i < _size; i++) _elem[i + 1] = _elem[i]; • No problem, just change it from front to back 没有问题，只是改为从前向后移动罢了 • Overwrite all elements in the original vector with rank greater than r 会覆盖原向量中秩大于r的所有元素 • Overwrite all elements in the original vector with rank less than r 会覆盖原向量中秩小于r的所有元素 • Will cause vector expansion failure 会引起向量扩容失败 ## Why the suffix of the deleted element is moved from front to back in the interval deletion algorithm remove(lo, hi)? 为什么区间删除算法remove(lo, hi)中要从前向后移动被删除元素的后缀？ • This is a customary practice, which in turn is also feasible 这是一个约定俗成的习惯，反过来也可行 • Otherwise it may cover some elements 否则可能会覆盖部分元素 • Otherwise it may fail to delete all elements within the interval [lo, hi) 否则可能未能删除区间[lo, hi)内所有的元素 • Otherwise it may lead to inefficiency 否则可能导致效率低下 ## For the deduplicate() algorithm, the worst-case time complexity for the vector scale n is: 对于deduplicate()算法，向量规模为n时的最坏时间复杂度为： • \Theta({n}^{2}) • \Theta(nlog_2n) • \Theta(n) • \Theta(1) ## As a function object class XXX, which of the following member functions must be explicitly defined: 作为一个函数对象的类XXX，它必须显式定义以下哪个成员函数： • XXX() • ~XXX() • operator[]() • operator()() ## The return value of the disordered() algorithm is: disordered()算法的返回值是： • Reverse order number 逆序数 • The number of adjacent inversion 相邻逆序对个数 • The bool value of whether it's ordered 表示是否有序的bool值 • The int value of whether it's ordered 表示是否有序的int值 ## Repeating elements in an ordered vector 有序向量中的重复元素 • Same as the unordered vector 与无序向量相同 • Most of them is adjacent distribution , only a very small part spread in other locations 大部分紧邻分布，只有极小部分散布在其它位置 • All of them are adjacent distribution 必定全部紧邻分布 • All of them are time distribution 全部相间分布 ## For vectors of size n, the worst-case time complexity of the inefficient version of uniquify() is: 对于规模为n的向量，低效版uniquify()的最坏时间复杂度为： • \Theta(n^2) • \Theta(nlog_2n) • \Theta(n) • \Theta(1) ## Why doesn't the algorithm need to call remove() to delete an element? 为什么该算法中不需要调用remove()进行元素删除？ • There is no duplicate element 本来就没有重复元素 • Duplicate elements are ignored directly 重复元素被直接忽略了 • Duplicate elements are moved to the end of the vector 重复元素被移到了向量末尾 • Duplicate elements have been modified to be non-repeating elements 重复元素修改成了不重复的元素 ## For vectors of size n, the worst-case time complexity of the efficient version of uniquify() is: 对于规模为n的向量，高效版uniquify()的最坏时间复杂度为： • \Theta(n^2) • \Theta(nlog_2n) • \Theta(n) • \Theta(1) ## For a vector of size n, the return value of find() on a search failure is: 对于规模为n的向量，查找失败时find()的返回值是： • -1 • 0 • n • nan ## Insert the element e in the ordered vector V and keep it in order, which of the following code is correct: 在有序向量V中插入元素e并使之保持有序，下列代码正确的是: • V.put(V.search(e) , e); • V.insert(V.search(e), e); • V.put(V.search(e) + 1, e); • V.insert(V.search(e) + 1, e); ## In binsearch(e, lo, hi) version A, if V[mi] < e, then the next search range is: 在binsearch(e, lo, hi)版本A中，若V[mi] < e，则下一步的查找范围是： • V(mi, hi) • V[mi, hi] • V(mi, hi] • V[lo, hi) ## Which of the following expressions is equivalent to Rank mi = (lo + hi) >> 1 ? (lo and hi are non-negative) Rank mi = (lo + hi) >> 1 等效于下列哪个表达式?（lo和hi非负） • Rank mi = (lo + hi) \ 2 • Rank mi = (lo + hi) % 2 • Rank mi = (lo + hi) / 2 • Rank mi = (double)(lo + hi) / 2 ## V={2, 3, 5, 7, 11, 13, 17}. How many comparisons V.search(16, 0, 7) need to make? V={2, 3, 5, 7, 11, 13, 17}。V.search(16, 0, 7)需要进行多少次比较？ • 4 • 5 • 6 • 7 ## V1={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61}V2={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}The search length of searching 43 in V1 is x, then the search length of searching 14 in V2 is: 在V1中查找43的查找长度是x，则在V2中查找14的查找长度为： • x • x+1 • 2 * x • x / 2 ## What is the difference between the fibSearch() algorithm and binSearch() algorithm? fibSearch()算法与binSearch()有什么区别？ • Their return value is different 二者的返回值不同 • The former is a recursive algorithm, and the latter is an iterative algorithm 前者是递归算法，后者是迭代算法 • There are different ways to choose the axis point mi 二者选取轴点mi的方式不同 • The former's asymptotic time complexity is lower than the latter, so the former is more efficient 前者的渐进时间复杂度低于后者，故前者效率更高 ## V={1, 2, 3, 4, 5, 6, 7}, using Fibonacci to find element 1 in V, the element selected as the pivot point mi is:V={1, 2, 3, 4, 5, 6, 7}，在V中用Fibonacci查找元素1，被选取为轴点mi的元素依次是： • 4, 3, 2, 1 • 4, 2, 1 • 5,2,1 • 5,3,2,1 ## Why is the search process for binSearch() version A not balanced? 为什么说binSearch()版本A的查找过程并不平衡? • Because the left and right branches have different subvector sizes 因为向左、向右两个分支的子向量规模不同 • Because the number of comparisons required for the left and right branches is not equal 因为向左、向右两个分支所需要的比较次数不相等 • Because the Fibonacci search is more balanced than the binary search 因为Fibonacci查找比二分查找更平衡 • Because the probability that the key is in the left subvector is greater than the probability that it is in the right 因为关键码位于左子向量中的概率比位于右侧的概率大 ## For a vector of size n, the optimal time complexity for binary search versions A and B is:对于规模为n的向量，二分查找版本A和B的最优时间复杂度分别为： • \Theta(n^2),\Theta(n) • \Theta(nlog_2n),\Theta(n) • \Theta(log_2n),\Theta(log_2n) • \Theta(1),\Theta(log_2n) ## For the search() interface, what we are going to return when there is more than one target element in the vector: 对于search()接口，我们约定当向量中存在多个目标元素时返回其中： • Rank maximun秩最大者 • Rank minimum秩最小者 • Rank intermediate 秩中间者 • Randomly return one of them 随机返回其中一个即可 ## For binary search version C, what is the next search range when e<V[mi] is not established: 对于二分查找版本C，当e<V[mi]不成立时下一步的查找范围是： • V[lo, mi) • V[mi, hi) • V[mi, hi] • V(mi, hi) ## For binary search version C, when the length of the search interval is reduced to 0, V[lo] is: 对于二分查找版本C，当查找区间的长度缩小为0时，V[lo]是：A、 max\{0\leq r < n|V[r]< e\} B、 max\{0\leq r < n|V[r]\leq e\} C、 min\{0\leq r < n|e < V[r]\} D、 min\{0\leq r < n|e\leq V[r]\} ## If the distribution of elements in an (ordered) vector satisfies an independent uniform distribution (before sorting), the average time complexity of the interpolation search is:如果（有序）向量中元素的分布满足独立均匀分布（排序前），插值查找的平均时间复杂度为： • O(n) • O(logn) • O(loglogn) • O(1) ## Searching for search elements 7 with interpolation in the vector V={2, 3, 5, 7, 11, 13, 17, 19, 23}在向量V={2, 3, 5, 7, 11, 13, 17, 19, 23}中用插值查找搜索元素7Guess the pivot point mi猜测的轴点mi[填空1] • 暂无选项 ## V={7, 2, 3, 11, 17, 5, 19, 13} After two scan exchange of V, V[6] = V={7, 2, 3, 11, 17, 5, 19, 13}，对V进行两次扫描交换后V[6] = • 11 • 13 • 17 • 19 ## Which situation will the improved blistering order will end prematurely ? 经改进的起泡排序在什么情况下会提前结束？ • Complete all n-1 scans 完成全部n-1趟扫描交换 • The number of scan conversions completed = The number of scan switching parameters for the actual element exchange + 1 完成的扫描交换趟数 = 实际发生元素交换的扫描交换趟数 + 1 • The number of scan conversions completed = The number of scan switchings that actually took place for element exchange 完成的扫描交换趟数 = 实际发生元素交换的扫描交换趟数 • Complete (n - 1) / 2 scan exchange 完成 (n - 1) / 2趟扫描交换 ## Try the following algorithm to sort V={19, 17, 23}: 试用以下算法对V={19, 17, 23}排序：1. Sort by units at first 1. 先按个位排序2. On the basis of the previous step, sort again by tens 2. 在上一步基础上，再按十位排序Is this algorithm correct? 这个算法的是否正确？ • Certainly correct 一定正确 • Certainly incorrect 一定不正确 • If the sorting algorithm used in step 2 is stable, then correct 若第2步用的排序算法是稳定的，则正确 • If the sorting algorithm used in step 1 is stable, then correct 若第1步用的排序算法是稳定的，则正确 ## What is the solution to the recurrence formula T(n)=2T(\frac{n}{2})+O(n)? Which of the O(n) items represent? 归并排序时间复杂度的递推公式T(n)=2T(\frac{n}{2})+O(n)的解是什么？其中O(n)项代表什么？ • O(n), time for merging two sorted subvectors O(n),归并两个已排序子向量的时间 • O(nlog_2n), the time for sorting two sub-vectors separatelyO(nlog_2n),对两个子向量分别进行排序的时间 • O(n^2), the time for sorting two sub-vectors separatelyO(n^2),对两个子向量分别进行排序的时间 • O(nlog_2n), time for merging two sorted subvectorsO(nlog_2n),归并两个已排序子向量的时间 ## The two-way merger of {2, 5, 7} and {3, 11, 13} is performed by comparing: 对{2, 5, 7}和{3, 11, 13}进行二路归并，执行的元素比较依次是： • 2 and 3, 5 and 3, 5 and 11, 7 and 11 2与3、5与3、5与11、7与11 • 2 and 5, 5 and 3, 11 and 13, 5 and 7 2与5、5与3、11与13、5与7 • 2 and 3, 2 and 11, 7 and 11, 13 and 7 2与3、2与11、7与11、13与7 • 2 and 3, 5 and 11, 7 and 13 2与3、5与11、7与13 ## For vectors of size n, the optimal and worst-case time complexity for merge sorting is: 对于规模为n的向量，归并排序的最优、最坏时间复杂度分别为： • \Theta(n),\Theta(nlog_2n) • \Theta(nlog_2n),\Theta(nlog_2n) • \Theta(nlog_2n),\Theta(n^2) • \Theta(n),\Theta(n^2) ## By using two expansion strategies, one for each additional fixed memory space and one for double up memory space, the amortized time complexity of inserting an element of vector of size n is:分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，在规模为n的向量中插入一个元素的分摊时间复杂度为： • O(n),O(1) • O(n),O(n) • O(1),O(1) • O(n),O(log_2(n)) ## Insert the element e in the ordered vector V and keep it in order, which of the following code is correct:在有序向量V中插入元素e并使之保持有序，下列代码正确的是: • V.put(V.search(e) , e); • V.insert(V.search(e), e); • V.put(V.search(e) + 1, e); • V.insert(V.search(e) + 1, e); ## The binary search for "version C" is extracted as follows:二分查找“版本C”摘录如下：The vector V={2, 3, 5, 7, 11, 13, 17, 19} is used to find the target element 16 in V. The elements that have been compared with the target element in the whole process are:向量V={2, 3, 5, 7, 11, 13, 17, 19}，在V中使用它查找目标元素16，整个过程中与目标元素发生过比较的元素依次为： • 11, 17, 13 • 7, 3, 17 • 13, 11, 17 • 5, 7, 11 ## The binary search for "version C" is extracted as follows:二分查找“版本C”摘录如下：When there are multiple elements to be searched in the array A, the return value of the function:当数组A中有多个待查找元素e时，函数的返回值为： • Return the element whose rank is smallest 返回秩最小者 • Return the element whose rank is biggest返回秩最大者 • Return the element whose rank is in the middle返回秩位于正中间者 • Randomly return one of them随机返回其中一个 ## The following function is a recursive version of the binary search:以下函数是二分查找的递归版：For a vector of size n, the time and space complexity of the recursive version and the iterated version learned in class are: 对于规模为n的向量，该递归版的时间、空间复杂度和课堂上所学的迭代版的时间、空间复杂度分别是： • O(n),O(nlog_2(n)),O(n),O(1) • O(nlog_2(n)),O(nlog_2(n)),O(nlog_2(n))，O(nlog_2(n)) • O(log_2(n)),O(1),O(log_2(n)),O(1) • O(log_2(n)), O(log_2(n)),O(log_2(n)),O(1) ## The vector V={1, 2, 3, 4, 5, 6, 7}, uses the Fibonacci search to find the target element 1 in V, the elements selected as the pivot mi are: 向量V={1, 2, 3, 4, 5, 6, 7}，在V中用斐波那契查找查找目标元素1，被选取为轴点mi的元素依次是： • 4, 3, 2, 1 • 4, 2, 1 • 5, 2, 1 • 5, 3, 2, 1 ## The two-way merger of {2, 5, 7} and {3, 11, 13} is performed by comparing: 对{2, 5, 7}和{3, 11, 13}进行二路归并，执行的元素比较依次是： • 2 and 3, 5 and 3, 5 and 11, 7and 11 2与3、5与3、5与11、7与11 • 2 and 5, 5 and 3, 11 and 13, 5 and 7 2与5、5与3、11与13、5与7 • 2 and 3, 2 and 11, 7 and 11, 13 and 72与3、2与11、7与11、13与7 • 2 and 3, 5 and 11, 7 and 132与3、5与11、7与13 ## In any scanning exchange of bubbling ordering, if the last exchange is to swap elements X > Y for Y Y交换为Y < X，则此后： • X and Y must have been in place X和Y必然都已经就位 • X must be in place while Y is not necessarily X必然就位，而Y未必 • Y must be in place while X is not necessarily X未必就位，而Y必然 • Neither X nor Y are necessarily in place X和Y都未必已经就位 ## On an initially empty vector, what's the answer after executing: insert(0, 2), insert(1, 6), put(0, 1), remove(1), insert(0, 7) 在一个初始为空的向量上依次执行：insert(0, 2), insert(1, 6), put(0, 1), remove(1), insert(0, 7) 后的结果是： • {1, 2, 7} • {2, 1, 0, 7} • {7, 1} • {2, 1, 7} ## The following code implements interval deletion of vectors by continuously deleting individual elements: 以下代码通过不断删除单个元素实现向量的区间删除：The overloaded function remove(Rank r) completes the operation of deleting a single element, and its time complexity is proportional to the number of succeeding elements of the deleted element. For vectors of size n, the worst-case complexity of this interval deletion algorithm is:其中重载函数remove(Rank r)完成删除单个元素的操作，其时间复杂度正比于被删除元素的后继个数。对于规模为n的向量，该区间删除算法的最坏时间复杂度为： • O(n) • O(nlog_2(n)) • O(n^2) • O(log_2(n)) ## Which of the following options about rank of list node is incorrect下列关于列表的秩的说法中不正确的是 • The physical address of a list node can be determined by its rank列表节点的秩与物理地址有明确的对应关系 • The cost of maintaining rank of list node is high列表的秩具有很高的维护成本 • In a list, the cost of rank-based access is high在列表中循秩访问的成本较高 • In a list, location-based access is faster than rank-based access在列表中循位置访问会比循秩访问更快 ## Which of the following options about defined interface is incorrect?下列关于我们定义的接口的描述中，哪一条是错误的？ • For the nodes in the list, we can take their predecessor and successor respectively by calling the pred() and succ() interfaces.对于列表中的节点，我们可以通过调用 pred() 和 succ() 接口分别取其前驱和后继。 • One of the important differences between find(e) and search(e) in list interface is that find(e) is suitable for all lists, and search(e) is applied to ordered lists.对于列表接口中的 find(e) 与 search(e)，其中一个重要区别在于 find 普适于所有列表，而 search 适用于有序列表。 • If the length of the 'visible list' part is n, the ranks of the 'head', first, last, and 'trail' nodes are -1, 0, n, n + 1 respectively.如果一个列表的 visible list 部分长度为 n，则头、首、末、尾节点的秩分别为 -1, 0, n, n + 1 • In constructing the list, we need to construct sentry nodes first.在构造列表时，我们需要首先构造哨兵节点。 ## If you change insertAsPred() to the following function, the result is:若将insertAsPred()改为以下函数，其结果是： • Can insert nodes normally.能正常插入节点 • Cannot insert node, original list remains unchanged.不能插入节点，原列表仍然保持不变 • Cannot insert node, the structure of the original list is destroyed.不能插入节点，原列表的结构被破坏 • Can insert a node related to the structure of the list at the time.能否插入节点与当时列表的结构有关 ## We can consider speeding up call-by-rank by: If r>\frac{n}{2} , then we can continue to access pred() from the tail and eventually move backwards to find the node with rank r.我们可以考虑通过如下方式加快循秩访问的速度：如果r>\frac{n}{2} ，则我们可以从尾部哨兵开始不断访问pred()，最终从后向前地找到秩为r的节点。What kind of argument is wrong about this optimization?关于这种优化，哪种说法是错误的？ • From the perspective of expectation, if r is an equal probability distribution in [0,n), the number of visits to the list element can be reduced by half during the call-by-rank.从期望的角度看，r在[0,n)中是等概率分布的话，那么在循秩访问的过程中，对列表 元素的访问次数可以节约一半。 • The slowest access time of origin method was mostly seen at r\approx n, while the slowest access time after improvement was generally seen at r\approx n/2.原有方法访问最慢的情形大致出现在r\approx n时，而改进后的方法访问最慢的情形大致出现在r\approx n/2时。 • When the access to the list is concentrated at the end of the list, the effect of this optimization strategy is most pronounced.当对于列表的访问集中在列表尾部时，这种优化策略的效果最明显。 • Through this optimization, we can make the call-by-rank time complexity better than O(n).通过这样的优化，我们可以使循秩访问时间复杂度优于O(n)。 ## The process of ordered list unique algorithm is:有序列表唯一化算法的过程是： • Keep only the first element of each interval of equal elements.只保留每个相等元素区间的第一个元素 • Each time an element is encountered, find backward and delete the same one.每遇到一个元素，向后查找并删除与之雷同者 • Every time an element is encountered, look ahead and delete the same one.每遇到一个元素，向前查找并删除与之雷同者 • Check (n ¦ 2) pairs of different elements. For each pair of elements, if they are identical, arbitrarily delete one of them.检查(n¦2)个不同的元素对，对于每一对元素，若雷同则任意删除其一 ## Can a binary search be used in an ordered list to reduce the time complexity to \Theta(log_2n)?能否在有序列表中用二分查找使得时间复杂度降为\Theta(log_2n)？ • Yes能 • No, because the amortized time complexity of list expansion is not \Theta(1)不能，因为列表扩容的分摊复杂度不是\Theta(1) • No, because the list cannot be efficiently accessed by rank不能，因为列表不能高效地循秩访问 • Yes, because the time complexity of the list delete node is \Theta(1)能，因为列表删除节点的时间复杂度为\Theta(1) ## V={11, 5, 7, 13, 2, 3}, sorting V by selection sort, the largest element selected as the unsorted subvector isV={11, 5, 7, 13, 2, 3}，对V进行选择排序，被选为未排序子向量中最大的元素依次为： • 11, 5, 7, 2, 3 • 13, 7, 11, 2, 5 • 13, 11, 7, 5, 3 • 2, 11, 13, 5, 7 ## In order to ensure the stability of the selectSort() algorithm, the measures we take are为了保证selectSort()算法的稳定性，我们采取的措施是： • In selectMax(), among the multiple equal largest elements, the selection position is the last oneselectMax()中对于多个相等的最大元素，选取其中位置最靠后者 • In selectMax(), among the multiple equal largest elements, the selection position is the first oneselectMax()中对于多个相等的最大元素，选取其中位置最靠前者 • First call deduplicate() to remove all duplicate elements.先调用deduplicate()删除所有重复元素 • Regardless of implementation details, the algorithm is inherently stable无论实现细节如何，该算法本来就是稳定的 ## For a vector or list of size n, the worst-case time complexity for selecting sorting and bubble sorting is.对于规模为n的向量或列表，选择排序和冒泡排序的最坏时间复杂度为： • \Theta(nlog_2n),\Theta(n^2) • \Theta(nlog_2n),\Theta(nlog_2n) • \Theta(n^2),\Theta(n^2) • \Theta(n^2),\Theta(nlog_2n) ## The average and worst time complexity of insertionSort() isinsertionSort()的平均、最坏时间复杂度分别为： • \Theta(n),\Theta(n^2 ) • \Theta(n^2 ),\Theta(n^2 ) • \Theta(n\log_2(n)),\Theta(n^2 ) • \Theta(n\log_2(n)),\Theta(n\log_2(n)) ## The maximum number of reversed pairs contained in a sequence of n elements isn个元素的序列所含逆序对的个数最大是： • n! • n!/2 • (n(n-1))/2 • n ## For a Ordered subsequence in the insertion process order (suppose its length to k)对于插入过程排序中的已排序子序列（设其长度为k）： • The elements are the smallest k elements in the entire sequence其中的元素是整个序列中最小的k个元素 • The elements are the largest k elements in the entire sequence其中的元素是整个序列中最大的k个元素 • The elements are the k elements at the front of the original sequence其中的元素是原序列中位于前方的k个元素 • The elements are the k elements in the back of the original sequence其中的元素是原序列中位于后方的k个元素 ## After a step of insertion sorting, the following sub-sequence V={2,7,13,5,3} is obtained, and the 3 elements are sorted . After another iteration, the result is:在插入排序的某一步后得到如下子序列V=\{2, 7, 13, 5, 3\}，此时已排序部分有3个元素。经过又一轮迭代后的结果是： • \{2, 3, 7, 13, 5\} • \{2, 7, 13, 3, 5\} • \{2, 5, 7, 13, 3\} • \{3, 2, 7, 13, 5\} ## About vector and the following list, which is wrong:下列关于向量和列表的说法错误的是： • Vectors usually occupy continuous space in memory, but the list is usually not the case向量通常在内存中占据连续的空间，列表则通常不是如此 • Finding in ordered vectors is progressively faster than finding in ordered lists在有序向量中查找渐进地比在有序列表中查找快 • The time complexity of merging sorting in vector is O(n\log_2(n)), and in list is \Omega(n^2)向量归并排序的时间复杂度是O(n\log_2(n))，而列表为\Omega(n^2) • Deleting single node in List progressively faster than that in vectors. 列表删除单个节点渐进地比向量删除单个元素快 ## In order to insert a new node in the list as a direct precursor to p, there are four related statements为了在列表中插入一个新节点node作为p的直接前驱，有四个相关的语句①p->pred->succ = node ②node->pred = p->pred ③node->succ = p ④ p->pred = node The correct execution order of the above statement is: 上述语句执行顺序正确的是： • ③②④① • ③②①④ • ①④③② • ④②③① ## For a bi-directional and unidirectional list of n nodes, the worst-case complexity of locating a node p's direct precursor is:对于n个节点的双向、单向列表，定位某节点p直接前驱的最坏时间复杂度分别为： • O(1),O(1) • O(1),O(n) • O(n),O(1) • O(n),O(n) ## The time complexity of finding an element in an ordered list is在有序列表中查找一个元素的时间复杂度是： • \Omega(n\log_2(n)) • \Omega(n) • O(\log_2(n)) • O(1) ## Selecting the list {11, 5, 7, 13, 2, 3}. Each time the elements are selected as the largest element in the unsorted sublist in selectMax()对列表{11, 5, 7, 13, 2, 3}进行选择排序，每一次selectMax()被选为未排序子列表中最大者的元素依次为： • 11, 5, 7, 2, 3 • 13, 7, 11, 2, 5 • 13, 11, 7, 5, 3 • 2, 11, 13, 5, 7 ## Which implementation of the selectSort() algorithm is stableselectSort()算法的哪种实现是稳定的： • Each time moves the smallest element to the front. For multiple equal minimum elements, select the one with the smallest position.每一趟将最小元素移到前方，对于多个相等的最小元素，选取其中位置最靠前者。 • Each time moves the biggest element to the front. For multiple equal maximum elements, select the one with the smallest position.每一趟将最大元素移到后方，对于多个相等的最大元素，选取其中位置最靠前者。 • Each time moves the smallest element to the front. For multiple equal minimum elements, select the one with the largest position.每一趟将最小元素移到前方，对于多个相等的最小元素，选取其中位置最靠后者。 • The above implementations are all stable以上实现皆稳定。 ## For ordered subsequences (set their length to k) during insertion sorting.对于插入排序过程中的已排序子序列（设其长度为k）： • The elements are the smallest k elements in the entire sequence其中的元素是整个序列中最小的k个元素 • The elements are the biggest k elements in the entire sequence其中的元素是整个序列中最大的k个元素 • The elements are the k elements at the front of the original sequence.其中的元素是原序列中位于前方的k个元素 • The elements are the k elements at the back of the original sequence.其中的元素是原序列中位于后方的k个元素 ## The sequence {2, 7, 13, 5, 3, 19, 17} is obtained after one insertion in the insertion order, and the sorted portion has 3 elements. After 2 iterations, the result is插入排序中的某一次插入后得到序列{2, 7, 13, 5, 3, 19, 17}，此时已排序部分有3个元素。又经过2趟迭代后的结果是： • {2, 3, 5, 7, 13, 17, 19} • {2, 3, 5, 7, 13, 19, 17} • {2, 5, 7, 3, 13, 19, 17} • {2, 3, 5, 13, 7, 17, 19} ## The reverse number of a sequence \tau is defined as the total number of reversed pairs in the sequence, and the total number of element comparisons performed by the insertion sort in the list of size n is:一个序列的逆序数\tau定义为该序列中的逆序对总数，规模为n的列表中插入排序进行的元素比较总次数为: • O(n + \tau\log_2(\tau)) • O(n+\tau) • O(n^2 + \log_2(\tau)) • O(\tau) ## A list of length n is equally divided into n/k segments. Each segment has a length of k. There is no reverse order for elements between different segments. The worst-case complexity for insertion sort on this list is:长度为n的列表，被等分为n/k段，每段长度为k，不同段之间的元素不存在逆序。对该列表进行插入排序的最坏时间复杂度为： • O(n^2) • O(nk) • O(n^2/k) • O(n^2k) ## The stack S is initially empty. After the following operations, the elements from the top of the stack to the bottom of the stack are:栈S初始为空，进行以下操作后从栈顶到栈底的元素依次为：S.push(5);S.push(4);S.pop();S.push(2);S.pop();S.pop();S.push(1) • 5, 4, 2, 1 • 1, 2, 4, 5 • 1 • 5, 4 ## The binary number of hexadecimal number AF is:16进制数AF的二进制为：[填空1] • 暂无选项 ## When an open parenthesis is scanned:当扫描到一个左括号时： • Popup stack 出栈 • Enter the stack 进栈 • Skip this character 跳过该字符 • End the algorithm 算法结束 ## Is {3,1,2,4} a stack shuffle of {1,2,3,4}?{3,1,2,4}是否是{1,2,3,4}的栈混洗？ • Yes 是 • No 不是 ## How many different stack shuffles are there for a sequence of length 4长度为4的序列共有多少个不同的栈混洗？[填空1] • 暂无选项 ## When does the actual calculation happen?什么时候进行实际的运算？ • Each time a new number is encountered每遇到一个新的操作数 • Each encounters a new operator每遇到一个新的操作符 • The current operator has a higher priority than the operator on the top of the stack当前的操作符比栈顶的操作符优先级高 • The current operator has a lower priority than the operator on the top of the stack当前的操作符比栈顶的操作符优先级低 ## When evaluating an inverse Polish expression, when does an actual calculation occur?逆波兰表达式的求值算法中，什么时候进行一次实际的运算？ • Each time a new operand is encountered每遇到一个新的操作数 • Each encounters a new operator每遇到一个新的操作符 • The current operator has a higher priority than the top of the stack当前操作符优先级高于栈顶 • The current operator has a lower priority than the top of the stack当前操作符优先级低于栈顶 ## Reverse Polish Expression of 1 5 +逆波兰表达式 1 5 +[填空1] • 暂无选项 ## The stack is initially empty and goes through the following operations in sequence:栈初始为空，依次经过以下操作： push(5); push(8); pop(); push(5); top(); push(1); push(3); pop(); pop(); push(2);At this point from the top of the stack to the bottom of the stack:此时从栈顶到栈底依次为： • 2, 5, 5 • 2, 3, 1 • 5, 5, 2 • 1, 3, 2 ## 下The following is a vector-based implementation of the queue (for the interface and implementation of vectors refer to Chapter 2):面是队列的一种基于向量的实现(向量的接口和实现可参考第2章)：For this queue of size n, the worst-case complexity of enqueue() and dequeue() is:对于规模为n的该队列，enqueue()和dequeue()的最坏时间复杂度分别为： • O(n), O(n) • O(1), O(1) • O(n), O(1) • O(n), O(\log_2(n)) ## The following is some kind of data structure, which is implemented with two stacks and supports adding and deleting elements:下面是某种数据结构，它用2个栈实现，支持添加、删除元素的操作：When T is an integer, the following operations are performed sequentially on the initially empty data structure:当T为整数时，对初始为空的以上数据结构依次执行以下操作：The only remaining elements in XXX at this time are:此时XXX中唯一剩下的元素是： • 2 • 5 • 7 • 11 ## The following is some kind of data structure, which is implemented with two queues and supports adding and deleting elements:下面是某种数据结构，它用2个队列实现，支持添加、删除元素的操作：When T is an integer, the following operations are performed sequentially on the initially empty data structure:当T为整数时，对初始为空的以上数据结构依次执行以下操作：The only remaining elements in XXX at this time are:此时XXX中唯一剩下的元素是： • 2 • 5 • 7 • 11 ## Read the function below (where 1≤x, y≤16) and indicate its function:阅读下面函数(其中1≤x, y≤16)，指出其功能： • Prints the y-ary representation of a decimal integer x.打印十进制整数x的y进制表示 • Print the y-ary representation of the x-ary integer 100.打印x进制整数100的y进制表示 • Print X-ary representation of a decimal number y.打印十进制整数y的x进制表示 • Print the x-ary representation of a y-ary integer 100打印y进制整数100的x进制表示 ## The operations on transfer stack S when sequence {2, 3, 5, 7, 11} is shuffled to get {3, 5, 2, 11, 7}对序列{2, 3, 5, 7, 11}进行栈混洗得到{3, 5, 2, 11, 7}的过程中用于中转的栈S进行的操作是: • push, pop, pop, push, push, pop, push, push, pop, pop • push, push, pop, pop, pop, pop, push, push, push, pop • push, push, pop, push, pop, pop, push, pop, pop, pop • push, push, pop, push, pop, pop, push, push pop, pop ## Which of the following sequences must not be a stack shuffle for {1,2,3... i...j...k...n}:下列哪一个序列一定不是{1,2,3… i…j…k…n}的栈混洗： • {… i…j…k…} • {… k…j…i…} • {… k…i…j…} • {… j…k…i…} ## which of the following are equal以下几个量中相等的是: ① Numbers of different n-bit binary 不同的n位二进制数个数 ② The number of legal parentheses matched by n pairs of parenthesesn对小括号所能构成的合法括号匹配个数 ③ Numbers of different stack shuffle for {1, 2 .. n}{1, 2 .. n}的不同栈混洗个数 ④ Number of operator stack push operations during infix expression evaluation with n operators含n个运算符的中缀表达式求值过程中运算符栈push操作的次数 • ①② • ②③ • ③④ • ②④ ## In the evaluation of infix expressions, the stack of operands from the top of the stack to the bottom of the stack is:在中缀表达式求值中，某时刻运算数栈从栈顶到栈底依次为:6， 2， 1The stack of operators from the top of the stack to the bottom of the stack is:运算符栈从栈顶到栈底依次为:×, +, (The remaining pending expression is:剩下的待处理表达式为 :)/(4×5-7)In the following process, the stacking order of operators and the final calculation result are在接下来的过程中运算符的入栈顺序以及最终的计算结果分别为： • / ( × - The final result is 8最终结果为8 • ) / (× -) The final result is 8最终结果为8 • / ( × - The final result is 1最终结果为1 • ) / (× -) The final result is 1最终结果为1 ## (1+2×3!)/(4×5-7) The inverse Polish expression is (The integers in the expression are all one-digit numbers)(1+2×3!)/(4×5-7)的逆波兰表达式为(表达式中的整数都是一位数) • (1+2×3!)/ 4×5-7) • / + 1× 2 3 - × 4 5 7 • 1 2 + × 3 ! 4 × 5 / 7 - • 1 2 3 ! × + 4 5 × 7 - / ## Which of the following data structures can efficiently balance static operations with dynamic operations:下列哪种数据结构可以高效地兼顾静态操作和动态操作: • array数组 • vector向量 • list列表 • tree树 ## How many edges of the tree have n vertices?n个顶点的树有多少条边? • n • n-1 • n^2 • 2^n ## The tree is:树是: • Directed Connectivity Graph有向连通图 • Acyclic plan Graph无环平面图 • Connected Acyclic Graph连通无环图 • Directed acyclic graph有向无环图 ## 在一棵树中,顶点p是顶点v的父亲,则它们的高度的关系是 • height(v) < height(p) • height(v) = height(p) - 1 • height(v) = height(p) + 1 • height(p) < height(v) ## Save the tree of n nodes using the parent + child node method. The space required is:用父节点+孩子节点的方法存储n个节点的树,需要的空间是: • O(1) • O(n) • O(nlgn) • O(n^2) ## The above tree is represented on the computer as follows:以上树在计算机中表示如下:The content of parent[] in the third line should be:第三行中parent[]的内容应该是: • 0, 5, -1, 7, 0, 5, 4, 7, 0, 7 • -1, 5, 5, 7, 0, 4, 5, 0, 0, 7 • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 • -1, 7, 5, 2, 5, 4, 1, -1, 0, 7 ## How many nodes are in full binary trees of height h?高度为h的满二叉树有多少个节点? • 2^{h+1}-1 • 2^{h+1} • 2^h-1 • 2^h ## A true binary tree with height h and node n is characterized by:一棵高度为h,节点数为n的真二叉树的特点是: • h=O(\log_2(n)) • It's really a binary tree, not any other kind of tree真的是二叉树,而不会是其他种类的树 • There is no node with only one father不存在只有一个父亲的节点 • There is no node with only one child不存在只有一个孩子的节点 ## In the eldest son-brother representation, what will the eldest child of a node in the tree be equivalent to in the binary tree:在长子-兄弟表示法中,树中某节点的长子相当于二叉树中的: • Young child幼子 • left child左子 • right child右子 • eldest son长子 ## Consider a binary tree have n nodes with a height of h. Insert a new node in it, and the number of nodes whose height has changed is:设二叉树有n个节点,高度为h.在其中插入一个新的节点,高度发生改变的节点个数为: • O(1) • O(n) • O(h) • O(hlog_2(n)) ## Pre-order traversal of the following binary tree:对以下二叉树进行先序遍历:When you have just finished accessing node d (Implementation 2), the elements in the stack from the top of the stack to the bottom of the stack are:刚访问完节点d时（迭代实现2）栈中的元素从栈顶到栈底依次为: • e • g,f • f,g • f ## The binary tree is:二叉树是: • Linear structure线性结构 • Semi-linear structure半线性结构 • Nonlinear structure非线性结构 • reinforced-concrete structure钢筋混凝土结构 ## If in the pre-order traversal the access to the root node is followed by accessing the right subtree first and then the left subtree, then the stacking order of the left and right subtrees is:若在先序遍历中规定访问完根节点后先访问右子树再访问左子树,则左、右子树的入栈顺序是： • Left first and then right先左后右 • Right first and then left先右后左 • In stack simultaneously同时入栈 • Only the left subtree is stacked, and the right subtree is not stacked只有左子入栈，右子不入栈 ## Pre-order traversal is:先序遍历的顺序是: • Access the nodes on the left side chain from the bottom up and access their right subtree from the bottom up先自下而上访问左侧链上的节点,再自下而上访问它们的右子树 • Visit the nodes on the left side chain from top to bottom and access their right subtree from top to bottom先自上而下访问左侧链上的节点,再自上而下访问它们的右子树 • Visit the nodes on the left side chain from top to bottom and access their right subtree from bottom to top先自上而下访问左侧链上的节点,再自下而上访问它们的右子树 • Access the nodes on the left side chain from the bottom up and access their right subtree from the top down先自下而上访问左侧链上的节点,再自上而下访问它们的右子树 ## The first node visited in the in-order traversal is:中序遍历中第一个被访问的节点是: • Leftmost node最左的节点 • Rightmost node最右的节点 • Root node根节点 • Leaf node on the left branch左侧分枝的叶节点 ## Perform inorder traversal on the following binary tree:对以下二叉树进行中序遍历:When the node c has just been accessed, the elements in the stack from the top of the stack to the bottom of the stack are:节点c刚被访问完毕时栈中的元素从栈顶到栈底为: • d, c, f • d, f • f, g, d, e • d ## The order of hierarchy traversal is:层次遍历的次序是: • The first root and then the left and the last right先根再左子最后右子 • Left first and then right last right child先左子再根最后右子 • Top-down access to each node in depth, from left to right in nodes of the same depth自上而下访问各个深度的节点,同样深度的节点中自左向右 • Top-down access to each node in depth, from right to left in nodes of the same depth自下而上访问各个深度的节点,同样深度的节点中自左向右 ## Perform hierarchical traversal of the following binary tree:对以下二叉树进行层次遍历:The element in the queue when node F is about to dequeue is from the head to the end of the queue:节点F正欲出队时队列中的元素从队头到队尾为: • F • F,G • E,F • E,F,G ## The last node in the post-order traversal sequence is:后序遍历序列中最后一个节点是： • Root node根节点 • Leftmost node最左边的节点 • Rightmost node最右边的节点 • The deepest node深度最大的节点 ## A binary tree has n nodes and its height is h. In which a new node is inserted, the maximum number of nodes that have changed in height is:某二叉树有n个节点，高度为h。在其中插入一个新的节点，高度发生改变的节点个数最多为： • O(1) • O(n) • O(h) • O(hlog_2(n)) ## How many nodes could be in complete binary tree of height h?高度为 h 的完全二叉树可能有多少个节点? • 2^{h+1} • 2^h • 2^{h-1}-1 • 2^{h-1} ## The following proposition of the tree, which is wrong下列关于树的命题中错误的是： • The number of edges of a tree with n number of vertices is n-1.顶点数为n的树的边数为n-1。 • There is a unique path between any two vertices in the tree.树中任意两顶点之间存在唯一路径。 • Adding any edge in the tree destroys the structure of the tree.在树中添加任一条边都会破坏树的结构。 • Delete any edge in the tree to get the tree.在树中删除任一条边得到的还是树。 ## A lookup set is a data structure used to represent disjoint sets and supports the following operations:并查集是一种用于表示不相交集合的数据结构，支持以下操作：A basic implementation is to organize the elements of each set into a rooted tree. The elements in the set are the nodes in the tree. The root of the collection is the representative element of the set. The entire search set consists of several trees. Composition of the forest. The interface implementation method is:一种基本的实现是将每一个集合中的元素组织成一棵有根树，集合中的元素即树中的节点，选取树根为该集合的代表元，而整个并查集就是由若干棵树组成的森林。接口实现的方法是：Example: In the figure below, we look at the tree {c, h, b, e} and {f, d, g} that originally represented the two collections. After calling Union(h, f), we get the right tree. At this point, calling Find(e) returns f.例子：下图中的并查集原先有两棵表示集合的树{c,h,b,e}和{f,d,g}，调用Union(h, f)后得到了右边的树，如果此时再调用Find(e)会返回f。What is the best way to look for the most concentrated tree?并查集中的树最适合用什么方法表示： • Parent node method父节点法 • Child node method孩子节点法 • The eldest son - Brothers Act长子-兄弟法 • Adjacent table method邻接表法 ## From the node node u of the binary tree of n nodes to the root node node by node, the following mistakes are:从n个节点的二叉树的叶节点u逐个节点地上溯到根节点的过程中，以下说法中错误的是： • The passing nodes are all ancestors of u.经过的节点都是u的祖先。 • The worst time complexity is O(n)最坏时间复杂度为O(n) • The path that is passed is uniquely determined经过的路径是唯一确定的 • Each time it goes up one level, the depth of the current node decreases by one and the height increases by one.每上溯一层，当前节点的深度减小1，而高度增加1。 ## In order to traverse the binary tree, the successor of the node v in the order traversal is (assuming that the successor of v exists):对二叉树进行中序遍历，节点v在中序遍历下的后继为（假设v的后继存在）： • The first visited node in its right subtree其右子树中第一个被访问的节点 • The first visited node in its left subtree其左子树中第一个被访问的节点 • The first visited node in its right subtree or an ancestor of v其右子树中第一个被访问的节点或v的某个祖先 • The first node in its right subtree or a node in its left subtree其右子树中第一个被访问的节点或其左子树中的某个节点 ## Similar to pre-order and in-order traversal, accessing the binary tree in the order of left child->right child->root node is called post-order traversal. The first visited node in the post-order traversal is与先序、中序遍历类似，以左子->右子->根节点的顺序来访问二叉树称为后序遍历。后序遍历中第一个被访问的节点是： • The deepest node in the left chain左侧链中最深的节点 • Root node根节点 • The deepest node in the right chain右侧链中最深的节点 • None of the above以上皆不是 ## The binary tree is traversed in order. u and v are two nodes on the left chain, and u is the ancestor of v. x and y are the right children of u and v. The order in which these four nodes are accessed is:对二叉树进行先序遍历，u和v是左侧链上两个节点，且u是v的祖先，x、y分别是u和v的右子，试问这四个节点被访问的顺序是： • y,v,x,u • x,y,v,u • u,v,y,x • unconfirmed无法确定 ## The misconception about the relationship between binary tree traversal sequences is:关于二叉树遍历序列之间关系的说法错误的是： • Knowing the pre-order traversal sequence and the mid-order traversal sequence can determine the post-order traversal sequence已知先序遍历序列和中序遍历序列可以确定后序遍历序列 • Knowing mid-order traversal and post-order traversal sequences, we can determine the sequence of pre-order traversal已知中序遍历序列和后序遍历序列可以确定先序遍历序列 • Knowing mid-order traversal and post-order traversal sequences, we can determine the sequence of Hierarchical traversal已知中序遍历序列和后序遍历序列可以确定层次遍历序列 • Knowing pre-order traversal and post-order traversal sequences, we can determine the sequence of mid-order traversal已知先序遍历序列和后序遍历序列可以确定中序遍历序列 ## When using a queue to hierarchically traverse a binary tree, the nodes in the queue at any time satisfy:借助队列对二叉树进行层次遍历时,任意时刻队列中的节点满足： • Both are on the path from the root node to the current node均位于从根节点到当前节点的路径上 • Both are descendants of the current node均是当前节点的后代 • The difference in height does not exceed 1高度相差不超过1 • The difference in depth does not exceed 1深度相差不超过1 ## The relationship between two vertices connected by a edge is called:两个通过一条边连起来的顶点之间的关系称为： • connected 相连 • adjacent 邻接 • related 关联 • neighbor 邻居 ## The one-touch-drawing question is to find out: 一笔画问题即要找出： • Path 路径 • Euler path 欧拉路径 • Hamiltonian cycle 哈密尔顿环路 • Simple cycle 简单环路 ## 06-b1-09A graph with an (undirected) edge between any two vertices is called a complete graph, and a complete graph containing n vertices is represented by K_{n} Which of the following figures must not be a plan? 任何两个顶点间都有一条（无向）边的图称为完全图，包含n个顶点的完全图用K_{n}表示。下列哪个图一定不是平面图？ • K_{2} • K_{3} • K_{4} • K_{5} ## The adjacency matrix of the above digraph is (in order of A, B, C, D) 以上有向图的邻接矩阵为（以A、B、C、D为顺序） ## In the graph implemented with adjacency matrices with n vertices, the vertex v has m neighbors, and the time complexity of traversing all m neighbors is:在包含n个顶点的用邻接矩阵实现的图中，顶点v有m个邻居，遍历所有m个邻居的时间复杂度为： • O(1) • O(m) • O(n) • O(mn) ## The graph G contains n vertices (n>0), implemented with an adjacency matrix. How many items have been added to the adjacency matrix after adding a new vertex?图G包含n个顶点(n>0)，用邻接矩阵实现。在其中加入一个新的顶点后邻接矩阵增加了多少项？ • n+1 • 2n • 2n-1 • 2n+1 ## Traversing graphs in a sense is to translate the graph into: 对图进行遍历某种意义上是将图转化为： • Vector向量 • List列表 • Tree树 • Binary tree二叉树 ## The breadth-first search of a graph is similar to that of a binary tree: 图的广度优先搜索访问各顶点的模式类似于二叉树的： • Pre-order traversal 先序遍历 • In-order traversal 中序遍历 • Post-order traversal 后序遍历 • Level-order traversal 层次遍历 ## The BFS is performed on the above undigraph with the vertex s as the starting point. The neighbors of the same vertex are in the order of a~z. When the vertex c is just out of the queue, the vertices in the queue from the head of the queue to the end of the queue are: 以顶点s为起点对以上无向图进行BFS，同一顶点的邻居之间以a~z为顺序，顶点c刚出队时队列中顶点从队头到队尾为： • d, e • e, d • d, a • a, d ## For graphs with n vertices and e edges implemented with adjacency list, the time complexity of BFS is:对于用邻接表实现的包含n个顶点e条边的图，BFS的时间复杂度为： • O(n) • O(n^{2}) • O(n+e) • O(n^{2}+e) ## DFS on the above undigraph with A as the starting point, and the neighbors of the same vertex are in order of a~z. The order in which the vertices are accessed is: 以A为起点对以上无向图进行DFS，同一顶点的邻居以a~z为序，各顶点被访问的顺序为： • a, e, b, c, f, g, h, j, i, d • a, b, c, f, g, d, i, h, j, e • a, b, e, c, f, h, g, i, d, j • a, e, b, c, f, h, g, i, d, j ## u and v are two vertices in the graph. After performing DFS on the graph, dTime(u) < dTime(v) < fTime(v) < fTime(u), then the relationship between u and v in the DFS forest is: u 和 v 为图中两个顶点，对图进行 DFS 后，dTime(u) < dTime(v) < fTime(v) < fTime(u)，则 u 和 v 在 DFS 森林中的关系是： • Belong to different connected components 属于不同的连通分量 • u is the ancestor of v u 为 v 的祖先 • v is the ancestor of u v 为 u 的祖先 • u and v are siblings 互为兄弟 ## Run breadth-first search (BFS) and depth-first search (DFS) respectively on the same undirected graph, the numbers of TREE edges satisfy: 对同一个无向图分别运行广度优先算法和深度优先算法，得到的树边数量： • BFS results in more TREE edges广度优先的树边更多 • DFS results in more TREE edges深度优先的树边更多 • they result in same number of TREE edges两种算法得到的树边一样多 • uncertainty in quantitative relationship数量关系不确定 ## DFS on a graph, which situation means that the graph contains a loop 对图进行DFS，一下哪种情况意味着该图包含环路 • There has a TREE edge 有TREE边 • There has a BACKWARD edge 有BACKWARD边 • There has a FORWARD edge 有FORWARD边 • There has a CROSS edge 有CROSS边 ## In a simple undigraph with 20 vertices, the maximum number of edges is:在含20个顶点的简单无向图中，边的数量最多为：[填空1]The degree of the vertex with the smallest degree at this time is:此时度最小的顶点的度为：[填空2] • 暂无选项 ## A total of 7 people took part in the banquet and a friendly handshake took place among the participants. The number of hands-on handshakes known to each of them is:3, 1, 2, 2, 3, 1, 2How many handshakes have occurred at the banquet?某宴会一共有7个人参加，与会者之间进行了亲切的握手。已知他们中的每个人进行握手的次数分别为：3, 1, 2, 2, 3, 1, 2请问宴会上总共发生了多少次握手？[填空1] • 暂无选项 ## （接上题）In the long history of humanity, everyone may have to shake hands with other people. If someone makes an odd number of handshakes in his life, he is called a Class A person, otherwise he is called a Class B person. The number of people of type A since ancient times is: (assuming that humans can only shake hands with humans)在人类的历史长河中，每个人都可能要与其他人握手。如果某人在他的一生中进行握手的次数为奇数，则称他为A类人，否则称为B类人。试问从古至今A类人的个数是：(假设人类只能和人类握手) • Even number偶数 • Odd number奇数 • Prime number 素数 • Complete square number 完全平方数 ## The adjacency matrix of the above digraph is (in order of A, B, C, D) 以上有向图的邻接矩阵为（图中顶点以A、B、C、D为顺序） ## For a simple undigraph with n vertices and e edges, which of the following argument for its adjacency matrix A is wrong: 对于包含n个顶点e条边的简单无向图，以下关于它的邻接矩阵A的说法中错误的是： • A has n rows and e columns, where the elements take a value of {0, 1} A有n行e列，其中元素取值于{0, 1} • The number of 1 in the kth row of A is equal to the degree of vertex k A的第k行中1的个数等于顶点k的度 • A=A^{T} • The element in row A and column V in A is 1 if and only if vertex u is associated with vertex v A中位于第u行v列的元素为1当且仅当顶点u和顶点v邻接 ## G is a simple undigraph, A is an adjacency matrix of G, M is an associative matrix of G, and D is a diagonal matrix of the degree of the i-th element of the vertex on the diagonal. Their relationship is: G是简单无向图，A为G的邻接矩阵，M为G的关联矩阵，D是对角线上第i个元素为顶点i的度的对角矩阵,它们的关系是： • A=M • A+D=MM^{T} • A+D=M^{T}M • Not direct relationship 没有直接关系 ## Using the adjacency matrix to implement a graph with n vertices and e edges: 用邻接矩阵实现含n个顶点e条边的图：Space complexity: 空间复杂度： • O(1) • O(n) • O(nlgn) • O(n^2) ## Time complexity of deleting edge(i,j): 删除边(i, j)的时间复杂度： • O(1) • O(n) • O(nlgn) • O(n^2) ## Time complexity of traversing all the neighbors of vertex v: 遍历顶点v的所有邻居的时间复杂度： • O(1) • O(n) • O(nlgn) • O(n^2) ## Time complexity of accessing data stored in vertex v: 访问顶点v中存储的数据的时间复杂度： • O(1) • O(n) • O(nlgn) • O(n^2) ## G is a directed acyclic graph, and (u, v) is an edge in G that points from u to v. The result of DFS on G is: G是有向无环图，(u, v)是G中的一条由u指向v的边。对G进行DFS的结果是： • dTime(u) > dTime(v) • dTime(u) < dTime(v) • fTime(u) > fTime(v) • fTime(u) < fTime(v) ## The following is the dTime and fTime of each vertex after performing a DFS on a simple undigraph: 下面是对一个简单无向图进行DFS后得到各顶点的dTime和fTime:Vertex顶点abcdefghijdTime123101746597fTime2019161118151314128The DFS tree is: 得到的DFS树为： ## Starting from s, perform BFS on the above undigraph, order a~z between the neighbors of the same vertex, and find the dTime of the vertex从s开始，对以上无向图进行BFS，同一顶点的邻居之间以a~z为序，求顶点的dTimedTime of s =s的dTime =1dtime of a =a的dTime =[填空1]dtime of b =b的dTime =[填空2]dtime of e =e的dTime =[填空3]dtime of f =f的dTime =[填空4] • 暂无选项 ## Starting from s, perform DFS on the above undigraph, order a~z between the neighbors of the same vertex, and find the dTime and fTime of each vertex从s开始，对以上无向图进行DFS，同一顶点的邻居之间以a~z为序，求各顶点的dTime和fTimedTime of s =s的dTime =1fTime of s =s的fTime =16dTime of c =c的dTime =[填空1]fTime of c =c的fTime =[填空2]dTime of g =g的dTime =[填空3]fTime of g =g的fTime =[填空4] • 暂无选项 ## For computing the Hailstone sequence (a.k.a. 3n+1 problem), the Hailstone(n) program 视频中提到的Hailstone问题（又名3n+1问题）中Hailstone(n)的计算程序是 • won't terminate for any value of n. 对于所有的n都是无穷的 • won't terminate for some values of n (but will terminate otherwise). 对于部分n是无穷的 • We don't know if it termiates for any value of n. 不能确定是否存在n，使程序无法终止 • always terminate for any value of n. 对于所有的n都是有穷的 ## What is the foremost criterion for a "good algorithm"? 判断一个算法是否是一个“好算法”，最重要的一条性质是 • correctness 正确 • robustness 健壮 • readability 可读 • efficiency 效率 ## Which of the following is NOT a component of a Turing machine? 以下哪项不是图灵机的组成要件？ • A tape of finite length 有限长的纸带 • A finite alphabet 有限的字母表 • A finite set of states 有限种状态 • A head for reading and writing 读写头 ## True of false: The RAM model is equipped with a finite amount of storage, which differs from the Turing machine. 判断正误：RAM模型与图灵机模型的区别在于图灵机的存储空间无限，而RAM的存储空间有限。 • True 对 • False 错 ## Which one of the following is equivalent to O({n}^{3}) in the sense of big-O? (m is not a constant) 在大O记号的意义下，以下哪一项与O({n}^{3}) 相等？(m不是常数) • O({3}^{n}) • O({n}^{3}+2000{n}^{2}+1000{n}) • O({n}^{3}+m) • O(2000{n}^{3}+{n}^{4}) ## Which of the following equations is wrong? 下列对应关系中错误的是 • {1}^{2}+{2}^{2}+{3}^{2}+...+{n}^{2}=O({n}^{3}) • 1+2+4+...+{2}^{n}=O({2}^{n}) • log1+log2+log3+...+logn=O(nlogn) • 1+1/2+1/3+...+1/n=O(nlogn) ## x=n;$$y=1;$$while(x>=(y-1)*(y-1))$$\quad \quad y++;$The complexity of the program above is 以上程序的时间复杂度为

• $O(logn)$
• $O(\sqrt{n})$
• $O(nlogn)$
• $O({n}^{2})$

• True 对
• False 错

• True 对
• False 错

## Li Lei and Han Meimei have different opinions regarding the linear time complexity in the video lecture.对于视频中线性递归的时间复杂度，A、B两位同学有不同的看法。Li Lei aggrees to the video, the complexity is O(n) because there are n instances each requiring O(1) execution time. A同学赞同视频中的算法，由于单个递归实例需要O（1）时间完成，共有n个实例，所以整个算法的复杂度是O（n）。However, Han Meimei believes the time for sum（A,n) to be O(n) instead of O(1), since it's still executing even when calling sum(A,n-1), leading to a total time complexity of $n+n-1+...+3+2+1=O（{n}^{2}$. You agree with 但B同学认为，当sum（A,n）函数中调用sum(A,n-1)时，sum(A,n)仍在执行，因此sum（A,n）的完成时间不是O(1)而是O（n），依此计算，整个算法的复杂度应该为$n+n-1+...+3+2+1=O（{n}^{2}）。$请问哪位同学对了？

• Li Lei A同学
• Han Meimei B同学

## In the video lecture we see a comment in the code: "Two base cases are required". What does it refer to? 视频里代码注释中“需要两个递归基”的含义是

• We need two functions handling different cases (when n is even or odd). 问题需要按照“n为奇数”、“n为偶数”两种情况分别设计两个函数
• The sequence of recursive callls is terminated when the problem size is reduced to either 0 or 1. 在问题规模缩减为0或1时，停止递归
• The program returns to the main function when the problem size is reduced to either 0 or 1. 在问题规模缩减为0或1时，返回main函数（或递归函数被调用的函数）
• Two sub-instances are generated from every instance of the recursive calls. 递归函数在执行过程中将每次创建两个递归实例

## The naive way of computing fib(n) recursively leads to a time complexity of 直接用定义以递归的方式计算fib(n)的时间复杂度是：

• $\Theta({n}^{2})$
• $O({2}^{n})$
• $\Theta({2}^{n})$
• $O(n)$

## With a regular computer, computing fib(100) naively using recursion would cost (no need to consider overflow). 以现在普通计算机的速度，直接用定义以递归的方式计算fib(100)需要多少时间（不考虑溢出）:

• less than an hour 一小时之内
• ten years 十年

• 21
• 13
• 17
• 34

## The time and space complexities for computing fib(n) with dynamic programming are 用动态规划计算fib(n)的时间、空间复杂度分别为

• $\Theta(n^2),\Theta(n^2)$
• $\Theta(n^2),\Theta(n)$
• $\Theta(n),\Theta(n)$
• $\Theta(n),\Theta(1)$

• 1
• 2
• 3
• 4

## LCS(x,y) is defined to be the length of the LCS between strings x and y. LCS("program", "algorithm") = LCS(x,y)表示字符串x,y最长公共子序列长度，则LCS（“program”, “algorithm”）=

• LCS（“progra”, “algorith”） + 1
• LCS（“progra”, “algorithm”）
• LCS（“program”, “algorith”）
• max{ LCS（“progra”, “algorithm”）, LCS（“program”, “algorith”）}

• Visual Basic
• VC++
• X window
• MS Excel

## Computing the LCS using dynamic programming leads to a time complexity of (m and n are the lengths of the input strings) 用动态规划求解输入序列长度分别为m,n的LCS问题，时间复杂度为：

• $\Theta(mn)$
• $\Theta(n\log_2(m))$
• $\Theta(m+n)$
• $\Theta(n^2)$

## Given non-negative functions f(n), g(h) and h(n), which of the following statements about $O,\Theta,\Omega$ is correct? 设函数$f(n),g(n),h(n)$非负，以下关于$O,\Theta,\Omega$记号的命题，正确的有：

• If $f(n)=O(h(n))$ and $g(n)=O(h(n))$, then $f(n)=g(n)$ 已知$f(n)=O(h(n))$ 且$g(n)=O(h(n))$，则$f(n)=g(n)$
• $\Theta(n)+\Theta(n)>\Theta(n)$
• $\Theta(n)+\Theta(n/2)+\Theta(n/4)+\ldots+\Theta(1)=\Theta(n^2)$
• if $f(n)=O(h(n))$ and $f(n)=Ω(h(n))$, then $f(n)=\Theta(h(n))$ 已知$f(n)=O(h(n))$且$f(n)=Ω(h(n))$，则$f(n)=\Theta(h(n))$

## Which of the following functions grows fastest asymptotically? 下列函数渐进增长速度最快的是：

• $n^{2/3}$
• $\frac{n}{\log_2(n)}$
• $\log_2{(\log_2(n))}$
• $\log_2^2{n}$

## Given the following three functions: 以下是三个函数：Their time complexities are: 它们的时间复杂度分别为：

• $\Theta(n),\Theta(n^2),\Theta(n)$
• $\Theta(n\log_2(n)), \Theta(n\log_2(n)), \Theta(n)$
• $\Theta(n), \Theta(n^2), \Theta(n\log_2(n))$
• $\Theta(n^2), \Theta(n), \Theta(n\log_2(n))$

## The following recursive function is for reversing array A[lo, hi] 以下递归函数实现数组A[lo, hi]的倒置：What is the time complexity of reverse(A, 0, n-1), for reversing an array of length n? 调用reverse(A, 0, n-1)以倒置长度为n的数组，算法的时间复杂度为：

• $\Theta(n)$
• $\Theta(n\log_2(n))$
• $\Theta(n^2)$
• $\Theta(\log_2(n))$

• 17
• 19
• 23
• 29

## Which of the following options is correct:下列说法中正确的是：

• The abstract data type is an advanced data type provided by C++ for implementing data structures. 抽象数据类型是C++提供的一种高级的数据类型，用于实现数据结构。
• The abstract data type determines how data is stored. 抽象数据类型决定了数据的存储方式。
• The same abstract data type may be implemented using multiple data structures. 同一个抽象数据类型可能用多种数据结构实现。
• Data structure is an abstract data type. 数据结构即抽象数据类型。

• {6, 2, 7}
• 2, 6, 0, 7}
• {7, 1}
• {2, 1, 7}

• --hi
• hi--
• ++lo
• lo++

• 10%
• 20%
• 30%
• 40%

## Is it possible to replace:是否可以将视频里向量扩容代码中的：for (int i = 0; i < _size; i++) _elem[i] = oldElem[i]; in the vector expansion code in the video with: 替代为： memcpy(_elem, oldElem, _size * sizeof(T));P.S.This question involves the relevant knowledge of C++ P.S.本题涉及C++的相关知识

• Yes, they are equivalent and there will be no problem. 是，二者是等价的，不会有任何问题。
• No, because the range of elemental intervals for the two copies is different. 否，因为二者复制的元素区间范围不同。
• No, because their efficiency are different. 否，因为二者的效率不同。
• No, because whether the latter can achieve the purpose is related to element type T. 否，因为后者能否达到目的与元素类型T有关。

## Using the expansion strategy of appending fixed memory space each time, the amortized time complexity of inserting element of vector of size n is: 采用每次追加固定内存空间的扩容策略，规模为n的向量插入元素的分摊时间复杂度为：

• $\Theta(nlog_2n)$
• $\Theta(n)$
• $\Theta(log_2n)$
• $\Theta(1)$

## By using two expansion strategies, one for each additional fixed memory space and one for double up memory space, the amortized time complexity of inserting elements of vector of size n is: 分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，规模为n的向量插入元素的分摊时间复杂度分别为：

• $\Theta(n),\Theta(1)$
• $\Theta(n),\Theta(n)$
• $\Theta(1),\Theta(1)$
• $\Theta(n),\Theta(log_2n)$

## With regard to the average complexity and the amortized complexity, which of the following statement is wrong: 关于平均复杂度和分摊复杂度，下列说法中错误的是：

• The sequence of operations considered by the amortized complexity must be realistic and feasible 分摊复杂度所考量的一串操作序列一定是真实可行的
• The average complexity depends on the assumption of the probability of occurrence of each operation, while the amortized complexity is not 平均复杂度依赖于对各操作出现概率的假设，而分摊复杂度则不是如此
• Amortized complexity results in lower than average complexity 分摊复杂度得到的结果比平均复杂度低
• The conclusion of Θ(1) in the double up expansion strategy refers to the amortized complexity 加倍扩容策略中Θ(1)的结论是指分摊复杂度

## What is the meaning of the return value of T & Vector::operator[](Rank r) { return _elem[r]; }? T & Vector::operator[](Rank r) { return _elem[r]; } 中的返回值T&是什么意义？

• This is a pointer of type T because it is more efficient 这是类型T的指针，使用它是因为效率更高
• This is a reference to type T because it is more efficient 这是类型T的引用，使用它是因为效率更高
• This is a pointer of type T because its return value can be used as an left value 这是类型T的指针，使用它是因为返回值可以作为左值
• This is a reference to the type T because its return value can be used as an left value 这是类型T的引用，使用它是因为返回值可以作为左值

## What happens if the FOR loop in the insert() function changes to the following form？for (int i = r; i < _size; i++) _elem[i + 1] = _elem[i];

• No problem, just change it from front to back 没有问题，只是改为从前向后移动罢了
• Overwrite all elements in the original vector with rank greater than r 会覆盖原向量中秩大于r的所有元素
• Overwrite all elements in the original vector with rank less than r 会覆盖原向量中秩小于r的所有元素
• Will cause vector expansion failure 会引起向量扩容失败

## Why the suffix of the deleted element is moved from front to back in the interval deletion algorithm remove(lo, hi)? 为什么区间删除算法remove(lo, hi)中要从前向后移动被删除元素的后缀？

• This is a customary practice, which in turn is also feasible 这是一个约定俗成的习惯，反过来也可行
• Otherwise it may cover some elements 否则可能会覆盖部分元素
• Otherwise it may fail to delete all elements within the interval [lo, hi) 否则可能未能删除区间[lo, hi)内所有的元素
• Otherwise it may lead to inefficiency 否则可能导致效率低下

## For the deduplicate() algorithm, the worst-case time complexity for the vector scale n is: 对于deduplicate()算法，向量规模为n时的最坏时间复杂度为：

• $\Theta({n}^{2})$
• $\Theta(nlog_2n)$
• $\Theta(n)$
• $\Theta(1)$

• XXX()
• ~XXX()
• operator[]()
• operator()()

## The return value of the disordered() algorithm is: disordered()算法的返回值是：

• Reverse order number 逆序数
• The number of adjacent inversion 相邻逆序对个数
• The bool value of whether it's ordered 表示是否有序的bool值
• The int value of whether it's ordered 表示是否有序的int值

## Repeating elements in an ordered vector 有序向量中的重复元素

• Same as the unordered vector 与无序向量相同
• Most of them is adjacent distribution , only a very small part spread in other locations 大部分紧邻分布，只有极小部分散布在其它位置
• All of them are adjacent distribution 必定全部紧邻分布
• All of them are time distribution 全部相间分布

## For vectors of size n, the worst-case time complexity of the inefficient version of uniquify() is: 对于规模为n的向量，低效版uniquify()的最坏时间复杂度为：

• $\Theta(n^2)$
• $\Theta(nlog_2n)$
• $\Theta(n)$
• $\Theta(1)$

## Why doesn't the algorithm need to call remove() to delete an element? 为什么该算法中不需要调用remove()进行元素删除？

• There is no duplicate element 本来就没有重复元素
• Duplicate elements are ignored directly 重复元素被直接忽略了
• Duplicate elements are moved to the end of the vector 重复元素被移到了向量末尾
• Duplicate elements have been modified to be non-repeating elements 重复元素修改成了不重复的元素

## For vectors of size n, the worst-case time complexity of the efficient version of uniquify() is: 对于规模为n的向量，高效版uniquify()的最坏时间复杂度为：

• $\Theta(n^2)$
• $\Theta(nlog_2n)$
• $\Theta(n)$
• $\Theta(1)$

• -1
• 0
• n
• nan

## Insert the element e in the ordered vector V and keep it in order, which of the following code is correct: 在有序向量V中插入元素e并使之保持有序，下列代码正确的是:

• V.put(V.search(e) , e);
• V.insert(V.search(e), e);
• V.put(V.search(e) + 1, e);
• V.insert(V.search(e) + 1, e);

• V(mi, hi)
• V[mi, hi]
• V(mi, hi]
• V[lo, hi)

## Which of the following expressions is equivalent to Rank mi = (lo + hi) >> 1 ? (lo and hi are non-negative) Rank mi = (lo + hi) >> 1 等效于下列哪个表达式?（lo和hi非负）

• Rank mi = (lo + hi) \ 2
• Rank mi = (lo + hi) % 2
• Rank mi = (lo + hi) / 2
• Rank mi = (double)(lo + hi) / 2

• 4
• 5
• 6
• 7

• x
• x+1
• 2 * x
• x / 2

## What is the difference between the fibSearch() algorithm and binSearch() algorithm? fibSearch()算法与binSearch()有什么区别？

• Their return value is different 二者的返回值不同
• The former is a recursive algorithm, and the latter is an iterative algorithm 前者是递归算法，后者是迭代算法
• There are different ways to choose the axis point mi 二者选取轴点mi的方式不同
• The former's asymptotic time complexity is lower than the latter, so the former is more efficient 前者的渐进时间复杂度低于后者，故前者效率更高

• 4, 3, 2, 1
• 4, 2, 1
• 5,2,1
• 5,3,2,1

## Why is the search process for binSearch() version A not balanced? 为什么说binSearch()版本A的查找过程并不平衡?

• Because the left and right branches have different subvector sizes 因为向左、向右两个分支的子向量规模不同
• Because the number of comparisons required for the left and right branches is not equal 因为向左、向右两个分支所需要的比较次数不相等
• Because the Fibonacci search is more balanced than the binary search 因为Fibonacci查找比二分查找更平衡
• Because the probability that the key is in the left subvector is greater than the probability that it is in the right 因为关键码位于左子向量中的概率比位于右侧的概率大

## For a vector of size n, the optimal time complexity for binary search versions A and B is:对于规模为n的向量，二分查找版本A和B的最优时间复杂度分别为：

• $\Theta(n^2),\Theta(n)$
• $\Theta(nlog_2n),\Theta(n)$
• $\Theta(log_2n),\Theta(log_2n)$
• $\Theta(1),\Theta(log_2n)$

## For the search() interface, what we are going to return when there is more than one target element in the vector: 对于search()接口，我们约定当向量中存在多个目标元素时返回其中：

• Rank maximun秩最大者
• Rank minimum秩最小者
• Rank intermediate 秩中间者
• Randomly return one of them 随机返回其中一个即可

• V[lo, mi)
• V[mi, hi)
• V[mi, hi]
• V(mi, hi)

• O(n)
• O(logn)
• O(loglogn)
• O(1)

• 暂无选项

• 11
• 13
• 17
• 19

## Which situation will the improved blistering order will end prematurely ? 经改进的起泡排序在什么情况下会提前结束？

• Complete all n-1 scans 完成全部n-1趟扫描交换
• The number of scan conversions completed = The number of scan switching parameters for the actual element exchange + 1 完成的扫描交换趟数 = 实际发生元素交换的扫描交换趟数 + 1
• The number of scan conversions completed = The number of scan switchings that actually took place for element exchange 完成的扫描交换趟数 = 实际发生元素交换的扫描交换趟数
• Complete (n - 1) / 2 scan exchange 完成 (n - 1) / 2趟扫描交换

## Try the following algorithm to sort V={19, 17, 23}: 试用以下算法对V={19, 17, 23}排序：1. Sort by units at first 1. 先按个位排序2. On the basis of the previous step, sort again by tens 2. 在上一步基础上，再按十位排序Is this algorithm correct? 这个算法的是否正确？

• Certainly correct 一定正确
• Certainly incorrect 一定不正确
• If the sorting algorithm used in step 2 is stable, then correct 若第2步用的排序算法是稳定的，则正确
• If the sorting algorithm used in step 1 is stable, then correct 若第1步用的排序算法是稳定的，则正确

## What is the solution to the recurrence formula $T(n)=2T(\frac{n}{2})+O(n)$? Which of the $O(n)$ items represent? 归并排序时间复杂度的递推公式$T(n)=2T(\frac{n}{2})+O(n)$的解是什么？其中$O(n)$项代表什么？

• $O(n)$, time for merging two sorted subvectors $O(n)$,归并两个已排序子向量的时间
• $O(nlog_2n)$, the time for sorting two sub-vectors separately$O(nlog_2n)$,对两个子向量分别进行排序的时间
• $O(n^2)$, the time for sorting two sub-vectors separately$O(n^2)$,对两个子向量分别进行排序的时间
• $O(nlog_2n)$, time for merging two sorted subvectors$O(nlog_2n)$,归并两个已排序子向量的时间

## The two-way merger of {2, 5, 7} and {3, 11, 13} is performed by comparing: 对{2, 5, 7}和{3, 11, 13}进行二路归并，执行的元素比较依次是：

• 2 and 3, 5 and 3, 5 and 11, 7 and 11 2与3、5与3、5与11、7与11
• 2 and 5, 5 and 3, 11 and 13, 5 and 7 2与5、5与3、11与13、5与7
• 2 and 3, 2 and 11, 7 and 11, 13 and 7 2与3、2与11、7与11、13与7
• 2 and 3, 5 and 11, 7 and 13 2与3、5与11、7与13

## For vectors of size n, the optimal and worst-case time complexity for merge sorting is: 对于规模为n的向量，归并排序的最优、最坏时间复杂度分别为：

• $\Theta(n),\Theta(nlog_2n)$
• $\Theta(nlog_2n),\Theta(nlog_2n)$
• $\Theta(nlog_2n),\Theta(n^2)$
• $\Theta(n),\Theta(n^2)$

## By using two expansion strategies, one for each additional fixed memory space and one for double up memory space, the amortized time complexity of inserting an element of vector of size n is:分别采用每次追加固定内存空间和每次内存空间翻倍两种扩容策略，在规模为n的向量中插入一个元素的分摊时间复杂度为：

• $O(n),O(1)$
• $O(n),O(n)$
• $O(1),O(1)$
• $O(n),O(log_2(n))$

## Insert the element e in the ordered vector V and keep it in order, which of the following code is correct:在有序向量V中插入元素e并使之保持有序，下列代码正确的是:

• V.put(V.search(e) , e);
• V.insert(V.search(e), e);
• V.put(V.search(e) + 1, e);
• V.insert(V.search(e) + 1, e);

• 11, 17, 13
• 7, 3, 17
• 13, 11, 17
• 5, 7, 11

## The binary search for "version C" is extracted as follows:二分查找“版本C”摘录如下：When there are multiple elements to be searched in the array A, the return value of the function:当数组A中有多个待查找元素e时，函数的返回值为：

• Return the element whose rank is smallest 返回秩最小者
• Return the element whose rank is biggest返回秩最大者
• Return the element whose rank is in the middle返回秩位于正中间者
• Randomly return one of them随机返回其中一个

## The following function is a recursive version of the binary search:以下函数是二分查找的递归版：For a vector of size n, the time and space complexity of the recursive version and the iterated version learned in class are: 对于规模为n的向量，该递归版的时间、空间复杂度和课堂上所学的迭代版的时间、空间复杂度分别是：

• $O(n),O(nlog_2(n)),O(n),O(1)$
• $O(nlog_2(n)),O(nlog_2(n)),O(nlog_2(n))，O(nlog_2(n))$
• $O(log_2(n)),O(1),O(log_2(n)),O(1)$
• $O(log_2(n)), O(log_2(n)),O(log_2(n)),O(1)$

• 4, 3, 2, 1
• 4, 2, 1
• 5, 2, 1
• 5, 3, 2, 1

## The two-way merger of {2, 5, 7} and {3, 11, 13} is performed by comparing: 对{2, 5, 7}和{3, 11, 13}进行二路归并，执行的元素比较依次是：

• 2 and 3, 5 and 3, 5 and 11, 7and 11 2与3、5与3、5与11、7与11
• 2 and 5, 5 and 3, 11 and 13, 5 and 7 2与5、5与3、11与13、5与7
• 2 and 3, 2 and 11, 7 and 11, 13 and 72与3、2与11、7与11、13与7
• 2 and 3, 5 and 11, 7 and 132与3、5与11、7与13

## In any scanning exchange of bubbling ordering, if the last exchange is to swap elements X > Y for Y Y交换为Y < X，则此后：

• X and Y must have been in place X和Y必然都已经就位
• X must be in place while Y is not necessarily X必然就位，而Y未必
• Y must be in place while X is not necessarily X未必就位，而Y必然
• Neither X nor Y are necessarily in place X和Y都未必已经就位

• {1, 2, 7}
• {2, 1, 0, 7}
• {7, 1}
• {2, 1, 7}

## The following code implements interval deletion of vectors by continuously deleting individual elements: 以下代码通过不断删除单个元素实现向量的区间删除：The overloaded function remove(Rank r) completes the operation of deleting a single element, and its time complexity is proportional to the number of succeeding elements of the deleted element. For vectors of size n, the worst-case complexity of this interval deletion algorithm is:其中重载函数remove(Rank r)完成删除单个元素的操作，其时间复杂度正比于被删除元素的后继个数。对于规模为n的向量，该区间删除算法的最坏时间复杂度为：

• $O(n)$
• $O(nlog_2(n))$
• $O(n^2)$
• $O(log_2(n))$

## Which of the following options about rank of list node is incorrect下列关于列表的秩的说法中不正确的是

• The physical address of a list node can be determined by its rank列表节点的秩与物理地址有明确的对应关系
• The cost of maintaining rank of list node is high列表的秩具有很高的维护成本
• In a list, the cost of rank-based access is high在列表中循秩访问的成本较高
• In a list, location-based access is faster than rank-based access在列表中循位置访问会比循秩访问更快

## Which of the following options about defined interface is incorrect?下列关于我们定义的接口的描述中，哪一条是错误的？

• For the nodes in the list, we can take their predecessor and successor respectively by calling the pred() and succ() interfaces.对于列表中的节点，我们可以通过调用 pred() 和 succ() 接口分别取其前驱和后继。
• One of the important differences between find(e) and search(e) in list interface is that find(e) is suitable for all lists, and search(e) is applied to ordered lists.对于列表接口中的 find(e) 与 search(e)，其中一个重要区别在于 find 普适于所有列表，而 search 适用于有序列表。
• If the length of the 'visible list' part is n, the ranks of the 'head', first, last, and 'trail' nodes are -1, 0, n, n + 1 respectively.如果一个列表的 visible list 部分长度为 n，则头、首、末、尾节点的秩分别为 -1, 0, n, n + 1
• In constructing the list, we need to construct sentry nodes first.在构造列表时，我们需要首先构造哨兵节点。

## If you change insertAsPred() to the following function, the result is:若将insertAsPred()改为以下函数，其结果是：

• Can insert nodes normally.能正常插入节点
• Cannot insert node, original list remains unchanged.不能插入节点，原列表仍然保持不变
• Cannot insert node, the structure of the original list is destroyed.不能插入节点，原列表的结构被破坏
• Can insert a node related to the structure of the list at the time.能否插入节点与当时列表的结构有关

## We can consider speeding up call-by-rank by: If $r>\frac{n}{2}$, then we can continue to access pred() from the tail and eventually move backwards to find the node with rank r.我们可以考虑通过如下方式加快循秩访问的速度：如果$r>\frac{n}{2}$，则我们可以从尾部哨兵开始不断访问pred()，最终从后向前地找到秩为r的节点。What kind of argument is wrong about this optimization?关于这种优化，哪种说法是错误的？

• From the perspective of expectation, if r is an equal probability distribution in $[0,n)$, the number of visits to the list element can be reduced by half during the call-by-rank.从期望的角度看，r在$[0,n)$中是等概率分布的话，那么在循秩访问的过程中，对列表 元素的访问次数可以节约一半。
• The slowest access time of origin method was mostly seen at $r\approx n$, while the slowest access time after improvement was generally seen at $r\approx n/2$.原有方法访问最慢的情形大致出现在$r\approx n$时，而改进后的方法访问最慢的情形大致出现在$r\approx n/2$时。
• When the access to the list is concentrated at the end of the list, the effect of this optimization strategy is most pronounced.当对于列表的访问集中在列表尾部时，这种优化策略的效果最明显。
• Through this optimization, we can make the call-by-rank time complexity better than O(n).通过这样的优化，我们可以使循秩访问时间复杂度优于O(n)。

## The process of ordered list unique algorithm is:有序列表唯一化算法的过程是：

• Keep only the first element of each interval of equal elements.只保留每个相等元素区间的第一个元素
• Each time an element is encountered, find backward and delete the same one.每遇到一个元素，向后查找并删除与之雷同者
• Every time an element is encountered, look ahead and delete the same one.每遇到一个元素，向前查找并删除与之雷同者
• Check (n ¦ 2) pairs of different elements. For each pair of elements, if they are identical, arbitrarily delete one of them.检查(n¦2)个不同的元素对，对于每一对元素，若雷同则任意删除其一

## Can a binary search be used in an ordered list to reduce the time complexity to $\Theta(log_2n)$?能否在有序列表中用二分查找使得时间复杂度降为$\Theta(log_2n)$？

• Yes能
• No, because the amortized time complexity of list expansion is not $\Theta(1)$不能，因为列表扩容的分摊复杂度不是$\Theta(1)$
• No, because the list cannot be efficiently accessed by rank不能，因为列表不能高效地循秩访问
• Yes, because the time complexity of the list delete node is $\Theta(1)$能，因为列表删除节点的时间复杂度为$\Theta(1)$

## V={11, 5, 7, 13, 2, 3}, sorting V by selection sort, the largest element selected as the unsorted subvector isV={11, 5, 7, 13, 2, 3}，对V进行选择排序，被选为未排序子向量中最大的元素依次为：

• 11, 5, 7, 2, 3
• 13, 7, 11, 2, 5
• 13, 11, 7, 5, 3
• 2, 11, 13, 5, 7

## In order to ensure the stability of the selectSort() algorithm, the measures we take are为了保证selectSort()算法的稳定性，我们采取的措施是：

• In selectMax(), among the multiple equal largest elements, the selection position is the last oneselectMax()中对于多个相等的最大元素，选取其中位置最靠后者
• In selectMax(), among the multiple equal largest elements, the selection position is the first oneselectMax()中对于多个相等的最大元素，选取其中位置最靠前者
• First call deduplicate() to remove all duplicate elements.先调用deduplicate()删除所有重复元素
• Regardless of implementation details, the algorithm is inherently stable无论实现细节如何，该算法本来就是稳定的

## For a vector or list of size n, the worst-case time complexity for selecting sorting and bubble sorting is.对于规模为n的向量或列表，选择排序和冒泡排序的最坏时间复杂度为：

• $\Theta(nlog_2n),\Theta(n^2)$
• $\Theta(nlog_2n),\Theta(nlog_2n)$
• $\Theta(n^2),\Theta(n^2)$
• $\Theta(n^2),\Theta(nlog_2n)$

## The average and worst time complexity of insertionSort() isinsertionSort()的平均、最坏时间复杂度分别为：

• $\Theta(n),\Theta(n^2 )$
• $\Theta(n^2 ),\Theta(n^2 )$
• $\Theta(n\log_2(n)),\Theta(n^2 )$
• $\Theta(n\log_2(n)),\Theta(n\log_2(n))$

• n!
• n!/2
• (n(n-1))/2
• n

## For a Ordered subsequence in the insertion process order (suppose its length to k)对于插入过程排序中的已排序子序列（设其长度为k）：

• The elements are the smallest k elements in the entire sequence其中的元素是整个序列中最小的k个元素
• The elements are the largest k elements in the entire sequence其中的元素是整个序列中最大的k个元素
• The elements are the k elements at the front of the original sequence其中的元素是原序列中位于前方的k个元素
• The elements are the k elements in the back of the original sequence其中的元素是原序列中位于后方的k个元素

## After a step of insertion sorting, the following sub-sequence V={2,7,13,5,3} is obtained, and the 3 elements are sorted . After another iteration, the result is:在插入排序的某一步后得到如下子序列$V=\{2, 7, 13, 5, 3\}$，此时已排序部分有3个元素。经过又一轮迭代后的结果是：

• $\{2, 3, 7, 13, 5\}$
• $\{2, 7, 13, 3, 5\}$
• $\{2, 5, 7, 13, 3\}$
• $\{3, 2, 7, 13, 5\}$

## About vector and the following list, which is wrong:下列关于向量和列表的说法错误的是：

• Vectors usually occupy continuous space in memory, but the list is usually not the case向量通常在内存中占据连续的空间，列表则通常不是如此
• Finding in ordered vectors is progressively faster than finding in ordered lists在有序向量中查找渐进地比在有序列表中查找快
• The time complexity of merging sorting in vector is $O(n\log_2(n))$, and in list is $\Omega(n^2)$向量归并排序的时间复杂度是$O(n\log_2(n))$，而列表为$\Omega(n^2)$
• Deleting single node in List progressively faster than that in vectors. 列表删除单个节点渐进地比向量删除单个元素快

• ③②④①
• ③②①④
• ①④③②
• ④②③①

## For a bi-directional and unidirectional list of n nodes, the worst-case complexity of locating a node p's direct precursor is:对于n个节点的双向、单向列表，定位某节点p直接前驱的最坏时间复杂度分别为：

• $O(1),O(1)$
• $O(1),O(n)$
• $O(n),O(1)$
• $O(n),O(n)$

## The time complexity of finding an element in an ordered list is在有序列表中查找一个元素的时间复杂度是：

• $\Omega(n\log_2(n))$
• $\Omega(n)$
• $O(\log_2(n))$
• $O(1)$

## Selecting the list {11, 5, 7, 13, 2, 3}. Each time the elements are selected as the largest element in the unsorted sublist in selectMax()对列表{11, 5, 7, 13, 2, 3}进行选择排序，每一次selectMax()被选为未排序子列表中最大者的元素依次为：

• 11, 5, 7, 2, 3
• 13, 7, 11, 2, 5
• 13, 11, 7, 5, 3
• 2, 11, 13, 5, 7

## Which implementation of the selectSort() algorithm is stableselectSort()算法的哪种实现是稳定的：

• Each time moves the smallest element to the front. For multiple equal minimum elements, select the one with the smallest position.每一趟将最小元素移到前方，对于多个相等的最小元素，选取其中位置最靠前者。
• Each time moves the biggest element to the front. For multiple equal maximum elements, select the one with the smallest position.每一趟将最大元素移到后方，对于多个相等的最大元素，选取其中位置最靠前者。
• Each time moves the smallest element to the front. For multiple equal minimum elements, select the one with the largest position.每一趟将最小元素移到前方，对于多个相等的最小元素，选取其中位置最靠后者。
• The above implementations are all stable以上实现皆稳定。

## For ordered subsequences (set their length to k) during insertion sorting.对于插入排序过程中的已排序子序列（设其长度为k）：

• The elements are the smallest k elements in the entire sequence其中的元素是整个序列中最小的k个元素
• The elements are the biggest k elements in the entire sequence其中的元素是整个序列中最大的k个元素
• The elements are the k elements at the front of the original sequence.其中的元素是原序列中位于前方的k个元素
• The elements are the k elements at the back of the original sequence.其中的元素是原序列中位于后方的k个元素

## The sequence {2, 7, 13, 5, 3, 19, 17} is obtained after one insertion in the insertion order, and the sorted portion has 3 elements. After 2 iterations, the result is插入排序中的某一次插入后得到序列{2, 7, 13, 5, 3, 19, 17}，此时已排序部分有3个元素。又经过2趟迭代后的结果是：

• {2, 3, 5, 7, 13, 17, 19}
• {2, 3, 5, 7, 13, 19, 17}
• {2, 5, 7, 3, 13, 19, 17}
• {2, 3, 5, 13, 7, 17, 19}

## The reverse number of a sequence $\tau$ is defined as the total number of reversed pairs in the sequence, and the total number of element comparisons performed by the insertion sort in the list of size n is:一个序列的逆序数$\tau$定义为该序列中的逆序对总数，规模为n的列表中插入排序进行的元素比较总次数为:

• $O(n + \tau\log_2(\tau))$
• $O(n+\tau)$
• $O(n^2 + \log_2(\tau))$
• $O(\tau)$

## A list of length n is equally divided into n/k segments. Each segment has a length of k. There is no reverse order for elements between different segments. The worst-case complexity for insertion sort on this list is:长度为n的列表，被等分为n/k段，每段长度为k，不同段之间的元素不存在逆序。对该列表进行插入排序的最坏时间复杂度为：

• $O(n^2)$
• $O(nk)$
• $O(n^2/k)$
• $O(n^2k)$

• 5, 4, 2, 1
• 1, 2, 4, 5
• 1
• 5, 4

• 暂无选项

## When an open parenthesis is scanned:当扫描到一个左括号时：

• Popup stack 出栈
• Enter the stack 进栈
• Skip this character 跳过该字符
• End the algorithm 算法结束

• Yes 是
• No 不是

• 暂无选项

## When does the actual calculation happen?什么时候进行实际的运算？

• Each time a new number is encountered每遇到一个新的操作数
• Each encounters a new operator每遇到一个新的操作符
• The current operator has a higher priority than the operator on the top of the stack当前的操作符比栈顶的操作符优先级高
• The current operator has a lower priority than the operator on the top of the stack当前的操作符比栈顶的操作符优先级低

## When evaluating an inverse Polish expression, when does an actual calculation occur?逆波兰表达式的求值算法中，什么时候进行一次实际的运算？

• Each time a new operand is encountered每遇到一个新的操作数
• Each encounters a new operator每遇到一个新的操作符
• The current operator has a higher priority than the top of the stack当前操作符优先级高于栈顶
• The current operator has a lower priority than the top of the stack当前操作符优先级低于栈顶

• 暂无选项

• 2, 5, 5
• 2, 3, 1
• 5, 5, 2
• 1, 3, 2

## 下The following is a vector-based implementation of the queue (for the interface and implementation of vectors refer to Chapter 2):面是队列的一种基于向量的实现(向量的接口和实现可参考第2章)：For this queue of size n, the worst-case complexity of enqueue() and dequeue() is:对于规模为n的该队列，enqueue()和dequeue()的最坏时间复杂度分别为：

• $O(n), O(n)$
• $O(1), O(1)$
• $O(n), O(1)$
• $O(n), O(\log_2(n))$

• 2
• 5
• 7
• 11

• 2
• 5
• 7
• 11

## Read the function below (where 1≤x, y≤16) and indicate its function:阅读下面函数(其中1≤x, y≤16)，指出其功能：

• Prints the y-ary representation of a decimal integer x.打印十进制整数x的y进制表示
• Print the y-ary representation of the x-ary integer 100.打印x进制整数100的y进制表示
• Print X-ary representation of a decimal number y.打印十进制整数y的x进制表示
• Print the x-ary representation of a y-ary integer 100打印y进制整数100的x进制表示

## The operations on transfer stack S when sequence {2, 3, 5, 7, 11} is shuffled to get {3, 5, 2, 11, 7}对序列{2, 3, 5, 7, 11}进行栈混洗得到{3, 5, 2, 11, 7}的过程中用于中转的栈S进行的操作是:

• push, pop, pop, push, push, pop, push, push, pop, pop
• push, push, pop, pop, pop, pop, push, push, push, pop
• push, push, pop, push, pop, pop, push, pop, pop, pop
• push, push, pop, push, pop, pop, push, push pop, pop

• {… i…j…k…}
• {… k…j…i…}
• {… k…i…j…}
• {… j…k…i…}

• ①②
• ②③
• ③④
• ②④

## In the evaluation of infix expressions, the stack of operands from the top of the stack to the bottom of the stack is:在中缀表达式求值中，某时刻运算数栈从栈顶到栈底依次为:$6， 2， 1$The stack of operators from the top of the stack to the bottom of the stack is:运算符栈从栈顶到栈底依次为:$×, +, ($The remaining pending expression is:剩下的待处理表达式为 :$)/(4×5-7)$In the following process, the stacking order of operators and the final calculation result are在接下来的过程中运算符的入栈顺序以及最终的计算结果分别为：

• $/ ( × -$ The final result is 8最终结果为8
• $) / (× -)$ The final result is 8最终结果为8
• $/ ( × -$ The final result is 1最终结果为1
• $) / (× -)$The final result is 1最终结果为1

## $(1+2×3!)/(4×5-7)$ The inverse Polish expression is (The integers in the expression are all one-digit numbers)$(1+2×3!)/(4×5-7)$的逆波兰表达式为(表达式中的整数都是一位数)

• $(1+2×3!)/ 4×5-7)$
• $/ + 1× 2 3 - × 4 5 7$
• $1 2 + × 3 ! 4 × 5 / 7 -$
• $1 2 3 ! × + 4 5 × 7 - /$

• array数组
• vector向量
• list列表
• tree树

## How many edges of the tree have n vertices?n个顶点的树有多少条边?

• $n$
• $n-1$
• $n^2$
• $2^n$

## The tree is:树是:

• Directed Connectivity Graph有向连通图
• Acyclic plan Graph无环平面图
• Connected Acyclic Graph连通无环图
• Directed acyclic graph有向无环图

## 在一棵树中,顶点p是顶点v的父亲,则它们的高度的关系是

• height(v) < height(p)
• height(v) = height(p) - 1
• height(v) = height(p) + 1
• height(p) < height(v)

• O(1)
• O(n)
• O(nlgn)
• O(n^2)

## The above tree is represented on the computer as follows:以上树在计算机中表示如下:The content of parent[] in the third line should be:第三行中parent[]的内容应该是:

• 0, 5, -1, 7, 0, 5, 4, 7, 0, 7
• -1, 5, 5, 7, 0, 4, 5, 0, 0, 7
• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• -1, 7, 5, 2, 5, 4, 1, -1, 0, 7

## How many nodes are in full binary trees of height h?高度为h的满二叉树有多少个节点?

• $2^{h+1}-1$
• $2^{h+1}$
• $2^h-1$
• $2^h$

## A true binary tree with height h and node n is characterized by:一棵高度为h,节点数为n的真二叉树的特点是:

• $h=O(\log_2(n))$
• It's really a binary tree, not any other kind of tree真的是二叉树,而不会是其他种类的树
• There is no node with only one father不存在只有一个父亲的节点
• There is no node with only one child不存在只有一个孩子的节点

## In the eldest son-brother representation, what will the eldest child of a node in the tree be equivalent to in the binary tree:在长子-兄弟表示法中,树中某节点的长子相当于二叉树中的:

• Young child幼子
• left child左子
• right child右子
• eldest son长子

## Consider a binary tree have n nodes with a height of h. Insert a new node in it, and the number of nodes whose height has changed is:设二叉树有n个节点,高度为h.在其中插入一个新的节点,高度发生改变的节点个数为:

• $O(1)$
• $O(n)$
• $O(h)$
• $O(hlog_2(n))$

• e
• g,f
• f,g
• f

## The binary tree is:二叉树是:

• Linear structure线性结构
• Semi-linear structure半线性结构
• Nonlinear structure非线性结构
• reinforced-concrete structure钢筋混凝土结构

## If in the pre-order traversal the access to the root node is followed by accessing the right subtree first and then the left subtree, then the stacking order of the left and right subtrees is:若在先序遍历中规定访问完根节点后先访问右子树再访问左子树,则左、右子树的入栈顺序是：

• Left first and then right先左后右
• Right first and then left先右后左
• In stack simultaneously同时入栈
• Only the left subtree is stacked, and the right subtree is not stacked只有左子入栈，右子不入栈

## Pre-order traversal is:先序遍历的顺序是:

• Access the nodes on the left side chain from the bottom up and access their right subtree from the bottom up先自下而上访问左侧链上的节点,再自下而上访问它们的右子树
• Visit the nodes on the left side chain from top to bottom and access their right subtree from top to bottom先自上而下访问左侧链上的节点,再自上而下访问它们的右子树
• Visit the nodes on the left side chain from top to bottom and access their right subtree from bottom to top先自上而下访问左侧链上的节点,再自下而上访问它们的右子树
• Access the nodes on the left side chain from the bottom up and access their right subtree from the top down先自下而上访问左侧链上的节点,再自上而下访问它们的右子树

## The first node visited in the in-order traversal is:中序遍历中第一个被访问的节点是:

• Leftmost node最左的节点
• Rightmost node最右的节点
• Root node根节点
• Leaf node on the left branch左侧分枝的叶节点

• d, c, f
• d, f
• f, g, d, e
• d

## The order of hierarchy traversal is:层次遍历的次序是:

• The first root and then the left and the last right先根再左子最后右子
• Left first and then right last right child先左子再根最后右子
• Top-down access to each node in depth, from left to right in nodes of the same depth自上而下访问各个深度的节点,同样深度的节点中自左向右
• Top-down access to each node in depth, from right to left in nodes of the same depth自下而上访问各个深度的节点,同样深度的节点中自左向右

• F
• F,G
• E,F
• E,F,G

## The last node in the post-order traversal sequence is:后序遍历序列中最后一个节点是：

• Root node根节点
• Leftmost node最左边的节点
• Rightmost node最右边的节点
• The deepest node深度最大的节点

## A binary tree has n nodes and its height is h. In which a new node is inserted, the maximum number of nodes that have changed in height is:某二叉树有n个节点，高度为h。在其中插入一个新的节点，高度发生改变的节点个数最多为：

• $O(1)$
• $O(n)$
• $O(h)$
• $O(hlog_2(n))$

## How many nodes could be in complete binary tree of height h?高度为 h 的完全二叉树可能有多少个节点?

• $2^{h+1}$
• $2^h$
• $2^{h-1}-1$
• $2^{h-1}$

## The following proposition of the tree, which is wrong下列关于树的命题中错误的是：

• The number of edges of a tree with n number of vertices is n-1.顶点数为n的树的边数为n-1。
• There is a unique path between any two vertices in the tree.树中任意两顶点之间存在唯一路径。
• Adding any edge in the tree destroys the structure of the tree.在树中添加任一条边都会破坏树的结构。
• Delete any edge in the tree to get the tree.在树中删除任一条边得到的还是树。

## A lookup set is a data structure used to represent disjoint sets and supports the following operations:并查集是一种用于表示不相交集合的数据结构，支持以下操作：A basic implementation is to organize the elements of each set into a rooted tree. The elements in the set are the nodes in the tree. The root of the collection is the representative element of the set. The entire search set consists of several trees. Composition of the forest. The interface implementation method is:一种基本的实现是将每一个集合中的元素组织成一棵有根树，集合中的元素即树中的节点，选取树根为该集合的代表元，而整个并查集就是由若干棵树组成的森林。接口实现的方法是：Example: In the figure below, we look at the tree {c, h, b, e} and {f, d, g} that originally represented the two collections. After calling Union(h, f), we get the right tree. At this point, calling Find(e) returns f.例子：下图中的并查集原先有两棵表示集合的树{c,h,b,e}和{f,d,g}，调用Union(h, f)后得到了右边的树，如果此时再调用Find(e)会返回f。What is the best way to look for the most concentrated tree?并查集中的树最适合用什么方法表示：

• Parent node method父节点法
• Child node method孩子节点法
• The eldest son - Brothers Act长子-兄弟法

## From the node node u of the binary tree of n nodes to the root node node by node, the following mistakes are:从n个节点的二叉树的叶节点u逐个节点地上溯到根节点的过程中，以下说法中错误的是：

• The passing nodes are all ancestors of u.经过的节点都是u的祖先。
• The worst time complexity is $O(n)$最坏时间复杂度为$O(n)$
• The path that is passed is uniquely determined经过的路径是唯一确定的
• Each time it goes up one level, the depth of the current node decreases by one and the height increases by one.每上溯一层，当前节点的深度减小1，而高度增加1。

## In order to traverse the binary tree, the successor of the node v in the order traversal is (assuming that the successor of v exists):对二叉树进行中序遍历，节点v在中序遍历下的后继为（假设v的后继存在）：

• The first visited node in its right subtree其右子树中第一个被访问的节点
• The first visited node in its left subtree其左子树中第一个被访问的节点
• The first visited node in its right subtree or an ancestor of v其右子树中第一个被访问的节点或v的某个祖先
• The first node in its right subtree or a node in its left subtree其右子树中第一个被访问的节点或其左子树中的某个节点

## Similar to pre-order and in-order traversal, accessing the binary tree in the order of left child->right child->root node is called post-order traversal. The first visited node in the post-order traversal is与先序、中序遍历类似，以左子->右子->根节点的顺序来访问二叉树称为后序遍历。后序遍历中第一个被访问的节点是：

• The deepest node in the left chain左侧链中最深的节点
• Root node根节点
• The deepest node in the right chain右侧链中最深的节点
• None of the above以上皆不是

## The binary tree is traversed in order. u and v are two nodes on the left chain, and u is the ancestor of v. x and y are the right children of u and v. The order in which these four nodes are accessed is:对二叉树进行先序遍历，u和v是左侧链上两个节点，且u是v的祖先，x、y分别是u和v的右子，试问这四个节点被访问的顺序是：

• y,v,x,u
• x,y,v,u
• u,v,y,x
• unconfirmed无法确定

## The misconception about the relationship between binary tree traversal sequences is:关于二叉树遍历序列之间关系的说法错误的是：

• Knowing the pre-order traversal sequence and the mid-order traversal sequence can determine the post-order traversal sequence已知先序遍历序列和中序遍历序列可以确定后序遍历序列
• Knowing mid-order traversal and post-order traversal sequences, we can determine the sequence of pre-order traversal已知中序遍历序列和后序遍历序列可以确定先序遍历序列
• Knowing mid-order traversal and post-order traversal sequences, we can determine the sequence of Hierarchical traversal已知中序遍历序列和后序遍历序列可以确定层次遍历序列
• Knowing pre-order traversal and post-order traversal sequences, we can determine the sequence of mid-order traversal已知先序遍历序列和后序遍历序列可以确定中序遍历序列

## When using a queue to hierarchically traverse a binary tree, the nodes in the queue at any time satisfy:借助队列对二叉树进行层次遍历时,任意时刻队列中的节点满足：

• Both are on the path from the root node to the current node均位于从根节点到当前节点的路径上
• Both are descendants of the current node均是当前节点的后代
• The difference in height does not exceed 1高度相差不超过1
• The difference in depth does not exceed 1深度相差不超过1

• connected 相连
• related 关联
• neighbor 邻居

## The one-touch-drawing question is to find out: 一笔画问题即要找出：

• Path 路径
• Euler path 欧拉路径
• Hamiltonian cycle 哈密尔顿环路
• Simple cycle 简单环路

## 06-b1-09A graph with an (undirected) edge between any two vertices is called a complete graph, and a complete graph containing n vertices is represented by $K_{n}$ Which of the following figures must not be a plan? 任何两个顶点间都有一条（无向）边的图称为完全图，包含n个顶点的完全图用$K_{n}$表示。下列哪个图一定不是平面图？

• $K_{2}$
• $K_{3}$
• $K_{4}$
• $K_{5}$

• O(1)
• O(m)
• O(n)
• O(mn)

• n+1
• 2n
• 2n-1
• 2n+1

## Traversing graphs in a sense is to translate the graph into: 对图进行遍历某种意义上是将图转化为：

• Vector向量
• List列表
• Tree树
• Binary tree二叉树

## The breadth-first search of a graph is similar to that of a binary tree: 图的广度优先搜索访问各顶点的模式类似于二叉树的：

• Pre-order traversal 先序遍历
• In-order traversal 中序遍历
• Post-order traversal 后序遍历
• Level-order traversal 层次遍历

• d, e
• e, d
• d, a
• a, d

## For graphs with n vertices and e edges implemented with adjacency list, the time complexity of BFS is:对于用邻接表实现的包含n个顶点e条边的图，BFS的时间复杂度为：

• $O(n)$
• $O(n^{2})$
• $O(n+e)$
• $O(n^{2}+e)$

## DFS on the above undigraph with A as the starting point, and the neighbors of the same vertex are in order of a~z. The order in which the vertices are accessed is: 以A为起点对以上无向图进行DFS，同一顶点的邻居以a~z为序，各顶点被访问的顺序为：

• a, e, b, c, f, g, h, j, i, d
• a, b, c, f, g, d, i, h, j, e
• a, b, e, c, f, h, g, i, d, j
• a, e, b, c, f, h, g, i, d, j

## u and v are two vertices in the graph. After performing DFS on the graph, dTime(u) < dTime(v) < fTime(v) < fTime(u), then the relationship between u and v in the DFS forest is: u 和 v 为图中两个顶点，对图进行 DFS 后，dTime(u) < dTime(v) < fTime(v) < fTime(u)，则 u 和 v 在 DFS 森林中的关系是：

• Belong to different connected components 属于不同的连通分量
• u is the ancestor of v u 为 v 的祖先
• v is the ancestor of u v 为 u 的祖先
• u and v are siblings 互为兄弟

## Run breadth-first search (BFS) and depth-first search (DFS) respectively on the same undirected graph, the numbers of TREE edges satisfy: 对同一个无向图分别运行广度优先算法和深度优先算法，得到的树边数量：

• BFS results in more TREE edges广度优先的树边更多
• DFS results in more TREE edges深度优先的树边更多
• they result in same number of TREE edges两种算法得到的树边一样多
• uncertainty in quantitative relationship数量关系不确定

## DFS on a graph, which situation means that the graph contains a loop 对图进行DFS，一下哪种情况意味着该图包含环路

• There has a TREE edge 有TREE边
• There has a BACKWARD edge 有BACKWARD边
• There has a FORWARD edge 有FORWARD边
• There has a CROSS edge 有CROSS边

• 暂无选项

• 暂无选项

## （接上题）In the long history of humanity, everyone may have to shake hands with other people. If someone makes an odd number of handshakes in his life, he is called a Class A person, otherwise he is called a Class B person. The number of people of type A since ancient times is: (assuming that humans can only shake hands with humans)在人类的历史长河中，每个人都可能要与其他人握手。如果某人在他的一生中进行握手的次数为奇数，则称他为A类人，否则称为B类人。试问从古至今A类人的个数是：(假设人类只能和人类握手)

• Even number偶数
• Odd number奇数
• Prime number 素数
• Complete square number 完全平方数

## For a simple undigraph with n vertices and e edges, which of the following argument for its adjacency matrix A is wrong: 对于包含n个顶点e条边的简单无向图，以下关于它的邻接矩阵A的说法中错误的是：

• A has n rows and e columns, where the elements take a value of {0, 1} A有n行e列，其中元素取值于{0, 1}
• The number of 1 in the kth row of A is equal to the degree of vertex k A的第k行中1的个数等于顶点k的度
• $A=A^{T}$
• The element in row A and column V in A is 1 if and only if vertex u is associated with vertex v A中位于第u行v列的元素为1当且仅当顶点u和顶点v邻接

## G is a simple undigraph, A is an adjacency matrix of G, M is an associative matrix of G, and D is a diagonal matrix of the degree of the i-th element of the vertex on the diagonal. Their relationship is: G是简单无向图，A为G的邻接矩阵，M为G的关联矩阵，D是对角线上第i个元素为顶点i的度的对角矩阵,它们的关系是：

• $A=M$
• $A+D=MM^{T}$
• $A+D=M^{T}M$
• Not direct relationship 没有直接关系

• O(1)
• O(n)
• O(nlgn)
• O(n^2)

• O(1)
• O(n)
• O(nlgn)
• O(n^2)

• O(1)
• O(n)
• O(nlgn)
• O(n^2)

• O(1)
• O(n)
• O(nlgn)
• O(n^2)

## G is a directed acyclic graph, and (u, v) is an edge in G that points from u to v. The result of DFS on G is: G是有向无环图，(u, v)是G中的一条由u指向v的边。对G进行DFS的结果是：

• dTime(u) > dTime(v)
• dTime(u) < dTime(v)
• fTime(u) > fTime(v)
• fTime(u) < fTime(v)

• 暂无选项

• 暂无选项