算法竞赛基础训练题_判断题_if a directed graph g=(v, e) is weakly connected,

算法竞赛基础训练题

判断题

The major task of algorithm analysis is to analyze the time complexity and the space complexity. 算法分析的主要任务是分析时间复杂度和空间复杂度。T

For 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)。 T

In 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. “循环队列”被定义为由循环链表或循环数组实现的队列。 F

In a circular queue which is implemented by an array, the front value must always be no larger than the rear value. 在由数组实现的循环队列中，前值必须永远不大于后值。 F

The 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 F

In a connected graph, there exists at least one vertex of which the degree is 1. 在连通图中，至少存在一个度为1的顶点。 F

If a graph is represented by adjacency lists, then the space taken depends only on the number of vertices, not the number of edges. 如果一个图是用邻接表表示的，那么所占用的空间只取决于顶点的数量，而不是边的数量。 F

If a graph is represented by an adjacency matrix, then the space taken depends only on the number of vertices, not the number of edges. 如果一个图是用邻接矩阵表示的，那么所占用的空间只取决于顶点的数量，而不是边的数量。 T

In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. 在有向图中，所有顶点的入度和出度之和是总边数的两倍。 T

In 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)。 T

To sort N records, heap sort requires at least O(N) extra space. 为了对N条记录进行排序，堆排序至少需要O(N)个额外的空间。 F

To 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)。T

To sort N records by quick sort, the worst-case time complexity is O(NlogN). 对N条记录进行快速排序，最坏情况下时间复杂度为O(NlogN)。 F
*Shell sort is stable. 希尔排序是稳定的 F

To sort N distinct records by bubble sort, the number of record swaps must reach its maximum when the original sequence is almost in sorted order. 要按冒泡排序对N条不同的记录进行排序，当原始序列几乎是有序的时，交换记录的数量必须达到最大。 F

In a hash table, “synonyms”(同义词) means two elements sharing the same hash value. 在一个哈希表,“同义词”(同义词)意味着两个元素共享相同的散列值。 T

In a hash table, “synonyms”(同义词) means two elements being hashed into the same slot by two different hash functions. 在一个哈希表,“同义词”(同义词)意味着两个元素被散列到相同的位置由两个不同的哈希函数。 F

If quadratic probing is used to resolve collisions, then a new insertion must be successful if the size of the hash table is a prime. 如果使用二次探测来解决冲突，那么如果哈希表的大小是素数，则新的插入必须成功。 F

Store 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。 T

In hashing, functions “insert” and “find” have the same time complexity. 在哈希中，函数“insert”和“find”具有相同的时间复杂度。 T

It is still possible to have a collision even if we hash only 2 elements into a hash table of 100 cells. 即使我们将2个元素散列到包含100个单元格的哈希表中，仍然有可能发生碰撞。 T

If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. 如果一个线性链表用一个链表表示，那么内存中元素的地址必须是连续的。 F

For any node in an AVL tree, the height of the left subtree must be greater than that of the right subtree. 对于AVL树中的任何节点，左子树的高度必须大于右子树的高度 F

For any node in an AVL tree, the height of the right subtree must be greater than that of the left subtree. 对于AVL树中的任何节点，右子树的高度必须大于左子树的高度。 F

For any node in an AVL tree, the left and right subtrees must have the same height. 对于AVL树中的任何节点，左子树和右子树必须具有相同的高度。 F

If a problem can be solved by dynamic programming, it must be solved in polynomial time. 如果一个问题可以用动态规划方法求解，那么它必须在多项式时间内求解。 F

Greedy algorithm works only if the local optimum is equal to the global optimum. 贪婪算法只有在局部最优值等于全局最优值时才有效。 T

For finding an optimal binary search tree, we can use the same greedy algorithm as the one for building a Huffman tree. 为了找到最优二叉搜索树，我们可以使用与构建哈夫曼树相同的贪婪算法。F

Let S be the set of activities in Activity Selection Problem. Then the earliest finish activity am must be included in all the maximum-size subset of mutually compatible activities of S. 设S为活动选择问题中的活动集合。 那么，最早完成的活动am必须包含在S的所有相互兼容的活动的最大大小子集中 F

An 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 mutually compatible 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 some maximum-size subset of mutually compatible activities of S. 设S为活动选择问题中的活动集合。 那么最早的启动活动必须包含在S的相互兼容的活动的某个最大大小子集中 F

The best case time complexity of sorting algorithms based only on comparisons is at least O(NlogN). 在最好的情况下，只基于比较的排序算法的时间复杂度至少为O(NlogN)。 F

An algorithm to check for balancing symbols in an expression uses a queue to store the partial expression. 检查表达式中是否平衡符号的算法使用队列来存储部分表达式 F

An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. 检查表达式中符号是否平衡的算法使用堆栈来存储符号。T

Prim’s algorithm is to maintain a forest and to merge two trees into one at each stage. 普里姆的算法是维护森林，并在每个阶段将两棵树合并为一棵树。 F

Kruskal’s algorithm is to maintain a forest and to merge two trees into one at each stage. Kruskal的算法是维护一个森林，并在每个阶段将两棵树合并成一棵树。 T

Kruskal’s algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree in each stage. Kruskal的算法是通过在每个阶段向树中添加一条边，从而增加一个相关的顶点来增长最小生成树。 F

Prim’s algorithm is to grow the minimum spanning tree by adding one edge, and thus an associated vertex, to the tree in each stage. 普里姆的算法是通过在每一阶段向树中添加一条边，从而增加一个相关的顶点来增长最小生成树。 T

To 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 the latest” is correct for finding a maximum-size subset of mutually compatible activities of S. 设S为活动选择问题中的活动集合。 “收集最新开始的活动”的贪心规则对于找到S中相互兼容的活动的最大大小子集是正确的 T

O(N^2) is the same as O(1+2+3+⋯+N). T

After the first run of Bubble Sort, it is possible that no element is placed in its final position. 在第一次执行冒泡排序之后，可能没有元素被放置在其最终位置。 F

After 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, Heap Sort 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 only by 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 the number 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 latest start 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 the shortest lasting time. Then am must be included in some maximum-size subset of mutually compatible activities of S. 在活动选择问题中，考虑活动S的任何非空集，设am为S中持续时间最短的活动。那么am必须包含在S相互兼容的活动的某个最大大小子集中 F

Mergesort is stable. 归并排序是稳定的。 T

// the average time complexity of the travesal of a binary tree with n nodes is O(n). n个节点的二叉树的平均遍历时间复杂度为O(n)。 F

the average time complexity of the travesal of a binary tree with n nodes is O(logn). n个节点的二叉树的平均遍历时间复杂度为O(logn)。 T

For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. 对于一个图，如果每个顶点都是偶数度，我们可以找到一个欧拉回路，它恰好访问每个顶点一次。 F

For a graph, if each vertex has an even degree or only two vertexes have odd degree, we can find a cycle that visits every edge exactly once . 对于一个图，如果每个顶点都是偶数度，或者只有两个顶点是奇数度，我们可以找到一个循环，它恰好访问每条边一次。F

Linear probing is equivalent to double hashing with a secondary hash function of Hash2(k)=1 . 线性探测相当于使用Hash2(k)=1的二次哈希函数进行二次哈希。T

Quadratic 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)。 F

ADT is the abbreviation for Abstract Data Type in the textbook of data structures. ADT是《数据结构》教材中“抽象数据类型”的缩写。 T

If a linear list is represented by a 1-dimensional array, the addresses of the elements in the memory must be consecutive. 如果线性列表用一维数组表示，那么内存中元素的地址必须是连续的。T

During the sorting, processing every element which is not yet at its final position is called a “run”. To sort a list of integers using 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 of integers using quick sort, it may reduce the total number of recursions by processing the large partion first in each run. 在排序过程中，处理尚未到达最终位置的每个元素称为“运行”。 为了使用快速排序对整数列表进行排序，它可以在每次运行中先处理大分区，从而减少递归的总数。 F

It is always possible to represent a tree by a one-dimensional integer array. 总是可以用一维整数数组来表示树。 T

The 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 the number of 1-degree nodes. 二叉树的叶节点数只与2度节点数相关，与1度节点数无关。 T

In 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之前。 F

In 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之前。 T

There must be a collision if we insert a new element into a hash table with the loading density being 1. 如果我们在加载密度为1的哈希表中插入一个新元素，就一定会发生碰撞。 T

The 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). F

Non recursive programs are generally faster than equivalent recursive programs. However, recursive programs are in general much simpler and easier to understand. 非递归程序通常比等效的递归程序快。 然而，递归程序通常要简单得多，也更容易理解。 T

// Recursive programs are generally faster than equivalent non recursive programs. However, non recursive programs are in general much simpler and easier to understand. 递归程序通常比等效的非递归程序快。 然而，非递归程序通常要简单得多，也更容易理解。 F

If 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|条边 F

For the extra space taken by an internal sorting algorithm, we have: heap sort < quick sort < merge sort. 对于内部排序算法占用的额外空间，我们有:堆排序<快速排序<归并排序。 T

For the extra space taken by an internal sorting algorithm, we have: heap sort < merge sort < quick sort. 对于内部排序算法占用的额外空间，我们有:堆排序<归并排序<快速排序。 F

An algorithm may or may not require input, but each algorithm is expected to produce at least one result as the output. 一个算法可能需要输入，也可能不需要输入，但是每个算法至少要产生一个结果作为输出。 T

NlogN^2 and NlogN^3 have the same speed of growth. T

For a sequentially stored linear list of length N, the time complexities for deleting the last element and inserting the first element are O(1) and O(N), respectively. 对于长度为N的顺序存储线性列表，删除最后一个元素和插入第一个元素的时间复杂度分别为O(1)和O(N)。 T

For a sequentially stored linear list of length N, the time complexities for random query and inserting the first element are O(N) and O(1), respectively. 对于长度为N的顺序存储线性列表，随机查询和插入第一个元素的时间复杂度分别为O(N)和O(1)。 F

The time comlexity of Selection Sort will be the same no matter we store the elements in an array or a linked list. 无论我们将元素存储在数组还是链表中，选择排序的时间复杂度都是相同的。 T

The time comlexity of Binary Search will be the same no matter we store the elements in an array or a linked list. 无论我们将元素存储在数组还是链表中，二分搜索的时间复杂度都是相同的。 F

There are more NULL pointers than the actual pointers in the linked representation of any binary tree. 在任何二叉树的链接表示法中，NULL指针比实际指针要多。 T

The 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) F

The 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)。 T

Consider two programs with time complexities being T1=O(2^n) and T2=O(n). then program 2 must run faster than program 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 a stack. 大多数餐馆都遵循“先到先得”的原则。 这个原则可以通过堆栈来实现。 F

In most restaurants, we follow one principle called “First come, first served”. This principle can be implemented by a queue. 大多数餐馆都遵循“先到先得”的原则。 这个原则可以通过队列来实现。 T

// The storage size of a graph using the adjacency matrix is only related to the number of vertices but has nothing to do with 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 with the 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 every vertex 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 every vertex exactly once by starting from one of its odd-degree vertices. 对于连通图，如果恰好有两个顶点为奇数度，我们可以找到一个欧拉遍历，从其中一个奇数度顶点出发，恰好访问每个顶点一次。 F

In a greedy algorithm, a decision made in one stage is not changed in a later stage. 在贪心算法中，某一阶段的决策不会在以后的阶段发生改变。 T

To prove the correctness of a greedy algorithm, we must prove that an optimal solution to the original problem always makes the greedy choice, so that the greedy choice is always safe. 为了证明贪婪算法的正确性，我们必须证明原问题的一个最优解总是做出贪婪选择，从而使贪婪选择总是安全的。 F

A 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问题的子集。 F

If any NP-complete problem can be solved in polynomial time, then all the problems in NP can be solved in polynomial time. 如果任何NP完备问题都能在多项式时间内求解，那么所有NP问题都能在多项式时间内求解。 T

When 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个元素被推入一个堆栈时，它们可能会以不同的顺序弹出。 但是如果它们被插入到队列中，它们将总是按照插入的顺序被删除。 T

Depth-first search on a graph is a generalization of preorder traversal on a tree. The difference is that when dealing with a graph, we need to avoid cycles. 图上的深度优先搜索是对树的前序遍历的一种推广。 不同之处在于，在处理图形时，我们需要避免循环。 T

There are more NULL pointers than the actual pointers in the linked representation of any tree of degree k (≥2). 在任何k度(≥2)的树的链接表示中，NULL指针比实际指针要多。 T

To sort N records by quick sort, the worst-case time complexity is Ω(NlogN). 对N条记录进行快速排序，最坏情况下时间复杂度为Ω(NlogN)。 T