数据结构基础(八)

Mid Term Record

Judge

For a binary tree, if its pre-order travel sequence is { 4, 2, 1, 3, 6, 5, 7 }, and its in-order travel sequence is { 1, 2, 3, 4, 5, 6, 7 }, then 4 is the parent of 3. [F]
4
/ \
2 6
/ \ / \
1 3 5 7

Selection

Which of the following statements is FALSE? [B]

A. $100n^3=O(n^3)$

B. $\sqrt{n}\log n=o(n)$

C. $(\log n)^{100}=O(n^{1/100})$

D. $n\log n=O(n^{1.3}\log\log n)$

$o()$ 意味着函数的增长速度严格慢于与其进行比较的函数
Given a finite set of elements S. The sequences in and out are permutations of S. Start from an empty stack ST, which of the following statements is TRUE? [B]

A. If in is the pushing sequence and out is a corresponding popping sequence of ST, then in and out must be different.

B. If in is the pushing sequence of ST, then it cannot be determined if out is a possible popping sequence.

C. If in is the pushing sequence and out is a corresponding popping sequence of ST, then in and out might be in reversed order.

D. If out is the popping sequence of ST, then it cannot be determined if in is a possible pushing sequence.

注意语态是被动的, 栈的输出序列并不能确定栈的输入序列
Suppose that the level-order traversal sequence of a min-heap is { 3, 8, 12, 63, 17, 26, 82 }. Use the linear algorithm to adjust this min-heap into a max-heap, and then call DeleteMax. The postorder traversal sequence of the resulting tree is: [C]

A. 8, 17, 12, 63, 3, 26

B. 3, 12, 17, 8, 26, 63

C. 8, 12, 17, 3, 26, 63

D. 63, 17, 8, 12, 26, 3
1. 线性调整算法:
  1. 从给定的最小堆数组开始
  2. 从右到左遍历数组，从最后一个节点的父节点开始（即数组中最后一个元素的父节点）直到根节点
  3. 在每一步中，将当前节点与其子节点进行比较
  4. 如有必要，交换当前节点与较大的子节点，以保持最大堆的性质
  5. 持续此过程，直到整个数组被遍历
2. 删除后的堆的结构:
  63
  / \
  17 26
  / \ / \
  8 12 3
The array representation of the disjoint sets is given by S = { 2, 9, 2, -5, 4, 10, -1, 4, -4, 8 }. Keep in mind that the elements are numbered from 1 to 10. After invoking Union(Find(1), Find(10)) with union-by-size and path compression, which of the following statements is FALSE? [B]

A. S[1] = 9

B. S[2] = 4

C. S[6] = 10

D. S[10] = 4

在合并操作前, 并查集长这样:

合并后长这样:

值得注意的是, 执行 Union(Find(1), Find(10)) 的时候, 路径压缩操作发生在 Find() 函数, Union() 函数仅仅将较小的集合的根指向较大的集合的根, 不再重复路径压缩
A graph with 100 vertices and 12 edges must have at most ____ connected component(s). [95]

注意是最多有几个连通分量, 因此考虑牺牲 n 个结点消耗 12 个边, 剩下的就是最多的连通分量, 问题就转化成了 12 个边最少包含几个结点, 也就是 n 满足 $C_n^2\ge 12$ , 解得 $n \ge 6$ , 也就是有 1 个 6 结点连通分量和 94 个 1 结点连通分量, 总计是 95 个

Program

The function is to return the reverse linked list of L, with a dummy header.

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;

    while ( Old_head )  {
        Temp = Old_head->Next;
        Old_head->Next = New_head;    // blank 1
        New_head = Old_head;  
        Old_head = Temp; 
    }
    L->Next=New_head;   // blank 2
    return L;
}

The function Height is to find the height of a binary tree T. The height of a leaf node is defined to be 0.

The tree structure is defined as the following:

typedef struct Node *PtrToNode;
struct Node{
    int Data;
    PtrToNode Left, Right;
};
typedef PtrToNode Tree;

Please fill in the blanks.

int Height( Tree T )
{
    int left_H, right_H;

    if (T==NULL)  return -1;    // blank 1
    left_H = Height(T->Left);
    right_H = Height(T->Right); // blank 2
    return ( max(left_H, right_H) + 1 );
}

注意题目说叶子的高度是 0, 因此递归到空树 (也就是叶子的下一层) 要返回 -1 消除叶子对高度的影响