考试指导 - 清华大学 - 数据结构 - 习题集详细

}

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

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

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) { Sum temp; temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; int i; for(i=0;i

}

1.19 试编写算法，计算i!*2的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个

解：

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

int main() { int i,k; int a[ArrSize]; cout<<\ cin>>k; if(k>ArrSize-1) exit(0); for(i=0;i<=k;i++){ if(i==0) a[i]=1; else{ if(2*i*a[i-1]>MAXINT) exit(0); else a[i]=2*i*a[i-1]; } } for(i=0;i<=k;i++){ if(a[i]>MAXINT) exit(0); else cout<

1.20 试编写算法求一元多项式的值Pnik?1?k?n?，使

k!?2k?maxint时，应按出错处理。注意选择你认为较好的出错处理方法。

?x???aixi的值Pn?x0?，并确定算法中每一语句的执

i?0n行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为

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

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

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

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

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

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。

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

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

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

解：

2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L;

for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; }

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

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;