浙江大学2021–2022学年秋冬学期 《数据结构基础》课程期末考试试卷
R5-1

The function is to sort the array A in descending order. The function Swap(&A[0], &A[i]) is to exchange A[0] and A[i]. Please complete the following program.

#define leftchild(i) (2*(i)+1)
void PercDown(ElementType A[], int i, int N) {
    int child;
    ElementType tmp;
    for (tmp = A[i]; leftchild(i) < N; i = child) {
        child = leftchild(i);
        if (
3分
) child++; if (tmp > A[child]) A[i] = A[child]; else break; } A[i] = tmp; } void Heapsort(ElementType A[], int N) { int i; for (i = N / 2; i >= 0; i--) PercDown(A, i, N); for (i = N - 1; i > 0; i--) { Swap(&A[0], &A[i]);
3分
; } }
作者
郑友怡
单位
浙江大学
时间限制
400 ms
内存限制
64 MB
5-1
答案正确
(6 分)

R5-2

The following program implements the topological sort algorithm with a stack. Please fill in the blanks.

void Topsort(int a[NUM][NUM], int TopNum[NUM])  
// a[NUM][NUM] is adjacency matrix of the graph with NUM vertices
// TopNum[NUM] stores the topological orders 
{   int S[NUM],  Indegree[NUM];        //S[NUM] is a stack
    int  Counter = 0, top, n, i, j;     
    int V;     
    top= -1;
    n=NUM;
    for (j=0; j<n; j++) {
        Indegree[j]=0;
        for (i=0; i<n; i++)
            if (
3分
) Indegree[j]++; if ( Indegree[j] == 0 ) S[++top]=j; } while (top>=0) { V = S[top--]; TopNum[ V ] = ++ Counter; /* assign next */ for (j=0; j<n; j++) if ( a[V][j]!=0) if (
3分
== 0 ) S[++top]=j; } /* end-while */ if ( Counter!=n ) printf( "Graph has a cycle" ); }
作者
何钦铭
单位
浙江大学
时间限制
400 ms
内存限制
64 MB
5-2
答案正确
(6 分)