数据结构习题集答案解析清华大学版 下载本文

内容发布更新时间 : 2024/12/23 18:15:56星期一 下面是文章的全部内容请认真阅读。

(2)

?x??xii?0nnn?1?1/?x?1?

?

?x?1,n?0?

(3)

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

?n?1? ?n?1?

(4)

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

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

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

}

1、18 假设有A,B,C,D,E五个高等院校进行田径对抗赛,各院校得单项成绩均已存入计算机,并构成一张表,表中每一行得形式为牽駘珐猻鉤宝潷。 项目名称 解:

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或对某个kk?1?k?n?,使k!?2iSum 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时,

应按出错处理。注意选择您认为较好得出错处理方法。糁縟園虧荭紙复。 解:

#include #include #define MAXINT 65535 #define ArrSize 100

int fun(int i); int main() { }

1、20 试编写算法求一元多项式得值Pnint 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];

?x???aixi得值Pn?x0?,并确定算法中每一语句得执行次数

i?0n与整个算法得时间复杂度。注意选择您认为较好得输入与输出方法。本题得输入为ai与n,输出为Pn解:

#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]:\

?i?0,1,?,n?,x0?x0?。嘮鲰饭櫸橋单鎵。 }

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结点得语句序列就是__________________。