考研数据结构大题整合_组二（TJP组）

考研数据结构大题整合

二、TJP组

TJP组一

四、画图/计算/证明/算法分析（30分）
（1）证明题（8分）
如果一棵树有n1个度为1的结点，n2个度为2的结点，…… ，nm个度为m的结点，证明叶结点的个数n0 = 1+ ｛提示：模仿二叉树性质证明｝。

---

（2）画图及计算题（8分）
某工程的AOE网如右图所示，弧上的权值为活动a1～a10的期限（即完成活动所需的天数）。

求：
①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl及各活动的最早开始时间e和允许的最晚开始时间l (请列表Ve,Vl,e,l的各时间)，
②完成此项工程至少需要多少时间，及哪些活动是关键活动？

---

（3）已知某段电文中仅可能出现C, A, T, F, I五个字符，它们出现的频度分别为35, 15, 25, 7, 18。请图示一棵哈夫曼树并给出各字符的哈夫曼编码。（7分）

---

（4）给出的一组记录的关键字{78,12,45,98,23,109,85,68,89,256,34}，①写出对这组记录进行一趟快速排序的结果，并说明这趟排序中关键字比较的次数为多少；②将这组记录关键字建成一个大根堆（堆顶元素值最大）。（7分）

---

五、程序填空（每格2分，共20分）
1．有序线性表类（带表头的单链表结构）的定义如下：

tmd 气死了
1

---

2．快速排序：对a[low]…a[high]的元素按关键字降序排序

void QuickSort(Datatype a[], int low, int high)
{
    int i = low, j = high;
    Datatype temp = a[low];
    while (i < j)
    {
        while (i < j && ___________)
            j--;
        if (i < j)
            a[i++] = a[j];
        while (i < j && a[i].key >= temp.key)
            ______________;
        if (i < j)
            a[j--] = a[i];
    }
    a[i] = temp;
    if (low < i)
        QuickSort(a, low, i - 1);
    if (i < high)
        ____________________;
}
void QuickSort(Datatype a[], int n)
{
    QuickSort(a, 0, n - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

TJP组二

四、画图/计算/证明/算法分析（30分）
（1）已知一组记录的关键字为｛18,2,10,6,78,56,45,50,110,8｝, 按输入顺序画出此组记录的平衡二叉树，并求在等概率情况下查找成功的平均查找长度。（8分）

---

（2）设装填因子为0.77, 散列函数H(Key) = Key MOD 11, 并反复用H(Key) +1解决冲突，试对（1）的记录关键字构造散列表，请图示该表。（7分）

---

（3）已知有向图的邻接矩阵为：

V0  V1   V2  V3   V4   V5
V0  0   ∞   ∞   ∞    ∞   ∞
V1  30   0   ∞   40    ∞   ∞
V2  ∞  20    0   ∞    ∞   10
V3  ∞  ∞   20    0    50   40
V4  10  ∞   ∞   ∞     0   ∞
V5  20  10   ∞   ∞    20    0
1
2
3
4
5
6
7

试给出：①原图，②邻接表，③逆邻接表，④强连通分量。(8分)

---

（4）已知关键字序列{38,12,21,77,65,7,38,53}，图示采用快速排序方法（按关键字递增）对其进行第一趟排序时的过程（7分）

---

五、程序填空（每格2分，共20分）
1．有序线性表类的定义如下：

typedef char Datatype; // 或typedef int Datatype;
const int MaxListSize = 100;
class OrderSeqList
{
private:
    Datatype data[MaxListSize];
    int size; // 实际元素个数，即有效数据是data[0]..data[size-1]
public:
    OrderSeqList(void);
    ~OrderSeqList(void);
    int ListSize(void) const;        // 返回线性表实际大小，即返回size
    int ListEmpty(void) const;       // 判断线性表是否为空
    int Find(Datatype &item) const;  // 返回item在线性表中的位置
    Datatype GetData(int pos) const; // 取出线性表pos位置上的元素
    void Insert(Datatype item);      // 在有序线性表中插入新元素item
    Delete(Datatype item);           // 在有序线性表中删除元素item
    void ClearList(void);            // 清空线性表
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

下面是部分成员函数的实现：（这里的元素位置是指在data中的下标）

int OrderSeqList::Find(Datatype &item) const
{
    if (size == 0)
        return -1;
    int i = 0;
    while (________________________)
        i++;
    if (item == data[i])
        return i;
    else
        return -1;
}
void OrderSeqList::Insert(Datatype item)
{
    int i;
    if (___________________________)
    {
        cerr << "顺序表已满，无法插入！" << endl;
        exit(1);
    }
    for (i = size; (data[i - 1] > item) && (i > 0); i--)
        data[i] = ___________;
    data[i] = __________________;
    size++;
}
OrderSeqList::Delete(Datatype item)
{
    if (size == 0)
    {
        cerr << "顺序表已空，无元素可删！" << endl;
        exit(1);
    }
    int loc = Find(item);
    if (loc != -1)
    {
        for (int j = loc; j < size - 1; j++)
            data[j] = _______________;
        _______________;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2．编写一个删除子串的函数：

void deletestr(char *str, int start, int span)
{
    int i;
    int len = strlen(str);
    if ((start < 0) || (start > len - 1))
        return;
    if ((start + span < -1) || (start + span > len))
        return;
    if (span > 0)
        for (i = start; i <= _______________; i++)
            str[i] = ________________;
    else
        for (i = __________________; i <= len + span + 1; i++)
            _______________;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

TJP组三

四、画图/计算/证明/算法分析（30分）
（1）证明题（8分）
试证明二叉树的性质：若完全二叉树的深度为K，则对于具有n个结点的完全二叉树，其K是不大于long2n的最小正数。

---

（2）画图及计算题（8分）
某工程的AOE网如右图所示，弧上的权值为活动a1～a10的期限（即完成活动所需的天数）。
求：
①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl及各活动的最早开始时间e和允许的最晚开始时间l (请列表Ve,Vl,e,l的各时间)，
②完成此项工程至少需要多少时间，及哪些活动是关键活动？

---

（3）已知某段电文中仅可能出现a, b, c, d, e五个字符，它们出现的频度分别为32, 15, 24, 8, 19。要求：①图示一棵哈夫曼树；②再图示一棵对应于该哈夫曼树的后根次序遍历线索二叉树。（7分）

---

（4）给出的一组记录的关键字{25,18,46,2,53,39,32,4,74,67,60,11}，①图示一棵处于平衡状态的二叉排序树（二叉查找树）；②列出在等概率情况下各关键字在查找成功时的平均查找次数。（7分）

---

// ToDo
## 三、LZH组
### LZH 组一
### LZH 组二
### LZH 组三
### LZH 组四
### LZH 组五
### LZH 组六
### LZH 组七
## 四、LB组
### LB组一
### LB组二
### LB组三
### LB组四
### LB组五
### LB组六
### LB组七
### LB组八
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18