加载中...
StudyPilot
题库
价格
日历
中文
EN
UQ
登录
题库
COMP3506/7505
【公开题库】期末自测题
【公开题库】期末自测题
5 道算法与数据结构期末难题自测：线性探查哈希、堆计数、循环复杂度、负权边下的 Dijkstra、AVL 旋转。做完对照解析，看看自己离期末还差多少。
0
题目
0
已练习
0
%
你的正确率
~
0
分钟
预计时间
你的进度
0%
0 / 5
已练 0 / 5 · 正确率 0%
开始练习 →
题目预览
01
Consider a hash table with 8 slots (indices 0 to 7) and a hash function $h(k) = k \bmod 8$, which uses open addressing with linear probing and a step size of 1: if slot $j$ is taken, try slot $(j + 1) \bmod 8$, and so on. The keys 16, 23, 7, 10 and 12 are inserted in this order into an empty table.A lookup starts at slot $h(k)$ and compares the key with the key stored in each slot it visits; it stops when it finds the key or reaches an empty slot. You can assume that we can check if a slot is empty without making any comparisons.How many comparisons are required to look up the key 15?Answer format: a whole number, digits only.
02
Which of the following is the number of binary min-heaps with different key/node arrangements that all include the four keys 1, 2, 3 and 4?
03
Consider the following code snippet, where n is a positive integer. Assume integers never overflow.int ops = 0; int start = 1; for (int i = 0; i < n - 1; i++) { for (int j = start; j < n; j++) ops++; start = start * 2; }What is the strongest bound on the time complexity of this code snippet?
04
Decide whether the statement below is True or False, and briefly justify your answer.Let $G = (V, E)$ be a weighted directed graph in which some edge weights are negative, but $G$ contains no negative-weight cycle. Let $t \in V$ be a fixed target vertex. Dijkstra's algorithm is used in its standard form: each vertex is finalised when it is removed from the priority queue, and a finalised vertex is never updated again.Statement: A single call of Dijkstra's algorithm can always be used to find the shortest paths from all other vertices to the target $t$.
05
Insert the following letters, in this order, into an initially-empty AVL tree. Letters are compared in alphabetic order.A V L T R E X M PShow the tree after each insertion, and for every insertion that causes an imbalance, name the rotations you perform. Trees are written in bracket form: v [ left, right ] is a node with value v and its left and right subtrees, a bare value is a leaf, and - is an empty child.In this question the balance factor of a node is height(right subtree) minus height(left subtree), where an empty subtree has height 0 and a leaf has height 1. A node is unbalanced when its balance factor is +2 or -2; always fix the deepest unbalanced node first.