上海科技大学计算机考研真题
考生须知： 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. （ ）
下列树是二叉搜索树。（ ）
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 P NP. （ ）
给定一个图，确定图中是否存在一个正好包含 100 个节点的团是一个 NP-complete 的问 题，假设 P NP。（ ）
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 P NP. （ ）
给定一个图，确定是否可以去除图中一半的节点后使得该图可以三染，这可以在多项 式时间内完成，假设 P NP。（ ）
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. 每题只有一个正确选项。请在答题纸上写下正确选项的序号。
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. 2 n , n + (log n)2 , n3 , 10n2 , n log n
B. n + (log n)2 , n3 , 10n2 , n log n, 2 n
C. n + (log n)2 , n log n, 10n2 , n3 , 2 n
D. n + (log n)2 , 10n2 , n log n, n3 , 2 n E. 2 n , 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. 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
Prim’s 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？（ ）
  Prim’s algorithm is a greedy algorithm. ii. Prim’s algorithm is a dynamic programming algo
rithm. iii. Floyd-Warshall algorithm is a greedy algorithm. iv. Floyd-Warshall algorithm is a dynamic programming algorithm. Prim 算法是一种计算图的最小生成树算法，Floyd-Warshall 算法可用于计算有向图中所 有节点对之间的最短路径。以下哪些表述肯定是正确的？（ ）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。