数据结构习题参考答案

………………………………………………最新资料推荐………………………………………

1 / 35 习题1参考答案

1至8题答案略。

9.（1）【解】该逻辑结构为线性结构，其图形表示如下：

（2）【解】该逻辑结构为树型结构，其图形表示如下：

（3）【解】该逻辑结构为图型结构，其图形表示如下：

（4）【解】该逻辑结构为线性结构，其图形表示如下：

10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType类型。每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。可用一个表格（如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。

图书信息表

编号 书名 作者 出版社 出版日期

1 数据结构 顾泽元 北京航空航天大学出版社 2011年6月

2 高等数学 李 四 北京航空航天大学出版社 2009年1月

3 计算方法 张 五 清华大学出版社 2008年12月

根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。

所以，现用抽象数据类型bookList表示问题模型，其逻辑结构与基本操作的定义如下：

（1）逻辑结构

bookList=( D, {r} )

D={bi| bi为bookType类型的元素，i=1,2,3, ....., n，n≥0}

r={| i=1,2,…, n-1, n≥0 }

（2）基本操作

①初始化

操作函数：InitBookList(&BL)。 c1 c2 c3 cn …… b

c

d e a Sun Mon Tue Wed Thu Fri Sat

b c d

e f g h j i

k a ………………………………………………最新资料推荐………………………………………

2 / 35 初始条件：图书表BL不存在。

操作结果：构造一个空的图书表BL。

②求图书表长度

操作函数：bookListLength(BL)。

初始条件：图书表BL已存在。

操作结果：返回图书表BL中所包含的数据元素（图书）的个数。

③取图书表中元素

操作函数：getBook(BL,i, &b)。

初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)。

操作结果：用b返回图书表BL中的第i个数据元素的值。

④按编号查找

操作函数：locateById(BL,id)。

初始条件：图书表BL已存在，id是给定的一个图书编号。

操作结果：返回图书表BL中图书编号为id的数据元素的位序，若这样的数据元素不存在，则返回0。

⑤按编号查找

操作函数：locateByName(BL, i,name)。

初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)，name是给定的一个图书名。

操作结果：从图书表BL中第i个元素开始，查找图书名与给定name相等的第一个元素，若找到则返回其位序，否则返回0。

⑥插入图书

操作函数：insertBook(&BL,i,b)。

初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)+1。

操作结果：在图书表BL的第i个位置上插入一个值为b的新元素，使线性表的长度增1。

⑦删除操作

操作函数：deleteBook(&BL,i,&b)。

初始条件：线性表L已存在，1≤i≤listLength(L)。

操作结果：删除图书表BL的第i个数据元素，并用b返回其值，使线性表的长度减1。

11.（1）【解】函数体内为简单语句，时间复杂度为T(n)=O(1)

（2）【解】选取的基本语句为“if(a[i]>a[k]) k=i;”其执行频度为n-1，时间复杂度为T(n)=O(n)。

（3）【解】选取的基本语句为最内层的循环体语句“total+=a[i][j];”，其执行频度为n(n+1)/2，时间复杂度为T(n)=O(n2)。

（4）【解】选取的基本语句为最内层的循环体语句“c[i][j]+=a[i][k]*b[k][j];”，其执行频度为n3，时间复杂度为T(n)=O(n3)。

（5）【解】函数有两个并列的循环，其问题规模分别为n和m，对于第一个for循环选取的基本语句为“if(a[i]>a[max]) max=i;”，其执行频度为n-1；对于第二个for循环选取的基本语句为“if(b[i]

（6）【解】选取的基本语句为while的循环体，其执行频度为max{1|kikin}，时间复杂度为T(n)=O(n)。

12.【解】算法（1）中有两个并列的循环，每个循环的循环体语句执行次数均为n，故该函数的语句频度为2n。算法（2）只用了一个循环，其循环体语句执行次数为n，即该函数的语句频度为n。所以算法（1）与算法（2）相比较，算法（1）的时间效率更好。但它们的时间复杂度都为O（n），………………………………………………最新资料推荐………………………………………

3 / 35 这说明：随着n值的增大，这两个函数执行时间的增长率相同，都是线性增长的。

13.【解】由题意，设计程序如下：

#include

#include

struct stuInfo{

int num;

char name[18];

int score;

};

void inputInfo(struct stuInfo stus[], int n){

//输入n个同学信息存于数组stus中

int i;

for(i=0;i

{ printf("输入%d个学生信息：\n", i+1);

printf("学号："); scanf("%d", &stus[i].num);

printf("姓名："); scanf("%s", stus[i].name);

printf("成绩："); scanf("%d", &stus[i].score);

}

}

void sortByScore(struct stuInfo stus[], int n){

//将数组stus中n个同学信息按成绩进行递减排序

int i,j,k;

struct stuInfo temp;

for(i=0;i

{ k=i;

for(j=i+1;j

if(stus[j].score>stus[k].score) k=j;

if(k!=i) { temp=stus[i]; stus[i]=stus[k];stus[k]=temp; }

}

}

void outputInfo(struct stuInfo stus[], int n){

//输出数组stus中n个同学信息报表

int i;

printf("%6s %17s %6s\n", "学号", "姓名", "成绩")；

for(i=0;i

printf("%6d %17s %6d\n", stus[i].num, stus[i].name, stus[i].score);

}

int main(){

int n;

struct stuInfo *stus;

printf("输入学生数:"); scanf("%d", &n);

stus=(struct stuInfo*)malloc(n*sizeof(struct stuInfo));

if(!stus) { printf("内存空间溢出！\n"); return -2;}

inputInfo(stus, n);

sortByScore(stus, n); ………………………………………………最新资料推荐………………………………………

4 / 35 outputInfo(stus, n);

system("pause");

}

14.【解】由题意，函数设计如下：

Status TriArea(double a, double b, double c, double &area){

double s;

if(a<=0||b<=0||c<=0) return ERROR;

if(a+b<=c||a+c<=b||b+c<=a) return ERROR;

s=(a+b+c)/2;

area=sqrt(s*(s-a)*(s-b)*(s-c));

return OK;

}

15.【解】由题意，设欲交换的变量为int 类型，则swap函数设计如下：

void swap(int &a, int &b){

int temp;

temp=a;

a=b;

b=t;

}

习题2参考答案

1.属于同一数据对象

2. A

3. 2008

4. C

5.n-i+1、n-i

6. A

7. D

8.（1）s->next=p->next; p->next=s; （2）q=p->next; p->next=q->next; free(p);

（3）q->next=L->next;L->next=q;L->next==NULL（4）q->next=L; L=q; L==NULL

9.（1）s->next=p->next；s->pre=p; p->next->pre=s; p->next=s;

（2）s->pre=p->pre;s->next=p; p->pre->next=s; p->pre=s;

（3）q=p->next; p->next=q->next; q->next->pre=p; free(q);

（4）q=p>pre; p->pre=q->pre; q->pre->next=p; free(q);

（5）p->pre->next =p->next; p->next->pre= p->pre;free(p);

（6）s->next=L->next; s->pre=L; L->next->pre =s; L->next=s;

10. 略

11.【解】算法如下所示：

void union(List La,List Lb,List &Lc)

{

inti=1,j=1,k=1,m;