上海科技大学-991数据结构与算法【2018】考研真题
2023-06-21
999+
827.55KB
12 页
侵权投诉
第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
摘要：
展开>>
收起<<
第1页共12页上海科技大学2018年攻读硕士学位研究生招生考试试题科目代码：991科目名称：数据结构与算法考生须知：1.本试卷满分为150分，全部考试时间总计180分钟。2.所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。3.每道题的中文部分均已翻译为英文，考生可在中英文中任选一种语言作答。1.TrueorFalse(5problems,2pointseach)判断题（5题，每题2分）Pleaseindicateintheanswersheetwhethereachstatementistrueorfalse.Writedown“T”forbeingtrueand“F”forbein...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
