数据结构习题集答案c版清华大学严蔚敏.docx
《数据结构习题集答案c版清华大学严蔚敏.docx》由会员分享，可在线阅读，更多相关《数据结构习题集答案c版清华大学严蔚敏.docx（106页珍藏版）》请在冰点文库上搜索。
数据结构习题集答案c版清华大学严蔚敏
1.16
（z）按从大到小顺序输出三个数
{
（""）;
（xy;<->为表示交换的双目运算符,以下同
（yz;
（xy;冒泡排序
（""）;
}
1.17
（）求k阶斐波那契序列的第m项的值f
{
;
（k<2<0）;
（m<1）0;
（1）1;
{
（0<2）0;
[1]=1;初始化
（<）求出序列第k至第m个元素的值
{
0;
（<）[j];
;
}
[m];
}
;
}
分析:
通过保存已经计算出来的结果,此方法的时间复杂度仅为O（m^2）.如果采用递归编程（大多数人都会首先想到递归方法）,则时间复杂度将高达O（k^m）.
1.18
{
*;
{};
;校名为'A','B','C','D'或'E'
*;
;
};
{
;
;
;
};
（[]）求各校的男女总分和团体总分,假设结果已经储存在[]数组中
{
;
0;
（）
{
（）
{
'A':
[0];
（0）[0];
[0];
;
'B':
;
（0）;
;
;
……?
……?
……
}
；
}
（0<5）
{
（":
\n"）;
（"\n"）;
（"\n"）;
（"\n\n"）;
}
}
1.19
119（a[]）求i!
*2^i序列的值且不超过
{
1;
（1<）
{
a[1]*2*i;
（（a[1]）（2*i））;
[1];
;
}
}119
分析:
当某一项的结果超过了时,它除以前面一项的商会发生异常.
1.20
（）
{
;
*;
（":
"）;
（""）;
（"a0:
\n"）;
（0<）（""）;
（"x:
"）;
（""）;
10;用于存放x的i次方
（0<）
{
*（*）;
*;
}
（""）;
}
2.10
（k）删除线性表a中第i个元素起的k个元素
{
（i<1<01>）;
（11<）注意循环结束的条件
[1][1];
;
;
}
2.11
（x）把x插入递增有序表中
{
（1>）;
;
（1>>=0）
[1];
[1];
;
}
2.12
（B）比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A{
（1）
（）;
0;
}
2.13
*（x）链表上的元素查找,返回指针
{
（>>>）;
p;
}
2.14
（L）求链表的长度
{
（0>>）;
k;
}
2.15
（）把链表接在后面形成链表
{
;
（>）>;
>;
}
2.16
见书后答案.
2.17
（b）在无头结点链表L的第i个元素之前插入元素b
{
（*）（（））;
;
（1）
{
;插入在链表头部
}
{
（>1）>;
>>>;插入在第i个元素的位置
}
}
2.18
（i）在无头结点链表L中删除第i个元素
{
（1）>;删除第一个元素
{
;
（>1）>;
>>>;删除第i个元素
}
}
2.19
（）删除元素递增排列的链表L中值大于且小于的所有元素
{
;
（>><）>;是最后一个不大于的元素
（>）如果还有比更大的元素
{
>;
（><）>;是第一个不小于的元素
>;
}
}
2.20
（）删除元素递增排列的链表L中所有值相同的元素
{
>>;指向相邻两元素
（>）
{
（>>）
{
>>;当相邻两元素不相等时都向后推一步
}
{
（>>）
{
（q）;
>;
}
>>;当相邻元素相等时删除多余元素
}
}
}
2.21
（）顺序表的就地逆置
{
（1<）
<->[j];
}
2.22
（）链表的就地逆置;为简化算法,假设表长大于2
{
>>>>;
（>）
{
>;
>;把L的元素逐个插入新表表头
}
>>>;
}
分析:
本算法的思想是,逐个地把L的当前元素q插入新的链表头部为新表表头.
2.23
1（）把链表A和B合并为和B的元素间隔排列,且使用原存储空间
{
>>;
（）
{
>>;将B的元素插入
（s）
{
>>;如A非空,将A的元素插入
}
;
}
}1
2.24
（）把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
{
>>;和分别指向的当前元素
（）
{
（><>）
{
>>;将A的元素插入新表
}
{
>>;将B的元素插入新表
}
;
}
>;构造新表头
}
分析:
本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部处,最后处理A或B的剩余元素.
2.25
（）求元素递增排列的线性表A和B的元素的交集并存入C中
{
110;
（[j]）
{
（<[j]）;
（>[j]）;
（[j]）
{
[];当发现了一个在中都存在的元素,
;就添加到C中
}
}
}
2.26
（）在链表结构上重做上题
{
>>;
（*）（（））;
（）
{
（><>）>;
（>>>）>;
{
（*）（（））;
>>;
>;
>>;
}
}
;
}
2.27
（B）求元素递增排列的线性表A和B的元素的交集并存回A中
{
110;
（[j]）
{
（<[j]）;
（>[j]）;
（[k]）
{
[];当发现了一个在中都存在的元素
;且C中没有,就添加到C中
}
}
（[k]）[]=0;
}
2.28
（B）在链表结构上重做上题
{
>>;
（）
{
（><>）>;
（>>>）>;
（>>）
{
>;
>>;
>>;
}
}
}
2.29
（C）
{
0000;指示A中元素原来的位置为移动后的位置
（i<{
（[j]<[k]）;
（[j]>[k]）;
{
[j];找到了相同元素
（[j]）;
（[k]）;后移到新的元素
（i<<）
[][];需保留的元素移动到新位置
（i<）;跳过相同的元素
}
}
（i<）
[][];的剩余元素重新存储。
;
}
分析:
先从B和C中找出共有元素,记为,再在A中从当前位置开始,凡小于的
元素均保留（存到新的位置）,等于的就跳过,到大于时就再找下一个.
2.30
（C）在链表结构上重做上题
{
>>;
（）
{
（><>）>;
（>>>）>;
{
>;确定待删除元素u
（>>;确定最后一个小于u的元素指针r
（>>）
{
>;
（>）
{
>（t）;确定第一个大于u的元素指针s
}
>;删除r和s之间的元素
}
（>）>;
（>）>;
}
}
}
2.31
（*s）删除单循环链表中结点s的直接前驱
{
;
（>>）>;找到s的前驱的前驱p
>;
;
}
2.32
（）完成双向循环链表结点的域
{
（>>>）>>;
;
}
2.33
（）把单链表L的元素按类型分为三个循环链表为带头结点的单循环链表类型.
{
>;
（*）（（））;
（*）（（））;
（*）（（））;建立头结点
（s）
{
（（>））
{
>;
}
（（>））
{
>;
}
{
>;
}
}
>>>;完成循环链表
}
2.34
（L）从左向右输出异或链表的元素值
{
;
（p）
{
（"">）;
（>）;
;任何一个结点的域值与其左结点指针进行异或运算即得到其右结点指针
}
}
2.35
（i）在异或链表L的第i个元素前插入元素x
{
;
（*）（（））;
>;
（1）当插入点在最左边的情况
{
>（）;
>;
;
;
}
1>;当插入点在中间的情况
（<）
{
（>）;
;
}在两结点之间插入
（）;不可以超过表长
>（（>））;
>（（>））;
>（）;修改指针
;
}
2.36
（i）删除异或链表L的第i个元素
{
;
（1）删除最左结点的情况
{
>;
>（>）;
（p）;
;
}
1>;
（<）
{
（>）;
;
}找到待删结点q
（）;不可以超过表长
（）为最右结点的情况
{
>（>）;
（q）;
;
}
（>）;为中间结点的情况,此时分别为其左右结点
>（（>））;
>（（>））;修改指针
（q）;
;
}
2.37
（）按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点
{
;
（>>>）
{
>>>;
>;
}此时p指向最后一个奇数结点
（>）>>>;
>>;
>;此时p指向最后一个偶数结点
（>>）
{
>>>;
>;
}
>;按题目要求调整了链的结构,此时链仍为原状
（>>）>>;
>;调整链的结构,同2.32方法
}
分析链和链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.
2.38
*（x）带域的双向循环链表上的查找
{
;
（）>;
（）;没找到
>>;
（><>）>;查找插入位置
（>）
{
>>>>>>;
>>>>;
>>;调整位置
}
p;
}
2.39
（x0）求升幂顺序存储的稀疏多项式的值
{
*q;
1;
00;
（>）
{
（<>）*0;
>*;
;
}
;
}
2.40
（P1P2&3）求稀疏多项式P1减P2的差式P3
{
*p,*q,*r;
（P3）;建立空多项式P3
123;
（>>）
{
（><>）
{
>>;
>>;
;
}
（><>）
{
>>;
>>;
;
}
{
（（>>）0）只有同次项相减不为零时才需要存入P3中
{
>>>;
>>;
}
;
}
}
（>）处理P1或P2的剩余项
{
>>;
>>;
;
}
（>）
{
>>;
>>;
;
}
}
2.41
（）对有头结点循环链表结构存储的稀疏多项式L求导
{
>;
（>）
{
>>>;跳过常数项
}
（）
{
>*>对每一项求导
>;
}
}
2.42
（）把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
{
>;
（*）（（））;
（*）（（））;
;
（）
{
（>2*（>2））
{
>;
}
{
>;
}
>;
}
>>;
}
3.15
{
*[2];
*[2];
};双向栈类型
（m）初始化一个大小为m的双向栈
{
[0]=（*）（（））;
[1][0];
[0][0];
[1][1];
;
}
（x）入栈0表示低端栈1表示高端栈
{
（[0]>[1]）;注意此时的栈满条件
（0）*[0];
（1）*[1];
;
;
}
（）出栈0表示低端栈1表示高端栈
{
（0）
{
（[0][0]）;
*[0];
}
（1）
{
（[1][1]）;
*[1];
}
;
;
}
3.16
（*）这里用字符串表示火车,'H'表示硬席,'S'表示软席
{
;
（s）;
（*p）
{
（*'H'）（s,*p）;把'H'存入栈中
*（）=*p;把'S'调到前部
;
}
（（s））
{
（）;
*（）;把'H'接在后部
}
}
3.17
（）判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
（s）;
（（（））'&'）
（）;
（（（））'@'）
{
（（s））0;
（）;
（）0;
}
（（s））0;
1;
}
3.18
（*）判别表达式中小括号是否匹配
{
0;
（;*）
{
（*'（'）;
（*'）'）;
（<0）;
}
（）;注意括号不匹配的两种情况
;
}
3.19
（*）判别表达式中三种括号是否匹配
{
（s）;
（;*）
{
（*'（'*'['*'{'）（s,*p）;
（*'）'*']'*'}'）
{
（（s））;
（）;
（*'）''（'）;
（*']''['）;
（*'}''{'）;必须与当前栈顶括号匹配
}
}
（（s））;
;
}
3.20
{
. x;
y;
};
（g[m][n]）把点（）相邻区域的颜色置换为
{
[j];
（Q）;
（Q,{}）;
（（Q））
{
（）;
;
（x>1）
（g[1][y]）
{
g[1][y];
（Q,{1}）;修改左邻点的颜色
}
（y>1）
（g[x][1]）
{
g[x][1];
（Q,{1}）;修改上邻点的颜色
}
（x （g[1][y]）
{
g[1][y];
（Q,{1}）;修改右邻点的颜色
}
（y （g[x][1]）
{
g[x][1];
（Q,{1}）;修改下邻点的颜色
}
}
}
分析:
本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢?
3.21
（**）把中缀表达式转换成逆波兰式
{
;为方便起见,设的两端都加上了优先级最低的特殊符号
（s）;为运算符栈
（*p）
{
（*p是字母））**p;直接输出
{
（s）;
（*p优先级比c高）（s,*p）;
{
（（s）优先级不比*p低）
{
（）;*（）;
}
（s,*p）;运算符在栈内遵循越往栈顶优先级越高的原则
}
}
;
}
}参见编译原理教材
3.22
（*）对逆波兰式求值
{
（s）;为操作数栈
（*p）
{
（*p是数）（s,*p）;
{
（）（）;
（b,*）;假设为执行双目运算的过程
（）;
}
;
}
（）r;
}
3.23
（*）把逆波兰表达式转换为波兰式
{
（s）;的元素为类型
（*p）
{
（*p为字母）（s,*p）;
{
（（s））;
（）;
（（s））;
（）;
（（*））;
（）;
}
;
}
（）;
（（s））;
;
}
分析:
基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型,对其可以进行连接操作（）.
3.24
g（）求递归函数g的值s
{
（0>=0）0;
（m>0>=0）（1,2*n）;
;
;
}
3.25
（）递归算法
{
（n<0）;
（0）1;
{
（2）;
*r;
}
;
}
（s）非递归算法
{
（n<0）;
（0）1;
{
（s）;的元素类型为{b;}
（0）
{
2;
（s,{}）;
;
}
1;
（（s））
{
（）;
s*;
}
}
;
}
3.26
（e）求平方根的递归算法
{
（（p^2）<）p;
（A,（）/2）;
}
（e）求平方根的非递归算法
{
（（p^2）>）
（）/2;
p;
}
3.27
这一题的所有算法以及栈的变化过程请参见《数据结构（版）》,作者不再详细写出.
3.28
（）初始化循环链表表示的队列Q
{
（*）（（））;
>;
}
（x）把元素x插入循环链表表示的队列指向队尾元素>指向头结点>>指向队头元素
{
（*）（（））;
>;
>>;直接把p加在Q的后面
>;
; 修改尾指针
}
（x）从循环链表表示的队列Q头部删除元素x
{
（>）;队列已空
>>;
>;
>>>;
（p）;
;
}
3.29
（x）带域的循环队列入队算法
{
（1）域的值为0表示"空",1表示"满"
;
[];
（1）;
（）1;队列满
}
（）带域的循环队列出队算法
{
（0）;
（1）;
[];
（）1;队列空
;
}
分析:
当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.
3.30
（x）带域的循环队列入队算法
{
（）;
（1）;
[];
;
;
}
（）带域的循环队列出队算法
{
（0）;
（1）;详见书后注释
[];
;
}
3.31
（）判别输入的字符串是否回文序列,是则返回1,否则返回0
{
（S）（Q）;
（（（）'@'）
{
（）（）;同时使用栈和队列两种结构
}
（（S））
{
（）（））;
（）;
}
;
}
3.32
（n）求k阶斐波那契序列的前1项
{
（Q）;其设置为k
（0<1）0;
[1]=1;给前k项赋初值
（0<）（""）;
（<）
{
0;
（0<）[（）];
[m];求第i项的值存入队列中并取代已无用的第一项
（""）;
}
}
3.33
（x）输出受限的双端队列的入队操作
{
（
（1））;队列满
（[1][]）/2;
（x>）根据x的值决定插入在队头还是队尾
{
[];
（1）;
}插入在队尾
{
（1）;
[];
}插入在队头
;
}
（）输出受限的双端队列的出队操作
{
（）;队列空
[];
（1）;
;
}
3.34
（*）这里用字符串表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按的顺序排列
{
;
（Q）;
（*r）
{
（*'P'）
{
（"E"）;
（"D"）;实际上等于不入队列,直接输出P车厢
}
（*'S'）
{
（"E"）;
（Q,*r,0）;0表示把S车厢从头端入队列
}
{
（"A"）;
（Q,*r,1）;1表示把H车厢从尾端入队列
}
}
（（Q））
{
（"D"）;
（Q）;
}从头端出队列的车厢必然是先S后H的顺序
}
4.10（）求s的逆串r{（r,''）;初始化r为空串（（s））{（（,1））;（（））;把s的字符从后往前添加到r中}}
4.11（）求所有包含在串s中而t中没有的字符构成的新串r{（r,''）;（1<（s））{（（,1））;（1<（（,1）））;（k判断当前字符是否包含在t中（"1<（t）（（,1）））;"{（"）"判断s的当前字符c是否第一次出现>（t））（（））;}}}
4.12（V）将串S中所有子串T替换为V,并返回置换次数{（01<（S）（T）+1）注意i的取值范围（（（（T））））找到了与T匹配的子串{分别把T的前面和后面部分保存为和（（S,11））;（（（T）（S）（T）+1））;（（））;（（））;把连接为新串（V）;当前指针跳到插入串以后;}n;}分析（V）;这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:
设'','','',则省掉（V）;运行时会出现什么结果?
4.13（t）从串s中删除所有与t相同的子串,并返回删除次数{（01<（s）（t）+1）（（（（t））））{（（S,11））;（（（t）（s）（t）+1））;（（））;把连接为新串;}n,}
4.14（）把前缀表达式转换为后缀式{（s）;的元素为类型（1<（））{（,1）;（r为字母）（）;{（（s））;（）;（（s））;（
升级会员 