# FDS 复习

# 期中模拟卷

# 1. $\sqrt N logN$ is $O(N)$ .

# 2.In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2 , but not $O(logN)$ .

每做一次归并，都会使得小的集合深度加 1，但是总的深度还是看大的集合。只有深度相同的归并才能使得总的深度加 1，2,2 归并，深度变为 3；3,3 归并深度变为 4。因此深度最大为 ** $log_2 N+1$ **.

# 3.For a `sequentially stored` linear list of length N, the time complexities for query and insertion are:

C. $O(1)$ , $O(N)$ .

注意是顺序存储，因此查询只需要 $O(1)$ , 插入需要调整后面的元素的位置，因此是 $O(N)$ .

# 4.The following figure shows the AOE network of a project with 8 activities. The earliest and the latest start times of the activity `d` are __, respectively.

还没学，下次再来补

# 5.If besides finding the shortest path from `S` to every other vertices, we also need to count the number of different shortest paths, we can modify the Dijkstra algorithm in the following way: add an array `count[]` so that `count[V]` records the number of different shortest paths from `S` to `V` . Then `count[V]` shall be initialized as:

A. count[S]=1; and count[V]=0 for other V

还没学应该不考，下次再来补

# 6. 程序填空题 Reverse Linked List

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

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;
        New_head = Old_head;  
        Old_head = Temp; 
    }
    L->Next = New_head;
    return L;
}

先把下一个节点用 temp 存起来，然后把当前节点指向上一个节点，然后移动上一个节点的指针到当前节点，把当前节点指针移动到下一节点。

# 7. 程序填空题 MinHeap Deletion

Please fill in the blanks in the program which deletes a given element at position p from a min-heap H .

Deletion ( PriorityQueue H,  int p )  /* delete the element H->Elements[p] */
{
   ElementType temp;
   int child;

   temp = H-> Elements[ H->Size-- ];
   if ( temp < H->Elements[p] ) {
      while ( (p != 1) && (temp < H->Elements[p/2]) ) { 
         H->Elements[p] = H->Elements[p/2]；
         p /= 2;
      } 
   }
   else {
      while( (child = 2*p) <= H->Size) {
         if ( child != H->Size && H->Elements[child] < H->Elements[child + 1] )
            child ++;
         if ( temp > H->Elements[child] ) {
            H->Elements[p] = H->Elements[child];
            p = child;
         }
         else
            break;
      }
   }
   H->Elements[p] = temp;
}

# HW1

# 1-2 The Fibonacci number sequence { $F_N$ } is defined as: $F_0=0,F_1=1,$ $F_N=F_{N-1}+F_{N-2}$ , N=2, 3, … The time complexity of the function which calculates $F_N$ recursively is $\Theta(N!)$ .

递归求斐波那契数的时间复杂度是 $O(2^N)$ .

二叉树的高度是 n-1，一个高度为 k 的二叉树最多可以由 $2^k-1$ 个叶子节点，也就是递归过程函数调用的次数，所以时间复杂度为 $O(2^N)$ ，而空间复杂度就是树的高度 $S(N)$ .

# 2-1 Given the following four algorithms with their runtimes for problem size 100 and their time complexities:

Algorithm	Runtime	Time Complexity
A	100	$O(N)$
B	50	$O(N^2)$
C	2	$O(N^3)$
D	10	$O(N^4)$

Which algorithm is the fastest for problem size 200?

200 = 100*2

A 100*2 = 200

B 50 * $2^2$ =200

C 25* $2^3$ =200

D 10* $2^4$ =160 最快

# 2-3 The recurrent equations for the time complexities of programs P1 and P2 are:

P1: T(1)=1,T(N)=T(N/3)+1
P2: T(1)=1,T(N)=3T(N/3)+1

Then the correct conclusion about their time complexities is:

A.they are both O(logN)

B.O*(log*N) for P1, O(N) for P2

C.they are both O(N)

D.O(logN) for P1, O(NlogN) for P2

$T(N)=T(N/3)+1=T(N/3/3)+1+1=...=O(logN)$

$T(N)=3T(N/3)+1=3(3T(N/3/3)+1)+1=...=3^{log_3N}=O(N)$

# R1-2 $(logN)^2$ is $O(N)$ .

记住即可

# R1-3 The time comlexity of Selection Sort will be the same no matter we store the elements in an array or a linked list.

# HW2

# 1-1 For a `sequentially stored` linear list of length N, the time complexities for deleting the first element and inserting the last element are O(1) and O(N), respectively.

注意是顺序存储的。删除第一个节点需要把后面的都往前移动一个位置，所以是 $O(N)$ ，插入最后一个节点是 $O(1)$ 。

对于顺序存储的长度为 N 的线性表，访问节点的时间复杂度是 $O(1)$ （线性存储，直接按标号访问就可以了），插入的时间复杂度是 $O(N)$ （要调整后面的元素的位置）。

# 2-3 To merge two singly linked ascending lists, both with N nodes, into one singly linked ascending list, the minimum possible number of comparisons is:

B. $N$

最少比较的次数就是第一个链表的每个节点都和第二个链表的头节点比较一次，所以是 N

# 函数题

# 6-1 Add Two Polynomials

Write a function to add two polynomials. Do not destroy the input. Use a linked list implementation with a dummy head node.
Note: The zero polynomial is represented by an empty list with only the dummy head node.

# Format of functions:

1	Polynomial Add( Polynomial a, Polynomial b );

where Polynomial is defined as the following:

typedef struct Node *PtrToNode;
struct Node {
    int Coefficient;
    int Exponent;
    PtrToNode Next;
};
typedef PtrToNode Polynomial;
/* Nodes are sorted in decreasing order of exponents.*/

The function Add is supposed to return a polynomial which is the sum of a and b .

# Sample program of judge:

#include <stdio.h>
#include <stdlib.h>
typedef struct Node *PtrToNode;
struct Node  {
    int Coefficient;
    int Exponent;
    PtrToNode Next;
};
typedef PtrToNode Polynomial;

Polynomial Read(); /* details omitted */
void Print( Polynomial p ); /* details omitted */
Polynomial Add( Polynomial a, Polynomial b );

int main()
{
    Polynomial a, b, s;
    a = Read();
    b = Read();
    s = Add(a, b);
    Print(s);
    return 0;
}

/* Your function will be put here */

# Sample Input:

4
3 4 -5 2 6 1 -2 0
3
5 20 -7 4 3 1

# Sample Output:

1	5 20 -4 4 -5 2 9 1 -2 0

Polynomial Add( Polynomial a, Polynomial b )
{
    //如果有一个为空则直接返回
    if(a==NULL) return b;
    if(b==NULL) return a;
    //head用于保存头结点，pre用于遍历，tmp用于产生新节点
    Polynomial head,pre,tmp;
    pre=(struct Node*)malloc(sizeof(struct Node));//申请内存
    
    head=pre;//head保存头结点
    a=a->Next;//因为有头结点，所以需要next一下寻找第一个元素
    b=b->Next;//因为有头结点，所以需要next一下寻找第一个元素

    while(a!=NULL&&b!=NULL){//两多项式都没遍历完
    
        tmp=(Polynomial)malloc(sizeof(Polynomial));  
        
        if(a->Exponent == b->Exponent){
            tmp->Exponent=a->Exponent;
            tmp->Coefficient=a->Coefficient+b->Coefficient;
            a=a->Next;
            b=b->Next;
            if(tmp->Coefficient==0) continue;//系数可能为0
        }
        else if(a->Exponent>b->Exponent){
            tmp->Exponent=a->Exponent;
            tmp->Coefficient=a->Coefficient;
            a=a->Next;
        }
        else{
            tmp->Exponent=b->Exponent;
            tmp->Coefficient=b->Coefficient;
            b=b->Next;
        }
        tmp->Next=NULL;
        
        pre->Next=tmp;//pre遍历
        pre=tmp;//遍历
    }
    
    //其中一个多项式遍历完了
    if(a!=NULL&&b==NULL) pre->Next=a;
    else if(a==NULL&&b!=NULL) pre->Next=b;
    
    return head;
}

# 6-2 Reverse Linked List

Write a nonrecursive procedure to reverse a singly linked list in O(N) time using constant extra space.

# Format of functions:

1	List Reverse( List L );

where List is defined as the following:

typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node {
    ElementType Element;
    Position Next;
};

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

# Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node {
    ElementType Element;
    Position Next;
};

List Read(); /* details omitted */
void Print( List L ); /* details omitted */
List Reverse( List L );

int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}

/* Your function will be put here */

# Sample Input:

1 2	5 1 3 4 5 2

# Sample Output:

1 2	2 5 4 3 1 2 5 4 3 1

List Reverse( List L )
{
    PtrToNode p = NULL, q = NULL, r = NULL;
    p = L->Next;
    r = NULL;
    if(L->Next == NULL || p->Next == NULL){
        return L;
    }
    while(p){
        q = p->Next;
        p->Next = r;
        r = p;
        p = q;
    }
    L->Next = r;
    return L;
}

见期中模拟卷

# 线性表

# 线性表的定义与操作–顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

typedef int Position;
typedef struct LNode *List;
struct LNode { 
    ElementType Data[MAXSIZE];
    Position Last;
};

/* 初始化 */
List MakeEmpty()
{ 
    List L; 
    L = (List)malloc(sizeof(struct LNode)); 
    L->Last = -1; 
    return L;
}

/* 查找 */
#define ERROR -1
Position Find( List L, ElementType X )
{ 
    Position i = 0; 
    while( i <= L->Last && L->Data[i]!= X ) 
        i++; 
    if ( i > L->Last ) 
        return ERROR; /* 如果没找到，返回错误信息 */ 
    else return i; /* 找到后返回的是存储位置 */
}

/* 插入 */
bool Insert( List L, ElementType X, Position P ) 
{ 
    /* 在L的指定位置P前插入一个新元素X */ 
    Position i; 
    if ( L->Last == MAXSIZE-1) { /* 表空间已满，不能插入 */ 
        printf("表满"); 
        return false; 
    } 
    if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */ 
        printf("位置不合法"); 
        return false; 
    } 
    for( i=L->Last; i>=P; i-- ) 
        L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */ 
    L->Data[P] = X; /* 新元素插入 */ 
    L->Last++; /* Last仍指向最后元素 */ 
    return true; 
}

/* 删除 */
bool Delete( List L, Position P )
{ 
    /* 从L中删除指定位置P的元素 */ 
    Position i; 
    if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */ 
        printf("位置%d不存在元素", P ); 
        return false; 
    } 
    for( i=P+1; i<=L->Last; i++ ) 
        L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */ 
    L->Last--; /* Last仍指向最后元素 */ 
    return true; 
}

# 线性表的定义与操作–链表

typedef struct LNode *PtrToLNode;
struct LNode { 
    ElementType Data; 
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

/* 查找 */
#define ERROR NULL
Position Find( List L, ElementType X )
{ 
    Position p = L; /* p指向L的第1个结点 */ 
    while ( p && p->Data!=X ) 
        p = p->Next; 
    /* 下列语句可以用 return p; 替换 */ 
    if ( p ) return p; 
    else return ERROR;
}

/* 带头结点的插入 */
bool Insert( List L, ElementType X, Position P )
{ 
    /* 这里默认L有头结点 */ 
    Position tmp, pre; 
    /* 查找P的前一个结点 */ 
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; 
    if ( pre==NULL ) { 
        /* P所指的结点不在L中 */ 
        printf("插入位置参数错误\n"); 
        return false; 
    } else { 
        /* 找到了P的前一个结点pre */ 
        /* 在P前插入新结点 */ 
        tmp = (Position)malloc(sizeof(struct LNode)); 
        /* 申请、填装结点 */ 
        tmp->Data = X; 
        tmp->Next = P; 
        pre->Next = tmp; 
        return true; 
    }
}

/* 带头结点的删除 */
bool Delete( List L, Position P )
{ 
    /* 这里默认L有头结点 */ 
    Position pre; 
    /* 查找P的前一个结点 */ 
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ; 
    if ( pre==NULL || P==NULL) {
        /* P所指的结点不在L中 */ 
        printf("删除位置参数错误\n"); 
        return false; 
    } else { 
        /* 找到了P的前一个结点pre */ 
        /* 将P位置的结点删除 */ 
        pre->Next = P->Next; 
        free(P); 
        return true; 
    }
}

If N numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is O(logN).

链表不能用二分查找，只能从头开始遍历

# HW3

# 2-1 Push 5 characters `ooops` onto a stack. In how many different ways that we can pop these characters and still obtain `ooops` ?

C.5

stack-FILO

queue-FIFO

# 2-3 Suppose that an array of size 6 is used to store a circular queue, and the values of `front` and `rear` are 0 and 4, respectively. Now after 2 dequeues and 2 enqueues, what will the values of `front` and `rear` be?

graph LR;
0-->1;
1-->2;
2-->3;
3-->4;
4-->5;
5-->0;

In circular queue:

Rear = 0, front = 1

Empty: Rear = front-1

When enqueue, rear ++

When dequeue, front++

front = 0 + 2 = 2

rear = (4 + 2)%6 = 0

# 编程题

# 7-1 Pop Sequence

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

# Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

# Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

# Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

# Sample Output:

YES
NO
NO
YES
NO

#include<stdio.h>
int main(){
    int m, n, k;
    scanf("%d %d %d",&m, &n, &k);
    int stack[n], pop[n], result[k];
    int i, j;
    int ptr_s = 0, ptr_p = 0, element = 1;
    for(i = 0; i<k; i++){
        ptr_s =0, ptr_p = 0, element = 1;
        for(j = 0; j<n; j++){
            scanf("%d", &pop[j]);
        }
        while(ptr_p<n){
            if(element == pop[ptr_p]&&ptr_s<m){
                element++;
                ptr_p++;
            }else if(stack[ptr_s-1] == pop[ptr_p] && ptr_s>=0 && ptr_s<=m){
                ptr_p++;
                ptr_s--;
            }else if(element<=n && ptr_s<=m){
                stack[ptr_s] = element;
                ptr_s++;
                element++;
            }else{
                break;
            }
        }
        if(ptr_p<n){
            result[i] = 0;
        }else{
            result[i] = 1;
        }
    }
    for(i = 0; i<k; i++){
        if(result[i] == 0){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

新开一个栈用来存 1234567，然后依次比较用来 pop 栈顶元素和 popseq 的栈的元素，相等就 pop。

# HW4

# 1-1 It is always possible to represent a tree by a one-dimensional integer array.

二叉树可以经过前序遍历、中序遍历、后序遍历得到一维数组。其他 degree 的树也同理。

# 1-2 There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.

假设没有孩子的结点（叶结点）个数为 n₀，只有一个孩子的结点（度为 1 的结点）个数为 n₁，有两个孩子的结点（度为 2 的结点）个数为 n₂。
则 n₀+n₁+n₂=2016
∵n₀=n₂+1（二叉树的性质：叶结点个数等于度为 2 的结点个数加 1）
∴n₀+n₁+n₂=2016
⇨n₂+1+16+n₂=2016
⇨2n₂=1999
n₂除不尽，所以答案错误。

【 Theorem 】 A tree with n vertices has n-1 edges.

【 Theorem 】 edge = 1/2(sum of degree)

【 Theorem 】A full m-ary tree with i internal vertices contains n=mi+1 vertices.

For a full binary tree, l= i +1, e = v - 1.

对于二叉树来说，叶子结点的个数等于中间节点个数 + 1，边数等于节点数 - 1

# 2-1 Given a tree of degree 3. Suppose that there are 3 nodes of degree 2 and 2 nodes of degree 3. Then the number of leaf nodes must be ____.

$n=n_0+n_1+n_2+n_3$

$e=n-1=n_1+2n_2+3n_3$

$-->n_0=n_2+2n_3+1$

直接画一棵树

graph TD;
0-->1;
0-->2;
1-->3;
1-->4;
2-->5;
2-->6;
3-->7;
3-->8;
3-->9;
5-->10;
5-->11;
5-->12;

# 2-2 If a general tree T is converted into a binary tree BT, then which of the following BT traversals gives the same sequence as that of the post-order traversal of T?

B. In-order traversal

普通树转二叉树

1
2
3

将树的根节点直接作为二叉树的根节点
将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子
将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中

T：
前序 preorder：ABEICFDGJH
中序无（多节点没法定义中序）
后序：IEBFCJGHDA

BT：
前序 preorder: ABEICFDGJH
中序 inorder：IEBFCJGHDA
后序 postorder:IEBFJHGDCBA
层级 levelorder：ABECIFDGJH

结论：

T 的 preorder = BT 的 preorder
T 的 postorder = BT 的 inorder

preorder - 根左右 inorder - 左根右 postorder - 左右根

还可以这样理解普通树转换成二叉树（实际上是一样的）：

在所有兄弟结点之间加一连线
对每个结点，除了保留与其第一个儿子的连线外，去掉该结点与其它孩子的连线

# 2-3 Given the shape of a binary tree shown by the figure below. If its inorder traversal sequence is { E, A, D, B, F, H, C, G }, then the node on the same level of C must be:

未标题-2.jpg

B.E

graph TD
F-->E
F-->C
E-->_
E-->D
D-->A
D-->B
C-->H
C-->G

中序遍历：左根右

# 2-4 Among the following threaded binary trees (the threads are represented by dotted curves), which one is the postorder threaded tree?

thread tree 线索二叉树

下面这个树，后序排序是：dbca
前驱就是前面的，比如 b 的前驱是 d, d 的前驱是 Null
后驱就是后面的，比如 d 的后驱是 b，a 的后驱是 Null
d 有两个指针没有用，左边指向前驱 Null，右边指向 b（然后就选出来 B 了）
b 的右节点有用的（已经指向 d 了），左节点指向其前驱，也就是 d
c 前驱是 b，后驱是 a，所以左指向 b，右指向 a
a 没有指针可用了（已经左为 b 右为 c）了
所以选 B。

# Expression Trees (syntax trees)

prefix/infix/postfix 分别对应前序遍历、中序遍历、后序遍历

# 6-1 Isomorphic

Two trees, T1 and T2 , are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1 . For instance, the two trees in Figure 1 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. Give a polynomial time algorithm to decide if two trees are isomorphic.

# Format of functions:

1	int Isomorphic( Tree T1, Tree T2 );

where Tree is defined as the following:

typedef struct TreeNode *Tree;
struct TreeNode {
    ElementType Element;
    Tree  Left;
    Tree  Right;
};

The function is supposed to return 1 if T1 and T2 are indeed isomorphic, or 0 if not.

# Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;

typedef struct TreeNode *Tree;
struct TreeNode {
    ElementType Element;
    Tree  Left;
    Tree  Right;
};

Tree BuildTree(); /* details omitted */

int Isomorphic( Tree T1, Tree T2 );

int main()
{
    Tree T1, T2;
    T1 = BuildTree();
    T2 = BuildTree();
    printf(“%d\n”, Isomorphic(T1, T2));
    return 0;
}

/* Your function will be put here */

# Sample Output 1 (for the trees shown in Figure 1):

# Sample Output 2 (for the trees shown in Figure 2):

int Isomorphic(Tree T1,Tree T2)
{
 	if((T1 == NULL) && (T2 == NULL))  //树都为空树，视为同构 
 	    return 1;
 	if(((T1 == NULL)&&(T2 != NULL)) || ((T1 != NULL)&&(T2 == NULL)))  //两树其中之一为空树,不同构 
	    return 0;
	if(T1->Element != T2->Element)  //若两树都非空的话，比较根结点 
	    return 0;
	if((T1->Left == NULL) && (T2->Left == NULL))  //左子树都为空，比较右子树 
	    return Isomorphic(T1->Right,T2->Right);
    if((T1->Left != NULL)&&(T2->Left != NULL) && (T1->Left->Element == T2->Left->Element))
    /*左子树非空，并且左子树根结点相同，递归比较左右子树*/ 
        return (Isomorphic(T1->Left,T2->Left) && Isomorphic(T1->Right,T2->Right));
    else
        return (Isomorphic(T1->Left,T2->Right) && Isomorphic(T1->Right,T2->Left));
 }

# HW5

# 1-2 In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.

不一定是父节点，可能是祖先节点。

# 2-2 Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible?

1	83 67 91 98 20 75

1	83 67 75 91 20 98

1	83 91 75 67 20 98

1	83 91 98 67 75 20

# Binary Search Tree

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。
二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

非空左子树的所有键值小于其根结点的键值。
非空右子树的所有键值大于其根结点的键值。
左、右子树都是二叉搜索树。

定义：

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */
    ElementType Data; /* 结点数据 */
    BinTree Left;     /* 指向左子树 */
    BinTree Right;    /* 指向右子树 */
};

查找

（1）查找从根结点开始，如果树为空，返回 NULL
（2）若搜索树非空，则根结点关键字和 X 进行比较，并进行不同处理：
① 若 X 小于根结点键值，只需在左子树中继续搜索；
② 如果 X 大于根结点的键值，在右子树中进行继续搜索；
③若两者比较结果是相等，搜索完成，返回指向此结点的指针。

Position Find( ElementType X, BinTree BST )
{
	if( !BST ) return NULL; /*查找失败*/
	if( X > BST->Data )
		return Find( X, BST->Right ); /*在右子树中继续查找*/
	else if( X < BST->Data )
		return Find( X, BST->Left ); /*在左子树中继续查找*/
	else /* X == BST->Data */
		return BST; /*查找成功，返回结点的找到结点的地址*/
}

查找最小（递归法）

Position FindMin( BinTree BST )
{
	 if( !BST ) 
	 	return NULL; /*空的二叉搜索树，返回NULL*/
	 else if( !BST->Left )
	 	return BST; /*找到最左叶结点并返回*/
	 else
	 	return FindMin( BST->Left ); /*沿左分支继续查找*/
}

查找最大（迭代法）

Position FindMax( BinTree BST )
{
	 if(BST )
	 	while( BST->Right )  /*沿右分支继续查找，直到最右叶结点*/
	 		BST = BST->Right;
	 return BST;
}

插入

从根节点开始比较，大的插右边，小的插左边

BinTree Insert( BinTree BST, ElementType X )
{
    if( !BST ){ /* 若原树为空，生成并返回一个结点的二叉搜索树 */
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else { /* 开始找要插入元素的位置 */
        if( X < BST->Data )
            BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
        else  if( X > BST->Data )
            BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
        /* else X已经存在，什么都不做 */
    }
    return BST;
}

删除

BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 
    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else 
        { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) 
            {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else 
            { /* 被删除结点有一个或无子结点 */
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                free( Tmp );
            }
        }
    }
    return BST;
}

# Given a binary search tree with its preorder traversal sequence { 8, 2, 15, 10, 12, 21 }. If 8 is deleted from the tree, which one of the following statements is FALSE?

A. One possible preprder traversal sequence of the resulting tree may be

B. One possible preprder traversal sequence of the resulting tree may be

C. One possible preprder traversal sequence of the resulting tree may be

D. It is possible that the new root may have 2 children

8 是根节点，删除之后根可能是左子树最大的元素或者右子树最小的元素

graph TD
8-->2
8-->15
15-->10
10-->_
10-->12
15-->21

delete 8:

graph TD
2-->15
15-->10
10-->-
10-->12
15-->21

graph TD
10-->2
10-->15
15-->12
15-->21

# 2-4 Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty binary search tree. The postorder traversal sequence of the resulting tree is:

A. 1, 2, 3, 4, 6, 7, 5

B. 1, 4, 2, 6, 3, 7, 5

C. 1, 4, 3, 2, 6, 7, 5

D. 5, 4, 3, 7, 6, 2, 1

注意是 one by one，所以选 C

graph TD
5-->2
5-->7
2-->1
2-->3
3-->_
3-->4
7-->6
7-->-

后序遍历：1 4 3 2 6 7 5

# 2-5 Among the following binary trees, which one can possibly be the decision tree (the external nodes are excluded) for binary search?

决策树：左子树总是大于等于右子树或者右子树总是大于等于左子树才符合。

用排除法可得 A

# 2-6 For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence?

A. preorder traversal

B. postorder traversal

C. inorder traversal

D. level-order traversal

中序遍历得到的序列是非递减的，前序遍历和后序遍历得到的都是无序的。

# HW6

# 1-1 If a complete binary tree with 137 nodes is stored in an array (root at position 1), then the nodes at positions 128 and 137 are at the same level.

完全二叉树：若二叉树的深度为 h，则除第 h 层外，其他层的结点全部达到最大值，且第 h 层的所有结点都集中在左子树。

满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

堆（heap)

堆（英语：heap) 是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆是非线性数据结构，相当于一维数组，有两个直接后继。

注意：在二叉树中，若当前节点的下标为 i，则其父节点的下标为 i/2，其左子节点的下标为 i*2，其右子节点的下标为 i*2+1；

# 1-2 The inorder traversal sequence of any min-heap must be in sorted order.

在最小堆中，虽然父节点的值小于或等于其子节点的值，但是并没有要求兄弟节点之间的大小关系。因此，在进行中序遍历时，并不能保证得到一个有序的序列。（完全二叉树 vs 二叉搜索树）

# 2-1 In a max-heap with n (>1) elements, the array index of the minimum key may be __.

A. 1

B. ⌊n/2⌋−1

C. ⌊n/2⌋

D. ⌊n/2⌋+2

最大堆最小的元素在叶子结点上，⌊n/2⌋有子节点是⌊n⌋，所以肯定不是最小的元素，只能选 D

# 2-2 Using the linear algorithm to build a min-heap from the sequence {15, 26, 32, 8, 7, 20, 12, 13, 5, 19}, and then insert 6. Which one of the following statements is FALSE?

A. The root is 5

B. The path from the root to 26 is

C. 32 is the left child of 12

D. 7 is the parent of 19 and 15

先按 level order 建堆，然后从第一个父节点开始上滤，直到得到 MinHeap

插入 6：插入之后依旧是完全二叉树，然后上滤

堆的插入

插入到最后一层最左侧的位置，然后和父节点比较，如果最小堆插入的元素比父节点小就和父节点交换位置，一直换到比父节点大为止，复杂度 O (logn)。

void  Insert( ElementType  X,  PriorityQueue  H ) 
{ 
     int  i; 

     if ( IsFull( H ) ) 
     { 
		Error( "Priority queue is full" ); 
		return; 
     } 
	/*首先确定初始位置是堆的个数+1，这个位置到根的路径是i/2*/
     for ( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 ) 
		H->Elements[ i ] = H->Elements[ i / 2 ]; 
		/*当第(i/2)个大于X的时候，就往后移动，i/2小于X的时候，就让孩子i变成X*/
		
     H->Elements[ i ] = X; //
}

堆的删除

堆中每次都只能删除堆顶元素。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整 (shift_down)。

ElementType  DeleteMin( PriorityQueue  H ) 
{ 
    int  i, Child; 
    ElementType  MinElement, LastElement; 
    if ( IsEmpty( H ) ) 
    { 
         Error( "Priority queue is empty" ); 
         return  H->Elements[ 0 ];   
    } 
    MinElement = H->Elements[ 1 ];  /* save the min element */
    LastElement = H->Elements[ H->Size-- ];  /* take last and reset size */
    for ( i = 1; i * 2 <= H->Size; i = Child ) 
    {  /* Find smaller child */ 
         Child = i * 2; 
         if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child]) 
	       Child++;     /*如果child+1更小，让child指向child+1*/
         if ( LastElement > H->Elements[ Child ] )   /* Percolate one level */ 
	     	H->Elements[ i ] = H->Elements[ Child ]; /*把child放在i的位置，和最后一句对应*/
         else
         	break;   /* find the proper position */
    } 
    H->Elements[ i ] = LastElement; /*把本来的最后一个元素放在i的位置，和上面那句对应*/
    return  MinElement; 
}

建堆

1) 首先把数组按照层序（level order）放在一个空堆中
(2) 从最后一个父节点开始，让父节点，右孩子，左孩子中最小的放在父节点的位置。
(3) 如果父节点被换下去了，那么必须执行 shiftdown 操作，即被换下去的结点与当前的子节点比较，并交换，直到符合比任何一个子节点大的条件。
对于 2-2

graph TD;
15-->26;
15-->32;
26-->8;
26-->7;
32-->20;
32-->12;
8-->13;
8-->5;
7-->19;

一开始按层序遍历建堆，接下来从第一个父节点 7 开始执行 shift_down，不变

然后对 8shift_down，交换 8 和 5

graph TD;
15-->26;
15-->32;
26-->5;
26-->7;
32-->20;
32-->12;
5-->13;
5-->8;
7-->19;

以此类推

总的过程：

对 7shiftdown: 不变
对 8shiftdown:15 26 32 5 7 20 12 13 8 19
对 32shiftdown:15 26 12 5 7 20 32 13 8 19
对 26shiftdown:15 5 12 8 7 20 32 13 26 19
对 15shiftdown: 5 7 12 8 15 20 32 13 26 19
插入 6: 6 12 8 7 20 32 13 20 19 15

# 2-3 If a d-heap is stored as an array, for an entry located in position i, the parent, the first child and the last child are at:

A. ⌈(i+d−2)/d⌉, (i−2)d+2, and (i−1)d+1

B. ⌈(i+d−1)/d⌉, (i−2)d+1, and (i−1)d

C. ⌊(i+d−2)/d⌋, (i−1)d+2, and id+1

D. ⌊(i+d−1)/d⌋, (i−1)d+1, and id

# 2-6 If a binary search tree of N nodes is complete, which one of the following statements is FALSE?

A. the average search time for all nodes is O(logN)

二叉搜索的时间复杂度是 O (logN)，对

B. the minimum key must be at a leaf node

最左边的节点

C. the maximum key must be at a leaf node

最大值可能在上一层的最右边的结点（此节点只有 leftchildren），错

D. the median node must either be the root or in the left subtree

# 函数题

6-1 Percolate Up and Down

Write the routines to do a “percolate up” and a “percolate down” in a binary min-heap.

# Format of functions:

1 2	void PercolateUp( int p, PriorityQueue H ); void PercolateDown( int p, PriorityQueue H );

where int p is the position of the element, and PriorityQueue is defined as the following:

typedef struct HeapStruct *PriorityQueue;
struct HeapStruct {
    ElementType  *Elements;
    int Capacity;
    int Size;
};

# Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
#define MinData -1

typedef struct HeapStruct *PriorityQueue;
struct HeapStruct {
    ElementType  *Elements;
    int Capacity;
    int Size;
};

PriorityQueue Initialize( int MaxElements ); /* details omitted */

void PercolateUp( int p, PriorityQueue H );
void PercolateDown( int p, PriorityQueue H );

void Insert( ElementType X, PriorityQueue H ) 
{
    int p = ++H->Size;
    H->Elements[p] = X;
    PercolateUp( p, H );
}

ElementType DeleteMin( PriorityQueue H ) 
{ 
    ElementType MinElement; 
    MinElement = H->Elements[1];
    H->Elements[1] = H->Elements[H->Size--];
    PercolateDown( 1, H );
    return MinElement; 
}

int main()
{
    int n, i, op, X;
    PriorityQueue H;

    scanf("%d", &n);
    H = Initialize(n);
    for ( i=0; i<n; i++ ) {
        scanf("%d", &op);
        switch( op ) {
        case 1:
            scanf("%d", &X);
            Insert(X, H);
            break;
        case 0:
            printf("%d ", DeleteMin(H));
            break;
        }
    }
    printf("\nInside H:");
    for ( i=1; i<=H->Size; i++ )
        printf(" %d", H->Elements[i]);
    return 0;
}

/* Your function will be put here */

# Sample Input:

# Sample Output:

1 2	2 1 4 Inside H: 5 10 9

void PercolateUp( int p, PriorityQueue H )
{
    while(p>1 && H->Elements[p] < H->Elements[p/2]){
        int temp;
        temp = H->Elements[p];
        H->Elements[p] = H->Elements[p/2];
        H->Elements[p/2] = temp;
        p = p/2;
    }
}
void PercolateDown( int p, PriorityQueue H )
{
    while(p*2<=H->Size && H->Elements[p*2] < H->Elements[p]){
        int temp;
        temp = H->Elements[p];
        H->Elements[p] = H->Elements[p*2];
        H->Elements[p*2] = temp;
        p = p*2;
    }
}

PercolateUp 就是和父节点比较，如果比父节点小就交换，直到根节点或者比父节点大为止；

PercolateDown 就是和子节点比较，同理。

# HW7

并查集（disjoint set)

查找

SetType  Find ( ElementType X, 
                           DisjSet S )
{   for ( ; S[X] > 0; X = S[X] )   ;
    return  X ;
}

Please fill in the blanks in the program which performs Find as a Union/Find operation with path compression.

SetType Find ( ElementType X, DisjSet S )
{   
   ElementType root, trail, lead;

   for ( root = X; S[root] > 0; root=S[root] );  //查找
   for ( trail = X; trail != root; trail = lead ) {
      lead = S[trail];   
       S[trail]=root;
   } //路径压缩
   return root;
}

合并

void Union( ElementType i, ElementType j, DisjSet S )
{
    int root1, root2;
    root1 = Find(i);
    root2 = Find(j);
    S[root2] = root1;
}

Union by size:

Union by size 是一种基于并查集（Disjoint Set）的合并策略，用于在合并两个集合时选择根节点。该策略将小集合合并到大集合中，以减少合并后的树高度，提高查找效率。

具体来说，在 Union by size 策略中，每个集合的大小都可以表示为其根节点的负值，即 S [root] 的值是集合的大小。因此，当要将两个集合合并时，首先找到它们各自的根节点 root1 和 root2，并比较两个根节点所代表的集合大小。如果 S [root1] 大于 S [root2]，则将 root2 的父节点设为 root1，同时将 root1 的大小更新为两个集合的大小之和；否则，将 root1 的父节点设为 root2，同时将 root2 的大小更新为两个集合的大小之和。

这样做的原理是，将小集合合并到大集合中可以减少树的高度，从而提高了查找效率。因为树的高度越低，查找元素的时间复杂度就越小，路径压缩也更容易实现。

1-1 In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2, but not $$O(logN)$$.

graph TD
0-->1
0-->2
2-->3
2-->4
4-->5
4-->6

$height(T)<=log_2N+1$

# 2-3 Let T be a tree created by union-by-size with N nodes, then the height of T can be .

A.at most $$log_2N+1$$

B.at least $$log_2N+1$$

C.as large as $$N$$

D.anything that is greater than 1

# HW8

一些定义：

Complete graph: a graph that has the maximum number of edges.

An undirected graph G is connected if every pair of distinct vi and vj are connected.

(Connected) Component of an undirected G ::= the maximal connected subgraph—— 联通分量

最大联通分量

A tree ::= a graph that is connected and acyclic (无环的)

A DAG ::= a directed acyclic graph

Strongly connected directed graph G ::= for every pair of vi and vj in V( G ), there exist directed paths from vi to vj and from vj to vi. If the graph is connected without direction to the edges, then it is said to be weakly connected.

强联通：有向图的每一对顶点之间都有路径

弱连通：有向图底下的无向图之间都是联通的

边数最小的联通图是树，E=V-1

# 2-3 Given the adjacency list of a directed graph as shown by the figure. There is(are) __ strongly connected component(s).

A. 4 {{0, 1, 5}, {2}, {3}, {4}} B. 3 {{2}, {4}, {0, 1, 3, 5}} C. 1 {0, 1, 2, 3, 4, 5} D. 1 {0, 5, 1, 3}

graph LR;
0-->5;
1-->0;
1-->3;
2-->1;
2-->4;
3-->0;
3-->4;
5-->1;

强联通分量

在有向图 G 中，如果两个顶点 vi,vj 间（vi>vj）有一条从 vi 到 vj 的有向路径，同时还有一条从 vj 到 vi 的有向路径，则称两个顶点强连通 (strongly connected)。如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。有向图的极大强连通子图，称为强连通分量 (strongly connected components)，也就是说是图 G 的一些特殊子集。

# 1-3 If a directed graph G=(V, E) is weakly connected, then there must be at least |V| edges in G.

至少 | V|-1

# 2-1 If graph G is NOT connected and has 35 edges, then it must have at least ____ vertices.

A.7

B.8

C.9

D.10

$\frac{9×8}{2}=36>35$

9+1=10

重点区分：

# 2-2 A graph with 90 vertices and 20 edges must have at least __ connected component(s).

A.69

B.70

C.84

D.85

【解析】20×2=40，90-40+20=70

# 【区分】：A graph with 90 vertices and 20 edges must have at most __ connected component(s).

A.69

B.70

C.84

D.85

【解析】 (7×6)/2=21，90-7+1=84

# 2-4 Given an undirected graph G with 16 edges, where 3 vertices are of degree 4, 4 vertices are of degree 3, and all the other vertices are of degrees less than 3. Then G must have at least __ vertices.

A.10

B.11

C.13

D.15

$e=n_1+2n_2+3×4+4×3=16×2=32$

因为要求至少有几个，所以假设剩下的都是度为 2 的节点，32-24=8，8÷2=4，4+3+4=11

拓扑排序

拓扑排序存在的前提：

当且仅当一个有向图为有向无环图（directed acyclic graph，或称 DAG）时，才能得到对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。

方法：不断寻找入度为 0 的节点 pop 出去，删除该节点和相关的边

6-1 Is Topological Order

Write a program to test if a give sequence Seq is a topological order of a given graph Graph .

# Format of functions:

1	bool IsTopSeq( LGraph Graph, Vertex Seq[] );

where LGraph is defined as the following:

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

The function IsTopSeq must return true if Seq does correspond to a topological order; otherwise return false .

Note: Although the vertices are numbered from 1 to MaxVertexNum, they are indexed from 0 in the LGraph structure.

# Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef enum {false, true} bool;
#define MaxVertexNum 10  /* maximum number of vertices */
typedef int Vertex;      /* vertices are numbered from 1 to MaxVertexNum */

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

LGraph ReadG(); /* details omitted */

bool IsTopSeq( LGraph Graph, Vertex Seq[] );

int main()
{
    int i, j, N;
    Vertex Seq[MaxVertexNum];
    LGraph G = ReadG();
    scanf("%d", &N);
    for (i=0; i<N; i++) {
        for (j=0; j<G->Nv; j++)
            scanf("%d", &Seq[j]);
        if ( IsTopSeq(G, Seq)==true ) printf("yes\n");
        else printf("no\n");
    }

    return 0;
}

/* Your function will be put here */

# Sample Input (for the graph shown in the figure):

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

# Sample Output:

yes
yes
yes
no
no

bool IsTopSeq( LGraph Graph, Vertex Seq[] )
{
    Vertex InDegree[9999];
    for(int i = 0; i<9999; i++){
        InDegree[i] = 0;
    }
    PtrToAdjVNode p;
    int i;
    for(i = 0; i < Graph->Nv; i++){
        p = Graph->G[i].FirstEdge;
        while(p != NULL){
            InDegree[p->AdjV]++;
            p = p->Next;
        }
    }
    for(i = 0; i < Graph->Nv; i++){
        if(InDegree[Seq[i]-1] != 0){
            return false;
        }
        InDegree[Seq[i]-1] = -1;
        p = Graph->G[Seq[i]-1].FirstEdge;
        while(p != NULL){
            InDegree[p->AdjV]--;
            p = p->Next;
        }
    }
    return true;
}

Hamiltonian Cycle: 无向图中包含所有顶点的回路

Hamiltonian Path: 无向图中包含所有顶点的路径

哈密顿图：具有哈密顿回路的无向图

# HW9

无权图的单源最短路算法（BFS）

无权图的建立：

typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
    Vertex AdjV;
    PtrToAdjVNode Next;
};

typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];

typedef struct GNode *PtrToGNode;
struct GNode{  
    int Nv;
    int Ne;
    AdjList G;
};
typedef PtrToGNode LGraph;

跟 hw8 的一样

求从顶点 S 到任意一个顶点的最短路径

void Unweighted( Graph G, Queue Q, int dist[], int path[], Vertex S )
{
  Vertex V, U;
  NodePtr ptr;

  dist[S] = 0;
  Enqueue(S, Q);
  while ( !IsEmpty(Q) ) {
    V = Dequeue( Q ); //弹出队列的第一个元素
    for ( ptr=G->List[V].FirstEdge; ptr; ptr=ptr->Next) { //找到V的邻接点
      U = ptr->AdjV;
      if ( dist[U] == INFINITY ) {
         dist[U] = dist[V] + 1; //路径长度等于前一个点的路经长度+1
         path[U] = V; //把前一个点记录在当前点的path上
         Enqueue(U, Q); //把当前点入队
      }
    }
  }
}

有权图的单源最短路算法

Dijkstra 算法

多源最短路算法

Floyd 算法

# 2-3 If besides finding the shortest path from `S` to every other vertices, we also need to count the number of different shortest paths, we can modify the Dijkstra algorithm in the following way: add an array `count[]` so that `count[V]` records the number of different shortest paths from `S` to `V` . Then `count[V]` shall be initialized as:

A. count[S]=1; and count[V]=0 for other V

B. count[S]=0; and count[V]=1 for other V

C. count[V]=1 for all vertices

D. count[V]=0 for all vertices

# HW10

AOE 网

最早开始时间和最晚结束时间

V 代表事件，a 代表活动

事件（V）：

	V1	V2	V3	V4	V5	V6
最早开始时间	0	3	2	6	6	8
最晚完成时间	0	4	2	6	7	8

最早开始时间从前往后取最大的

最晚完成时间从后往前推 (用最早开始时间 - a），取最小的

最早开始时间 = 最晚完成时间 —— 关键路径

活动（A）：

	a1	a2	a3	a4	a5	a6	a7	a8
最早开始时间	0	0	3	3	2	2	6	6
最晚完成时间	1	0	4	4	2	5	6	7

最早开始时间取箭头的出发点的最早开始时间，最晚完成时间取箭头指向的点的最晚完成时间 - a

最早开始时间 = 最晚完成时间 —— 关键活动

Ford-Fulkerson Algorithm 寻找网络最大流

用 Residual Graph 添加反向路径，然后用原图减去 Residual Graph

worst-case time complexity: O (f*m) f 是最大流的大小，m 是边数

最小生成树

最小生成树：从连通无向图中找出一棵树（包含所有 n 个节点和 n-1 条边），同时边的权重之和要最小

Prim 算法：随便取一个根节点记作 visited，不断寻找 visited 节点和 unvisited 节点之间权重最小的边

Prim 算法寻找最小生成树

Kruskal 算法：（1）创建一个队列，将边按权重排序，最小的在最上面；（2）从顶端不断 dequeue，如果符合就在图中圈出那条边

—— 并查集

一句话：Prim 算法对点做操作，Kruskal 算法对边做操作

# HW11

# 1-1 For a graph, if each vertex has an even degree or only two vertexes have odd degree, we can find a cycle that visits every edge exactly once

欧拉回路：当且仅当图中每个顶点的度数都为偶数，并且图是连通的（一笔画）

欧拉路径：当且仅当图中恰有两个顶点的度数为奇数，其余顶点的度数都为偶数，并且图是连通的

哈密顿 Cycle：经过所有节点的环

哈密顿 Path：经过所有节点的回路

DFS: 寻路–回溯

# 2-1 Apply DFS to a directed acyclic graph, and output the vertex before the end of each recursion. The output sequence will be:

A.unsorted

B.topologically sorted

C.reversely topologically sorted

D.None of the above

Biconnected:（重连通）

插入排序：

void InsertionSort( ElementType A[], int N )
{
    int j, P;
    ElementType Tmp;
    
    for(P=1; P<N; P++){
        Tmp = A[P];
        for(j=P; j>0 && A[j-1]>Tmp; j--){
            A[j]=A[j-1];
        }
        A[j]=Tmp;
    }
}

worst-case time complexity: $$O(N^2)$$

best-case time complexity: $$O(N)$$

T(N,I) = O(I+N)$$ —— I:逆序对对于任意一个交换相邻元素的排序算法，平均时间复杂度都是$$\Omega(N^2)$$. **ShellSort** **希尔排序** 5-sort 3-sort 1-sort 每一步都是插入排序（1）Define an increment sequence h1 < h2 < … < ht ( h1 = 1 ) （2）Define an $$h_k-sort$$ at each phase for k = t, t - 1, …, 1 **Shell’s increment sequence：$$h_t=\lfloor N \rfloor$$, $$h_k = \lfloor h_k+1 / 2\rfloor $$** worst-case time complexity: $$\theta(N^2)

void Shellsort( ElementType A[ ], int N ) 
{ 
      int  i, j, Increment; 
      ElementType  Tmp; 
      for ( Increment = N / 2; Increment > 0; Increment /= 2 )  
	/*h sequence */
	for ( i = Increment; i < N; i++ ) { /* insertion sort */
	      Tmp = A[ i ]; 
	      for ( j = i; j >= Increment; j - = Increment ) 
		if( Tmp < A[ j - Increment ] ) 
		      A[ j ] = A[ j - Increment ]; 
		else 
		      break; 
		A[ j ] = Tmp; 
	} /* end for-I and for-Increment loops */
}

**Hibbard’s Increment Sequence: ** $$h_k = 2^k-1$$

worst-case time complexity: $$\theta(N$$^2/3$$)$$

in-place 不需要申请其余的空间

stability （插入排序稳定，希尔排序不稳定）

HeapSort

堆排序

void Heapsort( ElementType A[ ], int N ) 
{  int i; 
    for ( i = N / 2; i >= 0; i - - ) /* BuildHeap */ 
        PercDown( A, i, N ); 
    for ( i = N - 1; i > 0; i - - ) { 
        Swap( &A[ 0 ], &A[ i ] ); /* DeleteMax */ 
        PercDown( A, 0, i ); 
    }
}

时间复杂度 $$O (NlogN)$$

归并排序

$O(NlogN)$

快排

fds

# FDS 复习

# 期中模拟卷

# 1.NlogN\sqrt N logNN​logN is O(N)O(N)O(N).

# 2.In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2 , but not O(logN)O(logN)O(logN).

# 3.For a sequentially stored linear list of length N, the time complexities for query and insertion are:

# 4.The following figure shows the AOE network of a project with 8 activities. The earliest and the latest start times of the activity d are __, respectively.

# 6. 程序填空题 Reverse Linked List

# 7. 程序填空题 MinHeap Deletion

# HW1

# 1-2 The Fibonacci number sequence {FNF_NFN​} is defined as: F0=0,F1=1,F_0=0,F_1=1,F0​=0,F1​=1, FN=FN−1+FN−2F_N=F_{N-1}+F_{N-2}FN​=FN−1​+FN−2​, N=2, 3, … The time complexity of the function which calculates FNF_NFN​ recursively is Θ(N!)\Theta(N!)Θ(N!).

# 2-1 Given the following four algorithms with their runtimes for problem size 100 and their time complexities:

# 2-3 The recurrent equations for the time complexities of programs P1 and P2 are:

# R1-2 (logN)2(logN)^2(logN)2is O(N)O(N)O(N).

# R1-3 The time comlexity of Selection Sort will be the same no matter we store the elements in an array or a linked list.

# HW2

# 1-1 For a sequentially stored linear list of length N, the time complexities for deleting the first element and inserting the last element are O(1) and O(N), respectively.

# 2-3 To merge two singly linked ascending lists, both with N nodes, into one singly linked ascending list, the minimum possible number of comparisons is:

# 函数题

# 6-1 Add Two Polynomials

# Format of functions:

# Sample program of judge:

# Sample Input:

# Sample Output:

# 6-2 Reverse Linked List

# Format of functions:

# Sample program of judge:

# Sample Input:

# Sample Output:

# 线性表

# 线性表的定义与操作–顺序表

# 线性表的定义与操作–链表

# HW3

# 2-1 Push 5 characters ooops onto a stack. In how many different ways that we can pop these characters and still obtain ooops ?

# 2-3 Suppose that an array of size 6 is used to store a circular queue, and the values of front and rear are 0 and 4, respectively. Now after 2 dequeues and 2 enqueues, what will the values of front and rear be?

# 编程题

# 7-1 Pop Sequence

# Input Specification:

# Output Specification:

# Sample Input:

# Sample Output:

# HW4

# 1-1 It is always possible to represent a tree by a one-dimensional integer array.

# 1-2 There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child.

# 2-1 Given a tree of degree 3. Suppose that there are 3 nodes of degree 2 and 2 nodes of degree 3. Then the number of leaf nodes must be ____.

# 2-2 If a general tree T is converted into a binary tree BT, then which of the following BT traversals gives the same sequence as that of the post-order traversal of T?

# 2-3 Given the shape of a binary tree shown by the figure below. If its inorder traversal sequence is { E, A, D, B, F, H, C, G }, then the node on the same level of C must be:

# 2-4 Among the following threaded binary trees (the threads are represented by dotted curves), which one is the postorder threaded tree?

# Expression Trees (syntax trees)

# 6-1 Isomorphic

# Format of functions:

# Sample program of judge:

# Sample Output 1 (for the trees shown in Figure 1):

# Sample Output 2 (for the trees shown in Figure 2):

# HW5

# 1-2 In a binary search tree which contains several integer keys including 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent.

# 2-2 Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible?

# Binary Search Tree

# Given a binary search tree with its preorder traversal sequence { 8, 2, 15, 10, 12, 21 }. If 8 is deleted from the tree, which one of the following statements is FALSE?

# 2-4 Insert {5, 2, 7, 3, 4, 1, 6} one by one into an initially empty binary search tree. The postorder traversal sequence of the resulting tree is:

# 2-5 Among the following binary trees, which one can possibly be the decision tree (the external nodes are excluded) for binary search?

# 2-6 For a binary search tree, in which order of traversal that we can obtain a non-decreasing sequence?

# HW6

# 1-1 If a complete binary tree with 137 nodes is stored in an array (root at position 1), then the nodes at positions 128 and 137 are at the same level.

# 1-2 The inorder traversal sequence of any min-heap must be in sorted order.

# 2-1 In a max-heap with n (>1) elements, the array index of the minimum key may be __.

# 2-2 Using the linear algorithm to build a min-heap from the sequence {15, 26, 32, 8, 7, 20, 12, 13, 5, 19}, and then insert 6. Which one of the following statements is FALSE?

# 2-3 If a d-heap is stored as an array, for an entry located in position i, the parent, the first child and the last child are at:

# 2-6 If a binary search tree of N nodes is complete, which one of the following statements is FALSE?

# 函数题

# Format of functions:

# Sample program of judge:

# Sample Input:

# Sample Output:

# HW7

# 2-3 Let T be a tree created by union-by-size with N nodes, then the height of T can be .

# HW8

# 2-3 Given the adjacency list of a directed graph as shown by the figure. There is(are) __ strongly connected component(s).

# 1-3 If a directed graph G=(V, E) is weakly connected, then there must be at least |V| edges in G.

# 2-1 If graph G is NOT connected and has 35 edges, then it must have at least ____ vertices.

# 2-2 A graph with 90 vertices and 20 edges must have at least __ connected component(s).

# 1. $\sqrt N logN$ is $O(N)$ .

# 2.In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2 , but not $O(logN)$ .

# 3.For a `sequentially stored` linear list of length N, the time complexities for query and insertion are:

# 4.The following figure shows the AOE network of a project with 8 activities. The earliest and the latest start times of the activity `d` are __, respectively.

# 1-2 The Fibonacci number sequence { $F_N$ } is defined as: $F_0=0,F_1=1,$ $F_N=F_{N-1}+F_{N-2}$ , N=2, 3, … The time complexity of the function which calculates $F_N$ recursively is $\Theta(N!)$ .

# R1-2 $(logN)^2$ is $O(N)$ .

# 1-1 For a `sequentially stored` linear list of length N, the time complexities for deleting the first element and inserting the last element are O(1) and O(N), respectively.

# 2-1 Push 5 characters `ooops` onto a stack. In how many different ways that we can pop these characters and still obtain `ooops` ?

# 2-3 Suppose that an array of size 6 is used to store a circular queue, and the values of `front` and `rear` are 0 and 4, respectively. Now after 2 dequeues and 2 enqueues, what will the values of `front` and `rear` be?