ADS_midterm
1-1
分数 3
作者 Yuchen Mao
单位 浙江大学

The height of an AVL tree with 19 nodes must be 5. ( We assume that the height of a single node is 1).


1-2
分数 3
作者 Yuchen Mao
单位 浙江大学

Both AVL trees and red-black trees need at most O(1) rotations per insertion.


1-3
分数 3
作者 Yuchen Mao
单位 浙江大学

Consider the B+ trees of order MM. There exists a constant c>0c > 0 such that no matter how large MM is, the running time of FINDKEY cannot be less than clog2nc\log_2 n where nn is the number of the keys stored in the tree.


1-4
分数 3
作者 Yuchen Mao
单位 浙江大学

The longest simple path from a node xx in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node xx to a descendant leaf.


1-5
分数 3
作者 Yuchen Mao
单位 浙江大学

A binomial queue with 31 keys may consists of 6 binomial trees.


1-6
分数 3
作者 Yuchen Mao
单位 浙江大学

Backtracking always performs strictly better than bruteforce.


1-7
分数 3
作者 Yuchen Mao
单位 浙江大学

Consdier the activity selection (interval scheduling) problem. In class, we have proved that an optimal solution can be obtained by selecting the activities in increasing order of thier finishing time. We can also obtain an optimal solution by selecting the activities in decreasing order of their start time.


1-8
分数 3
作者 Yuchen Mao
单位 浙江大学

Consider the recurrence T(n)=aT(n/b)+ndT(n) = aT(n/b) + n^d with T(1)=1T(1) = 1. If a<bda < b^d, then T(n)T(n) is dominated (in asympototic sense) by the amount work at the root of the recursion tree. If a>bda > b^d, then T(n)T(n) is dominated (in asympototic sense) by the total amount work at the leaves of the recursion tree.