Push（&s,t[i]）;
while（!
EmptyStack（&s））
{//每弹出一个字符与相应字符比较
temp=Pop（&s）;
if（temp!
=S[i]） return0;//不等则返回0
elsei++;
}
return1;//比较完毕均相等则返回1
}
（7）假设以数组Q[m]存放循环队列中的元素,同时设置一个标志tag，以tag==0和tag==1来区别在队头指针（front）和队尾指针（rear）相等时，队列状态为“空”还是“满”。
试编写与此结构相应的插入（enqueue）和删除（dlqueue）算法。
【解答】
循环队列类定义
#include
templateclassQueue{//循环队列的类定义
public:
Queue（int=10）;
~Queue（）{delete[]Q;}
voidEnQueue（Type&item）;
TypeDeQueue（）;
TypeGetFront（）;
voidMakeEmpty（）{front=rear=tag=0;}//置空队列
intIsEmpty（）const{returnfront==rear&&tag==0;}//判队列空否
intIsFull（）const{returnfront==rear&&tag==1;}//判队列满否
private:
intrear,front,tag;//队尾指针、队头指针和队满标志
Type*Q;//存放队列元素的数组
intm;//队列最大可容纳元素个数
}
构造函数
template
Queue:
:
Queue（intsz）:
rear（0）,front（0）,tag（0）,m（sz）{
//建立一个最大具有m个元素的空队列。
Q=newType[m];//创建队列空间
assert（Q!
=0）;//断言:
动态存储分配成功与否
}
插入函数
template
voidQueue:
:
EnQueue（Type&item）{
assert（!
IsFull（））;//判队列是否不满，满则出错处理
rear=（rear+1）%m;//队尾位置进1,队尾指针指示实际队尾位置
Q[rear]=item;//进队列
tag=1;//标志改1，表示队列不空
}
删除函数
template
TypeQueue:
:
DeQueue（）{
assert（!
IsEmpty（））;//判断队列是否不空，空则出错处理
front=（front+1）%m;//队头位置进1,队头指针指示实际队头的前一位置
tag=0;//标志改0,表示栈不满
returnQ[front];//返回原队头元素的值
}
读取队头元素函数
template
TypeQueue:
:
GetFront（）{
assert（!
IsEmpty（））;//判断队列是否不空，空则出错处理
returnQ[（front+1）%m];//返回队头元素的值
}
第4章串、数组和广义表
1．选择题
BBCABBBCBBABDCBC
2.综合应用题
（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
模式串t的next和nextval值如下：
j
123456789101112
t串
abcaabbabcab
next[j]
011122312345
nextval[j]
011021301105
（3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。
求：
存放该数组所需多少单元？
存放数组第4列所有元素至少需多少单元？
数组按行存放时，元素A[7,4]的起始地址是多少？
数组按列存放时，元素A[4,7]的起始地址是多少？
每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。
（1）242
（2）22（3）s+182（4）s+142
（4）请将香蕉banana用工具H（）—Head（），T（）—Tail（）从L中取出。
L=（apple,（orange,（strawberry,（banana））,peach）,pear）
H（H（T（H（T（H（T（L）））））））
（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。
voidCount（）
//统计输入字符串中数字字符和字母字符的个数。
｛inti，num[36]；
charch；
for（i＝0；i<36；i++）num[i]＝０；//初始化
while（（ch＝getchar（））!
=‘#’）//‘#’表示输入字符串结束。
if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝//数字字符
else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝//字母字符
for（i=0；i<10；i++）//输出数字字符的个数
printf（“数字％d的个数＝％d\n”，i，num[i]）；
for（i＝10；i<36；i++）//求出字母字符的个数
printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）；
｝//算法结束。
第5章树和二叉树
1．选择题
ADDCACCBDCCCACC
2．应用题
（2）设一棵二叉树的先序序列：
ABDFCEGH，中序序列：
BFDAGEHC
画出这棵二叉树。
画出这棵二叉树的后序线索树。
将这棵二叉树转换成对应的树（或森林）。
（1）
（2）
（3）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
试为这8个字母设计赫夫曼编码。
试设计另一种由二进制表示的等长编码方案。
对于上述实例，比较两种方案的优缺点。
解：
方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：
【[（2,3），6],（7,10）】,……19,21,32
（100）
（40）（60）
192132（28）
（17）（11）
7106（5）
23
方案比较：
方案1的WPL＝2（0.19+0.32+0.21）+4（0.07+0.06+0.10）+5（0.02+0.03）=1.44+0.92+0.25=2.61
方案2的WPL＝3（0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03）=3
结论：
哈夫曼编码优于等长二进制编码
3．算法设计题
以二叉链表作为二叉树的存储结构，编写以下算法：
（1）统计二叉树的叶结点个数。
intLeafNodeCount（BiTreeT）
{
if（T==NULL）
return0;//如果是空树，则叶子结点个数为0
elseif（T->lchild==NULL&&T->rchild==NULL）
return1;//判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1
else
returnLeafNodeCount（T->lchild）+LeafNodeCount（T->rchild）;
}
（3）交换二叉树每个结点的左孩子和右孩子。
voidChangeLR（BiTree&T）
{
BiTreetemp;
if（T->lchild==NULL&&T->rchild==NULL）
return;
else
{
temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;
}
ChangeLR（T->lchild）;
ChangeLR（T->rchild）;
}
第6章图
1．选择题
CBBBCBABAADCCDDB
2．应用题
（1）已知如图6.27所示的有向图，请给出：
每个顶点的入度和出度；
邻接矩阵；
邻接表；
逆邻接表。
（2）已知如图6.28所示的无向网，请给出：
邻接矩阵；
邻接表；
最小生成树
a
→
b
4
→
c
3
b
→
a
4
→
c
5
→
d
5
→
e
9
^
c
→
a
3
→
b
5
→
d
5
→
h
5
^
d
→
b
5
→
c
5
→
e
7
→
f
6
→
g
5
→
h
4^
e
→
b
9
→
d
7
→
f
3
^
f
→
d
6
→
e
3
→
g
2
^
g
→
d
5
→
f
2
→
h
6
^
h
→
c
5
→
d
4
→
g
6
^
（3）已知图的邻接矩阵如6.29所示。
试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
（4）有向网如图6.29所示，试用迪杰斯特拉算法求出从顶点a到其他各顶点间的最短路径，完成表6.9。
D
终点
i=1
i=2
i=3
i=4
i=5
i=6
b
15
（a,b）
15
（a,b）
15
（a,b）
15
（a,b）
15
（a,b）
15
（a,b）
c
2
（a,c）
d
12
（a,d）
12
（a,d）
11
（a,c,f,d）
11
（a,c,f,d）
e
∞
10
（a,c,e）
10
（a,c,e）
f
∞
6
（a,c,f）
g
∞
∞
16
（a,c,f,g）
16
（a,c,f,g）
14
（a,c,f,d,g）
S
终点集
{a,c}
{a,c,f}
{a,c,f,e}
{a,c,f,e,d}
{a,c,f,e,d,g}
{a,c,f,e,d,g,b}
第7章查找
1．选择题
CDCABCCCDCBCADA
2．应用题
（1）假定对有序表：
（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
画出描述折半查找过程的判定树；
若查找元素54，需依次与哪些元素比较？
若查找元素90，需依次与哪些元素比较？
假定每个元素的查找概率相等，求查找成功时的平均查找长度。
先画出判定树如下（注：
mid=⎣（1+12）/2⎦=6）：
30
563
374287
424547295
查找元素54，需依次与30,63,42,54元素比较；
查找元素90，需依次与30,63,87,95元素比较；
求ASL之前，需要统计每个元素的查找次数。
判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，
所以ASL＝1/12（17＋20）＝37/12≈3.08
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。
12
717
2111621
4913
验算方法：
用中序遍历应得到排序结果：
2,4,7,9,11,12,13,16,17，21
（5）设哈希表的地址范围为0～17，哈希函数为：
H（key）=key%16。
用线性探测法处理冲突，输入关键字序列：
（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
画出哈希表的示意图；
若查找关键字63，需要依次与哪些关键字进行比较？
若查找关键字60，需要依次与哪些关键字比较？
假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
画表如下：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49
24
40
10
30
31
46
47
查找63,首先要与H（63）=63%16=15号单元内容比较，即63vs31,no;
然后顺移，与46,47,32,17,63相比，一共比较了6次！
查找60,首先要与H（60）=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。
对于黑色数据元素，各比较1次；共6次；
对红色元素则各不相同，要统计移位的位数。
“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，
所以ASL=1/11（6＋2＋3×3+6）＝23/11
（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：
H（key）=key%7，表长为10，用开放地址法的二次探测法处理冲突。
要求：
对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
散列地址
0
1
2
3
4
5
6
7
8
9
关键字
14
01
9
23
84
27
55
20
比较次数
1
1
1
2
3
4
1
2
平均查找长度：
ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：
H（27）=27%7=6（冲突）H1=（6+1）%10=7（冲突）
H2=（6+22）%10=0（冲突）H3=（6+33）%10=5所以比较了4次。
第8章排序
1．选择题
CDBDCBCDBCBCCCA
2．应用题
（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。
直接插入排序
②折半插入排序
希尔排序（增量选取5，3，1）
冒泡排序
快速排序
简单选择排序
堆排序
二路归并排序
直接插入排序
[212]1630281016*20618
[21216]30281016*20618
[2121630]281016*20618
[212162830]1016*20618
[21012162830]16*20618
[210121616*2830]20618
[210121616*202830]618
[2610121616*202830]18
[2610121616*18202830]
②折半插入排序排序过程同
希尔排序（增量选取5，3，1）
102166181216*203028（增量选取5）
621210181616*203028（增量选取3）
2610121616*18202830（增量选取1）
冒泡排序
21216281016*20618[30]
212161016*20618[2830]
212101616*618[202830]
2101216616*[18202830]
21012616[16*18202830]
210612[1616*18202830]
2610[121616*18202830]
2610121616*18202830]
快速排序
12[6210]12[283016*201618]
6[2]6[10]12[283016*201618]
28261012[181616*20]28[30]
18261012[16*16]18[20]2830
16*26101216*[16]18202830
左子序列递归深度为1，右子序列递归深度为3
简单选择排序
2[121630281016*20618]
26[1630281016*201218]
2610[30281616*201218]
261012[281616*203018]
26101216[2816*203018]
2610121616*[28203018]
2610121616*18[203028]
2610121616*1820[2830]
26101216
升级会员 