一、填空题解析

  1. 顺序表插入移动元素数 n-i+1（在第i个位置前插入需要移动后面所有元素）

  2. 循环队列队头指针指向 队头元素的前一个位置（通常实现方式）

  3. 双向链表指针域 前驱结点（prior），后继结点（next）

  4. 下三角矩阵存储位置 i*(i-1)/2 + j（行序为主存储，i≥j）

  5. 二叉树结点总数 89（30叶结点+30单孩子结点+29双孩子结点）

  6. 无向连通图最少边数 n-1（树的情况）

  7. 邻接表结点总数 2e（无向图每条边存储两次）

  8. 插入排序最佳比较次数 n-1（已有序时只需比较n-1次）

  9. 装填因子影响 冲突概率越小（装填因子=元素数/表长）

二、判断题解析

题号 答案 解析
1 × 线性表也可用链表存储
2 × 链式存储逻辑顺序与物理顺序可能不一致
3 √ 二维数组可视为元素为线性表的线性表
4 × 不是所有结构都支持这三种操作
5 × 删除后重新插入可能改变树结构
6 √ 中序最后结点也是前序最后结点
7 √ 无向图邻接矩阵对称
8 × 仅连通图才能一次遍历访问所有结点
9 √ 快排每趟确定一个元素最终位置
10 √ 理想散列表查找O(1)

三、单选题解析

题号 答案 解析
1 C 算法分析主要目的是分析效率
2 C dceab不可能是栈的输出序列
3 A 最少比较n-1次（一个表全小于另一个）
4 B 二叉排序树中序遍历有序
5 D 前序后序相反⇒高度等于结点数
6 A 最小生成树可能不唯一
7 D 归并排序需要O(n)辅助空间
8 D 基本有序时插入排序最有效
9 B 二分查找平均比较次数37/12
10 C 分块查找适合动态变化且较快

四、解析题解析

1. 树与二叉树转换

原始树结构：
        A
      / | \
     B  C  D
    / \  / \ 
   E F  G H
     /  / \
    K  I  J
       / \
      L  M
         /
        N
       /
      O

对应的二叉树：
        A
       /
      B
     / \
    E   C
     \   \
      F   D
     /   /
    K   G
       / \
      I   H
     / \
    L   J
       /
      M
     /
    N
   /
  O

2. Huffman树与编码

Huffman树构建过程：
1. 合并A(2),B(3)→5
2. 合并5,C(5)→10
3. 合并D(7),E(11)→18
4. 合并F(13),G(17)→30
5. 合并H(19),I(23)→42
6. 合并J(31),K(37)→68
7. 合并L(41),68→109
8. 合并10,18→28
9. 合并28,30→58
10. 合并42,58→100
11. 合并100,109→209

Huffman编码：
A: 11110
B: 11111
C: 1110
D: 100
E: 101
F: 110
G: 111
H: 00
I: 01
J: 011
K: 010
L: 10

3. Prim算法最小生成树

邻接矩阵表示的图：
  0 1 2 3 4 5
0 ∞ 7 ∞ 9 ∞ ∞
1 7 ∞ 5 ∞ ∞ 6
2 ∞ 5 ∞ 1 ∞ 2
3 9 ∞ 1 ∞ ∞ 1
4 ∞ ∞ ∞ ∞ ∞ ∞
5 ∞ 6 2 1 ∞ ∞

Prim算法步骤（从顶点0开始）：
1. 选择边(0,1,7)
2. 选择边(1,2,5)
3. 选择边(2,3,1)
4. 选择边(3,5,1)
5. 选择边(5,4,∞) - 无连接，无法继续
实际最小生成树总权值：7+5+1+1=14

4. 部分排序算法选择

最佳方法： 堆排序 原因： 只需建立大小为k的小根堆，时间复杂度O(nlogk) 比较次数分析： 对序列{57,40,38,11,13,34,48,75,25,6,19,9,7}

  1. 建堆(前4个)：11,13,38,40 → 3次比较
  2. 调整堆：
    • 34>11，不调整
    • 48>11，不调整
    • 75>11，不调整
    • 25>11，不调整
    • 6<11，替换并调整：6,13,38,40 → 2次比较
    • 19>6，不调整
    • 9>6，不调整
    • 7>6，不调整 总比较次数≈15次

五、算法设计题

1. 双向链表频度排序算法

typedef struct DuLNode {
    ElemType data;
    int freq;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

void Locate(DuLinkList L, ElemType x) {
    DuLNode *p = L->next, *q;
    while(p && p->data != x) p = p->next;
  
    if(!p) return; // 未找到
  
    p->freq++;
    // 从当前位置向前查找插入位置
    q = p->prior;
    while(q != L && q->freq < p->freq) q = q->prior;
  
    // 将p结点移动到q之后
    if(p->prior != q) {
        // 先删除p
        p->prior->next = p->next;
        if(p->next) p->next->prior = p->prior;
      
        // 再插入到q之后
        p->next = q->next;
        if(q->next) q->next->prior = p;
        q->next = p;
        p->prior = q;
    }
}

2. 无向图中通过给定顶点的简单回路

int visited[MAX_VERTEX_NUM]; // 访问标记数组
int path[MAX_VERTEX_NUM];    // 路径记录
int path_index = 0;          // 路径索引

void DFSCircuit(ALGraph G, int v, int start) {
    visited[v] = 1;
    path[path_index++] = v;
  
    ArcNode *p = G.vertices[v].firstarc;
    while(p != NULL) {
        int w = p->adjvex;
        if(!visited[w]) {
            DFSCircuit(G, w, start);
        } 
        else if(w == start && path_index > 2) {
            // 找到回路，输出路径
            printf("回路: ");
            for(int i=0; i<path_index; i++)
                printf("%d ", path[i]);
            printf("%d\n", start);
        }
        p = p->nextarc;
    }
  
    // 回溯
    visited[v] = 0;
    path_index--;
}

void FindCircuit(ALGraph G, int v) {
    for(int i=0; i<G.vexnum; i++)
        visited[i] = 0;
    path_index = 0;
    DFSCircuit(G, v, v);
}