-
1.
将森林转换为二叉树。
用左子女
-
右兄弟表示实现的树定义：
typedef struct node {
TreeData data;
struct node *
firstChild, * nextSibling;
} TreeNode;
2.
图的邻接矩阵、邻接表的存储表示。
图的邻接矩阵存储：
两点之间有边矩
阵对应的位置处填
1
，两点之间无边对应位置处填
0
EdgeData
Edge[NumVertices][NumVertices];
图的邻接表存储：
2.
计算
A
OE
网络的关键路径。
完成整个工程所需的时间取决于从源点到汇点的最长路径长度
,
即在这条路径上所有活动的持续时
间之和。这条路径长度最长的
路径就叫做关键路径
关键活动：最早开始时间和最晚开始时间相等
4.
画
出下图的结构，并分别给出以
A
顶点开始的深度优先遍历和广度
优先遍历。
0
1
2
3
4
5
A
B
C
D
E<
/p>
F
1
0
0
1
2
3
2
3
3
2
5
4
NULL
NULL
4
5
NULL
NULL
NULL
NULL
A
C
E
深度优先搜索：
ABDCEF
B
D
F
广度优先搜索：
ABCDEF
5.
(1)
哈希函数常用的构造方法有哪些
?
处理冲突的方法有哪些？
(2)
用除留余数法构建哈希表，并以线性探测再散列处理冲突。
1
、
常用的构造方法：
直接定址法、数字
分析法、平方取中法、折叠法、除留余数法、随机数法
处理冲突的方法：
开放定址法、再哈希法、链地址法
2
、
除留余数法：
H(key) =
key % p ------------m
为表长，
p
为不大于
m
的素数
P
为素数？
如
key
（关键字）
：
12 39 18 24 33 21
若
p = 9
则哈希函数值为：
3 3 0 6 6 3
< br>可见，当
p
的因子中含有素数
3
，则所有含因子
3
的关键字都对应到<
/p>
“3
的倍数
”
的
地址上，从而增加
了冲突的可能
!
/
**
表长为
6
，关键字个数
6
，
p<=m
且
p
为素数，故
p
取
5,
但是这样最后一个数
21
将永远不会放到
下标为
5
的
地方！那么这个
p
的取法不是有错吗？还是说表长必须比给的关
键字个数大？
**/
如
key
（关键字）
：
12 39
18
24
33
21
若
p = 7
则哈希函数值为
: 5 4
4
3
5
0
先行探测在散列处理冲突：
Key = 18
：
18 % 7 =
4
(
冲突
)
(4+1)%7=5(
冲突
)
(5+1)%7=6
key =
33
:
33%7=
5
（冲突）
(5+1)%7=6
（冲突）
(6+1)%7=0
Key = 21:
21%7 = 0(
冲突
)
(0+1)%7 = 1
所以最后得：
5 4 6 3 0 1
0
1
2
3
4
5
6
33
21
24
39
12
18
6.
证明二叉树性质：
n0=n2+1 ( n0
< br>度为
0
的结点；
n2:
度为
2
的结点
)
n1
为
度为
1
的节点，
e
表示二叉树的边数；
这里用到的一个等式是二叉树边的两种表达
:
e=n0+n1+n2-1
//<
/p>
每一个节点对应一条边，根节点除外所以减一
e=2*n2+n1
//2
倍的度为
2
的节点数目加上度为
1
的节点数
目，就是边的数目
得：
n0 =
n2 + n1
7.
求最小生成树
1
、
Pri
m
（普里姆）算法
从连通图中的某一顶点
u
0
出发
,
选择与它关联的具有最小权值的边，将其顶点加入到生成树顶点集合中
< br>
2
、
Kruskal
（克鲁斯卡尔）算法
对每一条边按照权值从小
到大排序，每一次选择最小的权值的边，注意避免选择出现环的边！
8.
以权重集合
{ 4, 5, 6,
7, 8
}
构建哈夫曼树（霍夫曼树）
。
带权路径长度达到最小的二叉树即为哈夫曼树。
9.
给出用下列关键字构建大顶堆的全过程，关键字集合为
{
70
40
55
81
74
18
46
70
}
0
70
1
40
2
55
3
81
4
74
5
18
6
46
7
70
10.
给出上述集合数据的快速排序的过程
选定初始关键字
temp
，
首先从右向左遍历，当遇到比
temp
小的时候
，就让
a[i] = a[j], i++;
然后重左向右遍
历，当遇到比
temp
大的时候，就让
a[j] = a[i], j--;
然后循环做上述两个过程，直到
i==j
时，就让
a[i] = temp;
这时枢轴就是
a[i];
然后递归调用从（
l,
i-1
）和
(i+1,r);
11.
请按照给出的数字顺序构造二叉排序树。
如：
50 30 80 20 40 90 10 25 35
85 23 88
12.
计算从顶点
b
到其它顶点的最短路径。
e
12
10
13
b
15
2
30
20
d
4
f
6
a
c
答题不能这样写，这样写最多
2
分，要写出步骤！这只是草稿，方便看！
Dijkstra
逐步求解的过程
:
13.
二叉树计数。
1
、由二叉树的前序序列和中序序列可唯一地确定一棵二叉树
前序序列
{
ABHFDECKG }
//
确定根节点
中序序列
{ HBDFAEKCG
}
//
在前序序列确定根节点的基础上，确定左右孩子节点
2
、计算具有
n
个结点的不同二叉树的棵数
14.
给出求顺序表
A
和
B
并集和交集的程序实现，要求并集存储在表
A
当中。
运行结果：
La :
0 1 2 3 4 5 6 7 8 9
Lb :
0 2 4 6 8 10 12 14 16
18
BingJi :
0 1 2 3 4 5 6 7
8 9 10 12 14 16 18
JiaoJi :
0 2 4 6 8
请按任意键继续
. . .
代码：
#include
#define
NewSeqList
(
SeqList
*)malloc(
sizeof
(
SeqList
))
#define
NewListData
(
int
*)malloc(40
*
sizeof
(
int
))
using
namespace
std;
typedef
struct
{
int
*data,
length;
}
< br>SeqList
;
void
SetL(
SeqList
*&
L
)
{
}
void
Show(
SeqList
*&
L
)
{
for
(
int
i
=
0;
i
<
L
->length;
++i)
cout
<<
L
->data[i]
<<
;
cout
<<
endl;
cout
<<
请输入
共多少数：
;
cin
>>
L
->length;
for
(
int
i
=
0;
i
<
L
->length;
++i)
cin
>>
L
->data[i];
}
bool
InL(
SeqList
*&
L
,
int
&
key
)
{
}
void
Insert(
SeqList
*&
L
,
int
key
)
{
}
void
Delete(
SeqList
*&
L
,
int
&
pos
)
{
}
void
Union(
SeqList
*&
La
,
SeqList
*&
Lb
)
{
}
void
Intersect(
SeqList
*&
La
,
SeqList
*&
Lb
)
{
for
(
int
i
=
0;
i
<
La
->length;
++i)
if
(!InL(
< br>Lb
,
La
->data[i]))
{
Delete(
< br>La
,
i);
--i;
}
//
for
(
int
i
=
0;
i
<
Lb
->length;
++i)
if
(!InL(
< br>La
,
Lb
->data[i]))
Insert(
La
,
Lb
->data[i]);
<
/p>
//
如果
Lb
中
元素不在
La
中就把该元素插入到
La
中
//pos
代表要删除的元素的下标
L
->data[
L
< br>->length++]
=
key
;
for
(
int
i
=
0;
i
<
L
->length;
++i)
if
(
key
==
L
->data[i])
return
true
;
return
false
;
for
(
int
i
=
pos
;
i
<
L
->length
-
1;
++i)
L
->data[i]
=
L
->data[i
+
1];
--
L
->length;
如果
La
中元素不在<
/p>
Lb
中就把
La
中该元素删除
}
int
main(){
体
La->data
=
NewListData
;
Lb->data
=
NewListData
;
La->length
=
Lb->length
=
0;
SetL(La);
SetL(Lb);
//
向顺
序表
La
输入数据
< br>//
向顺序表
Lb
输入数据
//NewListData
用宏定义创建数组
SeqList
*La
=
NewSeqList
,
*Lb
=
NewSeqList
;
//NewSeqList
用宏定义创建结构
cout
<<
输出集
合
La
：
;<
/p>
Show(La);
cout
<<
输出集
合
Lb
：
;<
/p>
Show(Lb);
Union(La,
Lb);
//
并集
cout
<<
并集结
果：
;
Show(La);
Intersect(La,
Lb);
//
交集
cout
<<
交集结
果：
;
Show(La);
system(
);
return
0;
}
15.
用
C
语言给出邻接表的定义。给出构建邻接表的源程序（先后输入顶点表和边表）
。编写程序求顶点表中顶点
V
的入度和出度。<
/p>
无向图的每个顶点的入度和出度相等，所以只要求出入度即可。
有向图求入度和出度有两种方法：
1
、
求入度一个一个遍历，遇到即
ans++
2
、
在一个
结构体中建立两个表，入度表，和出度表，查询的时候做相同的遍历即可
法
1
：
（按无向图来处理的，若按有向图处理只需删去建
tail->head
的代码即可）
运行结果：
please
input VertexNum and EdgeNum :
-
-
-
-
-
-
-
-
-
上一篇：3d建模常用命令——详细
下一篇：常用数学,物理英语词汇