8fddfea5-777d-4abb-ab47-fb93af3e8aa6.pdf
第 1 页 共 12 页 上海 科技大学 2018 年 攻读硕士学位研究生 招生 考试试题 科目代码 : 991 科目 名称: 数据结构与算法 考生 须知: 1. 本试卷 满分为 150 分 ,全部考试时间总计 180 分钟 。 2. 所有 答案必须写在答题纸上,写在试题纸上或草稿纸上一律无效。 3. 每道题的中文部分均已翻译为英文,考生可在中英文中任选一种语言作答 。 1. True or False (5 problems, 2 points each) 判断题( 5 题,每题 2 分) Please indicate in the answer sheet whether each statement is true or false. Write down “T” for being true and “F” for being false. 请在答题纸上写明下列每个命题的真假。真则写“ T”,假则写“ F”。 1. Let f(n) = n3 - 4n + 4 and g(n) = 5n3 100, then f(n) + g(n) is (n3) and f(n)*g(n) is o(n6). 若函数 f(n) = n3 - 4n + 4 以及 g(n) = 5n3 100, 则 f(n) + g(n) 是 (n3) 并且 f(n)*g(n) 是 o(n6). 2. Using a simple uniform hashing function h to hash n distinct keys into an array of length m, the expected cardinality of k, l: kl and h(k) = h(l) is n/m. 用简单均匀的哈希函数将 n 个不同的 keys 映射 到一个长度为 m 的数组,集合 k, l: kl and h(k) = h(l)的期望大小 是 n/m. 3. A directed acyclic graph with n nodes has at most n(n-1)/2 edges. 一个有 n 个节点的有向无环图最多有 n(n-1)/2 条边。 4. In any depth-first search of a graph G, if the finishing time of u is later than the finishing time of v for two vertices u and v in G, and u and v are in the same DFS tree, then u is an ancestor of v in the depth first tree. 在图深度优先遍历 DFS 算法中,对于图 G 任意两点节点 u 和 v,如果 u 的结束时间大于 v 的结束时间,并且 u 和 v 在同一个 DFS 树中,那么在此 DFS 树中 u 是 v 的先驱。 5. Given a boolean formula F of length n defined over 100 variables, deciding if F is satisfiable is NP-complete, assuming PNP. 科目 代码 : 991 科目 名称 : 数据结构与算法 第 2 页 共 12 页 给定一个长度为 n、包含 100 个变量的布尔公式 F,判断 F 是否可满足是 NP-complete, 假设 PNP. 2. Multiple Choices Select One (15 problems, 2 points each) 单选 题( 15 题,每 题 2 分) Each question has only one correct choice. Please indicate the correct choice in the answer sheet. 每题只有一个正确选项。请在答题纸上 写下 正确选项 的序号 。 1. Suppose a stack is implemented with a linear linked list that has just one pointer variable pointing to the first element of the list (the top of the stack). Which of the following correctly gives the time complexity of the (1) push, and (2) pop operations in this implementation? 假设一个栈由一个线性链表实现,其中仅有一个指针指向链表的第一个元素(栈顶)。 下面哪一个关于进 栈和出栈 操作 的算法复杂度是正确的? A. (1) O(1) (2) O(1) B. (1) O(1) (2) O(n) C. (1) O(n) (2) O(1) D. (1) O(n) (2) O(n) E. (1) O(log n) (2) O(1) 2. Which of the following is most efficient for updating a list that contains integers and is of predefined size? A. A stack B. A linked list C. An array D. A sequential file E. A binary search tree 下面哪种数据结构对更新由固定长度的整数组成的列表效率最高: A. 栈 B. 链表 C. 数组 D. 顺序文件 E. 二 叉 搜索树 3. Suppose that stacks and queues are provided opaque data types, offering only operations to add elements, to remove elements, and to test for emptiness. Suppose that a programmer wants to count the number of elements in a given stack or queue C, which is currently in some state t, using only one auxiliary stack or queue D. The structures C and D can be used in any way possible based on the methods they offer, but C must be restored to its state t after counting its elements. Counting elements as described above is possible for which of the 科目 代码 : 991 科目 名称 : 数据结构与算法 第 3 页 共 12 页 following data types? I C is a queue and D is a queue. II C is a stack and D is a stack. III C is a queue and D is a stack. A. None B. I and II only C. I and III only D. II and III only E. I, II, and III 假设栈和队列 是已 提供 的 非透明数据类型,仅实现 了元素增加、 元素 删除、 以及是否为 空的测试。一个程序员要计算一个栈或者队列 C 的元素个数,而 C 当前的状态是 t 并且 只能使用一个辅助的栈 或 队列 D。 C 和 D 可以被任何合理的方式使用,但计数之后 C 必 须恢复 到 原来的状态 t。下面哪些选项可以实现上述的计数 操作 ? I C 是队列并且 D 是队列 II C 是栈并且 D 是栈 III C 是队列并且 D 是栈 A. 无选项 B. I 和 II C. I 和 III D. II 和 III E. I, II 和 III 4. A hash function h maps 16-bit inputs to 8-bit hash values. What is the largest k such that in any set of 1,000 different inputs, there are at least k inputs that h maps to the same hash value? 一个哈希 函数 h 将 16 比特 的输入映射到一个 8 比特 的哈希值。假设 给定 任意一个包含 1000 个不同 输入的 集合 ,都 至少 有 k 个输入会被 h 影射到同一个哈 希 值。 这个 k 的最 大值是多少? A. 3 B. 4 C. 64 D. 256 5. Which of the following data structure is most efficient to schedule jobs on a shared computer, which keeps track of the jobs to be performed and their relative priorities? A. Priority queues B. Array 科目 代码 : 991 科目 名称 : 数据结构与算法 第 4 页 共 12 页 C. Linked list D. Stack 以下 哪种数据结构可以用来有效 的 调度一个共享计算机上的 工作 ,其 可以跟踪 需要完 成的 工作 和它们的相对优先级? A. 优先队列 B. 数组 C. 链表 D. 堆栈 6. What is the time-complexity to insert an element into a n-element priority queue? 在 一个长度为 n 的优先队列中插入一个新元素的复杂度是? A. O(1) B. O(lg n) C. O(n) D. O(n lg n) 7. A full binary tree is a rooted tree in which every internal node has exactly two children. How many internal nodes are there in a full binary tree with 50 leaves? 一棵满二叉树是一棵 有根树 ,其所有非叶节点都有两个孩子节点。一棵有 50 个叶节点 的满二叉树有几个非叶节点? A. 25 B. 49 C. 50 D. 51 E. 100 8. What are the indexes of the child nodes whose parent index is n in a binary tree stored in an array? Assume the index of the root node is 0. 在一棵存储于数组的二叉树中,索引 号 为 n 的节点的孩子节点的索引 号 是多少?假定 根节点 的 索引 号 为 0。 A. 2 , 2+ 1 B. 2 + 1 , 2 + 2 C. 2 + 1 , 2 + 2 D. 2 , 2 + 1 9. Suppose we have a disjoint set (with the forest representation) containing 6 elements. Initially its parent array is 0,1,2,3,4, i.e., each element belongs to a different set. Which of the following can be the parent array after we perform a sequence of union-by-rank (or 科目 代码 : 991 科目 名称 : 数据结构与算法 第 5 页 共 12 页 equivalently, union-by-height) operations? 假设我们有一个包 含 6 个元素、使用森林表示法的不相交集合( 并查集 )。其初始父亲 数组为 0,1,2,3,4,即每个元素属于一个不同的集合。当我们进行一系列 按 秩合并 (或等 价地, 按高度合并 )操作之后,下列哪一个可能是最终的父亲数组? A. 1,1,1,4,0 B. 2,0,2,0,2 C. 1,4,2,0,0 D. 3,2,4,4,4 10. Kruskals algorithm and Prims algorithm are two classical algorithms for finding a minimum spanning tree in a graph. Which of the following must be true? i. Kruskals algorithm is a greedy algorithm. ii. Kruskals algorithm is a dynamic programming algorithm. iii. Prims algorithm is a greedy algorithm. iv. Prims algorithm is a divide and conquer algorithm. A. i and iii B. i and iv C. ii and iii D. ii and iv Kruskal 算法和 Prim 算法是计算图中最小生成树的两个经典算法,以下哪些项是肯定正 确的? i. Kruskal 算法是一种贪心算法。 ii. Kruskal 算法是一种动态规划算法。 iii. Prim 算法是一种贪心算法。 iv. Prim 算法是一种分治算法。 A. i 和 iii B. i 和 iv C. ii 和 iii D. ii 和 iv 11. Given a weighted, directed graph G represented by an adjacency matrix W=(wij) where wij is the weight of the edge (i,j). Assume that the graph contains no negative-weight cycles and has n3 vertices, if one uses the matrix multiplication based algorithm to solve the all-pairs shortest-paths problem, let Wi for i=0 denotes the matrix after i-times of matrix multiplication, which of the following must be the matrix containing the shortest-path weights? i. W2 , ii. Wn-1 , iii. W2n-1, iv. W2n A. i 科目 代码 : 991 科目 名称 : 数据结构与算法 第 6 页 共 12 页 B. ii C. ii and iii D. ii, iii and iv 给定一个以邻接矩阵表示的带权有向图 W=(wij),其中 wij 表示 (i,j)的权值。假设该图不 包含非负权值环,并且含有 n3 个节点,如果采用基于矩阵乘法的算法解决所有节点对 间最短路径问题,以 Wi 表示矩阵 i 次乘法后的结果,以下那些矩阵肯定包含最短路径 的权值? i. W2 , ii. Wn-1 , iii. W2n-1, iv. W2n A. i B. ii C. ii 和 iii D. ii, iii 和 iv 12. Which of the following must be true? i. Given a directed graph G=(V,E), an associated graph of G is a graph G=(V,E), where the vertices in V are the strongly connected components of G and for vertices S,TV, (S,T) E if and only if there exist uS and vT such that (u,v) E.Then, Gis a directed acyclic graph. ii. Consider two positively weighted graphs G = (V,E,W) and G= (V,E,W) with the same vertices V and edges E such that, for any edge e E, we have W(e) = W(e)* W(e). For any two vertices u,vV, any shortest path between u and v in G is also a shortest path in G. iii. Consider two positively weighted graphs G = (V,E,W) and G= (V,E,W) with the same vertices V and edges E such that, for any edge e E, we have W(e) = W(e)+ W(e). For any two vertices u,vV, any shortest path between u and v in G is also a shortest path in G. A. only i B. i and ii C. i and iii D. ii and iii 以下哪些项是肯定正确的? i. 给定一个有向图 G=(V,E), G 的关联图是一个图 G=(V,E),其中 V中的节点是 G 的强连通分量,对于任意一对节点 S,TV, (S,T) E当且仅当存在 uS 和 vT 满足 (u,v) E。 G是一个有向无环图。 ii. 考虑带权图 G=(V,E,W)和 G=(V,E,W),所有 W 和 W中的权值为正数,如果 G 和 G有相同的节点和边,并且对于任意边 e 满足 W(e) = W(e)* W(e),那么对于 任意节点对 u,vV, G中的 u 和 v 之间的最短路径同样是 G 中的 u 和 v 之间的 最短路径。 iii. 考虑带权图 G=(V,E,W)和 G=(V,E,W),所有 W 和 W中的权值为正数,如果 G 和 G有相同的节点和边,并且对于任意边 e 满足 W(e) = W(e)+ W(e),那么对于 科目 代码 : 991 科目 名称 : 数据结构与算法 第 7 页 共 12 页 任意节点对 u,vV, G中的 u 和 v 之间的最短路径同样是 G 中的 u 和 v 之间的 最短路径。 A. i B. i 和 ii C. i 和 iii D. ii 和 iii 13. What is the worst case time complexity for quicksort to sort an array of n elements? 对包括 n 个元素的数组采用 quicksort 算法进行排序,其最坏时间复杂度是? A. O(n log n) B. O(n) C. O(n2) D. O(log n) 14. When is insertion sort a good choice for sorting an array? A. When the array has many elements. B. When the array has only a few elements out of place. C. When the inputs are strings instead of numbers. D. Insertion sort is never a good choice for sorting an array. 对于数组排序,以下哪种情况下应该选择插入排序? A. 当数组很大时。 B. 当数组中只有少数元素不在其排序后的位置时。 C. 当数组 内容 是字符串 而非数值 时。 D. 插入排序永远不是一个好的选择。 15. If an algorithm works by solving non-overlapping subproblems, the algorithm is called: A. Recursive B. Dynamic programming C. Divide and conquer D. Greedy 如果一个算法通过将问题划分成若干个没有重叠的子问题进行解决,那么该算法称为 : A. 递归法 B. 动态规划 C. 分治法 D. 贪心算法 科目 代码 : 991 科目 名称 : 数据结构与算法 第 8 页 共 12 页 3. Multiple Choices Select One or More (5 problems, 2 points each) 多选 题( 5 题, 每题 2 分) Each question may have one or more correct choices. Please indicate all the correct choice(s) in the answer sheet. 每题有一个 或多个 正确选项。请在答题纸上写下 所有 正确选项。 1. Read the following statements, and choose the statements that is (are) correct: 阅读下面的陈述,并选择正确的选项: A. log2 n = O(log10 n) B. log10 n = O(log2 n) C. n2 =O(2n) D. 2n =O(n2) E. None of the above 2. In the character-coding problem, a file contains only characters a, b, c with frequencies 45, 13, 12 respectively, which of the following codewords is an optimal character code for the file? 在一个字符编码问题中, 如果 一个文件只 由 a, b, c 组成, 它们 出现的频率分别是 45, 13, 12, 以下哪 些 编码是最优的? A. a:000, b:010, c:101. B. a:000, b:010, c:100. C. a:00, b:01, c:10. D. a:1, b:01, c:00. 3. Given a binary tree whose pre-order traversal is ABCDE and post-order traversal is CBEDA, which of the following can be its in-order traversal? 一棵二叉树的前序遍历是 ABCDE,后序遍历是 CBEDA, 它的 中序遍历有可能是哪个? A. BACDE B. BCADE C. CBAED D. ACBED 4. Consider the following directed graph. 考虑以下有向图。 1 2 3 4 5 6 7 8 9 科目 代码 : 991 科目 名称 : 数据结构与算法 第 9 页 共 12 页 Which are topological sorts of the nodes of the above graph? 以下哪一个或哪些是上图的拓扑排序? A. 2,1,9,3,4,7,5,6,8 B. 2,1,9,4,5,7,3,6,8 C. 2,9,1,4,7,3,5,6,8 D. 2,1,4,7,5,9,3,6,8 E. 2,9,1,4,3,7,5,6.8 5. Which of the following is true of problems solvable by dynamic programming? A. They cannot be solved by a greedy algorithm. B. They have the optimal substructure property. C. They can be divided into overlapping subproblems. D. The time and space complexities of the dynamic programming algorithm are equal. 对于 可以通过动态规划可以解决的问题,以下哪些表述是正确的? A. 这些问题无法通过贪心算法解决。 B. 这些问题具有最优子结构性质。 C. 这些问题可以划分成若干个重叠子问题。 D. 动态规划的时间复杂度和空间复杂度相等 。 4. Stack (20 points) 栈( 20 分) Design a stack which, in addition to push and pop, also has a function min which returns the minimum element. Push, pop and min should all operate in O(1) time. Please describe your design. 设计一个栈,除了提供入栈和出栈 操作 ,还提供 min 函数,返回栈里的最小元素。所有三 个函数都应该具有 O(1)的复杂度。 请 描述你的设计 。 5. Binary Search Tree (20 points) 二叉 搜索 树 ( 20 分) Consider the following binary search tree: 根据以下二叉 搜索 树回答: 1) Starting from an empty binary search tree, the insertion of which of the following sequences of integer keys could produce the binary search tree above? 1 7 4 9 5 3 科目 代码 : 991 科目 名称 : 数据结构与算法 第 10 页 共 12 页 从 一个空的二叉搜索树开始, 以下 哪个插入序列可以生成以上二叉搜索树? ( 4 分 ) A. 3, 7, 1, 5, 9, 4 B. 3, 7, 4, 1, 5, 9 C. 3, 4, 7, 5, 9, 1 D. 3, 1, 7, 9, 5, 4 2) What is the in-order traversal of the tree? 以上 二叉 树 的中序 遍历 是? ( 4 分 ) 3) Draw the updated tree when the root of key 3 is deleted from the tree. 画出 把 树 中 根 节点 3 去掉后的二叉搜索树。 ( 6 分 ) 4) Draw the updated tree when the node of key 3 is re-inserted back to the tree. 画出 把 3 节点重新插入到第 3)小问所 得 树之后的 二叉 搜索树。 ( 6 分 ) 6. Graph Representation (20 points) 图 的表示( 20 分) Given the following adjacent-list representation of a graph, 1) draw the graph; 2) draw the adjacent-matrix representation of the graph. 给定一个图的邻接表表示, 1) 画出该图; ( 10 分 ) 2) 画出该图的邻接矩阵表示 。 ( 10 分 ) 7. Graph Traversal (20 points) 图的遍历( 20 分) Consider the following modified traversal algorithm for graphs: 考虑以下修改后的图遍历算法: 1: Visited = ; 2: ModTraversal (v: Node, G: Graph) 3: / assume G.V is the set of nodes in the graph G 4: / G.E is the set of edges in the graph G 5: Queue active = ; / a queue that is first in first out 6: forall (v,w) in G.E do / an ascending alphabetical A B C D E B C E C D A E 科目 代码 : 991 科目 名称 : 数据结构与算法 第 11 页 共 12 页 / order of ws 7: if (not wVisited) then 8: Visit (w); 9: Visited = Visited w; 10: ENQUEUE(active ,w) ; 11: ; 12: ; 13: while (active ) do 14: w = DEQUEUE(active); 15: ModTraversal (w,G) ; 16: ; 17: 1) Consider the following graph: in what order are the nodes “visited” by the modified traversal at Line 8? The traversal shall be called by Visited = Visited a; / Visited=a ModTraversal (a, G) ; (a being the start node for the traversal, and edges connecting from the same node are visited in an ascending order at Line 6 according to the target nodes of the edges. For example, a has three edges (a,b),(a,e),(a,f), since bef, (a,b) should be visited before (a,e) and (a,f) at Line 6, while (a,e) should be visited before (a,f) at Line 6) 给出下图用上述遍历算法遍历时的节点访问顺序,遍历算法采用以下方式调用: Visited = Visited a; / Visited=a ModTraversal (a, G) ; ( a 是遍历的起始节点 ; 当存在多个同一个节点出发的边时,上述算法行 6 以 边的目标 节点的升序 访问 。比如,连接节点 a 的边有三条 (a,b),(a,e),(a,f),由于 bef, (a,b)必须在 (a,e)和 (a,f)前 访问 , (a,e)必须在 (a,f)前 访问 ) ( 8 分 ) a b c d e f g h i j k l m n o p 2) Draw the spanning tree computed by ModTraversal of (a) 画出上述算法在上图的遍历生成树 ( 6 分 ) 3) Assumes that the input graph G is represented using adjacency lists, set operations (e.g., membership checking and element adding) and ENQUEUE and DEQUEUE can be done in 科目 代码 : 991 科目 名称 : 数据结构与算法 第 12 页 共 12 页 constant time (i.e., O(1), give the worst-time complexity (Big O notation) of ModTraversal in terms of |V| and |E|. 假设上述算法的输入图是以邻接链表表示,集合的操作(检查是否包含某个节点和集 合中加入节点)和入队、出队都在常数时间内完成 ( 即 O(1)) , 使用 |V|和 |E|表示 上述 遍历算法的最坏时间复杂度 (大 O 表示法) 。 ( 6 分 ) 8. Sorting (20 points) 排序( 20 分) Suppose we are given an array of n numbers, where each number is at most k positions away from its position if we sort the array, for a constant k n. For example, given the array 2 3 1 4 6 5 7 9 8, each value is at most 2 positions away from its sorted position. Give an algorithm to sort the array running in O(n log k) time. Write pseudo-code for your algorithm and also explain it in words. 假设给定一个长度为 n 的数组,并且数组中每个值的位置距离排序后该值的位置不超过 k(小于或等于 k), k n。比如数组 2 3 1 4 6 5 7 9 8,每个值的位置距离其排序后的位 置不超过 2。设计一个最坏时间复杂度为 O(n log k)的排序算法,以伪代码形式给出,并 解释该程序。