考研数据结构大题整合_组二（TJP组）
考研数据结构大题整合
目录
- 考研数据结构大题整合
- 二、TJP组
- TJP组一
- TJP组二
- 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 气死了
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);
}
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
试给出：①原图，②邻接表，③逆邻接表，④强连通分量。(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; // 返回线性表实际大小，即返回sizeint ListEmpty(void) const; // 判断线性表是否为空int Find(Datatype &item) const; // 返回item在线性表中的位置Datatype GetData(int pos) const; // 取出线性表pos位置上的元素void Insert(Datatype item); // 在有序线性表中插入新元素itemDelete(Datatype item); // 在有序线性表中删除元素itemvoid ClearList(void); // 清空线性表
};
下面是部分成员函数的实现：（这里的元素位置是指在data中的下标）
int OrderSeqList::Find(Datatype &item) const
{if (size == 0)return -1;int i = 0;while (________________________)i++;if (item == data[i])return i;elsereturn -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] = _______________;_______________;}
}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] = ________________;elsefor (i = __________________; i <= len + span + 1; i++)_______________;
}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组八