数据结构习题集(C语言版严蔚敏)第一二三章

C的算法，即使得

C??a1,b1,?,am,bm,bm?1,?,bn? C??a1,b1,?,an,bn,an?1,?,am?

当m?n时； 当m?n时。

线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。

2.26 要求同2.25题。试对单链表编写求C的算法。

2.27 对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。

(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同； (2) 利用A表空间存放表C。

2.28 对2.25题的条件作以下两点修改，对单链表重新编写求得表C的算法。

(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同； (2) 利用原表（A表或B表）中的结点构成表C，并释放A表中的无用结点空间。

2.29 已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。

2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。

2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

2.32 已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。

2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。

2.34 假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且

a⊕(a⊕b)=(a⊕a)⊕b=b (a⊕b)⊕b=a⊕(b⊕b)=a

则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。

2.35 采用2.34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。

2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。 2.37 设以带头结点的双向循环链表表示的线性表L将L改造为L??a1,a2,?,an?。试写一时间复杂度O(n)的算法，

??a1,a3,?,an,?,a4,a2?。

2.38 设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。 2.39 已知稀疏多项式

Pn?x??c1xe1?c2xe2???cmxem，其中

n?em?em?1???e1?0，

ci?0?i?1,2,?,m?，m?1。试采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn?x0?的算法（x0为给定值），并分析你的算法的时间复杂度。 2.40 采用2.39题给定的条件和存储结构，编写求P新辟的空间中，并分析你的算法的时间复杂度。

2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。

2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。

?x??Pn1?x??Pn2?x?的算法，将结果多项式存放在

第3章 栈和队列

3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：

(1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？

(2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列）。

3.2 简述栈和线性表的差别。

3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。

void main() { }

Stack S; char x,y; InitStack(S); x= ‘c’; y= ‘k’;

Push(S,x); Push(S, ‘a’); Pop(S,x); Push(S, ‘t’); Pop(S,x); Push(S, ‘s’);

while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x);

Push(S,y); Push(S,x);

3.4 简述以下算法的功能（栈的元素类型SElemType为int）。

(1) status algo1(Stack S) {

3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。

3.6 试证明：若借助栈由输入序列12…n得到的输出序列为输出序列中不可能出现这样的情形：存在着i

} { }

Stack T; int d; InitStack(T);

while(!StackEmpty(S)){ }

while(!StackEmpty(T)){ }

Pop(T,d); Push(S,d); Pop(S,d);

if(d!=e) Push(T,d); int i,n,A[255]; n=0;

while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i<=n;i++) Push(S,A[i]);

(2) status algo2(Stack S,int e)

p1p2?pn(它是输入序列的一个排列)，则在

pj

3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：

3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。

3.9 试将下列递推过程改写为递归过程。

3.10 试将下列递归过程改写为非递归过程。

3.11 简述队列和堆栈这两种数据类型的相同点和差异处。

3.12 写出以下程序段的输出结果（队列中的元素类型QElemType为char）。

void main() {

Queue Q; InitQueue(Q); char x= ‘e’, y= ‘c’; EnQueue(Q, ‘h’); EnQueue(Q, ‘r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ‘a’); void test(int &sum) { }

int x; cin>>x; if(x==0) sum=0; else { }

cout<

test(sum); sum+=x;

void ditui(int n) { }

int i; i = n; while(i>1)

cout<

A-B×C/D+E↑F