2018年上海科技大学数据结构与算法考研真题991.pdf0页

2018年上海科技大学数据结构与算法考研真题991.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) = n 3 - 4n + 4 and g(n) = 5n 3 – 100, then f(n) + g(n) is ?(n 3 ) and f(n)*g(n) is o(n 6 ). 若函 数 f(n) = n 3 - 4n + 4 以及 g(n) = 5n 3 – 100, 则 f(n) + g(n) 是 ?(n 3 ) 并且 f(n)*g(n) 是 o(n 6 ). 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}: k ?l and h(k) = h(l)} is n/m. 用简单 均匀 的哈 希函 数 将 n 个不 同的 keys 映射到一 个长度 为 m 的数 组 ， 集 合{{k, l}: k ?l 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 P ?NP .