数据结构实验指导书严蔚敏

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

（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.若查找每个记录的概率均等，则在具有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

石 家 庄 铁 道 大 学

实 验 任 务 书

课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院

石 家 庄 铁 道 大 学

14学年—15学年第 2学期 数据结构实验任务书

专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 王明明 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的：

1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，成绩）的的顺序表或链表，使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息；

(3) 根据姓名进行查找，返回此学生的学号和成绩；

(4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。