Problem Set¶

记录一些错题

期末¶

10 道判断 + 20 道单选 + 2 道程序填空 + 1 道函数题

4.28 期中¶

单选¶

Given a directed graph of 5 vertices and 8 edges. Which one of the following statements is true?

A.The sum of degrees of all the vertices is 8.

B.There are totally 16 nodes in the adjacency list representation of the graph.

C.The sum of in-degrees of all the vertices is 8.

D.There are 16 non-zero elements in the adjacency matrix representation of the graph.

程序填空¶

MaxHeap Deletion

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]) ) { 
            ___________;
            p /= 2;
        } 
    }
    else {
        while( (child = 2*p) <= H->Size) {
            if ( child != H->Size && @@ )
                child ++;
            if ( _______________ ) {
                H->Elements[p] = H->Elements[child];
                p = child;
            }
            else
                break;
        }
    }
    H->Elements[p] = temp;
}

Function Call Simulation with Linked Stack

typedef struct node {
    int data;
    struct node *next;
} StackNode, *Stack;

void Push(Stack S, int data) {
    StackNode *p = (StackNode*)malloc(sizeof(StackNode));
    p->data = data;
    @@;
    @@;
}

int Pop(Stack S) {
    StackNode *p = S->next;
    int data = p->data;
    S->next = p->next;
    free(p);
    return data;
}

int GetTop(Stack S) {
    return S->next->data;
}

void Simulate(int call[][MAXN], int cnt[]) {
    int ptr[MAXN] = {0};
    
    StackNode head;
    Stack S = &head;
    S->next = NULL;

    Push(S, 1);
    printf("Enter 1\n");

    while (@@) {
        int u = GetTop(S);
        
        if (@@) {
            int v = call[u][ptr[u]++];
            Push(S, v);
            printf("Enter %d\n", v);
        } else {
            Pop(S);
            printf("Exit %d\n", u);
        }
    }
}