3_2算法与数据结构

算法与数据结构实验报告实验二实验名称：线性表实现集合运算姓名：卢丽娟学号：211006289专业：软件工程班级：二班指导教师：陈亦萍日期: 2012年3月24日一、实验目的本实验是要实现线性表的集合运算，通过该实验更深刻地理解线性结构的特点，学会并掌握线性表的顺序或链式表示和实现。

二、实验内容与实验步骤采用线性表表示集合，用线性表实现集合以及基本操作，实现两个集合的并、交、差运算。

用到的各种函数如下程序步骤所示。

步骤：1. 链表销毁void DestoryList_L(list& L){ list p=L->next,s;while(p){ s=p; p=p->next;free(s);}L->next=NULL;}2. 链表初始化void InitList(list &L){ L=NULL;}3. 往链表L中插入元素e，并按升序排列，如果L中已有元素e，则不插入ListInsert_L(list &L, char e){ list p=L->next,t,s; t = L;while(p!=NULL &&p->data<= e){ if(p->data==e) return OK;t=p; p=p->next;}s =(list)malloc(sizeof(LNode));s->data=e;s->next=p;t->next=s;return OK;}4. 创建链表,按字符串输入元素void CreateList_L(list &L, int n){ L =(list)malloc(sizeof(LNode));L->next=NULL;int i=0;for(i=n;i>0;i--){ char e; scanf("%c",&e);ListInsert_L(L,e);}getchar();}5.定义输入函数，分配存储空间void inputdata(list head)//定义输入函数{ list p;char tmp;scanf("%c",&tmp);while(tmp!='\n'){ p=(list)malloc(sizeof(struct LNode));//分配存储空间p->data=tmp;p->next=head->next;head->next=p;scanf("%c",&tmp); }}6.定义输出函数，初始化，并判断其是否为空void outputdata(list head)//定义输出集合函数{ list p;p=head->next;//初始化，p指向第一个结点while(p!=NULL)//判断是否为空{ printf("%c",p->data);p=p->next;} printf("\n");//输出集合函数}7.定义集合的并集函数，其中函数的数据元素均已按值非递减排列void MergeList(list head1,list head2,list head3)//定义集合的并集函数{//已知p1、p2中的数据元素按值非递减排列。

班号 学号 姓名 成绩《算法与数据结构(2) 》期末考试卷注意事项：1、关闭手机、将考试用文具以外的物品放于讲台上 2、严格遵守学校的考场纪律，违纪者请出考场 题目：一、 判断题（20分）请在正确的陈述前面括号中打√，在错误的陈述前面括号中打×。

1. （ × ）如果一个问题不是NP 问题，那么它有可能是P 问题。

2. （ × ）回溯法用深度优先或广度优先法搜索状态空间树。

3. （ × ）)(n n O 221=+且)(n n O 222=4． （ × ）贪心算法通过增加空间复杂性来减少时间复杂性。

5． （ × ）快速排序算法的平均时间复杂度是O(nlogn),使用随机化快速排序算法可以将平均时间复杂度降得更低。

6． （ √ ）基于比较的寻找数组A[1...n ]中最大值元素问题的下界是)3/(n Ω。

7． （ √ ）直观地讲，P 类问题是易解的问题；而NP 问题是易被验证的问题。

8． （ × ）下列问题是一个判定问题：给定一个合取范式，对其中的所有逻辑变量求一组真值赋值，使得给定的合取范式在该组真值赋值下为真。

9． （ √ ）max(f(n),g(n))= Θ(f(n)+g(n))10．（ √ ）若 ))(()(n g O n f =，则 ))(()(n f n g Ω=二、 简答题（30分）：1．简述拉斯维加斯（Las Vegas ）算法和蒙特卡洛（Monte Carlo ）算法的主要区别前者不一定总能给出解，但给出的解一定是正确的； 后者总能给出解，但是给出的解可能是错误的。

2．按照增长率上升的顺序排列以下函数，即，若在你的排序结果中，函数f(n) 跟在 g(n)的后面，则说明应该满足g(n)是O （f(n)）：4/31)(n n f = n n f 2)(2= n n f log )(3= !)(4n n f = 22)(5n n f = nn n f log )(6= )(3n f , )(1n f , )(6n f , )(2n f , )(4n f , )(5n f3．推导以下递推式的解：T(n)=2 当n = 1时T(n)=2T(n/3)+2n 当n ≥2时T(n)=2T(n/3)+2n=2[2T(n/32)+2(n/3)]+2n=4T(n/32)+4(n/3)+2n=4[2T(n/33)+2(n/32)]+ 4(n/3)+2n=8T(n/33)+8(n/32)+ 4(n/3)+2n=…设n=3k=2k T(n/3k )+ 2k (n/3k-1)+ 2k-1 (n/3k-2)+…+ 4(n/3)+2n =2k 2+2n[(2/3)k-1 +(2/3)k-2 +…+2/3+1]=2k 2+6n[1-(2/3)k]=2k 2+6n-6.2k=6n-4.2k=6n-4.2=n n3log246⋅-4．请给出基于比较的对数组A[1…n]进行排序问题的最紧的下界，并写出两个平均时间复杂度为该下界的排序算法的名称。

算法与数据结构课程设计报告系（院）：计算机科学学院专业班级：教技1001姓名：李##学号： ******### 指导教师：***设计时间：2012.6.16 - 2012.6.24设计地点：4号楼2号机房目录一、设计方案 (1)二、实现过程以及代码 (2)三、测试 (20)四、结论和分析 (23)五、难点和收获 (23)一、 设计方案1.程序设计基本过程：拿到课程设计任务书，按照要求，需要设计有向图、有向网、无向图 、无向网四种图，以及邻接矩阵、邻接表两种数据存储结构，三层以上的显示菜单。

图的操作中又包含了有关线性表、栈和队列的基本操作。

由于显示菜单已给出，剩下的任务就是把函数写入其中。

2.程序流程图：预定义 定义结构体 定义变量 各种函数3.程序设计的原理：图的操作都是以两种存储结构为基础的：邻接矩阵存储结构和邻接表存储结构，如有向图，有向网，无向图，无向网的创建，其他的操作都是在四种图创建后才开始进行的。

所以，首先必须理解两种存储结构的定义。

图的邻接矩阵存储结构即图的数组表示法。

用两个数组分别存储数据元素（如顶点）的信息和数据元素之间的关系（如边或弧）的信息。

用邻接矩阵存储结构的图具有以下几点特征：（一）：顶点数：vexnum ，边（弧）数：arcnum ，图的种类：kind ；（二）：邻接矩阵：arcs(1顶点关系类型:adj 2相关信息:*info)；（三）：顶点向量（顶点名）：vexs[]；其优点是以二维数组表示有n 个顶点的图时，需存放n 个顶点的信息和n*n 条弧的信息存储量。

借助邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求出各个顶点的度。

缺点是时间复杂度是O （n*n ）,例如，构造一个具有n 个顶点和e 条边的无向网的时间复杂度为O （n*n+e*n ）。

图的邻接表存储结构是图的一种链式存储结构。

对图中的每个顶点建立一个单链表，每个结点由三个域组成，邻接点域adjvex （弧尾在邻接表链表中的位序），链域nextarc （下一条弧），数据域info(权值)。

第1章概论1.数据、数据元素、数据结构、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。

数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。

数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。

数据类型包含取值范围和基本运算等概念。

2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。

数据的逻辑结构包含下面两个方面的信息：①数据元素的信息；②各数据元素之间的关系。

物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。

数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。

采用不同的存储结构，其数据处理的效率是不同的。

因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。

3.数据结构的主要操作包括哪些？对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有：●创建：建立一个数据结构；●清除：清除一个数据结构；●插入：在数据结构中增加新的结点；●删除：把指定的结点从数据结构中删除；●访问：对数据结构中的结点进行访问；●更新：改变指定结点的值或改变指定的某些结点之间的关系；●查找：在数据结构中查找满足一定条件的结点；●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。

4.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。

一、单项选择题1 某算法的时间复杂度是O(n2 ) ，表明该算法（）。

A 问题规模是n2B 问题规模与n2成正比C 执行时间等于n2D 执行时间与n2成正比2、关于数据结构的描述，不正确的是（）。

A数据结构相同，对应的存储结构也相同。

B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。

C数据结构操作的实现与存储结构有关。

D定义逻辑结构时可不考虑存储结构。

3、按排序策略分来，起泡排序属于（）。

A插入排序B选择排序C交换排序D归并排序4、利用双向链表作线性表的存储结构的优点是（）。

A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度C节省空间D便于销毁结构释放空间5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。

A 1,2,3,4B 1,3,2,4C 1,4,2,3D 4,3,2,16、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。

A按长度递减的顺序求出图的某顶点到其余顶点的最短路径B按长度递增的顺序求出图的某顶点到其余顶点的最短路径C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径D通过广度优先遍历求出图的某顶点到其余顶点的最短路径7、字符串可定义为n（ n≥ 0）个字符的有限（）。

其中，n是字符串的长度，表明字符串中字符的个数。

A集合B数列C序列D聚合8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。

在这种情况下，元素A[8][5]的起始地址为（）。

A SA+141B SA+144C SA+222D SA+2559、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。

A2B3C4D510.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。

A. n+1B. nC. n-1D. n-211.一个递归算法必须包括 __________ 。

绪论单元测试1【单选题】(2分)数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的__ __和运算等的学科。

A.算法B.运算C.关系D.结构2【多选题】(2分)算法的描述形式包括A.N-S图B.类程序设计语言C.自然语言D.流程图3【判断题】(2分)算法的特征包括有穷性、确定性、可行性和输入输出。

A.对B.错4【判断题】(2分)对算法的描述包括程序形式和描述形式。

A.对B.错5【判断题】(2分)描述形式是算法的最终形式A.对B.错6【多选题】(2分)“数据结构”是介于()、()和()三者之间的一门核心课程。

A.计算机软件B.语句C.计算机硬件D.数学7【多选题】(2分)著名计算机科学家沃思教授提出的公式：程序=()+()，也说明了数据结构的重要性。

A.编程环境B.数据结构C.语法D.算法8【多选题】(2分)描述非数值计算问题的数学模型不再是数学方程，而是数据结构()。

A.集合B.表C.图D.树9【多选题】(2分)数据结构是一门研究()程序设计问题中计算机的()以及它们之间的()和()等的学科。

A.操作B.关系C.非数值计算D.操作对象10【单选题】(2分)顺序存储结构:借助元素在存储器中的()来表示数据元素间的逻辑关系。

A.地址B.相对位置C.数值D.结构第一章测试1【单选题】(1分)（）是一种最简单的线性结构。

A.线性表B.集合C.树D.图2【单选题】(2分)（）线性表的数据元素可以由所描述对象的各种特征的数据项组成。

A.链式存储B.散列存储C.顺序存储D.有序存储3【单选题】(2分)已知单向链表中指针p指向结点A，(）表示删除A的后继结点（若存在）的链操作（不考虑回收）。

A.p=p—>nextB.p=p—>next—>nextC.p—>next=pD.p—>next=p—>next—>next4【单选题】(2分)已知last指向单向简单链表的尾结点，将s所指结点加在表尾，不正确的操作是____。

《数据结构》学习指导说明：本指导以《数据结构》(C语言版)(严蔚敏等编著,清华大学出版社1997年出版，国家级优秀教材特等奖)和《数据结构题集》(严蔚敏等编著,清华大学出版社1999年出版)为教学主要参考书。

一、绪论1、学习目的：明确数据结构课程在本专业知识结构中的地位，作用。

课程的特点，教学的要求，方法。

明确数据结构所研究的问题以及有关基本概念。

初步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点，初步掌握算法分析的方法。

2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽象数据类型及其表示与实现，算法，算法设计的要求，算法的时间复杂度和算法的空间复杂度。

3、学习难点：数据结构的有关概念，抽象数据类型的表示与实现；算法的时间复杂度分析。

4、课程内容与基本要求(一) 数据结构的引入(1) 三个世界：现实世界，信息世界，机器世界。

数据结构要解决的就是实现从现实世界到信息世界，再由信息世界到机器世界的转换，从而实现用计算机来解决问题的目的。

(2) 非数值问题(结合三个世界讲)：控制，管理，数据处理(3) 数值问题：数值计算(4)数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及他们之间的关系和操作等等的学科。

(二) 课程的地位，性质，作用。

(1) 地位: 计算机专业的核心课程之一。

(2) 性质: 算法理论基础和软件设计的技术基础课。

(3) 作用: 程序设计的基础，编译程序，操作系统，数据库系统及软件系统和应用程序的基础(三) 数据结构的产生和发展(四) 课程的特点，学习的要求教材：《数据结构》(C语言版)严蔚敏等编著北京清华大学出版社1997年参考书：《数据结构》许卓群等编著北京高等教育出版社1987年数据结构实用教程》（C/C++描述）徐孝凯北京清华大学出版社1999年《数据结构题集》严蔚敏等编著北京清华大学出版社1999年《数据结构导学》苏光奎等编著北京清华大学出版社20XX年《数据结构》(C语言篇)－习题与解析李春葆编著北京清华大学出版社20XX年《数据结构》实验指导书唐开山自编讲义20XX年(五) 基本概念和术语数据数据元素数据对象(4)数据结构:按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构。

数据结构与算法严蔚敏第二版教案课程名称：数据结构与算法教材版本：严蔚敏第二版课程目标：1.理解数据结构的概念和基本操作；2.掌握常用数据结构的实现和应用；3.了解常用算法的设计和分析方法；4.能够灵活运用所学的数据结构和算法解决实际问题。

教学内容和方法：第一阶段：数据结构概述1.数据结构的定义和分类；2.数据结构的基本操作和性质；3.数据结构的存储表示和实现方法。

第二阶段：线性表和链表1.线性表的概念和实现方法；2.顺序表和链表的比较与应用；3.单链表、双链表和循环链表的实现。

第三阶段：栈和队列1.栈的定义和基本操作；2.队列的定义和基本操作；3.栈和队列的应用和实现。

第四阶段：树和二叉树1.树的基本概念和性质；2.树的存储结构和实现方法；3.二叉树的基本性质和遍历方法。

第五阶段：图1.图的概念和分类；2.图的存储结构和实现方法；3.图的遍历和最短路径算法。

第六阶段：查找和排序1.查找的基本概念和方法；2.顺序查找和二分查找的实现；3.排序的基本概念和方法；4.插入排序、冒泡排序和快速排序的实现。

教学方法：1.授课结合实例，注重理论与实践相结合；2.鼓励学生自主学习和思考，提出问题并进行解答；3.运用教学辅助工具，如PPT、代码演示等。

教学过程：第一课时：1.数据结构的概述-引入数据结构的概念和重要性；-分类介绍常用的数据结构；-讲解数据结构的基本操作和性质。

2.数据结构的存储表示和实现方法-简单介绍数据结构的存储方式，如顺序存储和链式存储；-分别讲解顺序表和链表的实现方法；-结合具体例子演示存储表示和实现过程。

第二课时：1.线性表和链表-介绍线性表的概念和特点；-对比顺序表和链表的利弊；-分别讲解单链表、双链表和循环链表的实现方法。

2.应用实例演示-演示线性表和链表在实际问题中的应用；-提供具体例子，让学生动手实现相应的线性表和链表。

第三课时：1.栈和队列-引入栈和队列的概念和基本操作；-讲解栈和队列的应用场景和实现方法。