数据结构习题集答案

第1章 绪论

1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中

D??d1,d2,d3,d4?，R??r?，r?试按图论中图的画法惯例画出其逻辑结构图。

解：

??d1,d2?,?d2,d3?,?d3,d4??

1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：

ADT Complex{

数据对象：D={r,i|r,i为实数} 数据关系：R={} 基本操作：

InitComplex(&C,re,im)

操作结果：构造一个复数C，其实部和虚部分别为re和im DestroyCmoplex(&C)

操作结果：销毁复数C

Get(C,k,&e)

操作结果：用e返回复数C的第k元的值 操作结果：改变复数C的第k元的值为e Put(&C,k,e)

IsAscending(C)

操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0

IsDescending(C)

操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 操作结果：用e返回复数C的两个元素中值较大的一个

Max(C,&e) Min(C,&e)

操作结果：用e返回复数C的两个元素中值较小的一个

}ADT Complex

ADT RationalNumber{

数据对象：D={s,m|s,m为自然数，且m不为0} 数据关系：R={} 基本操作：

InitRationalNumber(&R,s,m)

操作结果：构造一个有理数R，其分子和分母分别为s和m DestroyRationalNumber(&R)

操作结果：销毁有理数R

Get(R,k,&e)

操作结果：用e返回有理数R的第k元的值 操作结果：改变有理数R的第k元的值为e Put(&R,k,e)

IsAscending(R)

操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0

IsDescending(R) Max(R,&e)

操作结果：用e返回有理数R的两个元素中值较大的一个

Min(R,&e)

操作结果：用e返回有理数R的两个元素中值较小的一个

}ADT RationalNumber

1.5 试画出与下列程序段等价的框图。

(1) product=1; i=1; while(i<=n){ product *= i; i++; } (2) i=0; do { i++;

} while((i!=n) && (a[i]!=x)); (3) switch {

case x

1.6 在程序设计中，常用下列三种不同的出错处理方式：

(1) 用exit语句终止执行并报告错误； (2) 以函数的返回值区别正确返回或错误返回；

(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。

解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。 (2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。 (3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。 1.7 在程序设计中，可采用下列三种方法实现输出和输入：

(1) 通过scanf和printf语句； (2) 通过函数的参数显式传递； (3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。

解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。

(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。

(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。

1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：

(1) i=1; k=0; while(i<=n-1){ @ k += 10*i; i++; }

(2) i=1; k=0; do {

@ k += 10*i; i++; } while(i<=n-1); (3) i=1; k=0; while (i<=n-1) { i++;

@ k += 10*i; } (4) k=0;

for(i=1; i<=n; i++) { for(j=i; j<=n; j++) @ k++; }

(5) for(i=1; i<=n; i++) { for(j=1; j<=i; j++) { for(k=1; k<=j; k++) @ x += delta; }

(6) i=1; j=0; while(i+j<=n) { @ if(i>j) j++;

else i++; }

(7) x=n; y=0; // n是不小于1的常数 while(x>=(y+1)*(y+1)) { @ y++; }

(8) x=91; y=100; while(y>0) {

@ if(x>100) { x -= 10; y--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1

(4) n+(n-1)+(n-2)+...+1=

n(n?1)2

n (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=

?i?1ni(i?1)21n

=

1ni(i?1)??(i?22i?1i?11n2?i)?1i?2i?12?i ?2i?1 =

112n(n?1)(2n?1)?14n(n?1)?112n(n?1)(2n?3)

(6) n (7)

?n? 向下取整

(8) 1100

1.9 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。

int Time(int n) {

} 解：o(logcount=log2count = 0; x=2;

while(x

return count;

x *= 2; count++;

n) n?2

21.11 已知有实现同一功能的两个算法，其时间复杂度分别为O2

??和O?n?，假设现实计算机可连续

n10

运算的时间为10秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）10次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。

解：2n75?101012

12n=40

n?10 n=16

则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模下，第一种算法更适宜。 1.12 设有以下三个函数： f?n??21n4?n?1000，g?n??15n?500n，h?n??500n2433.5?nlogn

请判断以下断言正确与否：

(1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n) (5) h(n)是O(nlogn)

解：(1)对 (2)错 (3)错 (4)对 (5)错 1.13 试设定若干n值，比较两函数n和50nlog大于50nlog223.5

2n的增长趋势，并确定n在什么范围内，函数n的值

22n的值。

n的值较大。

解：n的增长趋势快。但在n较小的时候，50nlog

当n>438时，n22?50nlog2n

1.14 判断下列各对函数f?n?和g?n?，当n??时，哪个函数增长更快？

(1) f?n??10n2?lnn!?102?n3?，g?n??2n2.54?n?7

(2) f?n???ln?n!??5?，g?n??13n(3) f?n??n(4) f?n??22.1

2?n?1，g?n???ln?n!???n

4n?n?3??2?2，g?n??n?n?2?n

5解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明：

n(1)

?ii?1n2?n?n?1??2n?1?/6 ?n?0?

(2)

?xi?0i?x?n?1?1/?x?1?

?

?x?1,n?0?

n(3)

?2i?1ni?1n?2?1

?n?1? ?n?1?

(4)

??2i?1??ni?12

1.16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值

解：

int max3(int x,int y,int z) { }

1.17 已知k阶斐波那契序列的定义为

if(x>y)

if(x>z) return x; else return z; if(y>z) return y; else return z;

else

f0?0，f1?0，…，fk?2?0，fk?1?1； fn?fn?1?fn?2???fn?k，n?k,k?1,?

试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

解：k>0为阶数，n为数列的第n项 int Fibonacci(int k,int n) { }

1.18 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为

if(k<1) exit(OVERFLOW); int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j;

for(i=0;i

}

for(i=k+1;i

return p[k];

x=p[0];

for(j=0;j

项目名称 解：

typedef enum{A,B,C,D,E} SchoolName; typedef enum{Female,Male} SexType; typedef struct{

char event[3]; //项目 SexType sex; SchoolName school; int score;

性别 校名 成绩 得分 编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

} Component; typedef struct{

int MaleSum;

//男团总分

int FemaleSum; //女团总分 int TotalSum; //团体总分

} Sum;

Sum SumScore(SchoolName sn,Component a[],int n) { }

1.19 试编写算法，计算i!*2的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个k?1?k?n?，使k!?2应按出错处理。注意选择你认为较好的出错处理方法。

解：

#include #include #define MAXINT 65535 #define ArrSize 100 int fun(int i);

int main()

kiSum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i;

for(i=0;i

temp.TotalSum=temp.MaleSum+temp.FemaleSum; return temp;

if(a[i].school==sn){ }

if(a[i].sex==Male) temp.MaleSum+=a[i].score; if(a[i].sex==Female) temp.FemaleSum+=a[i].score;

?maxint时，

{ }

1.20 试编写算法求一元多项式的值Pn?x??nint i,k; int a[ArrSize]; cout<<\cin>>k;

if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ }

for(i=0;i<=k;i++){ }

return 0;

if(a[i]>MAXINT) exit(0); else cout<

if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1];

?ai?0iix的值Pn?x0?，并确定算法中每一语句的执行次数

和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai?i?0,1,?,n?，x0和n，输出为Pn?x0?。

解：

#include #include #define N 10

double polynomail(int a[],int i,double x,int n); int main() {

double x;

int n,i; int a[N];

cout<<\输入变量的值x:\cin>>x;

cout<<\输入多项式的阶次n:\cin>>n;

if(n>N-1) exit(0);

cout<<\输入多项式的系数a[0]--a[n]:\for(i=0;i<=n;i++) cin>>a[i];

cout<<\

}

return 0;

double polynomail(int a[],int i,double x,int n) { }

本算法的时间复杂度为o(n)。

if(i>0) return a[n-i]+polynomail(a,i-1,x,n)*x; else return a[n];

第2章 线性表

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：

2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); for(i=1;i<=4;i++){ }

P->next=NULL;

for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解：

P->next=(LinkList)malloc(sizeof(LNode)); P=P->next;

P->data=i*2-1;

P=L;

2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

b. 在P结点前插入S结点的语句序列是__________________。 c. 在表首插入S结点的语句序列是__________________。 d. 在表尾插入S结点的语句序列是__________________。 (1) P->next=S;

(2) P->next=P->next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P;

(8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P; 解：a. (4) (1)

b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6)

2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 删除P结点的直接后继结点的语句序列是____________________。 b. 删除P结点的直接前驱结点的语句序列是____________________。 c. 删除P结点的语句序列是____________________。 d. 删除首元结点的语句序列是____________________。

e. 删除尾元结点的语句序列是____________________。 (1) P=P->next; (2) P->next=P;

(3) P->next=P->next->next; (4) P=P->next->next;

(5) while(P!=NULL) P=P->next;

(6) while(Q->next!=NULL) { P=Q; Q=Q->next; } (7) while(P->next!=Q) P=P->next; (8) while(P->next->next!=Q) P=P->next; (9) while(P->next->next!=NULL) P=P->next; (10) Q=P; (11) Q=P->next; (12) P=L; (13) L=L->next; (14) free(Q); 解：a. (11) (3) (14)

b. (10) (12) (8) (3) (14) c. (10) (12) (7) (3) (14)

d. (12) (11) (3) (14) e. (9) (11) (3) (14)

2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是_______________________。 b. 在P结点前插入S结点的语句序列是_______________________。 c. 删除P结点的直接后继结点的语句序列是_______________________。 d. 删除P结点的直接前驱结点的语句序列是_______________________。 e. 删除P结点的语句序列是_______________________。 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P; (6) S->priou=P; (7) S->next=P->next; (8) S->priou=P->priou; (9) P->priou->next=P->next; (10) P->priou->next=P; (11) P->next->priou=P; (12) P->next->priou=S; (13) P->priou->next=S; (14) P->next->priou=P->priou; (15) Q=P->next; (16) Q=P->priou; (17) free(P); (18) free(Q);

解：a. (7) (3) (6) (12)

b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17)

2.9 简述以下算法的功能。

(1) Status A(LinkedList L) { //L是无表头结点的单链表

}

if(L && L->next) { }

return OK;

Q=L;

L=L->next;

P=L;

while(P->next) P=P->next; P->next=Q;

Q->next=NULL;

(2) void BB(LNode *s, LNode *q) {

p=s;

while(p->next!=q) p=p->next; p->next =s;

}

void AA(LNode *pa, LNode *pb) { }

解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。

//pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa);

(2) 将单循环链表拆成两个单循环链表。

2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList &a,int i,int k) {

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法 else {

for(count=1;count

} 解：

Status DeleteK(SqList &a,int i,int k) { }

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

解：

Status InsertOrderList(SqList &va,ElemType x) {

//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;

if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0,x

va.elem[i]=va.elem[i-1]; va.elem[i]=x;

//从顺序存储结构的线性表a中删除第i个元素起的k个元素 //注意i的编号从0开始 int j;

if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j++)

a.elem[j+i]=a.elem[j+i+k];

}

//删除第一个元素

for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--;

return OK;

a.length=a.length-k; return OK;

}

va.length++; return OK;

2.12 设A??a1,?,am?和B??b1,?,bn?均为顺序表，A?和B?分别为A和B中除去最大共同前缀后的子表。若A??B??空表，则A?B；若A?=空表，而B??空表，或者两者均不为空表，且A?的首元小于B?的首元，则A?B；否则A?B。试写一个比较A，B大小的算法。

解：

Status CompareOrderList(SqList &A,SqList &B) { }

2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);

解：

int LocateElem_L(LinkList &L,ElemType x) { }

2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。

解：

//返回单链表的长度

int ListLength_L(LinkList &L) {

int i=0; LinkList p=L; if(p) p=p-next; while(p){

p=p->next; int i=0; LinkList p=L;

while(p&&p->data!=x){ }

if(!p) return 0; else return i;

p=p->next; i++; int i,k,j;

k=A.length>B.length?A.length:B.length; for(i=0;i

if(A.length>k) j=1; if(B.length>k) j=-1; if(A.length==B.length) j=0; return j;

if(A.elem[i]>B.elem[i]) j=1; if(A.elem[i]

}

}

i++;

return i;

2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

解：

void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) { }

2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) { } 解：

Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)

if(i<0||j<0||len<0) return INFEASIBLE; p=la;

k=1;

p=p->next;

k++; }

while(k

while(k<=len){ q=q->next; s=lb; k=1; while(knext=p; return OK;

s=s->next;

k++; }

q->next=s->next;

k++; }

LinkList pa,pb; pa=ha; pb=hb;

while(pa->next&&pb->next){ }

if(!pa->next){ } else{ }

hc=ha;

while(pa->next) pa=pa->next; pa->next=hb->next; hc=hb;

while(pb->next) pb=pb->next; pb->next=ha->next; pa=pa->next; pb=pb->next;

{ }

LinkList pa,pb,qa,qb,pt; pa=A; pb=B; qa=pa; qb=pb;

// 保存pa的前驱指针 // 保存pb的前驱指针

pa=pa->next; pb=pb->next; C=A;

while(pa&&pb){ }

while(pa){ }

while(pb){ } pb=B; free(pb); return OK;

pt=pb; pb=pb->next; qb->next=pb; free(pt); pt=pa; pa=pa->next; qa->next=pa; free(pt);

if(pa->datadata){ } else

if(pa->data>pb->data){ } else{ }

qa=pa; pa=pa->next; pt=pb; pb=pb->next; qb->next=pb; free(pt); pt=pa; pa=pa->next; qa->next=pa; free(pt);

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

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

// A、B求交，然后删除相同元素，将结果放在C表中

Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C) { } (2)

// A、B求交，然后删除相同元素，将结果放在A表中 Status ListCrossDelSame_Sq(SqList &A,SqList &B) {

int i=0,j=0,k=0;

while(i

if(A.elem[i]

if(A.elem[i]>B.elem[j]) j++; else{

if(k==0){ } else

if(A.elem[k]!=A.elem[i]){ A.elem[k]=A.elem[i]; k++;

int i=0,j=0,k=0;

while(i

return OK;

if(A.elem[i]

if(A.elem[i]>B.elem[j]) j++; else{ }

if(C.length==0){ } else

if(C.elem[C.length-1]!=A.elem[i]){ }

ListInsert_Sq(C,k,A.elem[i]); k++;

ListInsert_Sq(C,k,A.elem[i]); k++;

i++;

}

}

}

}

A.elem[k]=A.elem[i]; k++;

i++;

A.length=k; return OK;

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

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

(1)

// A、B求交，结果放在C表中，并删除相同元素

Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkList &C) {

LinkList pa,pb,qa,qb,pt; pa=A; pb=B; qa=pa; qb=pb;

// 保存pa的前驱指针 // 保存pb的前驱指针

pa=pa->next; pb=pb->next; C=A;

while(pa&&pb){

if(pa->datadata){ } else

if(pa->data>pb->data){ } else{

if(pa->data==qa->data){

pt=pa; pa=pa->next; qa->next=pa; pt=pb; pb=pb->next; qb->next=pb; free(pt); pt=pa; pa=pa->next; qa->next=pa; free(pt);

} (2)

}

}

}

free(pt);

else{ }

qa=pa; pa=pa->next;

while(pa){ }

while(pb){ } pb=B; free(pb); return OK;

pt=pb; pb=pb->next; qb->next=pb; free(pt); pt=pa; pa=pa->next; qa->next=pa; free(pt);

// A、B求交，结果放在A表中，并删除相同元素 Status ListCrossDelSame_L(LinkList &A,LinkList &B) {

LinkList pa,pb,qa,qb,pt; pa=A; pb=B; qa=pa; qb=pb;

// 保存pa的前驱指针 // 保存pb的前驱指针

pa=pa->next; pb=pb->next; while(pa&&pb){

if(pa->datadata){ } else

if(pa->data>pb->data){ pt=pa; pa=pa->next; qa->next=pa; free(pt);

}

}

}

pt=pb; pb=pb->next; qb->next=pb; free(pt);

else{ }

if(pa->data==qa->data){ } else{ }

qa=pa; pa=pa->next; pt=pa; pa=pa->next; qa->next=pa; free(pt);

while(pa){ }

while(pb){ } pb=B; free(pb); return OK;

pt=pb; pb=pb->next; qb->next=pb; free(pt); pt=pa; pa=pa->next; qa->next=pa; free(pt);

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

解：

// 在A中删除既在B中出现又在C中出现的元素，结果放在D中 Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C) {

SqList Temp; InitList_Sq(Temp); ListCross_L(B,C,Temp);

}

ListMinus_L(A,Temp,D);

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

解：

// 在A中删除既在B中出现又在C中出现的元素，并释放B、C Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C) { }

// 求集合A-B，结果放在A表中，并删除B表 Status ListMinus_L(LinkList &A,LinkList &B) {

LinkList pa,pb,qa,qb,pt; pa=A; pb=B; qa=pa; qb=pb;

// 保存pa的前驱指针 // 保存pb的前驱指针

ListCross_L(B,C); ListMinus_L(A,B);

pa=pa->next; pb=pb->next; while(pa&&pb){ }

while(pb){

pt=pb; pb=pb->next; qb->next=pb; free(pt);

if(pb->datadata){ } else

if(pb->data>pa->data){ } else{ }

pt=pa; pa=pa->next; qa->next=pa; free(pt); qa=pa; pa=pa->next; pt=pb; pb=pb->next; qb->next=pb; free(pt);

}

} pb=B; free(pb); return OK;

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

解：

// 在单循环链表S中删除S的前驱结点 Status ListDelete_CL(LinkList &S) { }

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

解：

// 建立一个空的循环链表

Status InitList_DL(DuLinkList &L) { }

// 向循环链表中插入一个结点

Status ListInsert_DL(DuLinkList &L,ElemType e) {

DuLinkList p;

p=(DuLinkList)malloc(sizeof(DuLNode)); if(!p) return ERROR; p->data=e; p->next=L->next;

L=(DuLinkList)malloc(sizeof(DuLNode)); if(!L) exit(OVERFLOW); L->pre=NULL; L->next=L; return OK; LinkList p,q;

if(S==S->next)return ERROR; q=S; p=S->next;

while(p->next!=S){ }

q->next=p->next; free(p); return OK;

q=p; p=p->next;

}

L->next=p; return OK;

// 将单循环链表改成双向链表 Status ListCirToDu(DuLinkList &L) { }

DuLinkList p,q; q=L; p=L->next; while(p!=L){ }

if(p==L) p->pre=q; return OK;

p->pre=q; q=p; p=p->next;

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

解：

// 将单链表L划分成3个单循环链表

Status ListDivideInto3CL(LinkList &L,LinkList &s1,LinkList &s2,LinkList &s3) {

LinkList p,q,pt1,pt2,pt3; p=L->next; pt1=s1; pt2=s2; pt3=s3; while(p){

if(p->data>='0' && p->data<='9'){ } else

if((p->data>='A' && p->data<='Z') ||

(p->data>='a' && p->data<='z')){ q=p; p=p->next;

q->next=pt2->next; pt2->next=q; pt2=pt2->next; q=p; p=p->next;

q->next=pt1->next; pt1->next=q; pt1=pt1->next;

}

}

} else{ }

q=p; p=p->next;

q->next=pt3->next; pt3->next=q; pt3=pt3->next;

q=L; free(q); return OK;

在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为： typedef struct

char data; struct

XorNode *LRPtr;

//无头结点的异或指针双向链表

//分别指向链表的左侧和右端

XorNode {

} XorNode, *XorPointer; typede

struct { XorPointer

Left, Right;

} XorLinkedList;

XorPointer XorP(XorPointer p, XorPointer q); // 指针异或函数XorP返回指针p和q的异或值

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指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。

解：

Status TraversingLinkList(XorLinkedList &L,char d) {

XorPointer p,left,right; if(d=='l'||d=='L'){ }

p=L.Left; left=NULL; while(p!=NULL){ }

VisitingData(p->data); left=p;

p=XorP(left,p->LRPtr);

}

else

if(d=='r'||d=='R'){ }

else return ERROR;

p=L.Right; right=NULL; while(p!=NULL){ }

VisitingData(p->data); right=p;

p=XorP(p->LRPtr,right);

return OK;

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

2.37 设以带头结点的双向循环链表表示的线性表L??a1,a2,?,an?。试写一时间复杂度O(n)的算法，将L改造为L??a1,a3,?,an,?,a4,a2?。

解：

// 将双向链表L=(a1,a2,...,an)改造为(a1,a3,...,an,...,a2) Status ListChange_DuL(DuLinkList &L) {

int i;

DuLinkList p,q,r; p=L->next; r=L->pre; i=1;

while(p!=r){ }

if(i%2==0){ }

else p=p->next; i++;

q=p; p=p->next; // 删除结点

q->pre->next=q->next; q->next->pre=q->pre; // 插入到头结点的左面 q->pre=r->next->pre; r->next->pre=q; q->next=r->next; r->next=q;

}

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

Push(S, ‘a’); Push(S,y);

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

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

解：stack

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

(1) status algo1(Stack S) {

}

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)

{ }

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);

解：(1) 栈中的数据元素逆置 (2) 如果栈中存在元素e，将其从栈中清除

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

解：任何前n个序列中S的个数一定大于X的个数。 设两个合法序列为： T1=S??X??S??

T2=S??X??X??

假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。

第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b

压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为??ba??，而T2的输出顺序为??ab??，说明两个不同的合法栈操作序列的输出元素的序列一定不同。

3.6 试证明：若借助栈由输入序列12…n得到的输出序列为p1p2?pn(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i

解：这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若pj

3.1题。所以不可能存在着i

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

A-B×C/D+E↑F

主要操作 PUSH(OPND,A) PUSH(OPTR,-) PUSH(OPND,B) PUSH(OPTR,*) PUSH(OPND,C) Operate(B,*,C) PUSH(OPTR,/) PUSH(OPND,D) Operate(G,/,D) Operate(A,-,H) PUSH(OPTR,+) PUSH(OPND,E) PUSH(OPTR,^) PUSH(OPND,F) Operate(E,^,F) Operate(I,+,J) RETURN 解：BC=G G/D=H A-H=I E^F=J I+J=K 步骤 OPTR栈 OPND栈 输入字符 1 # A-B*C/D+E^F# 2 # A -B*C/D+E^F# 3 #- A B*C/D+E^F# 4 #- A B *C/D+E^F# 5 #-* A B C/D+E^F# 6 #-* A B C /D+E^F# 7 #- A G /D+E^F# 8 #-/ A G D+E^F# 9 #-/ A G D +E^F# 10 #- A H +E^F# 11 # I +E^F# 12 #+ I E^F# 13 #+ I E ^F# 14 #+^ I E F# 15 #+^ I E F # 16 #+ I J # 17 # K # 3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。

解：2n?1

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

void ditui(int n) { } 解：

void ditui(int j)

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

cout<

{ }

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

void test(int &sum) { } 解：

void test(int &sum) { }

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

解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。

队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。 3.12 写出以下程序段的输出结果（队列中的元素类型QElemType为char）。

void main() {

Queue Q; Stack s; InitStack(s); int x; do{

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

cout<

test(sum); sum+=x; if(j>1){ } return;

cout<

}while(x>0);

while(!StackEmpty(s)){ }

DestoryStack(s);

Pop(s,x); sum+=x;

cout<

}

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’); While(!QueueEmpty(Q)) { } cout<

DeQueue(Q,y); cout<

解：char

3.13 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q)

{ }

解：队列逆置

3.14 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列： (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。 (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。 (3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。

3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。

解：

Stack S; int d; InitStack(S);

while(!QueueEmpty(Q)) { }

while(!StackEmpty(S)) { }

Pop(S, d); EnQueue(Q, d); DeQueue(Q, d); Push(S, d);

class DStack{

ElemType *top[2]; ElemType *p; int stacksize; int di; public:

DStack(int m) { };

// 链栈的数据结构及方法的定义 typedef struct NodeType{

ElemType data; }

~DStack(){delete p;} void Push(int i,ElemType x) { }

ElemType Pop(int i) { }

di=i; if(di==0){ }

return OK;

if(top[0]

if(top[1]>top[0]) return *top[1]--; else cerr<<\di=i; if(di==0){ } else{ }

if(top[1]=p) *top[0]--=x; else cerr<<\p=new ElemType[m]; if(!p) exit(OVERFLOW); top[0]=p+m/2; top[1]=top[0]; stacksize=m;

}else{

NodeType *next;

}NodeType,*LinkType; typedef struct{

LinkType top; int size;

}Stack;

void InitStack(Stack &s) { }

void DestroyStack(Stack &s) { }

void ClearStack(Stack &s) { }

int StackLength(Stack s) { }

Status StackEmpty(Stack s) {

if(s.size==0) return TRUE; else return FALSE; return s.size; LinkType p; while(s.top){ }

p=s.top; s.top=p->next; delete p; s.size--; LinkType p; while(s.top){ }

p=s.top; s.top=p->next; delete p; s.size--; s.top=NULL; s.size=0;

}

Status GetTop(Stack s,ElemType &e) { }

Status Push(Stack &s,ElemType e) { }

Status Pop(Stack &s,ElemType &e) { }

// 从栈顶到栈底用Visit()函数遍历栈中每个数据元素 void StackTraverse(Stack s,Status (*Visit)(ElemType e)) { }

3.16 假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到

LinkType p; p=s.top;

while(p) Visit(p->data); LinkType p; if(s.top){ }

return OK;

e=s.top->data; p=s.top; s.top=p->next; delete p; s.size--; LinkType p; p=new NodeType; if(!p) exit(OVERFLOW); p->next=s.top; s.top=p; p->data=e; s.size++; return OK;

if(!s.top) return ERROR; else{ }

e=s.top->data; return OK;

硬席车厢之前。

解： int main() { }

3.17 试写一个算法，识别一次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

解：

BOOL Symmetry(char a[]) {

int i=0; Stack s; InitStack(s); ElemType x;

while(a[i]!='&' && a[i]){ }

if(a[i]) return FALSE; i++;

while(a[i]){

Pop(s,x); Push(s,a[i]); i++; Stack s;

char Buffer[80]; int i=0,j=0; InitStack(s);

cout<<\请输入硬席(H)和软席车厢(S)序列：\cin>>Buffer; cout<

while(Buffer[j]){ }

cout<

Pop(s,Buffer[j]); j++;

if(Buffer[i]=='S'){ }

else Push(s,Buffer[i]); i++;

Buffer[j]=Buffer[i]; j++;

}

}

if(x!=a[i]){ } i++;

DestroyStack(s); return FALSE;

return TRUE;

3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。

解：

BOOL BracketCorrespondency(char a[]) { }

3.20 假设以二维数组g(1…m, 1…n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点

int i=0; Stack s; InitStack(s); ElemType x; while(a[i]){ }

if(s.size!=0) return FALSE; return TRUE;

switch(a[i]){ case '(':

Push(s,a[i]); break;

case '[':

Push(s,a[i]); break;

case ')':

GetTop(s,x); if(x=='(') break;

Pop(s,x);

else return FALSE;

case ']':

GetTop(s,x);

if(x=='[') Pop(s,x); else return FALSE; break;

default: } i++;

break;

为同色区域的点。

解：

#include #include

typedef struct{

int x; int y;

}PosType; typedef struct{

#include \

#define M 8 #define N 8

ElemType g[M][N];

void CreateGDS(ElemType g[M][N]); void ShowGraphArray(ElemType g[M][N]);

void RegionFilling(ElemType g[M][N],PosType CurPos,int NewColor);

int main() { }

void RegionFilling(ElemType g[M][N],PosType CurPos,int FillColor) {

Stack s;

PosType StartPos; StartPos.x=5; StartPos.y=5; int FillColor=6;

RegionFilling(g,StartPos,FillColor); cout<

}ElemType;

}

InitStack(s); ElemType e;

int OldColor=g[CurPos.x][CurPos.y].Color;

Push(s,g[CurPos.x][CurPos.y]); while(!StackEmpty(s)){

Pop(s,e); CurPos=e.seat;

g[CurPos.x][CurPos.y].Color=FillColor; g[CurPos.x][CurPos.y].Visited=1;

}

if(CurPos.x

Push(s,g[CurPos.x+1][CurPos.y]);

!g[CurPos.x+1][CurPos.y].Visited && g[CurPos.x+1][CurPos.y].Color==OldColor

if(CurPos.x>0 && )

Push(s,g[CurPos.x-1][CurPos.y]); !g[CurPos.x-1][CurPos.y].Visited && g[CurPos.x-1][CurPos.y].Color==OldColor

if(CurPos.y

Push(s,g[CurPos.x][CurPos.y+1]); !g[CurPos.x][CurPos.y+1].Visited && g[CurPos.x][CurPos.y+1].Color==OldColor

if(CurPos.y>0 && )

Push(s,g[CurPos.x][CurPos.y-1]); !g[CurPos.x][CurPos.y-1].Visited && g[CurPos.x][CurPos.y-1].Color==OldColor

void CreateGDS(ElemType g[M][N]) {

int i,j;

for(i=0;i

for(j=0;j

g[i][j].seat.x=i; g[i][j].seat.y=j; g[i][j].Visited=0; g[i][j].Color=0;

}

for(i=2;i<5;i++)

for(j=2;j<4;j++)

g[i][j].Color=3;

for(i=5;i

for(j=3;j<6;j++)

g[i][j].Color=3;

void ShowGraphArray(ElemType g[M][N]) { }

3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。

解：

// 输入的表达式串必须为#...#格式

void InversePolandExpression(char Buffer[]) {

Push(s,Buffer[i]); i++;

while(Buffer[i]!='#'){

if(!IsOperator(Buffer[i])){ // 是操作数 } else{

// 是操作符 Buffer[j]=Buffer[i]; i++; j++;

Stack s; InitStack(s); int i=0,j=0; ElemType e; int i,j;

for(i=0;i

for(j=0;j

cout<

GetTop(s,e);

if(Prior(e,Buffer[i])){// 当栈顶优先权高于当前序列时，退栈 } else{

Pop(s,e); Buffer[j]=e; j++;

}

}

}

}

Push(s,Buffer[i]); i++;

while(!StackEmpty(s)){ }

Pop(s,e); Buffer[j]=e; j++;

Status IsOpertor(char c) { }

Status Prior(char c1,char c2) { }

3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。

解：

char CalVal_InverPoland(char Buffer[]) {

Stack Opnd; InitStack(Opnd); int i=0; char c;

char ch[]=\int i=0,j=0;

while(ch[i] && ch[i]!=c1) i++;

if(i==2) i--; // 加和减可认为是同级别的运算符 if(i==4) i--; // 乘和除可认为是同级别的运算符 while(ch[j] && ch[j]!=c2) j++; if(j==2) j--; if(j==4) j--;

if(i>=j) return TRUE; else return FALSE; char *p=\while(*p){ }

return FALSE;

if(*p==c)

return TRUE; p++;

}

ElemType e1,e2;

while(Buffer[i]!='#'){ }

return c;

if(!IsOperator(Buffer[i])){ } else{ } i++;

Pop(Opnd,e2); Pop(Opnd,e1);

c=Cal(e1,Buffer[i],e2); Push(Opnd,c);

Push(Opnd,Buffer[i]);

char Cal(char c1,char op,char c2) {

ch[0]=c2; ch[1]='\\0'; x2=atoi(ch);

switch(op){ case '+':

x=x1+x2; break; x=x1-x2; break; int x,x1,x2; char ch[10]; ch[0]=c1; ch[1]='\\0'; x1=atoi(ch);

case '-':

case '*':

x=x1*x2; break;

case '/':

x=x1/x2; break; break;

default:

}

}

itoa(x,ch,10); return ch[0];

3.23 如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。

解：

#include #include #include

#include \

typedef char ARRAY[30]; typedef ARRAY ElemType; typedef struct NodeType{

ElemType data; NodeType *next;

}NodeType,*LinkType; typedef struct{

LinkType top; int size;

}Stack;

void InitStack(Stack &s);

Status Push(Stack &s,ElemType e); Status Pop(Stack &s,ElemType e); Status IsOperator(char c); Status StackEmpty(Stack s);

Status InvToFroPoland(char a[]);

int main() { }

Status InvToFroPoland(char a[]) {

Stack s; char a[30];

cout<<\请输入逆波兰算术表达式字符序列：\cin>>a;

if(InvToFroPoland(a)) cout<

else cout<<\输入逆波兰算术表达式字符序列错误!\return 0;

本文来源：https://www.bwwdw.com/article/yw4r.html