数据结构与算法c语言版第二版课后答案

第9章 集合

一、基础知识题

9.1 若对长度均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？

（1）查找不成功，即表中没有和关键字K相等的记录； （2）查找成功，且表中只有一个和关键字K相等的记录；

（3）查找成功，且表中有多个和关键字K相等的记录，要求计算有多少个和关键字K相等的记录。 【解答】

（1）平均查找长度不相同。前者在n+1个位置均可能失败，后者失败时的查找长度都是n+1。 （2）平均查找长度相同。在n个位置上均可能成功。 （3）平均查找长度不相同。前者在某个位置上(1<=i<=n)查找成功时，和关键字K相等的记录是连续的，而后者要查找完顺序表的全部记录。

9.2 在查找和排序算法中，监视哨的作用是什么？

【解答】监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

9.3 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【解答】分成45块，每块的理想长度为45(最后一块长20)。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5(顺序查找确定块)，或ASL=19(折半查找确定块)。

9.4 用不同的输入顺序输入n个关键

第9章 集合

一、基础知识题

9.1 若对长度均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？

（1）查找不成功，即表中没有和关键字K相等的记录； （2）查找成功，且表中只有一个和关键字K相等的记录；

（3）查找成功，且表中有多个和关键字K相等的记录，要求计算有多少个和关键字K相等的记录。 【解答】

（1）平均查找长度不相同。前者在n+1个位置均可能失败，后者失败时的查找长度都是n+1。 （2）平均查找长度相同。在n个位置上均可能成功。 （3）平均查找长度不相同。前者在某个位置上(1<=i<=n)查找成功时，和关键字K相等的记录是连续的，而后者要查找完顺序表的全部记录。

9.2 在查找和排序算法中，监视哨的作用是什么？

【解答】监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

9.3 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【解答】分成45块，每块的理想长度为45(最后一块长20)。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5(顺序查找确定块)，或ASL=19(折半查找确定块)。

9.4 用不同的输入顺序输入n个关键

数据结构（C语言版）（第2版）

课后习题答案

李冬梅 2015.3

目 录

第第第第第第第第

1章 绪论 .................................................................................................................. 1 2章 线性表 .............................................................................................................. 5 3章 栈和队列......................................................................................................... 14 4章 串、数组和广义表 ......................................................................................... 27 5章 树和二叉

数据结构（C语言版）（第2版）

课后习题答案

李冬梅 2015.3

目 录

第第第第第第第第

1章 绪论 .................................................................................................................. 1 2章 线性表 .............................................................................................................. 5 3章 栈和队列......................................................................................................... 14 4章 串、数组和广义表 ......................................................................................... 27 5章 树和二叉

第一章 习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽

（3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型

（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作

（9）有限性、输入、可行性 4、（1）A（2）C（3）C

5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定

（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A

B：H、L、I、E、A C：F、M

D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C

3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什

习

判断题：

9解答

1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。)

2.有n个数据放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL要比有序表的ASL小。)

3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE

4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE

5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE

单选题：

6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。

A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次?(1?18)/2? = 9,

第一章绪论

1.16

void print_descending(int x,int y,int z)//

按从大到小顺序输出三个数

{

scanf("%d,%d,%d",&x,&y,&z);

if(xy; //<->为表示交换的双目运算符,以下同

if(yz;

if(xy; //冒泡排序

printf("%d %d %d",x,y,z);

}//print_descending

1.17

Status fib(int k,int m,int &f)//求k 阶斐波那契序列的第m 项的值f

{

int tempd;

if(k<2||m<0) return ERROR;

if(m

else if (m==k-1) f=1;

else

{

for(i=0;i<=k-2;i++) temp[i]=0;

temp[k-1]=1; //初始化

for(i=k;i<=m;i++) //求出序列第k 至第m 个元素的值

{

sum=0;

for(j=i-k;j

temp[i]=sum;

}

f=temp[m];

}

return OK;

}//fib

分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m).

1.18

typedef struct{

char *sport;

enum{male,female}

gender;

char schoolname; //校名为'A

数据结构实验与习题

杨秀金 汪沁 编

浙江万里学院计算机系

1

内 容 简 介

数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结构实验与习题”。

本参考书包括C语言基础知识、上机实验习题和书面作业练习题三部分。

在C语言基础知识部分，主要介绍了输入/输出、函数及参数传递和结构体的概念应用。这部分内容非常重要，掌握的是否熟练会直接影响“数据结构“的学习。

在实验部分，包括有完整的C语言源程序例题，介绍了一些设计数据结构题目所需的C语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已

数据结构(C语言版)课件

第二章 线性表19:09

数据结构(C语言版)课件

第2章 第3章 第4章 第5章

线性表 栈和队列 串 数组和广义表

线性结构(逻辑、存储 和运算)

线性结构的定义：若结构是非空有限集，则有且仅有一个开始结 点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。 可表示为：(a1 ,

a2

, ……,

a n)

数据结构(C语言版)课件

线性结构表达式：(a1 ,

a2

, ……,

a n)

线性结构的特点：① 只有一个首结点和尾结点； ② 除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。简言之，线性结构反映结点间的逻辑关系是 一对一 的

线性结构包括线性表、堆栈、队列、字符串、数 组等等，其中，最典型、最常用的是

线性表19:09

数据结构(C语言版)课件

第2章

线性表

教学目标1. 了解线性结构的特点 2.掌握顺序表的定义、查找、插入和删除 3.掌握链表的定义、查找、插入和删除 4.能够从时间和空间复杂度的角度比较两种 存储结构的不同特点及其适用场合

19:09

数据结构(C语言版)课件

教学内容2.1 线性表的类型定义 2.2 线性表的顺序表示和实现

2.3 线性表的链式表示和实现2.4 线性表的应用

19:09

数据结构(C语言版)课

数据结构习题一 1/8

习题一

一、 单选题

1. 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行

( )。

A. HL=p; p->next=HL; B. p->next=HL->next; HL->next=p; C. p->next=HL; p=HL; D. p->next=HL; HL=p;

2. 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（ ）个元素. A. n B.n-1 C. n+1 D.不确定 3. 下述哪一条是顺序存储方式的优点？（ ）

A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快

4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元

素占一个空间，问A[2