做题节选

15-16年

判断

• The best “worst-case time complexity” for any algorithm that sorts by comparisons only must be O(NlogN).

  T
  就是熟知的 $NlogN$ 结论,
  为什么不是冒泡排序的$N^2$呢, 因为这个不满足 best

• $N(logN)^2$   is   $O(N^2).$

  T
  基础概念要牢固:Ο（大写）；表示上界(tightness unknown)，小于等于的意思
  参考文章
  $\Theta$ 才是严格的情况

• If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest.

  T
  你只是忘记了线性存储是什么东西
  参考文章
  其底层原理通过数组来实现。数组中的元素是有序的，通过下标访问。对于需要频繁访问使用的元素，使用顺序表的效率非常之高。
  优点：

  • 顺序表有序，访问顺序表中的数据很快。

  缺点：

  • 由于底层由数组实现，每当分配的空间用完后都需要扩容，而对于未使用的空间，也是一种浪费。
  • 进行插入和删除操作的效率很低，因为可能需要挪动大量的元素。
    但是本题插入和删除的是最后的元素!

• T

• T

选择(填空)

• Given a tree of degree 4.Suppose that the numbers of nodes of degrees 2, 3 and 4 are 4, 2 and 1, respectively. Then the number of leaf nodes must be:

  最多四个子节点
  强行作图就可以(感觉没什么其他方法?), 但是要细心, 我的答案:12

• 知识:front 指向队列的第一个元素，而 rear 指向队列最后一个元素的下一个位置. 竟然是rear不放元素!

• 知识: a complete binary tree : 若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边

• union的参考文章

• Union by size(当前根节点所在树的节点个数): 小size并入大size

• Union by rank: 把高度小的集合树 指向 高度大的集合树

- Suppose that the level-order traversal sequence of a min-heap is {1, 3, 2, 5, 4, 7, 6}. Use the linear algorithm to adjust this min-heap into a max-heap. The inorder traversal sequence of the resulting tree is:

linear algorithm:
把一个堆变成最大堆(Java), 大循环小递归

void maxHeapify(int [] A, int heapSize, int i)
{
	int left = 2*i;
	int right = 2*i + 1;
	int larger = i;
    // (有左子节点)左子节点大于当前节点
	if (left <= heapSize && A[left] > A[larger])
	{
		larger = left;
	}
    // (有右子节点)右子节点大于当前节点
	if (right <= heapSize && A[right] > A[larger])
	{
		larger = right;
	}
    // 交换函数
	if (larger != i)
	{
		int temp = A[i];
		A[i] = A[larger];
		A[larger] = temp;
        // 检查交换后是否依然满足最大堆
		maxHeapify(A, heapSize, larger); 
	}
}

// 从倒数第二层的最左边开始, 依次往前遍历
void BuildHeap(int [] A, int heapSize)
{
	for (int i = heapSize/2-1; i> = 0; i++)
	{
		maxHeapify(A, heapSize, i);
	}
}

• If on the 9th level of a complete binary tree (assume that the root is on the 1st level) there are 100 leaf nodes, then the maximum number of nodes of this tree must be:

823
读题失误: 第九层有100个叶节点的意思是, 还有第十层, (256-100)*2 + 511 = 823

• The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are: