数据结构2007严蔚敏

第九章 集合

一、 选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n

2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】

2

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N 4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3

第二章 习题与解答

一 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二 单选题 (请从下列A，B，C，D选项中选择一项)

1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或

严蔚敏版数据结构所有算法代码

------------------------线性数据结构-----------------------------

2013年9月//线性表、链表

//栈、队列

//数组、广义表

//串

-------------------------线性表----------------------

typedef struct

{

char name[20];//注意如果应用指针的形式

//在初始化每个结点时一定要先为结点中的每个变量开辟内存空间

char sex;

char addr[100];

unsigned int age;

char phonenum[20];

}node;//结点描述

typedef struct

{

node *p;

int length;//当前顺序表长度

int listsize;//当前分配的线性表长度

}list;//线性表描述

list L;//定义一个线性表

int initlist(list &l)//构造一个空的线性表

{

l.p=(node*)malloc(LIST_INIT_SIZE*sizeof(node));

if(!(l.p))

exit(1);

l.length=0;

l.listsize=LIST_INIT_SIZE

数据结构习题及解答

第1章 概述

【例1-1】分析以下程序段的时间复杂度。

for(i=0;i

解：该程序段的时间复杂度为O(m*n)。 【例1-2】分析以下程序段的时间复杂度。

i=s=0; ① while(s

解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O(1)。语句②和语句③构成while循环语句的循环体，它们的执行次数由循环控制条件中s与n的值确定。假定循环重复执行x次后结束， 则语句②和语句③各重复执行了x次。其时间复杂度按线性累加规则为O(x)。此时s与n满足关系式：s≥n，而s=1+2+3+?+x。所以有：1+2+3+?+x≥n，可以推出：

?1?1?8n11????2n224x=

x与n之间满足x=f(n），所以循环体的时间复杂度为O(n)，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O(n）。 【例1-3】分析以下程序段的时间复杂度。

i=1; ① while(i<=n) i=2*i; ②

解：其中语句①的执行次数是1，设语句②的执行次数为f(n)，则有：2f(n)?n。

得：T（n）=O(log2n)

【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n) { if(n<=1)

retu

第二章 习题与解答

一 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二 单选题 (请从下列A，B，C，D选项中选择一项)

1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或

第一章 绪论

一、选择题

1.组成数据的基本单位是（ ）

（A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（ ）以及它们之间的相互关系。 （A）理想结构，物理结构 （B）理想结构，抽象结构 （C）物理结构，逻辑结构 （D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（ ） （A）动态结构和静态结构 （B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构

4.数据结构是一门研究非数值计算的程序设计问题中计算机的 （①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构 （B）关系 （C）运算 （D）算法 5.算法分析的目的是（）。

（A） 找出数据结构的合理性 （B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性

6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C

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

说明:

1. 本文是对严蔚敏《数据结构(c语言版)习题集》一书中所有算法设计题目的解决方案,主要作者为一具.以下网友:biwier,szm99,siice,龙抬头,iamkent,zames,birdthinking,lovebuaa等为答案的修订和完善工作提出了宝贵意见,在此表示感谢;

2. 本解答中的所有算法均采用类c语言描述,设计原则为面向交流、面向阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意义);

3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有: 5.20, 10.40;

4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答,以保证复习效果;

5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.请将你发现的错误或其它值得改进之处向作者报告: [email]yi-ju@263.net[/email]

第一章 绪论

1.16

void p

《数据结构》实验指导及报告书

（2012）

/ 学年 第 学期

姓 名：______________ 学 号：______________ 班 级：______________ 指导教师：______________

信息科学与工程学院

2012

1

预备实验 C语言的函数数组指针结构体知识

一、实验目的

1、复习C语言中函数、数组、指针、结构体与共用体等的概念。 2、熟悉利用C语言进行程序设计的一般方法。

二、实验预习

说明以下C语言中的概念 1、 函数：

2、 数组：

3、指针：

4、结构体

5、共用体

三、实验内容和要求

1、调试程序：输出100以内所有的素数（用函数实现）。 #include

int isprime(int n){ /*判断一个数是否为素数*/ int m; for(m=2;m*m<=n;m++) if(n%m==0) return 0; return 1; }

int main(){ /*输出100以内所有素数*/ int i; printf(\ for(i=2;i<100;i++) if(isprime(i)==1) printf(\ return 0; }

运行结果：

2、 调试程序：对一维数组中的元素进行逆序排列。 #include #define N 10 int ma

《数据结构》实验指导及报告书

/ 学年 第 学期

姓 名：______________ 学 号：______________ 班 级：______________ 指导教师：______________

数学与统计学院

2011

1

预备实验 C语言的函数数组指针结构体知识

一、实验目的

1、复习C语言中函数、数组、指针、结构体与共用体等的概念。 2、熟悉利用C语言进行程序设计的一般方法。

二、实验预习

说明以下C语言中的概念 1、 函数：

2、 数组：

3、指针：

4、结构体

5、共用体

三、实验内容和要求

1、调试程序：输出100以内所有的素数（用函数实现）。 #include

int isprime(int n){ /*判断一个数是否为素数*/ int m; for(m=2;m*m<=n;m++)

if(n%m==0) return 0; return 1;

}

int main(){ /*输出100以内所有素数*/

int i; printf(\for(i=2;i<100;i++)

if(isprime(i)==1) printf(\return

1.复杂性分析

对各种操作的时间复杂性的分析。

主要是链表，树，排序等简单一些的分析。

分析的时候，从简单的入手，学会方法。

后续的各种豆可能让你分析时间复杂度。

线性链表（顺序表和单链表）

链表循环链表

双向链表

2.线性结构队列（循环队列）

栈

链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定）

队列：查找，插入（位置固定），删除（位置固定）

顺序表（可以视为一个数组）

单链表：

（删除）

（插入）

倒置：

（查找）

循环链表

双向链表

栈：

（插入删除查找）

队列

（插入删除查找）

循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。

3.二叉树

基本概念

二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。

二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，