《数据结构》大题

（1）

链式存储结构

（2）

front为队首指针，rear为队尾指针

初始时，创建只有一个空闲结点的循环单链表

front，rear均指向空闲结点

队空判别：front = rear

队满判别：front = rear->next

（3）

（4）

入队：

若(front == rear -> next)
    则在rear后插入一个新的空闲结点;
入队元素保存到rear所指结点中;
rear = rear -> next;
返回

出队：

若(front == rear)
    则出队失败，返回;
取front所指结点的元素e;
front = front -> next;
返回e;

（1）

二叉树

（2）

$01011010\cdots$

从左至右依次扫描01串中的各位，从二叉树根开始，根据串中当前位沿树中当前结点的左子指针或右子指针（0左1右）下移，直到叶子结点，输出叶子结点保存的字段。然后再从根节点开始重复这个过程，直到01串结束，译码完成

（3）

$01011010\cdots$

对每个编码C，建立从根开始对应于该编码的一条路径，从左到右扫描C，C为0则沿结点左指针下移（为1沿结点右指针）。遇到空指针时，创建新结点，让空指针指向该结点并继续移动，移动中

1. 若遇到叶结点，则表明不具有前缀特性，返回
2. 若处理C的所有位中，均没创建新结点，则表明不具有前缀特性，返回
3. 若在C的最后一个编码创建了新结点，则继续验证下一个编码

若所有编码都通过，则编码具有前缀特性

（1）

表集合{10(A),35(B),40(C),50(D),60(E),200(F)}

1. AB合并，最多比较次数 35+10-1 = 44
2. AB与C合并，最多比较次数 40+45-1=84
3. DE合并，最多比较次数50+60-1=109
4. ABC与DE合并，最多比较次数85+110-1=194
5. ABCDE与F合并，最多比较次数195+200-1 = 394

比较的总次数最多 = 825次

（2）

对多个有序表进行两两合并时，若表长不同，则最坏情况下总得比较次数依赖于表的合并次序，借助哈夫曼树的思想，依次选择最短的两个表进行合并，此时可以获得最坏情况下的最佳合并效率

（1）

有两类结点：叶结点数$n_0$,度为k的分支结点$n_k$

则$n_{总} = n_0 + n_k = n_0+m,$树的边e = n -1

且e = mk，的$n_0+m = mk+1$

因此，$n_0 = (k-1)m+1$

（2）

最多即为满k叉树，第j层结点为$k^{j-1}$

所以 最多 = $\sum_{j=1}^n k^{j-1} = \frac{k^h-1}{k-1}$

最少 = $1+(h-2)k+k = 1+(h-1)k$

（2）

唯一，若AE替代CE，则形成了回路

（3）

当带权连通图的任意一个环中所包含的边权值不相同时，MST是唯一的

（1）

$A = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix}$

（2）

$$ A^2 = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 3 & 1 & 0 & 3 & 1 \\ 1 & 3 & 2 & 1 & 2 \\ 0 & 2 & 2 & 0 & 2 \\ 3 & 1 & 0 & 3 & 1 \\ 1 & 1 & 2 & 1 & 3 \\ \end{bmatrix} $$

0行3列的值表示从顶点0到顶点3之间长度为2的路径共有3条

（3）

从顶点i到顶点j的长度为m的路径条数

（1）

无向图

（2）

链式存储结构

$$ \begin{array} |\text{Flag = 1} | \text{Next}| \\ \hline \text{ID}| \\ \hline \text{IP}| \\ \hline \text{Metrix}| \\ \end{array} $$

$$ \begin{array} |\text{Flag = 2} | \text{Next}| \\ \hline \text{Prefix}| \\ \hline \text{Mask}| \\ \hline \text{Metrix}| \\ \end{array} $$

表头结点

数据结构类型

 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

//link的结构
typedef Struct
{
    unsigned int ID,IP;

}LinkNode;

//net的结构
typedef Struct{
    unsigned int prefix,Mask;
}NetNode;
//弧结点
typedef struct{
    int Flag;
    union{
        LinkNode Lnode;
        NetNode Noded;
    }LinkOrNet;
    unsigned int *next;
}arcNode;

//表头结点
typedef struct hNode
{
    unsigned int RouterID;
    ArcNode * LN_link;
    struct hNode *next;
}HNode;

(3)

不一定能求得最短路径

按题方法求得最短路径：A->B->C

实际最短路径：A->D->C

（1）

$$ A=\begin{bmatrix} 0 & 4 & 6 & \infty & \infty & \infty \\ \infty & 0 & 5 & \infty & \infty & \infty \\ \infty & \infty & 0 & 4 & 3 & \infty \\ \infty & \infty & \infty & 0 & \infty & 3 \\ \infty & \infty & \infty & \infty & 0 & 3 \\ \infty & \infty & \infty & \infty & \infty & 0 \\ \end{bmatrix} $$

（2）

（3）

关键路径 0->1->2->3->5

长度为 4+5+4+3 = 16

总费用均为16

（2）

用邻接矩阵存储，构造最小生成树则使用Prim算法

（3）

TTL = 5=>IP分组的最大传递距离 = 5

方案一太远，不能收到

方案二邻近可以收到

（1）

一维数组大小7/0.7 = 10,下标为 0~9

$$ \begin{array}{c|lcr} \text{key} & 7 & 8 & 30 & 11 & 18 & 9 & 14 \\ \hline \text{H(key)} & 0 & 3 & 6 & 5 & 5 & 6 & 0 \\ \end{array} $$

$$ \begin{array}{c|lcr} \text{地址} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text{关键字} & 7 & 14 & & 8 & & 11 & 30 & 18 & 9 & \\ \end{array} $$

（2）

查找成功：

$$ \begin{array}{c|lcr} \text{key} & 7 & 8 & 30 & 11 & 18 & 9 & 14 \\ \hline \text{比较次数} & 1 & 1 & 1 & 1 & 3 & 3 & 2 \\ \end{array} $$

$ASL_{成功} = \frac{1+1+1+1+3+3+2}{7} = \frac{12}{7}$

查找失败：

$$ \begin{array}{c|lcr} \text{地址} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \text{关键字} & 3 & 2 & 1 & 2 & 1 & 5 & 4 \\ \end{array} $$

$ASL_{失败} = \frac{3+2+1+2+1+5+4}{7} = \frac{18}{7}$

（1）

按查找概率逆序排列

顺序查找方法

平均查找长度 = $1\times 0.35 + 2\times 0.35+3\times 0.15+4\times 0.15 = 2.1$

（2）

方法一：

按查找概率逆序排列

顺序查找方法

平均查找长度 = $1\times 0.35 + 2\times 0.35+3\times 0.15+4\times 0.15 = 2.1$

方法二：

二叉排序树的查找方法：

$ASL=0.15\times1 + 0.35\times2 + 0.35\times2 + 0.15\times3 = 2.0$

（1）

b的内容为{-10,10,11,19,25,25}

（2）

比较次数 = (n-1) + (n-2)+(n-3)$\cdots$+1 = $\frac{n(n-1)}{2}$

（3）

不是

将if修改为

1
2
3
4
5
6
7
8

if(a[i]<=a[j])
{
    count[j]++;
}
else
{
    count[i]++;
}

如果不加=，两个相等的元素在比较时，前面的元素的count值会加1，导致原序列中靠前的元素在排序后的序列处于靠后的位置