2023年7月29日发(作者：)

算法竞赛基础训练题_判断题算法竞赛基础训练题判断题The major task of algorithm analysis is to analyze the time complexity and the space complexity. 算法分析的主要任务是分析时间复杂度和空间复杂度。TFor a sequentially stored linear list of length N, the time complexities for query and insertion are O(1) and O(N),respectively. 对于长度为N的顺序存储线性列表，查询和插⼊的时间复杂度分别为O(1)和O(N)。 TIn a singly linked list of N nodes, the time complexities for query and insertion are O(1) and O(N), respectively. 在N个节点的单链表中，查询和插⼊的时间复杂度分别为O(1)和O(N)。F“Circular Queue” is defined to be a queue implemented by a circularly linked list or a circular array. “循环队列”被定义为由循环链表或循环数组实现的队列。 FIn a circular queue which is implemented by an array, the front value must always be no larger than the rear value. 在由数组实现的循环队列中，前值必须永远不⼤于后值。 FThe sum of the degrees of all the vertices in a connected graph must be an even number. 连通图中所有顶点的度数之和必须是偶数。 T// In a connected graph, the number of edges must be greater than the number of vertices minus 1. 在连通图中，边的个数必须⼤于顶点的个数减1 FIn a connected graph, there exists at least one vertex of which the degree is 1. 在连通图中，⾄少存在⼀个度为1的顶点。 FIf a graph is represented by adjacency lists, then the space taken depends only on the number of vertices, not the numberof edges. 如果⼀个图是⽤邻接表表⽰的，那么所占⽤的空间只取决于顶点的数量，⽽不是边的数量。 FIf a graph is represented by an adjacency matrix, then the space taken depends only on the number of vertices, not thenumber of edges. 如果⼀个图是⽤邻接矩阵表⽰的，那么所占⽤的空间只取决于顶点的数量，⽽不是边的数量。 TIn a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. 在有向图中，所有顶点的⼊度和出度之和是总边数的两倍。 TIn a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. 在有向图中，⼊度之和必须等于所有顶点出度之和。 T// The best “worst-case time complexity” for any algorithm that sorts by comparisons only must be O(NlogN). 对于任何只通过⽐较排序的算法来说，最好的“最坏情况时间复杂度”必须是O(NlogN)。 TTo sort N records, heap sort requires at least O(N) extra space. 为了对N条记录进⾏排序，堆排序⾄少需要O(N)个额外的空间。 FTo sort N records by simple selection sort, the numbers of comparisons and record movements are O(N^2) and O(N),respectively. 对N个记录进⾏简单选择排序，⽐较次数和记录移动次数分别为O(N²)和O(N)。TTo sort N records by quick sort, the worst-case time complexity is O(NlogN). 对N条记录进⾏快速排序，最坏情况下时间复杂度为O(NlogN)。 F*Shell sort is stable. 希尔排序是稳定的 FTo sort N distinct records by bubble sort, the number of record swaps must reach its maximum when the original sequenceis almost in sorted order. 要按冒泡排序对N条不同的记录进⾏排序，当原始序列⼏乎是有序的时，交换记录的数量必须达到最⼤。 FIn a hash table, “synonyms”(同义词) means two elements sharing the same hash value. 在⼀个哈希表,“同义词”(同义词)意味着两个元素共享相同的散列值。 TIn a hash table, “synonyms”(同义词) means two elements being hashed into the same slot by two different hash functions.在⼀个哈希表,“同义词”(同义词)意味着两个元素被散列到相同的位置由两个不同的哈希函数。 FIf quadratic probing is used to resolve collisions, then a new insertion must be successful if the size of the hash table is aprime. 如果使⽤⼆次探测来解决冲突，那么如果哈希表的⼤⼩是素数，则新的插⼊必须成功。 FStore M elements in a hash table which is represented by an array of size S, the loading density is then M/S. 将M个元素存储在哈希表中，哈希表由⼤⼩为S的数组表⽰，加载密度为M/S。 TIn hashing, functions “insert” and “find” have the same time complexity. 在哈希中，函数“insert”和“find”具有相同的时间复杂度。 TIt is still possible to have a collision even if we hash only 2 elements into a hash table of 100 cells. 即使我们将2个元素散列到包含100个单元格的哈希表中，仍然有可能发⽣碰撞。 TIf a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. 如果⼀个线性链表⽤⼀个链表表⽰，那么内存中元素的地址必须是连续的。 FFor any node in an AVL tree, the height of the left subtree must be greater than that of the right subtree. 对于AVL树中的任何节点，左⼦树的⾼度必须⼤于右⼦树的⾼度 FFor any node in an AVL tree, the height of the right subtree must be greater than that of the left subtree. 对于AVL树中的任何节点，右⼦树的⾼度必须⼤于左⼦树的⾼度。 FFor any node in an AVL tree, the left and right subtrees must have the same height. 对于AVL树中的任何节点，左⼦树和右⼦树必须具有相同的⾼度。 FIf a problem can be solved by dynamic programming, it must be solved in polynomial time. 如果⼀个问题可以⽤动态规划⽅法求解，那么它必须在多项式时间内求解。 FGreedy algorithm works only if the local optimum is equal to the global optimum. 贪婪算法只有在局部最优值等于全局最优值时才有效。 TFor finding an optimal binary search tree, we can use the same greedy algorithm as the one for building a Huffman tree. 为了找到最优⼆叉搜索树，我们可以使⽤与构建哈夫曼树相同的贪婪算法。FLet S be the set of activities in Activity Selection Problem. Then the earliest finish activity am must be included in all themaximum-size subset of mutually compatible activities of S. 设S为活动选择问题中的活动集合。 那么，最早完成的活动am必须包含在S的所有相互兼容的活动的最⼤⼤⼩⼦集中 FAn AVL tree that all the balance factors of non-leaf nodes are 0 must be a perfect binary tree. 所有⾮叶节点的平衡因⼦均为0的AVL树必定是⼀棵完美⼆叉树。T// Let S be the set of activities in Activity Selection Problem. Then there must be some maximum-size subset of mutuallycompatible activities of S that includes the earliest finish activity am. 设S为活动选择问题中的活动集合。 然后，S的相互兼容的活动必须有⼀个最⼤⼤⼩的⼦集，其中包括最早完成的活动am。 T// Let S be the set of activities in Activity Selection Problem. Then the earliest start activity as must be included in somemaximum-size subset of mutually compatible activities of S. 设S为活动选择问题中的活动集合。 那么最早的启动活动必须包含在S的相互兼容的活动的某个最⼤⼤⼩⼦集中 FThe best case time complexity of sorting algorithms based only on comparisons is at least O(NlogN). 在最好的情况下，只基于⽐较的排序算法的时间复杂度⾄少为O(NlogN)。 FAn algorithm to check for balancing symbols in an expression uses a queue to store the partial expression. 检查表达式中是否平衡符号的算法使⽤队列来存储部分表达式 FAn algorithm to check for balancing symbols in an expression uses a stack to store the symbols. 检查表达式中符号是否平衡的算法使⽤堆栈来存储符号。TPrim’s algorithm is to maintain a forest and to merge two trees into one at each stage. 普⾥姆的算法是维护森林，并在每个阶段将两棵树合并为⼀棵树。 FKruskal’s algorithm is to maintain a forest and to merge two trees into one at each stage. Kruskal的算法是维护⼀个森林，并在每个阶段将两棵树合并成⼀棵树。 TKruskal’s algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the treein each stage. Kruskal的算法是通过在每个阶段向树中添加⼀条边，从⽽增加⼀个相关的顶点来增长最⼩⽣成树。 FPrim’s algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree ineach stage. 普⾥姆的算法是通过在每⼀阶段向树中添加⼀条边，从⽽增加⼀个相关的顶点来增长最⼩⽣成树。 TTo sort N records by merge sort, the best-case time complexity and worst-case time complexity are both O(NlogN). 对N条记录进⾏归并排序，最佳和最坏情况时间复杂度均为O(NlogN)。 T// Let S be the set of activities in Activity Selection Problem. The greedy rule of “collecting the activity that starts thelatest” is correct for finding a maximum-size subset of mutually compatible activities of S. 设S为活动选择问题中的活动集合。“收集最新开始的活动”的贪⼼规则对于找到S中相互兼容的活动的最⼤⼤⼩⼦集是正确的 TO(N^2) is the same as O(1+2+3+…+N). TAfter the first run of Bubble Sort, it is possible that no element is placed in its final position. 在第⼀次执⾏冒泡排序之后，可能没有元素被放置在其最终位置。 FAfter the first run of Insertion Sort, it is possible that no element is placed in its final position. 在第⼀次执⾏插⼊排序之后，可能没有元素被放置在其最终位置。 T// If there are less than 20 inversions in an integer array, then Insertion Sort will be the best method among Quick Sort,Heap Sort and Insertion Sort. 如果在⼀个整数数组中有少于20个逆序，那么插⼊排序将是快速排序、堆排序和插⼊排序中最好的⽅法。T**// If there are less than 20 inversions in an integer array, the Quick Sort will be the best method among Quick Sort, HeapSort and Insertion Sort. 如果在⼀个整数数组中有少于20个逆序，快速排序将是快速排序、堆排序和插⼊排序中最好的⽅法。 F// If devide-and-conquer strategy is used to find the closest pair of points in a plane, unless the points are sorted not onlyby their x coordinates but also by their y coordinates, it would be impossible to solve it in a time of O(NlogN), where N is thenumber of points. 如果分治策略是⽤来找到最接近的⼀对点飞机,除⾮点排序不仅通过他们的x坐标还y坐标,它是不可能解决在O (NlogN),其中N是点的数量。 T// In the Activity Selection problem, consider any non-empty set of activities S, and let am be an activity in S with

the lateststart time. Then am must be included in some maximum-size subset of mutually compatible activities of S. 在活动选择问题中，考虑活动S的任何⾮空集合，设am为S中的⼀个活动，其最晚开始时间为。 那么am必须包含在S相互兼容的活动的某个最⼤⼤⼩⼦集中 T// In the Activity Selection problem, consider any non-empty set of activities S, and let am be an activity in S with theshortest lasting time. Then am must be included in some maximum-size subset of mutually compatible activities of S. 在活动选择问题中，考虑活动S的任何⾮空集，设am为S中持续时间最短的活动。那么am必须包含在S相互兼容的活动的某个最⼤⼤⼩⼦集中FMergesort is stable. 归并排序是稳定的。 T// the average time complexity of the travesal of a binary tree with n nodes is O(n). n个节点的⼆叉树的平均遍历时间复杂度为O(n)。 Fthe average time complexity of the travesal of a binary tree with n nodes is O(logn). n个节点的⼆叉树的平均遍历时间复杂度为O(logn)。 TFor a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. 对于⼀个图，如果每个顶点都是偶数度，我们可以找到⼀个欧拉回路，它恰好访问每个顶点⼀次。 FFor a graph, if each vertex has an even degree or only two vertexes have odd degree, we can find a cycle that visits everyedge exactly once . 对于⼀个图，如果每个顶点都是偶数度，或者只有两个顶点是奇数度，我们可以找到⼀个循环，它恰好访问每条边⼀次。FLinear probing is equivalent to double hashing with a secondary hash function of Hash2(k)=1 . 线性探测相当于使⽤Hash2(k)=1的⼆次哈希函数进⾏⼆次哈希。TQuadratic probing is equivalent to double hashing with a secondary hash function of Hash2(k)=k. ⼆次探测等价于⼆次哈希，⼆次哈希函数为Hash2(k)=k。F// In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2, but not O(logN). 在Union/Find算法中，如果按⼤⼩进⾏Union，则任何节点的深度不能⼤于N/2，但不能⼤于O(logN)。 FADT is the abbreviation for Abstract Data Type in the textbook of data structures. ADT是《数据结构》教材中“抽象数据类型”的缩写。 TIf a linear list is represented by a 1-dimensional array, the addresses of the elements in the memory must be consecutive. 如果线性列表⽤⼀维数组表⽰，那么内存中元素的地址必须是连续的。TDuring the sorting, processing every element which is not yet at its final position is called a “run”. To sort a list of integersusing quick sort, it may reduce the total number of recursions by processing the small partion first in each run. 在排序过程中，处理尚未到达最终位置的每个元素称为“运⾏”。 要使⽤快速排序对整数列表进⾏排序，它可以通过在每次运⾏中先处理⼩分区来减少递归的总数。 F// During the sorting, processing every element which is not yet at its final position is called a “run”. To sort a list ofintegers using quick sort, it may reduce the total number of recursions by processing the large partion first in each run. 在排序过程中，处理尚未到达最终位置的每个元素称为“运⾏”。 为了使⽤快速排序对整数列表进⾏排序，它可以在每次运⾏中先处理⼤分区，从⽽减少递归的总数。 FIt is always possible to represent a tree by a one-dimensional integer array. 总是可以⽤⼀维整数数组来表⽰树。 TThe number of leaf nodes in a binary tree is only related to the number of 2-degree nodes , i.e it has nothing to do with thenumber of 1-degree nodes. ⼆叉树的叶节点数只与2度节点数相关，与1度节点数⽆关。 TIn a binary tree, if node A is an ancestor of node B, then A must precede B in the inorder traversal sequence. 在⼆叉树中，如果节点a是节点B的祖先，那么在中序遍历序列中，a必须在B之前。 FIn a binary tree, if node A is a descendant of node B, A may precede B in the inorder traversal sequence. 在⼀棵⼆叉树中，如果节点a是节点B的后代，则在中序遍历序列中，a可以在B之前。 TThere must be a collision if we insert a new element into a hash table with the loading density being 1. 如果我们在加载密度为1的哈希表中插⼊⼀个新元素，就⼀定会发⽣碰撞。 TThe class of languages decided by polynomial-time algorithms is a subset of the class of languages accepted by polynomial-time algorithms. 由多项式时间算法决定的⼀类语⾔是被多项式时间算法接受的⼀类语⾔的⼦集。 T// 序列{1,2,3,4,5}依次⼊栈，则不可能得到{3,4,1,2,5}的出栈序列。序列{1,2,3,4,5}依次⼊栈,则不可能得到{3、4、1、2、5}的出栈序列。 T// n^0.01 is O(logn). FNon recursive programs are generally faster than equivalent recursive programs. However, recursive programs are ingeneral much simpler and easier to understand. ⾮递归程序通常⽐等效的递归程序快。 然⽽，递归程序通常要简单得多，也更容易理解。 T// Recursive programs are generally faster than equivalent non recursive programs. However, non recursive programs arein general much simpler and easier to understand. 递归程序通常⽐等效的⾮递归程序快。 然⽽，⾮递归程序通常要简单得多，也更容易理解。 FIf a directed graph G=(V, E) is strongly connected, then there must be at least 2|V|-2 edges in G. 如果有向图G=(V, E)是强连通的，则在G中⾄少存在2条|V|-2边 F// If a directed graph G=(V, E) is weakly connected, then there must be at least |V| edges in G. 如果有向图G=(V, E)是弱连通的，则G. F中⾄少存在|V|条边 FFor the extra space taken by an internal sorting algorithm, we have: heap sort < quick sort < merge sort. 对于内部排序算法占⽤的额外空间，我们有:堆排序<快速排序<归并排序。 TFor the extra space taken by an internal sorting algorithm, we have: heap sort < merge sort < quick sort. 对于内部排序算法占⽤的额外空间，我们有:堆排序<归并排序<快速排序。 FAn algorithm may or may not require input, but each algorithm is expected to produce at least one result as the output. ⼀个算法可能需要输⼊，也可能不需要输⼊，但是每个算法⾄少要产⽣⼀个结果作为输出。 TNlogN^2 and NlogN^3 have the same speed of growth. TFor a sequentially stored linear list of length N, the time complexities for deleting the last element and inserting the firstelement are O(1) and O(N), respectively. 对于长度为N的顺序存储线性列表，删除最后⼀个元素和插⼊第⼀个元素的时间复杂度分别为O(1)和O(N)。 TFor a sequentially stored linear list of length N, the time complexities for random query and inserting the first element areO(N) and O(1), respectively. 对于长度为N的顺序存储线性列表，随机查询和插⼊第⼀个元素的时间复杂度分别为O(N)和O(1)。 FThe time comlexity of Selection Sort will be the same no matter we store the elements in an array or a linked list. ⽆论我们将元素存储在数组还是链表中，选择排序的时间复杂度都是相同的。 TThe time comlexity of Binary Search will be the same no matter we store the elements in an array or a linked list. ⽆论我们将元素存储在数组还是链表中，⼆分搜索的时间复杂度都是相同的。 FThere are more NULL pointers than the actual pointers in the linked representation of any binary tree. 在任何⼆叉树的链接表⽰法中，NULL指针⽐实际指针要多。 TThe average run time and the extra space of Quicksort for sorting n elements are O(nlogn) and O(1), respectively. 快速排序对n个元素进⾏排序的平均运⾏时间和额外空间分别为O(nlogn)和O(1) FThe average run time and the extra space of Heapsort for sorting n elements are O(nlogn) and O(1), respectively. 对n个元素进⾏堆排序的平均运⾏时间和额外空间分别为O(nlogn)和O(1)。 TConsider two programs with time complexities being T1=O(2^n) and T2=O(n). then program 2 must run faster thanprogram 1. 考虑两个时间复杂性为T1=O(2^n)和T2=O(n)的程序。 那么程序2必须⽐程序1运⾏得快。 F// In most restaurants, we follow one principle called “First come, first served”. This principle can be implemented by astack. ⼤多数餐馆都遵循“先到先得”的原则。 这个原则可以通过堆栈来实现。 FIn most restaurants, we follow one principle called “First come, first served”. This principle can be implemented by aqueue. ⼤多数餐馆都遵循“先到先得”的原则。 这个原则可以通过队列来实现。 T// The storage size of a graph using the adjacency matrix is only related to the number of vertices but has nothing to dowith the number of edges. 使⽤邻接矩阵的图的存储⼤⼩只与顶点的数量有关，与边的数量⽆关。 T// The storage size of a graph using the adjacency list is only related to the number of vertices but has nothing to do withthe number of edges. 使⽤邻接表的图的存储⼤⼩只与顶点的数量有关，与边的数量⽆关。 F// For a connected graph, if there are exactly two vertices having odd degree, we can find an Euler circuit that visits everyvertex exactly once by starting from one of its odd-degree vertices. 对于连通图，如果恰好有两个顶点为奇数度，我们可以找到⼀个欧拉回路，它从其中⼀个奇数度顶点开始，恰好访问每个顶点⼀次。 F// For a connected graph, if there are exactly two vertices having odd degree, we can find an Euler tour that visits everyvertex exactly once by starting from one of its odd-degree vertices. 对于连通图，如果恰好有两个顶点为奇数度，我们可以找到⼀个欧拉遍历，从其中⼀个奇数度顶点出发，恰好访问每个顶点⼀次。 FIn a greedy algorithm, a decision made in one stage is not changed in a later stage. 在贪⼼算法中，某⼀阶段的决策不会在以后的阶段发⽣改变。 TTo prove the correctness of a greedy algorithm, we must prove that an optimal solution to the original problem alwaysmakes the greedy choice, so that the greedy choice is always safe. 为了证明贪婪算法的正确性，我们必须证明原问题的⼀个最优解总是做出贪婪选择，从⽽使贪婪选择总是安全的。 FA binary tree that is not full cannot correspond to an optimal prefix code. ⾮满的⼆叉树不能对应于最优前缀代码。 T// NP-hard problems and NP-complete problems are the subsets of NP problems. NP困难问题和NP完全问题是NP问题的⼦集。FIf any NP-complete problem can be solved in polynomial time, then all the problems in NP can be solved in polynomial time.如果任何NP完备问题都能在多项式时间内求解，那么所有NP问题都能在多项式时间内求解。 TWhen n elements are pushed into a stack, they may be popped in a different order. But if they are inserted into a queue,they will always be deleted in the same order as the insertions. 当n个元素被推⼊⼀个堆栈时，它们可能会以不同的顺序弹出。 但是如果它们被插⼊到队列中，它们将总是按照插⼊的顺序被删除。 TDepth-first search on a graph is a generalization of preorder traversal on a tree. The difference is that when dealing with agraph, we need to avoid cycles. 图上的深度优先搜索是对树的前序遍历的⼀种推⼴。 不同之处在于，在处理图形时，我们需要避免循环。 TThere are more NULL pointers than the actual pointers in the linked representation of any tree of degree k (≥2). 在任何k度(≥2)的树的链接表⽰中，NULL指针⽐实际指针要多。 TTo sort N records by quick sort, the worst-case time complexity is Ω(NlogN). 对N条记录进⾏快速排序，最坏情况下时间复杂度为Ω(NlogN)。 T