数据结构(c语言版)课后习题答案.doc

第1章 绪论
5．选择题：CCBDCA
6．试分析下面各程序段的时间复杂度。
（1）O（1）
（2）O（m*n）
（3）O（n2）
（4）O（log3n）
（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）
（6）O()
第2章 线性表
1．选择题
babadbcabdcddac
2．算法设计题
（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
ElemType Max (LinkList L ){
if(L->next==NULL) return NULL;
pmax=L->next; //假定第一个结点中数据具有最大值
p=L->next->next;
while(p != NULL ){//如果下一个结点存在
if(p->data > pmax->data) pmax=p;
p=p->next;
}
return pmax->data;

（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
void inverse(LinkList &L) {
// 逆置带头结点的单链表 L
p=L->next; L->next=NULL;
while ( p) {
q=p->next; // q指向*p的后继
p->next=L->next;
L->next=p; // *p插入在头结点之后
p = q;
}
}

（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。
[题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。
void Delete（ElemType A[ ]，int n）
∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。
{i=1；j=n；∥设置数组低、高端指针（下标）。
while（iif（ipedef char DataType;//假定栈元素的数据类型为字符
　typedef struct{
　　DataType data[StackSize];
　　int top;
　}SeqStack; 

　int IsHuiwen( char *t)
　　{//判断t字符向量是否为回文，若是，返回1，否则返回0
　　　SeqStack s;
　　　int i , len;
　　　char temp;
　　　InitStack( &s);
　　　len=strlen(t); //求向量长度
　　　for ( i=0; i
　　　　Push( &s, t[i]);
　　　while( !EmptyStack( &s))
　　　　{// 每弹出一个字符与相应字符比较
　　　　　temp=Pop (&s);
　　　　　if( temp!=S[i])  return 0 ;// 不等则返回0
　　　　　else i++;
　　　　} 
　　　return 1 ; // 比较完毕均相等则返回 1
　　}
（7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。
【解答】
循环队列类定义
#include
template class Queue { //循环队列的类定义
public:
Queue ( int=10 );
~Queue ( ) { delete [ ] Q; }
void EnQueue ( Type & item );
Type DeQueue ( );
Type GetFront ( );
void MakeEmpty ( ) { front = rear = tag = 0; } //置空队列
int IsEmpty ( ) const { return front == rear && tag == 0; } //判队列空否
int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否
private:
int rear, front, tag; //队尾指针、队头指针和队满标志
Type *Q; //存放队列元素的数组
int m; //队列最大可容纳元素个数
}
构造函数
template
Queue:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) {
//建立一个最大具有m个元素的空队列。
Q = new Type[m]; //创建队列空间
assert ( Q != 0 ); //断言: 动态存储分配成功与否
}
插入函数
template
void Queue :: EnQueue ( Type &item ) {
assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理
rear = ( rear + 1 ) % m; //队尾位置进1, 队尾指针指示实际队尾位置
Q[rear] = item; //进队列
tag = 1; //标志改1，表示队列不空
}
删除函数
template
Type Queue :: DeQueue ( ) {
assert ( ! IsEmpty ( ) ); //判断队列是否不空空则出错处理
front = ( front + 1 ) % m; //队头位置进1, 队头指针指示实际队头的前一位置
tag = 0; //标志改0, 表示栈不满
return Q[front]; //返回原队头元素的值
}
读取队头元素函数
template
Type Queue :: GetFront ( ) {
assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理
return Q[(front + 1) % m]; //返回队头元素的值
}

第4章 串、数组和广义表
1．选择题
BBCAB BBCBB ABDCB C
2.综合应用题
（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。

模式串t的next和nextval值如下：
j
1 2 3 4 5 6 7 8 9 10 11 12
t串
a b c a a b b a b c a b
next[j]
0 1 1 1 2 2 3 1 2 3 4 5
nextval[j]
0 1 1 0 2 1 3 0 1 1 0 5

（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个数字）。

void Count（）
//统计输入字符串中数字字符和字母字符的个数。
｛int i，num[36]；
char ch；
　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．选择题
ADDCA CCBDC CCACC
2．应用题
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C
①画出这棵二叉树。
②画出这棵二叉树的后序线索树。
A

BM

F

D

(3)

C

EM

H

G

③将这棵二叉树转换成对应的树（或森林）。

(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

0 1
0 1 0 1
19 21 32
0 1
0 1 0 1
7 10 6
0 1
2 3

（100）
（40） （60）
19 21 32 （28）
（17） （11）
7 10 6 （5）
2 3

方案比较：
字母编号
对应编码
出现频率
1
1100
0.07
2
00
0.19
3
11110
0.02
4
1110
0.06
5
10
0.32
6
11111
0.03
7
01
0.21
8
1101
0.10

字母编号
对应编码
出现频率
1
000
0.07
2
001
0.19
3
010
0.02
4
011
0.06
5
100
0.32
6
101
0.03
7
110
0.21
8
111
0.10

方案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）统计二叉树的叶结点个数。
int LeafNodeCount(BiTree T)
{
if(T==NULL)
return 0; //如果是空树，则叶子结点个数为0
else if(T->lchild==NULL&&T->rchild==NULL)
return 1; //判断该结点是否是叶子结点（左孩子右孩子都为空），若是则返回1
else
return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
}
（3）交换二叉树每个结点的左孩子和右孩子。
void ChangeLR(BiTree &T)
{
BiTree temp;
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所示的无向网，请给出：
① 邻接矩阵；
② 邻接表；
③ 最小生成树
图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。
图6.29 邻接矩阵

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
5 63
3 7 42 87
4 24 54 72 95
②查找元素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
7 17
2 11 16 21
4 9 13
验算方法： 用中序遍历应得到排序结果： 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号单元内容比较，即63 vs 31 ,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）
④ 冒泡排序
⑤ 快速排序
⑥ 简单选择排序
⑦ 堆排序
⑧ 二路归并排序

①直接插入排序
[2 12] 16 30 28 10 16* 20 6 18
[2 12 16] 30 28 10 16* 20 6 18
[2 12 16 30] 28 10 16* 20 6 18
[2 12 16 28 30] 10 16* 20 6 18
[2 10 12 16 28 30] 16* 20 6 18
[2 10 12 16 16* 28 30] 20 6 18
[2 10 12 16 16* 20 28 30] 6 18
[2 6 10 12 16 16* 20 28 30] 18
[2 6 10 12 16 16* 18 20 28 30]
② 折半插入排序 排序过程同①
③ 希尔排序（增量选取5，3，1）
10 2 16 6 18 12 16* 20 30 28 （增量选取5）
6 2 12 10 18 16 16* 20 30 28 （增量选取3）
2 6 10 12 16 16* 18 20 28 30 （增量选取1）
④ 冒泡排序
2 12 16 28 10 16* 20 6 18 [30]
2 12 16 10 16* 20 6 18 [28 30]
2 12 10 16 16* 6 18 [20 28 30]
2 10 12 16 6 16* [18 20 28 30]
2 10 12 6 16 [16* 18 20 28 30]
2 10 6 12 [16 16* 18 20 28 30]
2 6 10 [12 16 16* 18 20 28 30]
2 6 10 12 16 16* 18 20 28 30]
⑤ 快速排序
12 [6 2 10] 12 [28 30 16* 20 16 18]
6 [2] 6 [10] 12 [28 30 16* 20 16 18 ]
28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]
18 2 6 10 12 [16* 16] 18 [20] 28 30
16* 2 6 10 12 16* [16] 18 20 28 30
左子序列递归深度为1，右子序列递归深度为3
⑥ 简单选择排序
2 [12 16 30 28 10 16* 20 6 18]
2 6 [16 30 28 10 16* 20 12 18]
2 6 10 [30 28 16 16* 20 12 18]
2 6 10 12 [28 16 16* 20 30 18]
2 6 10 12 16 [28 16* 20 30 18]
2 6 10 12 16 16* [28 20 30 18]
2 6 10 12 16 16* 18 [20 30 28]
2 6 10 12 16 16* 18 20 [28 30]
2 6 10 12 16 16* 18 20 28 [30]
⑧ 二路归并排序
2 12 16 30 10 28 16 * 20 6 18
2 12 16 30 10 16* 20 28 6 18
2 10 12 16 16 20 28 30 6 18
2 6 10 12 16 16* 18 20 28 30
⑦ 堆排序
第一步,形成初始大根堆（详细过程略），第二步做堆排序。
12
2
16
20
10
30
16*
28
6
18
30
28
16
10
20
16*
18
2
12
6

初始排序 不是大根堆 形成初始大根堆12
28
16
2
10
20
16*
18
6
30
28
20
16
10
12
16*
18
2
30
6

交换1与10对象 从1到9重新形成堆
6
20
16
2
10
12
16*
18
28
30
20
18
16
10
12
16*
6
2
30
28

交换1与9对象 从1到8重新形成堆
2
18
16
20
10
12
16*
6
28
30
18
12
16
10
2
16*
12
20
30
28

交换1与8对象 从1到7重新形成堆
16*
12
16
20
10
2
18
6
28
30
16*
12
16
10
2
18
6
20
30
28

交换1与7对象 从1到6重新形成堆
10
12
16
20
16*
2
18
6
28
30
16
12
10
16*
2
18
6
20
30
28

交换1与6对象 从1到5重新形成堆
6
12
10
20
16*
2
18
16
28
30
12
6
10
16*
2
18
16
20
30
28

交换1与5对象 从1到4重新形成堆
12
6
10
20
16*
12
18
16
28
30
10
6
2
16*
12
18
16
20
30
28

交换1与4对象 从1到3重新形成堆
2
6
10
20
16*
12
18
16
28
30
6
2
10
16*
12
18
16
20
30
28

交换1与3对象 从1到2重新形成堆
2
6
10
20
16*
12
18
16
28
30
2
6
10
16*
12
18
16
20
30
28

交换1与2对象 得到结果

3．算法设计题
（1）试以单链表为存储结构，实现简单选择排序算法。
void LinkedListSelectSort(LinkedList head)
//本算法一趟找出一个关键字最小的结点，其数据和当前结点进行交换;若要交换指针，则须记下
//当前结点和最小结点的前驱指针
p=head->next;
while(p!=null)
{q=p->next; r=p; //设r是指向关键字最小的结点的指针
while (q!=null)
{if(q->datadata) r=q;
q:=q->next;
}
if(r!=p) r->data<-->p->data;
p=p->next;
}