一、单项选择题

  1. B 数据项

    • 解析：数据项是不可分割的最小数据单位

  2. D n-i

    • 解析：删除第i个元素后，需要将i+1到n的元素前移，共n-i个

  3. C 小于1

    • 解析：存储密度=数据域占用量/结点总占用量，单链表有指针域

  4. C O(m)

    • 解析：需要遍历到长度为m的链表尾部

  5. A 栈

    • 解析：数制转换采用"除基取余"法，适合后进先出的栈结构

  6. B d,c,a,b

    • 解析：a必须在b之前出栈，此序列违反栈规则

  7. A 1和5

    • 解析：删除2个元素front=(3+2)%6=5，添加1个元素rear=(0+1)%6=1

  8. C 36

    • 解析：长度为n的串有n(n+1)/2个子串，8*9/2=36

  9. D a+296

    • 解析：LOC(a[7][4])=a+(7*10+4)*4=a+296

  10. B (())

  • 解析：Head(L)=Tail(L)仅当L=(( ))时成立
  1. B 2h-1
  • 解析：每层至少2个结点(除根)，总结点数=1+2+...+2^(h-1)=2^h-1
  1. C 后序
  • 解析：后序遍历满足父结点编号大于子结点
  1. C 8
  • 解析：n个顶点的连通图至少n-1条边，28≥n-1⇒n≥29
  1. D n-k
  • 解析：森林中树的数量=顶点数-边数
  1. B 右指针一定为空
  • 解析：二叉排序树最大结点无右孩子
  1. C 5
  • 解析：平衡二叉树最大深度≈1.44log(n+2)-0.328
  1. A 至少含有⌈m/2⌉棵子树
  • 解析：B树定义要求非根结点至少⌈m/2⌉棵子树
  1. A [da,ax,eb,de,bb] fp [hq,gv]
  • 解析：第一趟快排后基准fp左侧都≤fp，右侧都≥fp
  1. A 直接插入排序
  • 解析：局部有序时插入排序效率最高
  1. C 简单选择排序
  • 解析：选择排序时间复杂度恒为O(n²)

二、填空题

  1. O(n)
  2. n/2
  3. 4
  4. (r-f+n)%n
  5. 8
  6. 1120
  7. 195
  8. n-2n₀+1
  9. 247
  10. (n+1)/2
  11. 4
  12. 2(n-1)
  13. v1v3v2v4v5v6
  14. (12,38,65,97,76,45,28,56)
  15. 7
  16. 13

三、问答题

  1. 双循环链表插入操作：
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;

  1. 二叉树相关问题： (1) 二叉树结构： A /
    B C / /
    D E F /
    G H (2) 后序序列：GDBEHFCA (3) 对应森林： A C / /
    B E F /
    D H / G

  2. 二叉排序树： (1) 初始BST： 18 /
    13 31 / /
    11 20 35 / \
    8 25 40 / /

4 24
27 (2) 删除18后： 20 /
13 31 / /
11 25 35 / \ /
8 24 27 40 / 4

  1. 直接插入排序过程： 初始：50,80,63,45,48,92 第1趟：50,80,63,45,48,92 第2趟：50,63,80,45,48,92 第3趟：45,50,63,80,48,92 第4趟：45,48,50,63,80,92 第5趟：45,48,50,63,80,92

  2. 哈希表： 0: 21 1: 2: 23 → 16 → 30 3: 4: 18 → 11 5: 12 6: 6

  3. AVL树构建过程： 插入45： 45 插入15： 45 / 15 插入20： 20 /
    15 45 插入35： 20 /
    15 45 / 35 插入25： 20 /
    15 35 /
    25 45 插入60： 20 /
    15 35 /
    25 45
    60

四、算法应用题

  1. 无向网问题： (1) 邻接矩阵： v1 v2 v3 v4 v5 v6 v1 0 6 1 5 ∞ ∞ v2 6 0 5 ∞ 3 ∞ v3 1 5 0 5 6 4 v4 5 ∞ 5 0 ∞ 2 v5 ∞ 3 6 ∞ 0 6 v6 ∞ ∞ 4 2 6 0

    (2) 遍历序列：

    • DFS: v1→v3→v2→v5→v6→v4
    • BFS: v1→v3→v2→v4→v5→v6

    (3) Prim最小生成树： v1 /
    v3 v4 / \ \

v2 v6 v5

  1. Huffman编码： (1) Huffman树： (36) /
    (16) (20) / \ /
    (7) (9) (10) (10) / \ / \ /
    B1 C4 D5 A2 E7 F3 G4 H10 (2) 编码长度： 2*(2+1+4+5+7+3+4+10) = 2*36=72位

五、算法设计题

  1. 单链表逆置算法：
void ReverseList(Node *L) {
    Node *p = L->next, *q;
    L->next = NULL;
    while(p) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

时间复杂度：O(n) 空间复杂度：O(1)

以上解答严格遵循考研数据结构标准，涵盖了所有考点和解题要点。对于算法题，提供了时间复杂度和空间复杂度分析，确保解答的完整性和专业性。