资源描述
第 1 页 共 12 页 上海 科技大学 2019 年 攻读硕士学位研究生 招生 考试试题 科目代码： 991 科目 名称： 数据结构与算法 考生 须知： 1. 本试卷 满分为 150 分 ，全部考试时间总计 180 分钟 。 2. 所有 答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 3. 每道题的 英文 部分均已翻译为 中文 ，考生可在中英文中任选一种语言作答。 1. True or False (10 problems, 2 points each) 判断题（ 10 题，每题 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. 请在答题纸上写明下列每个命题的真假。真则 打 “ ”， 假则 打 “ ”。 1. In a circular linked list, some link fields may be null. （ ） 在循环链表中 ， 某些链接域可能为空。 （ ） 2. Given any functions f(n) and g(n), it is possible to have both f(n) = (g(n) and f(n) = o(g(n). （ ） 给定任意函数 f(n)和 g(n)， f(n) = (g(n)和 f(n) = o(g(n)可能同时成立 。 （ ） 3. A good hash function of a hash table satisfies the assumption of simple uniform hashing. （ ） 一个 好的哈希函数需满足简单 均匀 。 （ ） 4. The following tree is a binary search tree. （ ） 下列 树 是 二叉搜索树。 （ ） 1 74 953科目 代码 ： 991 科目 名称 ： 数据结构与算法 第 2 页 共 12 页 5. The number of nodes in a tree can be more than twice the number of leaf nodes. （ ） 一棵树的节点个数有可能大于叶节点个数的两倍。 （ ） 6. The space complexity of an adjacency-matrix representation of a graph is independent of the number of edges in the graph. （ ） 图的邻接矩阵表示的空间复杂度与图的边数无关。 （ ） 7. In the breadth-first search procedure of graphs, each vertex must be enqueued exactly once. （ ） 在图的广度遍历算法中，每个节点恰好仅入队一次。 （ ） 8. Given a weighted, directed graph with nodes numbered 1,2,n, finding the length of a shortest path from vertex 1 to vertex n or determining that no such path exists can be done in polynomial time. （ ） 给定一个带权有向图，图的节点为 1,2,n，要 计算节点 1 和 n 之间的最短路径或判断这样的路径不存在 ， 这个问题 可以在多项式时间内解决。 （ ） 9. Given a graph, deciding whether it has a clique of 100 nodes is NP-complete, assuming PNP. （ ） 给定一个图，确定图中是否存在一个 正好 包含 100 个 节点的 团是 一个 NP-complete 的问题， 假设 PNP。 （ ） 10. Given a graph, deciding whether it is possible to remove half the nodes in the graph so that the remaining graph is 3-colorable is solvable in polynomial time, assuming PNP. （ ） 给定 一个图， 确定 是否可以 去除 图中一半的节点后使得该图可以三染色 ，这可以 在 多项式时间 内 完成， 假设 PNP。 （ ） 2. Multiple Choices Select One (10 problems, 2 points each) 单选题（ 10 题，每题 2 分） Each question has only one correct choice. Please indicate the correct choice in the answer sheet. 每题只有一个正确选项。请在答题纸上 写下 正确选项 的序号 。 1. In what kind of storage structure for strings can one easily insert, delete, concatenate, and 科目 代码 ： 991 科目 名称 ： 数据结构与算法 第 3 页 共 12 页 rearrange substrings? （ ） A. Fixed length storage structure B. Linked list storage C. Variable length storage with fixed maximum D. Array list storage E. None of the above 哪种字符串的存储结构可以方便地进行插入，删除，并联以及重新安排子字符串 ? （ ） A. 固定长度的存储结构 B. 链表存储结构 C. 具有固定最大长度的变长存储结构 D. 数组存储结构 E. 以上都不是 2. In which of the following are the functions listed in order of increasing asymptotic size? （ ） 下面哪个选项中的函数是按照 渐进大小的 增序排列？ （ ） A. 2n, n + (log n)2, n3, 10n2, n log n B. n + (log n)2, n3, 10n2, n log n, 2n C. n + (log n)2, n log n, 10n2, n3, 2n D. n + (log n)2, 10n2, n log n, n3, 2n E. 2n, n3, 10n2, n log n, n + (log n)2 3. We store 10 elements with keys 5,28,19,15,20,12,33,17,10,18 into a hash table with collisions resolved by chaining (with linked list). The hash table has 9 slots and the hash function is defined as h(k) = k mod 9. What is the maximum length of the linked lists in the hash table? （ ） 存储 10 个 元素到一个哈希 表 ，这 10 个 元素的 key 是 5,28,19,15,20,12,33,17,10,18。哈希 表总共 有 9 个 slots， 哈 希函数是 h(k) = k mod 9， 并用 链表解决冲突。 哈 希 表 中最长的链表长度是？ （ ） A. 1 B. 2 C. 3 D. 4 4. A full binary tree is a rooted tree in which every internal node has exactly two children. How 科目 代码 ： 991 科目 名称 ： 数据结构与算法 第 4 页 共 12 页 many internal nodes are there in a full binary tree with 500 leaves? （ ） 满 二叉树的 所有 中间节点都有两个孩子节点。 一个 有 500 个 叶子节点的满二叉树有多少个中间节点？ （ ） A. 250 B. 499 C. 500 D. 501 E. 1,000 5. Which of the following statements about trees is false? （ ） A. An internal node may have no child B. Adding an edge to a tree creates a cycle C. Not every node has a parent node in a tree D. The height of a tree with one node is 0 以下哪一个关于树的描述是错误的？ （ ） A. 非叶节点有可能 没有孩子 B. 在一棵树中加一条边会形成一个环 C. 一棵树中并非每个节点 都有父亲节点 D. 一棵包含一个节点 的树高度为 0 6. What is the in-order traversal of the following binary tree? （ ） 下面二叉树的中序遍历是什么？ （ ） A. DFBEAC B. ABDFEC C. FDEBCA D. FDEBAC A B C D E F 科目 代码 ： 991 科目 名称 ： 数据结构与算法 第 5 页 共 12 页 7. Prims algorithm is one algorithm for finding a minimum spanning tree in a graph and the Floyd-Warshall algorithm can be used to solve the all-pairs shortest-paths problem on a directed graph. Which of the following must be true？ （ ） i. Prims algorithm is a greedy algorithm. ii. Prims algorithm is a dynamic programming algorithm. iii. Floyd-Warshall algorithm is a greedy algorithm. iv. Floyd-Warshall algorithm is a dynamic programming algorithm. Prim 算法是一种计算图的最小生成树算法， Floyd-Warshall 算法可用于计算有向图中所有节点对 之 间的最短路径。以下哪些表述肯定是正确的？ （ ） i. Prim 算法是一种贪心算法。 ii. Prim 算法是一种动态规划算法。 iii. Floyd-Warshall 算法是一种贪心算法。 iv. Floyd-Warshall 算法是一种动态规划算法。 A. i 和 iii B. i 和 iv C. ii 和 iii D. ii 和 iv 8. Among the following problems concerning a given graph G, which is currently known to be solvable in linear time? （ ） A. Finding a longest simple cycle in an undirected graph B. Computing the strongly connected components of a directed graph C. Solving the single-source shortest-paths problem of a weighted, directed graph G D. Finding a largest clique in an undirected graph G 以下哪一个图的问题可以在线性时间内解决？ （ ） A. 找到一个无向图中的最长简单环 B. 计算有向图的强连通分量 C. 解决带权有向图的单源最短路径问题 D. 找到一个无向图的最大团 9. Which of the following is true of merge sort and quicksort? （ ） A. Both are divide and conquer algorithms 科目 代码 ： 991 科目 名称 ： 数据结构与算法 第 6 页 共 12 页 B. Both take (n) time in each divide step, given an input array of size n C. Both have the same worst-case time complexity D. All of the above are true 下列关于 归并排序 和 快速排序的陈述哪一项是对的？ （ ） A. 都是 用分治法 B. 给定 一 个长度为 n 的 输入数组 ， 都是需要 (n)的时间 进行 每一次 切分 C. 都 有 相同的 最坏 时间复杂度 D. 以上都 对 10. Which of the following is the closest to the minimum number of comparisons between array elements that any comparison-based algorithm needs to perform to find both the minimum and maximum values in an input array of size n? （ ） 任何一个 基于 比较的算法在一个长度为 n 的数组中同时找出最大和最小值 ， 至少需要数组 元素 之间 的 比较 的次数 与下列 哪 个最接近？ （ ） A. n B. 1.5n C. 2n D. n2 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. Consider using a linked list to represent a sparse matrix. Only non-zero elements are stored in the list. What information should be stored in the nodes of the linked list? （ ） A. Row number B. Column number C. Value of the matrix element D. Number of non-zero elements E. Number of zero elements 假设使用一个链表来表示一个稀疏矩阵，其中只存储非零元素。在链表的节点中需要存科目 代码 ： 991 科目 名称 ： 数据结构与算法 第 7 页 共 12 页 储什么信息？ （ ） A. 行号 B. 列号 C. 矩阵元素的值 D. 非零元素的个数 E. 零元素的个数 2. In a character-coding problem, if a file contains only characters a, b, and c with frequencies 45, 13, and 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 an undirected graph with n nodes and m edges, select the correct statement(s) below. （ ） A. m = n - 1 if the graph is a tree B. n = m - 1 if the graph is a tree C. m K2 K3 K4 K5. Use a complete binary tree to represent this order as a binary search tree and then represent this binary search tree as an array. Draw the final array (the length of the array is 5). Note: Here a complete binary tree is a binary tree which is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. （ 5 points） 假设 给定的 关键字 满足一个线性关系： K1 K2 K3 K4 K5。用一个 完全 二叉树 将 这个线性关系表示成一个 二叉 搜索 树 ， 然后 将这个二叉搜索树用一个数组来表达， 最后 画出这个数组（数组的长度是 5）。 备注 ： 在这里 完 全 二叉树是一个二叉树， 其中 每一层（可能 除最后一层 之外 ） 都完全填充， 而 最后一层 从左到右 填到 某一个位置 为止 。 （ 5 分 ） 5. Binary Trees (25 points) 二 叉树 （ 25 分 ） 1) Write down the preorder, inorder, postorder, and breadth-first traversals of the following binary tree in the form of a sequence of nodes. （ 9 points） 请写 出 下面这棵二叉树的前序 、 中序 、 后序和广度优先遍历 ， 以 节点 序列 的 形式 给出 。 （ 9 分 ） 2) Draw the binary tree whose preorder is 1,3,2,7,6,5,4 and whose inorder is 1,2,3,4,5,6,7. （ 8 points） 一棵二叉树的前序遍历是 1,3,2,7,6,5,4， 中序遍历是 1,2,3,4,5,6,7。 请画出这棵树 。（ 8 分 ） 3) Draw the binary tree whose postorder is 1,3,2,7,6,5,4 and whose inorder is 1,2,3,4,5,6,7. （ 8 points） 一棵二叉树的 后 序遍历是 1,3,2,7,6,5,4， 中序遍历是 1,2,3,4,5,6,7。 请画出这棵树 。（ 8 分 ）
展开阅读全文