2006年解析

一、单项选择题解析

二、判断题解析

三、填空题解析

1. 100个结点的完全二叉树叶子数 50（完全二叉树叶子数=⌈n/2⌉）

2. 哈夫曼树外部带权路径长度 构建过程：

   • 合并2,3(5)
   • 合并5,6(11)
   • 合并8,9(17)
   • 合并11,17(28) 外部路径长度=3*(9+8)+2*(6+3)+1*(2)=61

3. 完全二叉树最小叶子编号 ⌊n/2⌋ = ⌊n/2⌋（编号从0开始）

4. 连通无向图邻接矩阵最少非零元素 2(n-1)（树的情况）

5. 折半查找比较顺序 10,15,12（查找A[12]的比较序列）

6. 建堆交换元素 8与60交换（将8上浮）

7. 顺序查找最大值时间复杂度 O(n)

8. 广义表运算结果 e（运算过程：tail(L)=((d,e,f)), head(tail(L))=(d,e,f), head(head(tail(L)))=d, tail(head(head(tail(L))))=(e,f), head(tail(head(head(tail(L)))))=e）

9. 模式串next值序列 0,1,1,2（P="abaa"的next数组）

10. 两层100阶B+树最多记录数 100*100=10,000（第一层100个指针，第二层每个结点100个记录）

四、解析题解析

1. 二叉树构建

层次序列：A B C D E F G H J
中序序列：D B G E H J A C I F

构建的二叉树：
        A
      /   \
     B     C
    / \    \
   D   E    F
      / \   /
     G   H  I
          \
           J

2. 二叉排序树性质证明

证明： ① 中序后继没有左孩子： 中序后继是右子树的最左结点，若有左孩子则不是最左结点，矛盾。

② 中序前趋没有右孩子： 中序前趋是左子树的最右结点，若有右孩子则不是最右结点，矛盾。

3. Prim算法最小生成树

S:        Edge:
① ,2       (1,2,9)
①,2 ,3     (2,4,4)
①,2,3,4    (2,5,5)
①,2,3,4,5  (5,3,6)
①,2,3,4,5,6 (3,6,7)

4. 平衡二叉排序树构建

插入序列：17,31,13,11,20,35,25,8,4,11,24,40,27 构建过程需要多次旋转调整，最终平衡树结构（图示略）

5. 散列表构造与ASL计算

H(k)=k%13
插入序列：18,22,78,205,40,16,35,104,61

散列表：
0:78(78%13=0)
1:40(40%13=1)
2:35(35%13=9→冲突→(9+1)%13=10→冲突→(10+1)%13=11→冲突→(11+1)%13=12→冲突→(12+1)%13=0→...→2)
3:16(16%13=3)
4:17(无)
5:22(22%13=9→冲突→(9+1)%13=10→冲突→(10+1)%13=11→冲突→(11+1)%13=12→冲突→(12+1)%13=0→...→5)
6:61(61%13=9→冲突→...→6)
7:205(205%13=10→冲突→...→7)
8:104(104%13=0→冲突→...→8)
9:18(18%13=5→冲突→(5+1)%13=6→冲突→(6+1)%13=7→冲突→(7+1)%13=8→冲突→(8+1)%13=9)

ASLsucc = (1+1+5+1+6+7+8+9+4)/9 ≈ 4.67

6. 置换-选择排序与归并路数

初始归并段： 工作区容量4，序列：20,3,18,40,9,30,5,11,32,7,28 第一归并段：3,9,18,20,30,40 第二归并段：5,7,11,28,32 第三归并段：无

最少归并路数： 50个初始归并段，3趟归并，设路数为k 需满足k³≥50 ⇒ k≥4（取k=4）

五、算法设计题

1. 顺序表查找前移算法

void SearchAndMove(SqList *L, ElemType x) {
    int i, j;
    for(i=0; i<L->length; i++) {
        if(L->data[i] == x) {
            // 找到元素，前移
            ElemType temp = L->data[i];
            for(j=i; j>0; j--) {
                L->data[j] = L->data[j-1];
            }
            L->data[0] = temp;
            return;
        }
    }
}

2. 判断Fibonacci序列算法

int IsFibonacciList(LinkList L) {
    if(L==NULL || L->next==NULL) return 0;
    Node *p = L;
    int a = p->data; p = p->next;
    int b = p->data; p = p->next;
  
    if(a!=1 || b!=1) return 0;
  
    while(p != NULL) {
        if(p->data != a + b) return 0;
        a = b;
        b = p->data;
        p = p->next;
    }
    return 1;
}

3. 二叉树最小距离算法

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 辅助函数：找最近公共祖先
BiTree FindLCA(BiTree root, BiTree p, BiTree q) {
    if(root==NULL || root==p || root==q) return root;
    BiTree left = FindLCA(root->lchild, p, q);
    BiTree right = FindLCA(root->rchild, p, q);
    if(left && right) return root;
    return left ? left : right;
}

// 计算从根到某结点的距离
int DistanceFromRoot(BiTree root, BiTree p, int level) {
    if(root == NULL) return -1;
    if(root == p) return level;
    int left = DistanceFromRoot(root->lchild, p, level+1);
    if(left != -1) return left;
    return DistanceFromRoot(root->rchild, p, level+1);
}

// 主函数：计算最小距离
int MinDistance(BiTree root, BiTree p, BiTree q) {
    BiTree lca = FindLCA(root, p, q);
    int d1 = DistanceFromRoot(lca, p, 0);
    int d2 = DistanceFromRoot(lca, q, 0);
    return d1 + d2;
}

4. 链表自然归并排序算法

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 合并两个有序链表
Node* Merge(Node* a, Node* b) {
    if(a == NULL) return b;
    if(b == NULL) return a;
  
    Node *result = NULL;
    if(a->data <= b->data) {
        result = a;
        result->next = Merge(a->next, b);
    } else {
        result = b;
        result->next = Merge(a, b->next);
    }
    return result;
}

// 自然归并排序主函数
Node* NaturalMergeSort(Node* head) {
    if(head == NULL || head->next == NULL) 
        return head;
  
    // 分割链表为自然有序子链表
    Node *a = head, *b = NULL;
    Node *p = head;
    while(p->next != NULL && p->data <= p->next->data) {
        p = p->next;
    }
    b = p->next;
    p->next = NULL;
  
    // 递归排序并合并
    a = NaturalMergeSort(a);
    b = NaturalMergeSort(b);
    return Merge(a, b);
}