算法与数据结构C语言习题参考答案15章.doc

1. 绪 论
1．将以下复杂度由小到大重新排序：
A．2n B．n! C．n5 D．10 000 E．n*2 (n)
【答】10 000< n*2(n)< n5< 2n < n!
2．将以下复杂度由小到大重新排序：
A．n*2(n) B．n + n2 + n3 C．24 D．n
【答】24< n< n*2 (n) < n + n2 + n3
3．用大“O〞表示法描述以下复杂度：
A．5n5/2 + n2/5 B．6*2(n) + 9n
C．3n4+ n* 2(n) D．5n2 + n3/2
【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2)
4．按照增长率从低到高的顺序排列以下表达式：4n2 , 3n, 3n , 20n , 2000 , 2n , n2/3。又n！应排在第几位？
【答】按照增长率从低到高依次为：2000, 3n, 2n , n2/3 , 20n , 4n2 , 3n。
n！的增长率比它们中的每一个都要大，应排在最后一位。
5. 计算以下程序片断的时间代价：
1;
(i<)
(“\n〞);
1;
【答】循环控制变量i从1增加到n，循环体执行n次，第一句i的初始化执行次数为1，第二句执行n次，循环体中第一句执行n次，第二句i从1循环到n，共执行n次。所以该程序段总的时间代价为：
T(n) = 1 + n + 2n = 3 1 = O(n)
6. 计算以下程序片断的时间代价：
1;
(i<)
1;
(j<)
1;
(k<)
(“\n〞);
1;
1;
1;
【答】循环控制变量i从1增加到n，最外层循环体执行n次，循环控制变量j从1增加到n，中间层循环体执行n次，循环控制变量k从1增加到n，最内层循环体执行n次，所以该程序段总的时间代价为：
T(n) = 1 + n + n｛1 + n + n[1 + n + 2n +1] +1 +1｝+ 1
= 3n3 + 3n2 +4n +2
= O(n3)
2. 线性表
1.试写一个插入算法 (, p, x )，在所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功及否的标志。
【答】
数据构造
采用2.1.2节中顺序表定义。
( , p, x ){
/* 在所指顺序表中下标为p的元素之后插入元素x */
q;
( >n >= > ) { /* 溢出 */
(“!\n〞);
0;
(p<0 p>>1 ) { /* 不存在下标为p的元素 */
(“ ! \n〞); 0;
(>n - 1; q>1; ) /* 插入位置及之后的元素均后移一个位置 */
>[1] = >[q];
>[1] = x; /* 插入元素x */
>n = >n + 1; /* 元素个数加1 */
1;
2试写一个删除算法(, x )，在所指顺序表中，删除一个值为x的元素，返回删除成功及否的标志。
【答】
数据构造
采用2.1.2节中顺序表定义。
( , p, x ) {
/* 在所指顺序表中删除值为x的元素 */
(0<) /*查找值为x的元素的下标*/
(>[p]){
(; q<>1; ) /* 被删除元素之后的元素均前移一个位置 */
>[q] = >[1];
>n = >n - 1; /* 元素个数减1 */
1 ;
0;
3. 设有一线性表e = (e0, e1 , e2 , … , -1 )，其逆线性表定义为e¢= (-1 , … , e2 , e1 0)。请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的空间。
【答】
数据构造
采用节中顺序表的定义。
思路
考虑对数组[ ]进展置逆，即把第一个元素与最后一个元素换位置，把第二个元素与倒数第二个元素换位置……。
A 注意
这种调换的工作只需对数组的前一半元素进展，所以设置整数变量用于存放数组长度的一半的值。大家可以考虑一下：为什么不能对整个数组进展如上的对元素“换位置〞的工作？〔提示：这样会将本来已经置逆的线性表又置逆回来，即又变成了原来的表。〕
顺序表的置逆算法
x;
, i;
(>n 0 >n 1) ; /*空表或只有一个元素，直接返回*/
= >n / 2;
( i = 0; i < ; ){ /*只需调换半个表的元素*/
x = >[i];
>[i] = >[>n - 1 - i];
>[>n - 1 - i] = x;
代价分析
该算法中包含一个循环，其循环次数为2。因此，算法的时间代价为O(n)。
4. 长度为n的线性表A采用顺序存储构造，请写一算法，找出该线性表中值最小的数据元素。
【答】
数据构造
采用节中顺序表定义。
思路
设置变量，遍历整个表，不断更新当前已经经历过的元素的最小值即可。
为方便起见，事先假设表不为空。
算法
( ){ /*求非空顺序表中的最小数据元素*/
i;
= >[0]; /*初始化*/
( i = 1; i < >n; ) /*中保存的总是当前的最小数据*/
( > >[i])
= >[i];
代价分析
该算法访问顺序表中每个元素各一次，时间代价为O(n)。
A 讨论
读者可以试图对上面的算法进展修改，使返回的值不是最小元素的值而是它的下标。
5. 线性表A的长度为n，并且采用顺序存储构造。写一算法，删除线性表中所有值为x的元素。
【答】
数据构造
采用节中顺序表的定义。
思路
为了减少移动次数，可以采用快速检索的思想，用两个变量i, j记录顺序表中被处理的两端元素的下标，开场时i = 0，j = n-1，边检索第i个元素边增加i，直到找到一个元素值等于x，再边检索第j个元素边减少j，直到找到一个元素值不等于x，把下标为j的元素移到下标为i的位置后重复上述过程，直到i ≥ j。另用一变量记录删除了多少个元素。
算法
( p, x){
/*删除顺序表中所有值为x的元素，新顺序表可能不保持原有顺序*/
i = 0, j = >n - 1, = 0; /*i定位于顺序表开场处，j定位于顺序表最后*/
( i < j) {
(>[i] x) { /*找到了一个要删除的元素*/
((>[j] x) (i j)) {
/*从后往前找不会被删除的元素，当i, j相等时退出循环，记录从后往前找的过程中遇到了多少个要删的元素*/
j- -;
( i = = j) {
>n = >n - - 1;
>[i] = >[j];
j- -;
>n = >n - ;
(>[i] x) p->n- -;
代价分析
该算法访问顺序表中每个元素各一次，时间代价为O (n)。
A 讨论
这个算法使用了一点技巧使得在中间删除元素时，防止了最后一串元素的移动。但是，它破坏了原来线性表中元素之间的顺序关系。
如果需要保持原来的顺序应该怎样做？这里提供一种可行的思路：从前向后遍历表，如果元素不是x，那么继续向后；如果元素是x，那么寻找其后第一个不是x的元素，将这两个元素互换。具体算法请读者自己实现。
6.写一算法，在带头结点的单链表中，p所指结点前面插入值为ｘ的新结点，并返回插入成功及否的标志。
【答】
数据构造
采用2.1.3节中单链表定义。
思想：
由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成插入。而找p所指结点的前驱结点，只能从单链表的第一个结点开场，使用及 类似的方式进展搜索。
算法：
( x){
/* 在带头结点的单链表中，p所指结点前面插入值为x的新结点 */
p1;
() 0;
p1;
(p11->)p11->; /*寻找p所指结点的前驱结点*/
(p1) 0;
()(( ))*申请新结点*/
() {(“ !!!\n〞) 0;}
>1->;
p1->;
1;
7.写一算法，在带头结点的单链表中,删除p所指的结点，并返回删除成功及否的标志。
【答】
数据构造
采用2.1.3节中单链表定义。
思想：
由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成删除。而找p所指结点的前驱结点，只能从单链表的第一个结点开场，使用及 类似的方式进展搜索。
( p){
/* 在带头结点的单链表中，删除p所指的结点 */
p1;
p1;
(p11->)p11->; /*寻找p所指结点的前驱结点*/
(p1) 0;
p1->>;
(p); /* 删除结点p */
1;
8. 是指向无头结点的单链表的指针变量，写出删除该链表下标为i的〔第1个〕结点的算法。
【答】
数据构造
采用节中单链表定义。
思路
依次遍历表中的每一个结点并计数，到第1个结点时实行删除。由于链表是无头结点的，所以在删除第一个结点时要特别注意。
算法
( * , i) {
/*删除单链表中下标为i的结点。删除成功返回，否那么返回。*/
j;
p, q;
((*) i < 0) ;
( i = = 0) { /*如果需要删除第一个结点*/
q = (*);
(q);
p = (*);
j = 0;
(> j < i - 1) { /*寻找下标为i-1的结点的地址*/
p = >;
(> ) ; /*此元素不存在*/
q = >;
(q);
代价分析
该算法访问单链表中前面i个结点，时间代价为O(i)，最大不超过O(n)。
A 讨论
如果函数参数不是 *类型而是类型，在删除0的结点时，程序不能正确实现，其原因请读者思考〔考虑C语言的参数传递方式〕。
如果单链表带表头结点，重写此题的算法。比拟这两个算法，是否能体会到表头结点的作用。
9. 是指向无头结点的单链表的指针变量，写出删除该链表中从下标为i的〔第1个〕结点开场的连续k个结点的算法。
【答】
数据构造
采用节单链表定义。
思路
这道题及上题相似，只需要增加计数即可。要注意的是应该判断给出的i与k是否合理，是不是会超出链表长度。
算法
( * , i, k) {
/*删除单链表中从下标i开场的k个结点。删除成功返回，否那么返回。*/
j;
p, q;
((*) i < 0 k <= 0) ;
( i = = 0) { /*如果需要删除从第一个结点开场的k个结点*/
( j = 0; j < k (*) ; ) {
q = (*);
(q);
p = (*);
j = 0;
( > j < i - 1) { /*寻找下标为i-1的结点的地址*/
p = >;
(> ) ; /*第i个结点不存在*/
( j = 0; j < k > ; ) {
q = >;
(q);
代价分析
该算法访问单链表中前面个结点，时间代价为O()，最大不超过O(n)。
13. 请设计一个算法，求出循环表中结点的个数。
【答】
数据构造
采用不带头结点的循环链表。
思路
遍历整个循环链表，同时计数即可。
A 错误算法
p, q;
p = ;
q = >;
( ) 0; /*如果是空表*/
= 1;
( q p){
q = >;
错误：如果是一个空表，那么第5行的语句“q = >;〞是非法的。
分析：应把第6行语句〔用下划线表示〕提前1行或2行。一定要放在语句“q = >;〞之前。
缺点：增加局部变量p。
分析：这样做没有必要，因为p的初值置为，在程序中并没有对p做其他修改，所以程序中不需要引入p而直接使用即可。
算法
q;
( ) 0; /*如果是空表*/
q = >;
= 1;
( q ){
q = >;
代价分析
该算法访问循环链表中每个结点各一次，时间代价为O(n)。
4. 栈及队列
1. 写一个递归算法来把整数字符串转换为整数。〔例：“43567”→ 43567。〕
【答】
思路
先递归调用本算法转换除去末位外剩余的字符串，结果乘以10。再转换末位。将两结果相加即为所求。
算法
1( * s, , ) {
/*把整数字符串s中从到的局部转换为整数*/
( > ) -1; /*转换失败*/
( ) s[] - '0'; /*只有一个字符，直接转换*/
1(s, , - 1) * 10 + s[] - '0'; /*先转换其他位，再转换末位*/
( * s) { /*把整数字符串s转换为整数*/
i = 0;
(s[i] '\0') ; /*计算字符串的长度*/
1(s, 0, i - 1);
代价分析
设n为字符串的长度。该算法访问每个字符各一次，时间代价为O(n)，计算字符串的长度的时间代价也为O(n)。故总的时间代价为O(n)。
递归算法需要栈的支持，栈的大小及递归调用的深度成正比。所以实际空间开销为O(n)。
2. 编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印出来。
【答】
数据构造
采用节中栈的顺序表示。
思路
将输入的十进制数字反复除以2，直到它变为0。将每次的数字模2的余数入栈。栈中存放的就是所要求的二进制表示。再将栈中的元素依次弹出打印即可。
算法
( ) { /*将十进制非负整数转化为二进制数打印出来*/
( < 0) {
("!\n");
= (); /*建立一个空栈*/
( > 0) {
(, % 2);
2;
代价分析
设输入的十进制数字为n，那么算法的时间代价为O()。空间代价主要是栈的大小，为O()。
3．写一个算法： ( m ) 创立一个空栈。
数据构造
采用节中栈的顺序表示。
( m){
/* 创立一个空栈 */
->s = (*)(()*m);
( ->s){
-> -1; /* 栈顶变量赋值为-1 */
(“ !!\n〞); /* 存储分配失败 */
4，写一个算法： ( ) 判断所指的栈是否为空栈。
数据构造
采用节中栈的顺序表示。
/* 判断所指的栈是否为空栈 */
(>t -1) 1;
0;
8. 假设以循环链表表示队列，并且只设一个指针指向队尾元素结点〔注意不设队头指针〕，试编写相应的创立空队列、入队列与出队列的算法。
【答】
数据构造
采用不带头结点的循环链表表示队列。
{ /*循环链表表示的队列类型*/
r; /*尾指针*/
* ; /*指向循环链表表示的队列的指针类型*/
思路
及队列的单链表表示相似，但节省了指向队头的指针变量，所以在需要找表头结点时必须通过表尾指针进展。
算法
() { /*创立空队列*/
>r = ;
( , x) { /*进队列*/
p;
p = ()(( ));
> = x;
(>r ) {
>r = p;
> = p;
} /*进空队列，即往空队列中参加第一个结点*/
>> = p;
>r = p;
( ) { /*出队列*/
p;
(>r ) { /*是空队列*/
("!\n");
(>> >r) { /*只有一个元素的队列*/
(>r);
>r = ;
p = >>; /*指向队头*/
(p);
代价分析
上述几个算法都不包含循环，只有常数条语句，因此每个算法的时间代价均为O(1)。
A 讨论
此题可以看成队列的循环表实现。
5. 二叉树及树
1. 写一个算法来计算给定二叉树的叶结点数。
【答】
数据构造
采用5.1.3节中二叉树的链接表示。
算法
( t) { /*计算二叉树的叶结点个数*/
(t = = ) 0; /*空树，返回0*/
(> = = > = = ) 1; /*根结点是树叶，返回1*/
/*返回“左子树的叶结点数+右子树的叶结点数〞*/
代价分析
该算法访问每个结点各一次，时间代价为O(n)。空间代价为O(h)。
2. 假设二叉树采用链接方法存储，编写一个计算一棵二叉树t的高度的函数。
【答】
数据构造
采用5.1.3节中二叉树的链接表示。
思路
对一棵二叉树t，考察它左右子树的高度，取其中大的一个，再加1即为t的高度。
算法
( t)
= t;
-1;
( > : ) + 1;
代价分析
设树中的结点个数为n，递归访问次数只可能是n。所以，时间代价为O(n)。空间代价为O(h)。h为二叉树的高度。
6. 设计一个程序，根据二叉树的先根序列与对称序序列创立一棵用左右指针表示的二叉树。
【答】
数据构造
采用5.1.3节中二叉树的链接表示。
思路
二叉树的先根序列与对称序序列，用两个数组与存放。先根序列的第一个元素的值[0]应为二叉树的根上的元素值，在另一个数组中查到此值，设为[k]。此时，数组中从[1]到[k]的序列〔长度为k〕与数组中从[0]到[k-1]〔长度为k〕的序列，恰好分别是根结点左子树〔k个结点〕的先根序列与对称序序列。数组中从[1]到[n-1]的序列〔长度为n-k-1〕与数组中从[1]到[n-1]〔长度为n-k-1〕的序列，恰好分别是根结点左子树〔n-k-1个结点〕的先根序列与对称序序列。
根据上述分析，算法先创立根结点，再递归调用自己两次来分别创立左右子树。
算法
( , * , * , n){
/*根据先根序列与对称序序列〔长度为n〕创立二叉树。对于正确的先根序列与对称序序列，算法返回，否那么返回。*/
i, k;
1, 2;
(n = = 0) {
(i = 0; i < n; )
([i] = = [0])
(i = = n) {
; /*输入的先根序列或对称序序列有误，创立失败*/
k = i;
(*)-> = [0];
1 = (&(*)->, + 1, , k);
/*递归调用本算法创立左子树*/
2 = (&(*)->, + k + 1, + k + 1, n - k - 1);
/*递归调用本算法创立右子树*/
(1 = = 2 = = ) ;
; /*二叉树创立成功当且仅当其左右子树都创立成功*/
代价分析
最坏的情况是，每个非叶结点只有左子树。这时两个数组之间需要比拟(1)+…+1(n2)次。所以，该算法的时间代价为O(n2)。空间代价主要包括：存放二叉树的空间O(n)与用于递归调用的栈空间〔不超过O(n)〕。
7. 试设计树的子表表示法的存储构造，并给出在这种表示根底上主要运算的实现算法。
【答】
数据构造
/*边表中结点的定义*/
; /*子结点位置*/
* ; /*下一个边的指针*/
/*结点的定义*/
; /*结点本身信息*/
* ; /*到子结点的边表*/
/*树的定义*/
[]; /*结点表*/
; /*根的位置*/
n; /*结点的个数*/
算法
创立空树
p;
p = ()(( ));
(p = = )
(" !\n");
>0;
> = -1;
p;
判断树是否为空
( t)
>n = = 0;
返回非空树的根结点的下标
( t)
返回下标为p的结点的父结点的下标
( t, p)
i;
* v;
(p < 0 p >= >n) -1;
(i = 0; i < >n; )
v = >[i];
(v )
(> = = p)
i;
v = >;
-1;
返回下标为p的结点的最左子结点的下标
( t, p)
* v;
(p < 0 p >= >n) -1;
v = >[i];
(v = = ) -1;
返回下标为p的结点的右兄弟结点的下标
( t, p)
i;
* v;
(p < 0 p >= >n) -1; /*没有下标为p的结点*/
(i = 0; i < >n; ) /*循环每次检查结点下标中一个元素*/
v = >[i];
(v ) /*每次循环检查结点i的边表中的一个元素*/
(> = = p)
-1; /*没有右兄弟结点*/
>>; /*返回右兄弟结点在结点表中的位置*/
-1; /*没有右兄弟结点*/
代价分析
这是一个两重循环程序，外层循环最多执行n次，内层循环对每个结点的子结点进展检查，子结点的个数最大可能及n接近，所以外表看来这是一个n2阶的时间代价；但是，仔细分析内层的循环体，可以看出内层循环最多对树中的每条边执行一次，由于树中边的个数及结点的个数成正比，所以时间代价仍然是O(n)。
补充题：
1. 试设计完全二叉树的顺序表示法的存储构造，并给出在这种表示根底上主要运算的实现算法。
【答】
数据构造
n; /*完全二叉树的结点个数*/
算法
判断二叉树是否为空
( t)
>n = = 0;
返回非空二叉树的根结点的下标
( t)
0;
返回下标为p的结点的父结点的下标
( t, p)
(p < 0 p >= >n) -1;
(p - 1) / 2;
返回下标为p的结点的左子结点的下标
( t, p)
(p < 0 p >= >n) -1;
2*p + 1;
返回下标为p的结点的右子结点的下标
( t, p)
(p < 0 p >= >n) -1;
2 * (p + 1);
2. 试设计二叉树的左右指针表示法的存储构造，并给出在这种表示根底上主要运算的实现算法。
【答】
数据构造
算法
判断二叉树是否为空
( t)
t = = ;
返回非空二叉树的根结点的地址
( t)
t;
返回二叉树t中结点p的父结点的地址
( p, t)
r;
(p = = ) ;
(p = = t t = = ) ;
(> = = p > = = p) t;
r = (p, >); /*递归调用*/
(r ) r;
r = (p, >); /*递归调用*/
(r ) r;
返回结点p的左子结点的地址
( p)
(p = = ) ;
返回结点p的右子结点的地址
( p)
(p = = ) ;
第 22 页