数据结构习题集答案（C语言严版）

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

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

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

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

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

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

操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0 操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0 操作结果：用e返回复数C的两个元素中值较大的一个 操作结果：用e返回复数C的两个元素中值较小的一个 Put(&C,k,e) IsAscending(C) IsDescending(C) Max(C,&e) Min(C,&e)

}ADT Complex

数据对象：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元的值

ADT RationalNumber{

Put(&R,k,e)

操作结果：改变有理数R的第k元的值为e

操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0 操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0 操作结果：用e返回有理数R的两个元素中值较大的一个 操作结果：用e返回有理数R的两个元素中值较小的一个 IsAscending(R) IsDescending(R) Max(R,&e) Min(R,&e)

}ADT RationalNumber

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

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

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

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

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

2 (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= =1n?i?1ni(i?1)2

1n1n21n 2(i?i)??i??i?i(i?1)?2?2i?12i?12i?1i?1 =

111n(n?1)(2n?1)?n(n?1)?n(n?1)(2n?3) 12412 (6) n (7)

?n? 向下取整

n) count=log2n?2

n=40 n=16

(8) 1100 1.9 解：o(log21.11 解：2 nn?1012 ?1012

10 则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模 下，第一种算法更适宜。 1.12 解：(1)对 (2)错 (3)错 (4)对 (5)错

1.13 解：n的增长趋势快。但在n较小的时候，50nlog22n的值较大。

当n>438时，n2?50nlog2n

1.14 解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快

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

解：

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

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

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

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

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

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

else

} Component; typedef struct{

int MaleSum;

//男团总分

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

} Sum;

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

#include #include #define MAXINT 65535 #define ArrSize 100 int fun(int i); int main() { } 1.20 解：

#include #include

int 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];

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

#define N 10

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

double x; }

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

本算法的时间复杂度为o(n)。 第2章 线性表

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

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

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位if(i>0) return a[n-i]+polynomail(a,i-1,x,n)*x; else return a[n]; 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;

置有关。

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

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

} 3.31 解：

Status SymmetryString(char* p) { } 3.32解：

int Fibonacci(int k,int n) {

if(k<1) exit(OVERFLOW); Queue q; InitQueue(q,k); ElemType x,e; int i=0; while(i<=n){ }

return q.base[(q.rear+q.MaxSize-1)%q.MaxSize];

if(i

if(i==k-1){ }

if(i>=k){ } i++;

// 队列求和 x=sum(q); DeQueue(q,e); EnQueue(q,x);

if(!EnQueue(q,1)) exit(OVERFLOW); if(!EnQueue(q,0)) exit(OVERFLOW);

Queue q;

if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ }

while(!StackEmpty(s)){ }

return OK;

Pop(s,e1); DeQueue(q,e2);

if(e1!=e2) return FALSE; Push(s,*p); EnQueue(q,*p); p++; return OK;

} 3.33 解：

// Filename:Queue.h typedef struct{

ElemType *base; int front; int rear; Status tag; int MaxSize;

}DQueue;

Status InitDQueue(DQueue& q,int size) { }

Status EnDQueue(DQueue& q,ElemType e) { }

Status DeDQueue(DQueue& q,ElemType& e) {

if(q.front==q.rear&&!q.tag)return FALSE; if(q.front==q.rear&&q.tag) return FALSE; if(q.front==q.rear&&!q.tag){ // 空队列 }

else{ // 非空非满 }

return OK;

if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){ }

else{ // 从队尾入队 }

q.base[q.rear]=e;

q.rear=(q.rear+1)%q.MaxSize; if(q.rear==q.front)q.tag=1; // 从队头入队

q.front=(q.front+q.MaxSize-1)%q.MaxSize; q.base[q.front]=e;

if(q.rear==q.front)q.tag=1; q.base[q.rear]=e;

q.rear=(q.rear+1)%q.MaxSize; if(q.rear==q.front)q.tag=1; q.MaxSize=size;

q.base=new ElemType[q.MaxSize]; if(!q.base) return FALSE; q.front=0; q.rear=0; q.tag=0; return OK;

}

// Filename:XT333.cpp 主程序文件 #include #include typedef int ElemType; #include \

int main() { } 3.34 解： int main() {

ElemType e; DQueue dq; InitDQueue(dq,20); char ch[20];

cout<<\请输入待调度的车厢字符序列(仅限PHS)：\cin>>ch; int i=0; while(ch[i]){

if(ch[i]=='P') cout<

if(ch[i]=='S') EnDQueue(dq,ch[i],0);// 从队头入队 if(ch[i]=='H') EnDQueue(dq,ch[i],1);// 从队尾入队 i++; int t1,t2,t3,t4; ElemType e;

cout<<\请输入作业a1、a2、a3、a4的执行时间: \cin>>t1>>t2>>t3>>t4; DQueue dq; InitDQueue(dq,5); EnDQueue(dq,t1); EnDQueue(dq,t2); EnDQueue(dq,t3); EnDQueue(dq,t4);

while(dq.front!=dq.rear||dq.tag){ } return 0;

DeDQueue(dq,e); cout<

return OK;

e=q.base[q.front];

q.front=(q.front+1)%q.MaxSize; q.tag=0;

}

}

while(dq.front!=dq.rear||dq.tag){ }

cout<

DeDQueue(dq,e); cout<

第5章 数组与广义表 5.1 解：

(1) 6×8×6=288 Byte

(2) LOC(5,7)=1000+(5×8+7)×6=1282 (3) LOC(1,4)=1000+(1×8+4)×6=1072 (4) LOC(4,7)=1000+(7×6+4)×6=1276 5.2 解：

(1) LOC(0,0,0,0)=100

(2) LOC(1,1,1,1)=100+(1×3×5×8 + 1×5×8 + 1×8 + 1)×4=776 (3) LOC(3,1,2,5)=100+(3×3×5×8 + 1×5×8 + 2×8 + 5)×4=1784 (4) LOC(8,2,4,7)=100+(8×3×5×8 + 2×5×8 + 4×8 + 7)×4=4416 5.3 解：

(0,0,0,0) (1,0,0,0) (0,1,0,0) (1,1,0,0) (0,0,1,0) (1,0,1,0) (0,1,1,0) (1,1,1,0) (0,0,2,0) (1,0,2,0) (0,1,2,0) (1,1,2,0) (0,0,0,1) (1,0,0,1) (0,1,0,1) (1,1,0,1) (0,0,1,1) (1,0,1,1) (0,1,1,1) (1,1,1,1) (0,0,2,1) (1,0,2,1) (0,1,2,1) (1,1,2,1) (0,0,0,2) (1,0,0,2) (0,1,0,2) (1,1,0,2) (0,0,1,2) (1,0,1,2) (0,1,1,2) (1,1,1,2) (0,0,2,2) (1,0,2,2) (0,1,2,2) (1,1,2,2) 5.4 解：

k?a(a?1)?b 2 其中，a=Max(i,j)，b=Min(i,j) 5.5 解：k

?ni?(n?j)?i(i?1)?1 (i?1，j?1，i?j) 211f1(i)?(n?)i?i2

22

v=j-1

f(j)?j

c??(n?1)

5.6 解：u=i-j+1

5.7 解：(1) k=2(i-1)+j-1

(

i?j?1)

(2) i=(k+1) DIV 3 + 1 (0

j=k+1-2(k DIV 3)

?k?3n?1)

5.8 解：i为奇数时，k=i+j-2

j为偶数时，k=i+j-1 k=2(i DIV 2)+j-1

2

5.9 解：设稀疏矩阵为n行n列，其中的非零元为m个，m远小于n。从时间上来说，采用二维数组存储稀疏矩阵需要n-1次加法运算，而用三元组只需m-1次加法运算。从空间上来说，用二维数组需要n个基本存储单元，而三元组需要m个基本存储单元外加2m个整型存储单元。由于n远远大于m，故实际存储空间也较大。 5.10 解：

(1) GetHead【(p,h,w)】= p (2) GetTail【(b,k,p,h)】= (k,p,h) (3) GetHead【((a,b),(c,d))】= (a,b) (4) GetTail【((a,b),(c,d))】= ((c,d))

(5) GetHead【GetTail【((a,b),(c,d))】】= GetHead【((c,d))】= (c,d) (6) GetTail【GetHead【((a,b),(c,d))】】= GetTail【(a,b)】= (b) (7) GetHead【GetTail【GetHead【((a,b),(c,d))】】】= GetHead【(b)】= b

2

2

2

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