Skip to content

程序填空题

【2015-2016 期末】BinQueue_Merge

The function BinQueue_Merge is to merge two binomial queues H1 and H2, and return H1 as the resulting queue.

BinQueue BinQueue_Merge( BinQueue H1, BinQueue H2 ) { 
    BinTree T1, T2, Carry = NULL;
    int i, j;
    H1->CurrentSize += H2-> CurrentSize;
    for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
        T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i];
        switch( 4*!!Carry + 2*!!T2 + !!T1 ) {
            case 0:
            case 1: break;
            case 2: 【填空 1】; break;
            case 3: Carry = CombineTrees( T1, T2 );
                    H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
            case 4: H1->TheTrees[i] = Carry; Carry = NULL; break;
            case 6: Carry = CombineTrees( T2, Carry );
                    H2->TheTrees[i] = NULL; break;
            case 5: Carry = CombineTrees( T1, Carry );
                    H1->TheTrees[i] = NULL; break;
            case 7: H1->TheTrees[i] = Carry;
                    【填空 2】;
                    H2->TheTrees[i] = NULL; break;
        } /* end switch */
    } /* end for-loop */
    return H1;
}
答案
  1. H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL
  2. Carry = CombineTrees( T1, T2 )

【2016-2017 期末】BinQueue_Find

The functions BinQueue_Find and Recur_Find are to find X in a binomial queue H. Return the node pointer if found, otherwise return NULL.

BinTree BinQueue_Find( BinQueue H, ElementType X )
{
    BinTree T, result = NULL;
    int i, j; 

    for( i=0, j=1; j<=H->CurrentSize; i++, j*=2) {  /* for each tree in H */
        T= H->TheTrees[i];
        if (【填空 1】){  /* if need to search inside this tree */
            result = Recur_Find(T, X);
            if ( result != NULL ) return result;
        } 
    }
    return result;
}

BinTree Recur_Find( BinTree T, ElementType X )
{
    BinTree result = NULL;
    if ( X==T->Element ) return T;
    if ( T->LeftChild!=NULL ){
        result = Recur_Find(T->LeftChild, X);
        if ( result!=NULL ) return result;
    } 
    if (【填空 2】)
        result = Recur_Find(T->NextSibling, X);
    return result;
}
答案
  1. X >= T->Element
  2. T->NextSibling!=NULL

【2017-2018 期末】IsRBTree

The functions IsRBTree is to check if a given binary search tree T is a red-black tree. Return true if T is, or false if not.

The red-black tree structure is defined as the following:

typedef enum { red, black } colors;
typedef struct RBNode *PtrToRBNode;
struct RBNode{
int Data;
PtrToRBNode Left, Right, Parent;
int BH; /* black height */
colors Color;
};
typedef PtrToRBNode RBTree;

Please fill in the blanks.

bool IsRBTree( RBTree T ) {
    int LeftBH, RightBH;
    if ( !T ) return true;
    if ( T->Color == black ) T->BH = 1;
    else {
        if ( T->Left && (T->Left->Color == red)) return false;
        if ( T->Right && 【填空 1】) return false;
    }
    if ( !T->Left && !T->Right ) return true;
    if (【填空 2】) {
        if ( T->Left ) LeftBH = T->Left->BH;
        else LeftBH = 0;
        if ( T->Right ) RightBH = T->Right->BH;
        else RightBH = 0;
        if ( LeftBH == RightBH ) {
            【填空 3】;
            return true;
        }
        else return false;
    }
    else return false;
    }
答案
  1. (T->Right->Color == red)
  2. IsRBTree( T->Left ) && IsRBTree( T->Right )
  3. T->BH += LeftBH

【2018-2019 期末】DeleteRoot

The function DeleteRoot is to delete the root of a subtree with index Ind from a binomial queue H. The rest of the subtree is then stored as a new binomial queue and returned.

BinQueue DeleteRoot( BinQueue H, int Ind ) {
    BinTree OldRoot, SubTree;
    BinQueue NewBinQ;
    int i;

    OldRoot = H->TheTrees[Ind];
    SubTree = OldRoot->LeftChild;
    free(OldRoot);
    NewBinQ = Initialize();
    NewBinQ->CurrentSize = 【填空 1】;
    for (【填空 2】) {
        NewBinQ->TheTrees[i] = SubTree;
        SubTree = SubTree->NextSibling;
        NewBinQ->TheTrees[i]->NextSibling = NULL;
    }
    return NewBinQ;
}
答案
  1. (1<<Ind)-1
  2. i=Ind-1; i>=0; i--

【2019-2020 期末】FindKey

The function FindKey is to check if a given key is in a B+ Tree with its root pointed by root.

Return true if key is in the tree, or false if not. The B+ tree structure is defined as following:

static int order = DEFAULT_ORDER;
typedef struct BpTreeNode BpTreeNode;
struct BpTreeNode {
BpTreeNode** childrens; /* Pointers to childrens. This field is not used by leaf nodes. */
ElementType* keys;
BpTreeNode* parent;
bool isLeaf; /* 1 if this node is a leaf, or 0 if not */
int numKeys; /* This field is used to keep track of the number of valid keys.
In an internal node, the number of valid pointers is always numKeys + 1. */
};


bool FindKey(BpTreeNode * const root, ElementType key){
    if (root == NULL) {
        return false;
    }
    int i = 0;
    BpTreeNode * node = root;
    while (【填空 1】) {
        i = 0;
        while (i < node->numKeys) {
            if (【填空 2】) i++;
            else break;
        }
        node = node->childrens[i];
    }
    for(i = 0; i < node->numKeys; i++){
        if(node->keys[i] == key)
        return true;
    }
    return false;
}
答案
  1. !node->isLeaf
  2. key >= node->keys[i]

【2020-2021 期末】BinQueue_Merge

The function BinQueue_Merge is to merge two binomial queues H1 and H2, and return H1 as the resulting queue.

BinQueue BinQueue_Merge( BinQueue H1, BinQueue H2 ) { 
    BinTree T1, T2, Carry = NULL;     
    int i, j;
    H1->CurrentSize += H2-> CurrentSize;
    for ( i=0, j=1; j<= H1->CurrentSize; i++, j*=2 ) {
        T1 = H1->TheTrees[i]; T2 = H2->TheTrees[i];
        switch(【填空 1】) { 
            case 0:
            case 4: break;
            case 3: 
            case 7: 【填空 2】;
                    H2->TheTrees[i] = NULL; break;
            case 1: H1->TheTrees[i] = Carry; Carry = NULL; break;  
            case 2: H1->TheTrees[i] = T2; H2->TheTrees[i] = NULL; break;
            case 5: Carry = CombineTrees( T1, Carry );
                    H1->TheTrees[i] = NULL; break;
            case 6: Carry = CombineTrees( T1, T2 );
                    H1->TheTrees[i] = H2->TheTrees[i] = NULL; break;
        } /* end switch */
    } /* end for-loop */
    return H1;
}
答案

【2021-2022 期末】Knapsack

You have \(N\) items and a knapsack with a capacity of \(W\). The weight of the \(i\)-th item is \(w_i\) and the value is \(v_i\). Suppose the number of each item is infinite, calculate the maximum sum of value if the total weight of the items does not exceed the capacity of the knapsack. All numbers are in the range of \([1,1000]\).

#include<bits/stdc++.h>
using namespace std;
int f[1010],w[1010],v[1010],n,W;
int main() {
    scanf("%d%d", &n,&W);
    for(int i=1;i<=n;i++)
        scanf("%d%d", &w[i],&v[i]);
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=W;j++)
            【填空 1】
    printf("%d\n", 【填空 2】));
    return 0;
}
答案
  1. f[j]=max(f[j],f[j-w[i]]+v[i]);
  2. f[W]

【2022-2023 期末】ColorRBTree

The function ColorRBTree is to check if it is possible to color the nodes of a given binary search tree BST and turn it into a legal red-black tree. Return true if it is indeed possible, or false otherwise.

The tree structure is defined as the following:

typedef struct Node *PtrToNode;
struct Node{
    int data;
    int color; /* 1 for black and 0 for red */
    PtrToNode left, right, parent;
    int bh; /* black height */
    int npl; /* null path length */
};
typedef PtrToNode RBTree;

Please fill in the blanks.

bool ColorRBTree( RBTree BST ) {
    int H, ret = true;

    if (!BST->parent) {
        H = Get_Height(BST); /* get the height of BST */
        BST->color = 1;
        if (H%2)  H++; /* make tree height H an even number */
        BST->bh = H/2-1; /* the black height of the tree is at least H/2 */
        /* besides the root itself, there are at least BST->bh black nodes to be colored */
        if (BST->bh >= BST->npl)  ret = false; 
    }
    else {
        if (BST->parent->color == 0) {
            BST->color = 1;
            BST->bh = 【填空 1】;
            if (BST->bh < 0)  ret = false;
        }
        else {
            if (BST->npl > BST->parent->bh) {
                BST->color = 0;
                BST->bh = 【填空 2】;
            }
            else if (BST->npl == BST->parent->bh) {
                【填空 3】;
                BST->bh = BST->parent->bh - 1;
            }
            else ret = false;
        }
    }
    if (ret && BST->left)
        ret = ColorRBTree(BST->left);
    if (ret && BST->right)
        ret = ColorRBTree(BST->right);
    return ret;
}

C

【2023-2024 期末】Is it a B+ tree?

The teacher wants to write the IsBpT function to check if the trees submitted by students satisfy the definition of the B+ tree of a given order (e.g., order 4) learned in our class. The B+ tree structure is defined as follows:

typedef struct BpTNode BpTNode; 
struct BpTNode { 
    bool isLeaf; /* 1 if this node is a leaf, or 0 if not */
    bool isRoot; /* 1 if this node is the root, or 0 if not */
    BpTNode** children; /* Pointers to children. This field is not used by leaf nodes. */ 
    ElementType* keys;
    int num_children; /* Number of valid children (not NULL) */
    int num_keys; /* Number of valid keys */
};

Fortunately, the students are all brilliant, so the B+ trees they submit guarantee to meet the following properties:

  1. There is a root node, and all leaf nodes are at the same depth;

  2. The key values stored in all leaf nodes are arranged in strictly ascending order from left to right.

Your task is to complete the function IsBpT as follows so that the teacher can determine whether a tree submitted by a student meets the other properties required by the definition of the B+ tree of a given order. Return true if the tree is a B+ tree, or false if not.

bool IsBpT(BpTNode* node, int order) {
    if (node->isLeaf == 1) { /* this is a leaf node */
        if (node->isRoot == 1) { /* this tree has only one node */
            if (node->num_keys < 1 || node->num_keys > order) return false;
        }
        else {
            if (node->num_keys < (order + 1) / 2 || node->num_keys > order) return false;
        }
    }
    else {
        /* check the property of the tree structure */
        if (node->num_keys != node->num_children - 1) return false;
        if (node->isRoot == 1) { /* this is the root node */
            if (node->num_keys < 1 || node->num_keys > order - 1) return false;
            else if (node->num_children < 2 || node->num_children > order) return false;
        }
        else {
            if (【填空 1】|| node->num_keys > order - 1) return false;
            else if (node->num_children < (order + 1) / 2 || node->num_children > order) return false;
        }

        /* check the property of the value of key */
        for (int i = 0; i < node->num_keys; i++) {
            BpTNode* key_node = 【填空 2】;
            while (key_node->isLeaf == 0) {
                key_node = key_node->children[0];
            }
            if (node->keys[i] != key_node->keys[0]) return false;
        }
        for (int i = 0; i < node->num_children; i++) {
            if (IsBpT(node->children[i], order) == false) return false;
        }
    }
    return true;
}

【2024-2025 期末】Fill in B+ Tree

Given a B+ Tree of order odr, please calculate the maximum number of keys that can be inserted into the current tree root without causing any split operation.

typedef struct BpTreeNode BpTreeNode;
struct BpTreeNode {
    BpTreeNode** childrens; /* Pointers to childrens. This field is not used by leaf nodes. */
    ElementType* keys;
    BpTreeNode* parent;
    bool isLeaf; /* 1 if this node is a leaf, or 0 if not */
    int numKeys; /* This field is used to keep track of the number of valid keys.*/
};
int odr;

int Solve(BpTreeNode * const root){
    BpTreeNode * node = root;
    if (node->isLeaf) {
        return 【填空 1】;
    }
    int ans = 0;
    for(int i = 0;【填空 2】; i++) 
        ans += Solve(node->childrens[i]);
    return ans;
}
答案
  1. (odr-node->numKeys)
  2. i<=node->numKeys