数据结构-1
- 格式：pdf
- 大小：334.80 KB
- 文档页数：22
下载文档原格式
合集下载
数据结构第1讲---线性表
type p=^integer; var p1:p; p1
34F2 地址 被释放，变 量P与地址 34F2没有关 系
p1^
200 34F2
34F2
new（p1） ——向计算机申请内存地址 p1^:=200 ——给p1指向的单元赋值 dispose(p1) ——释放存储单元
链式结构——什么是指针
Type p=^integer; arr=array[1..4] of char; arrp = ^arr; Var p1:p; p2:arrp;
线性结构 数据的逻辑结构 数 据 结 构 树形结构 图形结构 数据的存储结构 顺序存储
链式存储
数据结构的基本运算 :查找、插入、删除等
三、线性结构——线性表
1、线性表的概念
线性表是由n（n≥0）个具有相同特性数据元素(结点)
a1，a2，…，an组成的有限序列。
线性表的长度：所含元素的个数,用n表示，n>=０。
在我们生活中有哪些属于线性表的例子,列举几个。 1、英文字母表（A，B，…，Z）是线性表， 表中每个字母是一个数据元素（结点）
2、学生成绩表中，每个学生及其成绩是一
个数据元素，其中数据元素由学号、姓名、
各科成绩及平均成绩等数据项组成。
4、线性表的顺序存储
顺序存储是线性表的一种最 简单的存储结构，存储方式是： 在内存中为线性表开辟一块连 续的存储空间。用数组来存放 每一个节点。
[例4-2] 法雷序列
[问题描述]对任意给定的一个自然数n（n<=100），将 分母小于等于n的不可约的真分数按上升次序排序，并 且在第一个分数前加0/1，而在最后一个分数后加1/1, 这个序列称为n级的法雷序列。 当n=8时序列为：0/1, 1/8, 1/7, 1/6,1/5, 1/4,2/7,1/3,3/8, 2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4, 4/5,5/6,6/7,7/8, 1/1 。 编程求出n级的法雷序列，每行输出10个分数。
34F2 地址 被释放，变 量P与地址 34F2没有关 系
p1^
200 34F2
34F2
new（p1） ——向计算机申请内存地址 p1^:=200 ——给p1指向的单元赋值 dispose(p1) ——释放存储单元
链式结构——什么是指针
Type p=^integer; arr=array[1..4] of char; arrp = ^arr; Var p1:p; p2:arrp;
线性结构 数据的逻辑结构 数 据 结 构 树形结构 图形结构 数据的存储结构 顺序存储
链式存储
数据结构的基本运算 :查找、插入、删除等
三、线性结构——线性表
1、线性表的概念
线性表是由n（n≥0）个具有相同特性数据元素(结点)
a1，a2，…，an组成的有限序列。
线性表的长度：所含元素的个数,用n表示，n>=０。
在我们生活中有哪些属于线性表的例子,列举几个。 1、英文字母表（A，B，…，Z）是线性表， 表中每个字母是一个数据元素（结点）
2、学生成绩表中，每个学生及其成绩是一
个数据元素，其中数据元素由学号、姓名、
各科成绩及平均成绩等数据项组成。
4、线性表的顺序存储
顺序存储是线性表的一种最 简单的存储结构，存储方式是： 在内存中为线性表开辟一块连 续的存储空间。用数组来存放 每一个节点。
[例4-2] 法雷序列
[问题描述]对任意给定的一个自然数n（n<=100），将 分母小于等于n的不可约的真分数按上升次序排序，并 且在第一个分数前加0/1，而在最后一个分数后加1/1, 这个序列称为n级的法雷序列。 当n=8时序列为：0/1, 1/8, 1/7, 1/6,1/5, 1/4,2/7,1/3,3/8, 2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4, 4/5,5/6,6/7,7/8, 1/1 。 编程求出n级的法雷序列，每行输出10个分数。
精品课件-数据结构教程(胡元义)-第1章
(4) 哈希(或散列)存储结构：此方法的基本思想是根据 数据元素的关键字通过哈希(或散列)函数直接计算出该数据元 素的存储地址。
第1章 绪论
顺序存储结构的主要优点是节省存储空间，即分配给数据 的存储单元全部用于存放数据元素的数据信息，数据元素之间 的逻辑关系没有占用额外的存储空间。采用这种存储结构可以 实现对数据元素的随机存取，即每个数据元素对应有一个序号， 并由该序号可以直接计算出数据元素的存储地址(例如对于数 组A其序号为数组元素的下标，数组元素A[i]可以通过*(A+i) 进行存取)。但顺序存储结构的主要缺点是不便于修改，对数 据元素进行插入、删除运算时，可能要移动一系列的数据元素。
第1章 绪论
(1) 分析阶段：分析实际问题，从中抽象出一个数学模 型。
(2) 设计阶段：设计出解决数学模型的算法。 (3) 编程阶段：用适当的编程语言编写出可执行的程序。 (4) 测试阶段：测试、修改直到得到问题的解答。 数据结构课程集中讨论软件开发过程中的设计阶段，同时 涉及分析阶段和编程阶段的若干基本问题。此外，为了构造出 好的数据结构及其实现，还需考虑数据结构及其实现的评价与 选择。因此，数据结构课程的内容包括了如表1.1所示的数据 表示和数据处理方面所对应的3个层次。
第1章 绪论
1.2.2 存储结构 数据的存储结构是数据结构在计算机中的表示方法，也即
数据的逻辑结构到计算机存储器的映像，包括数据结构中数据 元素的表示以及数据元素之间关系的表示。数据元素及数据元 素之间的关系在计算机中可以有以下四种基本存储结构：
(1) 顺序存储结构：借助于数据元素在存储器中的相对 位置来表示数据元素之间的逻辑关系。通常顺序存储结构是利 用程序语言中的数组来描述的。
第1章 绪论
第1章 绪论
顺序存储结构的主要优点是节省存储空间，即分配给数据 的存储单元全部用于存放数据元素的数据信息，数据元素之间 的逻辑关系没有占用额外的存储空间。采用这种存储结构可以 实现对数据元素的随机存取，即每个数据元素对应有一个序号， 并由该序号可以直接计算出数据元素的存储地址(例如对于数 组A其序号为数组元素的下标，数组元素A[i]可以通过*(A+i) 进行存取)。但顺序存储结构的主要缺点是不便于修改，对数 据元素进行插入、删除运算时，可能要移动一系列的数据元素。
第1章 绪论
(1) 分析阶段：分析实际问题，从中抽象出一个数学模 型。
(2) 设计阶段：设计出解决数学模型的算法。 (3) 编程阶段：用适当的编程语言编写出可执行的程序。 (4) 测试阶段：测试、修改直到得到问题的解答。 数据结构课程集中讨论软件开发过程中的设计阶段，同时 涉及分析阶段和编程阶段的若干基本问题。此外，为了构造出 好的数据结构及其实现，还需考虑数据结构及其实现的评价与 选择。因此，数据结构课程的内容包括了如表1.1所示的数据 表示和数据处理方面所对应的3个层次。
第1章 绪论
1.2.2 存储结构 数据的存储结构是数据结构在计算机中的表示方法，也即
数据的逻辑结构到计算机存储器的映像，包括数据结构中数据 元素的表示以及数据元素之间关系的表示。数据元素及数据元 素之间的关系在计算机中可以有以下四种基本存储结构：
(1) 顺序存储结构：借助于数据元素在存储器中的相对 位置来表示数据元素之间的逻辑关系。通常顺序存储结构是利 用程序语言中的数组来描述的。
第1章 绪论
数据结构复习答案2013-1
数据结构复习答案一、选择填空1.下面关于线性表的叙述中，错误的是哪一个？（）A）线性表采用顺序存储，必须占用一片连续的存储单元。
√B）线性表采用顺序存储，便于进行插入和删除操作。
C）线性表采用链接存储，不必占用一片连续的存储单元。
D）线性表采用链接存储，便于插入和删除操作。
2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
√A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表3.链表不具有的特点是（）。
A）插入、删除不需要移动元素√B）可随机访问任一元素C）不必事先估计存储空间D）所需空间与线性长度成正比4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。
A）O(0) B）O(1) √C）O(n) D）O(n2)5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。
A）O(i) B）O(1) √C）O(n) D）O(i-1)6.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A）head==NULL B）head→next==NULL√C）head→next==head D）head!=NULL7.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。
A）p->next=s;s->next=p->next; √B）s->next=p->next;p->next=s;C）p->next=s;p->next=s->next; D）p->next=s->next;p->next=s;8.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( )。
√A）p->next=p->next->next B）p=p->nextC）p=p->next->next D）p->next=p9.( )又称为FIFO表；( )又称为FILO表。
03、1数据结构第一部分--线性表-树与二叉树
数据结构(一)目录第1章序论 (1)1.1 什么是数据? (1)1.2 什么是数据元素? (1)1.3 什么是数据结构及种类? (1)1.4 数据的逻辑结构 (1)1.5 数据的物理结构 (1)1.6 算法和算法分析 (1)1.7 算法的五个特性 (1)1.8 算法设计的要求 (2)1.9 算法效率的度量 (2)第2章线性表 (3)2.1 线性表举例 (3)2.2 线性表的存储 (4)2.3 线性表-栈 (4)2.4 队列 (4)2.5 双端队列 (6)第3章树和二叉树 (6)3.1 树 (6)3.1.1 树的基本概念 (6)3.1.2 树的常用存储结构 (6)3.1.3 树的遍历 (7)3.2 二叉树 (7)3.2.1 二叉树的基本概念 (7)3.2.2 二叉树与树的区别 (7)3.2.3 树及森林转到二叉树 (7)3.2.4 二叉树的性质 (8)3.2.5 满二叉树 (8)3.2.6 完全二叉树 (8)3.2.7 完全二叉树的性质 (9)3.2.8 二叉树的四种遍历 (9)3.2.9 二叉排序树 (10)3.2.10 平衡二叉树 (11)3.2.11 m阶B-树 (11)3.2.12 最优二叉树 (11)3.2.13 二叉树的存储结构 (12)3.3 广义表 (13)3.4 矩阵的压缩存储 (14)3.4.1 特殊矩阵 (14)3.4.2 压缩存储 (14)第4章历年真题讲解 (15)4.1 2009年上半年 (15)4.2 2009年下半年 (15)4.3 2010年上半年 (15)4.4 2011年上半年 (16)4.5 2011年下半年 (16)4.6 2012年上半年 (17)4.7 2012年下半年 (17)4.8 2013年上半年 (18)4.9 2013年下半年 (18)4.10 2014年上半年 (18)4.11 2014年下半年 (19)4.12 2015年上半年 (19)4.13 2015年下半年 (19)4.14 2016年上半年 (20)第1章序论什么是数据?所有能输入到计算机中并能够被计算机程序处理的符号的总称,它是计算机程序加工的原料。
数据结构导论自考题-1_真题-无答案
数据结构导论自考题-1(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。
1. 算法的便于阅读和理解的特性称为( )A．正确性 B．易读性C．健壮性 D．时空性2. 给定有n个元素，建立一个有序单链表的时间复杂度为( )A．O(1) B．O(n)C．O(n2) D．O(nlog2n)3. 在双链表中某结点(已知其地址)前插入一新结点，其时间复杂度为( )A．O(n) B．O(1)C．O(n2) D．O(log2n)4. 顺序栈s中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e 进栈操作的主要语句为( )A．s.elem[top]=e;s.top=s.top+1;B．s.elem[top+1]=e;s.top=s.top+1;C．s.top=s.top+1;s.elem[top+1]=e;D．s.top=s.top+1;s.elem[top]=e;5. 一个数组的第一个元素的存储地址是100，每个元素占2个存储单元，则第5个元素的存储地址是( )A．110 B．108C．100 D．1206. 已知某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为( )A．HDBEFCGA B．HDEBFGCAC．DHEBFGACA D．DEHBFGCA7. 除根结点外，树上每个结点( )A．可有任意多个孩子、一个双亲 B．可有任意多个孩子、任意多个双亲C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲8. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )A．250 B．500C．501 D．5059. 设有6个结点的无向图，若要确保此图是一个连通图，则至少应有边的条数是( )A．5 B．6C．7 D．810. 在含有n个顶点e条边的无向图的邻接矩阵中，零元素的个数为( )A．e B．2eC．n2-e D．n2-2e11. 设有无向图G=(V，E)和(G'=(V'，E')，如G'为G的生成树，则下面说法不正确的是( )A．G'为G的子图 B．G'为G的连通分量C．G'为G的极小连通子图且V'=V D．G'是G的无环子图12. 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行元素间比较的次数是( )A．4次 B．5次C．7次 D．10次13. 采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( )A．从MID/2位置开始 B．从MID位置开始C．从MID-1位置开始 D．从MID+1位置开始14. 当待排序序列中记录数较少或基本有序时，最适合的排序方法为( )A．直接插入排序法 B．快速排序法C．堆排序法 D．归并排序法15. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )A．(38，40，46，56，79，84) B．(40，38，46，79，56，84)C．(40，38，46，56，79，84) D．(40，38，46，84，56，79)二、填空题16. 算法的空间性能是指算法需要的______。
数据结构第1章 绪论
课程改革: 课程改革:
实验单独设课, 强调上机实践能力 数据结构课程: 理论课(68课时4学分)+实验课(24课时1.5 学分) 课程考核
1.3 基本概念和术语
1、 2、 3、 4、 5、 6、 数据 数据元素 数据对象 数据结构 数据类型 抽象数据类型
1. 数据 能输入到计算机中的符号集 数据: 合. 2. 数据元素 数据的基本单位. 数据元素: 3. 数据对象 数据对象: 具有相同性质的数据元素的集合. 4. 数据结构: DATA STRUCTURE 数据结构: 数据及其相互关 系的集合. 分为逻辑结构和存储结构(物理结 构). 数据结构-------------------------------类 数据结构----------------类 CLASS
数据的存储结构
1. 顺序存储结构 顺序存储结构：借助元素在存储器中的相对位置 来表示数据元素间的逻辑关系。 【例1.4】对于表1-1提出的学生信息登记表进行存储， 假定每个元素占用50个存储单元，数据从1000号单 元开始由低地址向高地址存放，对应的顺序存储结 构如表1-3所示。
数据的存储结构
顺序存储结构的主要特点： 可实现对各数据元素的随机访问。这是 因为只要知道存储的首地址以及每个数 据元素所占的存储单元，就可以计算出 各数据元素的存储地址。 不利于修改，在对数据元素进行插入、 删除运算时可能要移动一系列的数据元 素。
抽象数据类型的定义： 抽象数据类型的定义：
ADT： ADT：抽象数据类型名 data 数据元素之间逻辑关系定义 operation 操作1 操作1 操作2 操作2
……
操作n 操作n
抽象数据类型 的不同视图
1.4 1.4 算法和算法分析
1. 定义：算法（Algorithm）是对特定问题求 定义：算法（Algorithm） 解步骤的一种描述，它是指令的有限序列， 解步骤的一种描述，它是指令的有限序列，其 中每一条指令表示一个或多个操作。 中每一条指令表示一个或多个操作 特性： 2. 特性：
数据结构实验一顺序表
数据结构实验一1、实验目的∙掌握线性表的逻辑特征∙掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算2、实验内容：建立顺序表，完成顺序表的基本操作：初始化、插入、删除、逆转、输出、销毁, 置空表、求表长、查找元素、判线性表是否为空；1．问题描述：利用顺序表,设计一组输入数据（假定为一组整数），能够对顺序表进行如下操作：∙创建一个新的顺序表，实现动态空间分配的初始化；∙根据顺序表结点的位置插入一个新结点(位置插入)，也可以根据给定的值进行插入(值插入)，形成有序顺序表；∙根据顺序表结点的位置删除一个结点(位置删除)，也可以根据给定的值删除对应的第一个结点，或者删除指定值的所有结点(值删除)；∙利用最少的空间实现顺序表元素的逆转；∙实现顺序表的各个元素的输出；∙彻底销毁顺序线性表，回收所分配的空间；∙对顺序线性表的所有元素删除，置为空表；∙返回其数据元素个数；∙按序号查找，根据顺序表的特点，可以随机存取，直接可以定位于第i 个结点，查找该元素的值，对查找结果进行返回；∙按值查找，根据给定数据元素的值，只能顺序比较，查找该元素的位置，对查找结果进行返回；∙判断顺序表中是否有元素存在，对判断结果进行返回；.编写主程序，实现对各不同的算法调用。
2．实现要求：∙“初始化算法”的操作结果：构造一个空的顺序线性表。
对顺序表的空间进行动态管理，实现动态分配、回收和增加存储空间；∙“位置插入算法”的初始条件：顺序线性表L 已存在，给定的元素位置为i，且1≤i≤ListLength(L)+1 ；操作结果：在L 中第i 个位置之前插入新的数据元素e，L 的长度加1；∙“位置删除算法”的初始条件：顺序线性表L 已存在，1≤i≤ListLength(L) ；操作结果：删除L 的第i 个数据元素，并用e 返回其值，L 的长度减1 ；∙“逆转算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行交换，为了使用最少的额外空间，对顺序表的元素进行交换；∙“输出算法”的初始条件：顺序线性表L 已存在；操作结果：依次对L 的每个数据元素进行输出；∙“销毁算法”初始条件：顺序线性表L 已存在；操作结果：销毁顺序线性表L；∙“置空表算法”初始条件：顺序线性表L 已存在；操作结果：将L 重置为空表；∙“求表长算法”初始条件：顺序线性表L 已存在；操作结果：返回L 中数据元素个数；∙“按序号查找算法”初始条件：顺序线性表L 已存在，元素位置为i，且1≤i≤ListLength(L)操作结果：返回L 中第i 个数据元素的值∙“按值查找算法”初始条件：顺序线性表L 已存在，元素值为e；操作结果：返回L 中数据元素值为e 的元素位置；∙“判表空算法”初始条件：顺序线性表L 已存在；操作结果：若L 为空表，则返回TRUE，否则返回FALSE；分析: 修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。
数据结构第1章
example P9
抽象数据类型的表示与实现（看书中P10-13）
20
三、算法的概念和描述：
什么是算法？
所谓算法（Algorithm)是描述计算机 解决给定问题的操作过程（解题方 法），即为解决某一特定问题而由若 干条指令组成的有穷序列。
21
一个算法必须满足以下五个特性：
有穷性
（1）数据元素自身值的表示 （2）该结点与其它结点关系的域
两种基本的存储方法：
（1）顺序存储方法（结构） （2）链接存储方法（链式存储结构） 同一种逻辑结构可采用不同的存储方法，这 主要考虑的是运算方便及算法的时空要求。
14
逻辑结构、存储结构小结：
（1）数据的逻辑结构、存储结构和数据的 运算（算法）构成了数据结构三个方面的 含义。
18
抽象数据类型 是指一个数学模型以及定义在此数学模型上的 一组操作 数据结构+定义在此数据结构上的一组操作 = 抽象数据类型 例如：矩阵 +（求转置、加、乘、 求逆、求特征值） 构成一个矩阵的抽象数据类型
19
抽象数据类型的描述 抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P 是对D的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名
（2）程序设计的实质是对实际问题选择一 个好的数据结构，加之设计一个好的算法。 而好的算法在很大程度上取决于描述实际 问题的数据结构。
15
为什么学习数据结构？数据结构是什么？
16
二、抽象数据类型
17
数据类型（data type）：在一种程序设计语
抽象数据类型的表示与实现（看书中P10-13）
20
三、算法的概念和描述：
什么是算法？
所谓算法（Algorithm)是描述计算机 解决给定问题的操作过程（解题方 法），即为解决某一特定问题而由若 干条指令组成的有穷序列。
21
一个算法必须满足以下五个特性：
有穷性
（1）数据元素自身值的表示 （2）该结点与其它结点关系的域
两种基本的存储方法：
（1）顺序存储方法（结构） （2）链接存储方法（链式存储结构） 同一种逻辑结构可采用不同的存储方法，这 主要考虑的是运算方便及算法的时空要求。
14
逻辑结构、存储结构小结：
（1）数据的逻辑结构、存储结构和数据的 运算（算法）构成了数据结构三个方面的 含义。
18
抽象数据类型 是指一个数学模型以及定义在此数学模型上的 一组操作 数据结构+定义在此数据结构上的一组操作 = 抽象数据类型 例如：矩阵 +（求转置、加、乘、 求逆、求特征值） 构成一个矩阵的抽象数据类型
19
抽象数据类型的描述 抽象数据类型可用（D，S，P）三元组表示 其中，D是数据对象，S是D上的关系集，P 是对D的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名
（2）程序设计的实质是对实际问题选择一 个好的数据结构，加之设计一个好的算法。 而好的算法在很大程度上取决于描述实际 问题的数据结构。
15
为什么学习数据结构？数据结构是什么？
16
二、抽象数据类型
17
数据类型（data type）：在一种程序设计语
数据结构实验报告1-线性结构的顺序存储
评定等级为：优秀、良好、中等、及格、不及格
教师签名： 2008 年 月 日
第2页共2页
2、参照课本，定义一个向量类模板，编写它的成员函数模板，对类模板加以实现；编写向量的并、 交运算功能函数；编写主程序，对两个向量进行分别进行合并、交运算。
3、通过阅读课本栈类板代码，理解栈类操作特点；编写一个借助于栈，将二进制数转换为十进制数 字串的程序；编写汉诺塔问题程序，理解函数的递归调用。
4、参照课本，定义一个顺序队列类模板，编写它的成员函数模板 ，对类模板加以实现；编写主程序， 对队列进行各种基本操作，理解队列的操作特性。
五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页）
通过本次实验，基本上能够理解线性结构的顺序存储方式及各种不同线性结构的操作方式；顺序存 储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里结点之间 的关系由存储单元的邻接关系来体现。线性表、向量、栈、队列都属于线性结构的顺序存储，各结点的 物理地址是相邻的，每一次插入、删除运算会引起相应结点物理地址的重新排列；栈的操作特点是先进 后出，而队列的操作特点是先进先出。
2、 对两个向量进行合并、交运算，结果如下： 输入向量 La 的结点元素：1 2 3 4 5，输入 Lb 的结点元素：1 2 3 4 5 6，则两向量的交集为：1 2 3 4 5；并集为：1 2 3 4 5 6。
3、（1）将二进制数转换为十进制数字串的程序，结果如下： 输入要转换的带符号整数 x:+3;则 x 转换成十进制数字串输出为：+3
Байду номын сангаас
第1页共2页
四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）
1、 对线性表进行插入、删除、定位等操作，结果如下： 输入线性表元素：1 2 3 4 5，（1）选择插入，输入插入位置 2，插入值 9，则新的线性表为：1 2 9 3 4 5；（2）选择删除，输入删除元素序号 5，则新的线性表为：1 2 9 3 4；（3）选择取值，输入要求 值元素序号 2，则屏幕输出：第２个元素的值为 9；（4）选择查找，输入要查找的元素值 9，则屏幕输 出：要查找元素的序号为 2。
教师签名： 2008 年 月 日
第2页共2页
2、参照课本，定义一个向量类模板，编写它的成员函数模板，对类模板加以实现；编写向量的并、 交运算功能函数；编写主程序，对两个向量进行分别进行合并、交运算。
3、通过阅读课本栈类板代码，理解栈类操作特点；编写一个借助于栈，将二进制数转换为十进制数 字串的程序；编写汉诺塔问题程序，理解函数的递归调用。
4、参照课本，定义一个顺序队列类模板，编写它的成员函数模板 ，对类模板加以实现；编写主程序， 对队列进行各种基本操作，理解队列的操作特性。
五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页）
通过本次实验，基本上能够理解线性结构的顺序存储方式及各种不同线性结构的操作方式；顺序存 储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里结点之间 的关系由存储单元的邻接关系来体现。线性表、向量、栈、队列都属于线性结构的顺序存储，各结点的 物理地址是相邻的，每一次插入、删除运算会引起相应结点物理地址的重新排列；栈的操作特点是先进 后出，而队列的操作特点是先进先出。
2、 对两个向量进行合并、交运算，结果如下： 输入向量 La 的结点元素：1 2 3 4 5，输入 Lb 的结点元素：1 2 3 4 5 6，则两向量的交集为：1 2 3 4 5；并集为：1 2 3 4 5 6。
3、（1）将二进制数转换为十进制数字串的程序，结果如下： 输入要转换的带符号整数 x:+3;则 x 转换成十进制数字串输出为：+3
Байду номын сангаас
第1页共2页
四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）
1、 对线性表进行插入、删除、定位等操作，结果如下： 输入线性表元素：1 2 3 4 5，（1）选择插入，输入插入位置 2，插入值 9，则新的线性表为：1 2 9 3 4 5；（2）选择删除，输入删除元素序号 5，则新的线性表为：1 2 9 3 4；（3）选择取值，输入要求 值元素序号 2，则屏幕输出：第２个元素的值为 9；（4）选择查找，输入要查找的元素值 9，则屏幕输 出：要查找元素的序号为 2。
数据结构第一章--绪论(严蔚敏版)
解 T = (D, R ) D={A,B,a,b,c }
R是D上的关系的集合 是 上的关系的集合
A
B
a R={ P1,P2 } P1 ={<A,a>, <A,b>, <A,c>} P2 ={<B,a>, <B,b>, <B,c>}
b
c
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数可以表示为 a+bi 一个复数可以表示为 复数 C={a,b}
也可以表示成一个有序对 <a, b>
∴这里存在一种关系 P ={<a,b>} (只有一个有序对 只有一个有序对) 只有一个有序对
而R是C上的关系的集合 R={ P } 是 上的关系的集合
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数的数据结构为 Complex= (C , R) 其中， 其中， C={a,b} R={ P } P ={<a,b>}
a b c
解 其数据结构可描述为 d e T = (D, R ) D是数据元素的集合 D={a,b,c,d,e} 是数据元素的集合
R是D上的关系的集合 R={ P } 是 上的关系的集合
P ={<a,b>,<a,c>,<b,d>,<b,e>}
例2
一小组有a,b,c 三个学生，一个导师A 一小组有a,b,c 三个学生，一个导师A 和一个辅导员B 和一个辅导员B，此小组的数据结构如图：
48
ADT 抽象数据类型名 { 数据对象： 数据对象：〈数据对象的定义〉 数据关系： 数据关系：〈数据关系的定义〉 基本操作： 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 基本操作名 初始条件：〈初始条件描述〉 初始条件： 操作结果：〈操作结果描述〉 操作结果
数据结构(一)
数据的逻辑结构
•线性结构 •树形结构 •图状结构 •集合结构
差不多概念
差不多概念
线性结构 结构中有且仅有一个始结点和一个终结点，
每个内结点有且仅有一个前趋结点和一个后继 结点。
非线性结构 结构中的结点可能有多个前趋结点和多个后
继结点。
差不多概念
一行表示一个结点（元素），每个结点由学号、姓名、性别等九个 域（数据项）组成。
// 以二维数组存储矩阵元素，c 为 a 和 b 的乘积
for (i=0; i<n; ++i)
for (j=0; j<n; ++j) {
c[i][j] = 0;
for (k=0; k<n; ++k)
c[i][j] += a[i][k]*b[k][j]; } //for
O(n3)
} //mult
例子：
可读性: 可读性好的算法有助于设计者和他人阅读、理 解、修改和重用。晦涩难读的程序易于隐藏较多错误。
坚固性: 当输入数据非法时，算法能适当地作出合适的 反应。
高效率与低存储量需求:通常，效率指的是算法执行时间； 存储量指的是算法执行过程中所需的最大存储空间，两 者都与问题的规模有关。
差不多概念
假设所需额外空间相关于输入数据量来说是常 数，那么称此算法为原地工作。
若所需存储量依赖于特定的输入，则通常按最 坏情况考虑。
差不多概念
数据类型
在用高级程序语言编写的程序中，必须对程序中出现 的每个变量、常量或表达式，明确说明它们所属的数据 类型。
不同类型的变量，其所能取的值的范围不同， 所能进行的操作不同。 数据类型是一个值的集合和定义在此集合上的 一组操作的总称。
中国地质大学2011数据结构试卷及其答案-(1)
A.125436B.325641C.342165D.546231
5.若用数组A[60]存放循环队列的元素，已知头指针值为35，当前队列中有40个元素，则队列的尾指针值为( C )。约定头指针指向队头元素的前一个位置。
解答：(35+40)%60=15
A.75B.20C.15D.5
6.深度为6的完全二叉树（根结点的深度为0）至少有（B）个结点。
答：
（1）描述算法的基本设计思想（3分）
设置遍历指针p和计数器j，以及指向偶数项表尾的指针。将偶数项从原表中删除，插在偶数项表尾。
（2）描述算法的详细实现步骤（4分）略
（3）根据设计思想和实现步骤，采用C语言描述算法，关键处请给出注释（5分）略
（4）算法时间复杂度：O(n).（1分）
A.32B.64C.127D.128
解答：第0-5层全满，第6层1个，1+2+4+8+16+32+1=64个。
7.将一棵森林F转换为孩子兄弟链表表示的二叉树T，则F的后根遍历是T的（B）。
A.前序遍历B.中序遍历C.后序遍历D.层序遍历
8.假设使用图的深度优先搜索DFS算法从根开始遍历一棵二叉树，先访问左子树再访问右子树，则访问结点的顺序相当于二叉树的（A）序列。
MON
TUE
SUN
【评分说明】所画的散列表长度正确（长度为10，下标从0到9），给1分。填写关键字正确，每个给1分。考生可以不写出计算过程。若解答部分正确，酌情给分。
（2）查找成功的平均查找长度：（2分）
因为查找长度为1的关键字有4个，查找长度为2的关键字有1个，查找长度为3的关键字有2个，所以查找成功的平均查找长度：
（3）根据设计思想和实现步骤，采用C语言描述算法，关键处请给出注释（5分）略
5.若用数组A[60]存放循环队列的元素，已知头指针值为35，当前队列中有40个元素，则队列的尾指针值为( C )。约定头指针指向队头元素的前一个位置。
解答：(35+40)%60=15
A.75B.20C.15D.5
6.深度为6的完全二叉树（根结点的深度为0）至少有（B）个结点。
答：
（1）描述算法的基本设计思想（3分）
设置遍历指针p和计数器j，以及指向偶数项表尾的指针。将偶数项从原表中删除，插在偶数项表尾。
（2）描述算法的详细实现步骤（4分）略
（3）根据设计思想和实现步骤，采用C语言描述算法，关键处请给出注释（5分）略
（4）算法时间复杂度：O(n).（1分）
A.32B.64C.127D.128
解答：第0-5层全满，第6层1个，1+2+4+8+16+32+1=64个。
7.将一棵森林F转换为孩子兄弟链表表示的二叉树T，则F的后根遍历是T的（B）。
A.前序遍历B.中序遍历C.后序遍历D.层序遍历
8.假设使用图的深度优先搜索DFS算法从根开始遍历一棵二叉树，先访问左子树再访问右子树，则访问结点的顺序相当于二叉树的（A）序列。
MON
TUE
SUN
【评分说明】所画的散列表长度正确（长度为10，下标从0到9），给1分。填写关键字正确，每个给1分。考生可以不写出计算过程。若解答部分正确，酌情给分。
（2）查找成功的平均查找长度：（2分）
因为查找长度为1的关键字有4个，查找长度为2的关键字有1个，查找长度为3的关键字有2个，所以查找成功的平均查找长度：
（3）根据设计思想和实现步骤，采用C语言描述算法，关键处请给出注释（5分）略
数据结构课程1
-------------------
-------
-------
-------
-------
-------
这张表中的元素存在一个顺序关系，即谁在谁前，谁在谁 后的信息（即病人诊断顺序依次为张立，田方，……） 。 所以，可以用线性结构来刻画这种关系。。
例1-3 大学系级行政机构
大学系级行政机构，如图1.1所示：
数据结构的含义
因此可以认为，数据结构是介于数学、计算机硬件和计 算机软件三者之间的一门核心课程（如图1.1所示）。
数学
代数系统
编码理论 数据类型 算子关系
数据表示法
数据的操作 文件系统
存储装置
数据结构
硬件
数据存取
（ 计 算 机 系机器组织
统设计）
数据组织
信息检索
软件
（计算机程 序设计）
图1.1 “数据结构”所处的地位
3. 数据的操作
一般而言，必须对数据进行加工处理，才能得到问题的 解。在非数值性问题中，对数据的操作（或运算）已不限 于对数据进行加、减、乘、除等数学运算。数据的操作是 定义在逻辑结构上的，而操作的具体实现是在存储结构上 进行的。基本的数据操作主要有以下几种：
（1）查找：在数据结构中寻找满足某个特定条件的数据元 素的位置或值。
现实问
数学模
算法
程序
解
题
型
图1.8 计算机求解问题的流程
即首先要从现实问题出发，抽象出一个适当的数学模型，
然后设计一个求解此数学模型的算法，最后根据这个算法 编出程序，经过测试、排错、运行直至得到最终的解答。 （现实）问题、数学模型、算法和程序是问题求解过程中 出现的四个不同的概念。
数据结构 耿国华 西北大学 1-1数据结构的基础概念
第 1 章 绪论 1.3 算法设计
设计的要求：
② 可读性
一个好的算法首先应该便于 人们理解和相互交流，其次才 是机器可执行。可读性好的算 法有助于人对算法的理解，反 之难懂的算法易于隐藏错误且 难于调试和修改。
27
第 1 章 绪论 1.3 算法设计
设计的要求： ③ 健壮性
即对非法输入的抵抗能力。 它强调的是，如果输入非法 数据，算法应能加以识别并 做出处理，而不是产生误动 作或陷入瘫痪。
能输入机器且能被处理的各种符号集合。
数据包含整型、实型、布尔型、图象、
字符、声音等一切可以输入到计算机中的符号
集合。
返回 4
第 1 章 绪论
1.1 数据结构的基础概念
记录
数据元素（Data Element）：
是组成数据的基本单位 ，是数据集合的个体，
在计算机中通常作为一个整体进行考虑和处理
例如。：
算法描述的常用工具 1.自然语言 2. 框图 3. 类语言(伪语言) 类语言： 类语言是接近于高级语言而又不是严格 的高级语言。具有高级语言的一般语句 设施，撇掉语言中的细节，以便把注意
33
力主要集中在算法处理步骤本身的描述上。返回
第 1 章 绪论 1.5 对算法作性能评价
性能评价 有关数量关系计算
2
第 1 章 绪论
1.1 数据结构的基础概念
相关名词：
数据（Data） 数据元素（Data Element） 数据对象（Data Object） 数据结构（Data Structure） 数据类型(Data Type) 数据抽象与抽象数据类型
3
第 1 章 绪论 1.1 数据结构的基础概念
数据（Data）： 数据是描述客观事物的数值、字符以及
李春葆《数据结构教程》笔记和课后习题详解-第一章至第二章【圣才出品】
第1章绪论1.1复习笔记一、数据结构1．概述（1）计算机对具体问题的处理在用计算机解决一个具体的问题时，大致需要经过以下几个步骤：①分析问题，确定数据模型。
②设计相应的算法。
③编写程序，运行并调试程序，直至得到正确的结果。
（2）数据的含义①数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。
它是计算机操作的对象的总称，也是计算机所处理信息的某种特定的符号表示形式。
②数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，有些情况下数据元素也称为元素、结点、记录等。
一个数据元素可以由若干个数据项组成。
数据项是具有独立含义的数据的最小单位，也称为域。
③数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。
默认情况下，数据结构中的数据指的都是数据对象。
（3）数据结构的定义数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在特定关系的数据元素的集合，因此，可时把数据结构看成是带结构的数据元素的集合。
数据结构包括以下几个方面：①数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
数据的逻辑结构是从逻辑关系（主要指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。
数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（也称为映像），也是指逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。
一般情况下，只在高级语言（如C、C++、Java语言）的层次上讨论存储结构。
③施加在该数据上的操作，即数据的运算。
数据的运算是定义在数据的逻辑结构之上的，每种逻辑结构都有一组相应的运算。
数据结构第六版习题一答案
数据结构第六版习题一答案数据结构第六版习题一答案在学习数据结构的过程中，习题是帮助我们巩固知识、提高理解能力的重要方式之一。
本文将为大家提供数据结构第六版习题一的答案，希望能够帮助大家更好地理解和应用数据结构。
1. 问题描述：给定一个数组arr，长度为n，数组中的元素为整数。
请设计一个算法，找出数组中出现次数超过n/2的元素。
解答：可以使用摩尔投票算法来解决这个问题。
首先选取数组中的第一个元素作为候选元素，然后遍历数组，如果当前元素与候选元素相同，则计数器加1，否则计数器减1。
当计数器减到0时，将当前元素设置为新的候选元素。
遍历完数组后，候选元素即为出现次数超过n/2的元素。
2. 问题描述：给定一个链表，判断链表是否存在环。
解答：可以使用快慢指针的方法来解决这个问题。
定义两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。
如果链表存在环，那么快指针一定会追上慢指针，即它们会在某个节点相遇。
如果链表不存在环，那么快指针会先到达链表的末尾。
所以，我们可以通过判断快指针是否为空来确定链表是否存在环。
3. 问题描述：给定一个二叉树，判断它是否是平衡二叉树。
解答：可以使用递归的方法来解决这个问题。
首先定义一个函数来计算二叉树的高度，然后在判断平衡二叉树时，递归地计算左子树和右子树的高度差。
如果高度差大于1，或者左子树和右子树中存在不平衡的情况，则二叉树不是平衡二叉树。
如果左子树和右子树都是平衡二叉树，并且高度差小于等于1，则二叉树是平衡二叉树。
4. 问题描述：给定一个有序数组arr和一个目标值target，使用二分查找算法在数组中查找目标值的位置。
解答：可以使用二分查找算法来解决这个问题。
首先初始化左指针left为0，右指针right为数组长度减1。
然后进行迭代，直到左指针大于右指针为止。
在每一次迭代中，计算中间位置mid，如果中间元素等于目标值，则返回mid。
如果中间元素大于目标值，则将右指针更新为mid-1。
数据结构习题及答案-第1章 绪论
第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。
【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。
【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。
【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。
【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、3（1分）】A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。
《数据结构与算法》考研真题精选-1
《数据结构与算法》考研真题精选一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A．(n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。
在此假定N为线性表中结点数，且每次查找都是成功的。
A.N+1B.2log2NC.logND.N/2E.Nlog2NF.N24. 下面关于二分查找的叙述正确的是( )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储5. 对线性表进行二分查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序6．适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序7. 用二分（对半）查找表的元素的速度比用顺序法( )A．必然快 B. 必然慢 C. 相等 D. 不能确定8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减9. 具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 510. 折半查找的时间复杂性为（）A. O（n2）B. O（n）C. O（nlog n）D. O（log n）11．当采用分快查找时，数据的组织方式为( )A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在(（2）)时其查找效率最低(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
数据结构--重修作业题(1)
第一章绪论一、选择题3。
在数据结构中，从逻辑上可以把数据结构分成（）(A)动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构5.算法分析的目的是（）。
（A) 找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性二、判断题1.数据的机内表示称为数据的存储结构。
（）2。
算法就是程序。
（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态.( ）三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型，其中树形结构和图形结构合称为_____.2.在线性结构中，第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点，其余每个结点有且只有_______个后续结点。
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点，其余每个结点的后续结点可以_________.4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。
5.线性结构中元素之间存在________关系，树形结构中元素之间存在______关系，图形结构中元素之间存在_______关系。
8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
9。
设有一批数据元素，为了最快的存储某元素，数据结构宜用_________结构，为了方便插入一个元素,数据结构宜用____________结构。
四、算法分析题，求下列算法段的语句频度及时间复杂度for （i=1；i<=n;i++）for (j=1;j〈=i；j++)for （k=1;k<=j；k++)x=i+j—k；第二章线性表一、选择题1。
数据结构-1_真题-无答案
数据结构-1(总分100,考试时间90分钟)一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的1. 设数组data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )A. front:=front+1B. front:=(front+1)mod mC. rear:=(rear+1)mod mD. front:=(front+1)mod(m+1)2. 在Hash函数H(k)=k MOD m中，一般来讲，m应取( )A. 奇数B. 偶数C. 素数D. 充分大的数3. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。
A. 二叉链表B. 广义表C. 三叉链表D. 顺序4. 向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )A. Top—＞next=s;B. s—＞next=Top—＞next;Top—＞next=s;C. s—＞next=Top;top=s;D. s—＞next=Top; Top=Top—＞next;5. 快速排序在最坏情况下的时间复杂度是( )A. O(nlogB. O(n2)C. O(n3)D. 都不对6. 内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。
A. 归并排序B. 插入排序C. 快速排序D. 选择排序7. 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )A. (N-1)×(N-1)B. N×NC. (N+1)×(N+1)D. 不确定8. 在一个长度为n的顺序表(顺序存储的线性表)中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动( )个元素。
A. n-iB. n-i+1C. n-i-1D. i9. 下面四种排序方法中，平均查找长度最小的是( )A. 插入排序B. 选择排序C. 快速排序D. 归并排序10. 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高h≥2)。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
循环实现
递归பைடு நூலகம்现
令 N = 100, 1000, 10000, 100000, ……
例2：写程序实现一个函数PrintN，使得 传入一个正整数为N的参数后，能顺序 打印从1到N的全部正整数
#include <stdio.h> void PrintN ( int N ); int main () { int N; scanf("%d", &N); PrintN( N ); return 0; }
clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个 时间单位是clock tick，即“时钟打点”。 常数CLK_TCK：机器时钟每秒所走的时钟打点数。
#include <stdio.h> #include <time.h> clock_t start, stop; /* clock_t是clock()函数返回的变量类型 */ double duration; /* 记录被测函数运行时间，以秒为单位 */ int main () { /* 不在测试范围内的准备工作写在clock()调用之前*/ /* 开始计时 */ start = clock(); MyFunction(); /* 把被测函数加在这里 */ stop = clock(); /* 停止计时 */ duration = ((double)(stop - start))/CLK_TCK; /* 计算运行时间 */ /* 其他不在测试范围的处理写在后面，例如输出duration的值 */ return 0; }
数据对象集 数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
与存放数据的机器无关 与数据存储的物理结构无关 与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集“是什么”，并不涉及 “如何做到”的问题
例4：“矩阵”的抽象数据类型定义
类型名称：矩阵（Matrix）
f ( x ) a0 x(a1 x ( (a n1 x (a n ))))
double f( int n, double a[], double x ) { int i; double p = a[n]; for ( i=n; i>0; i-- ) p = a[i-1] + x*p; return p; }
先定类别，再二分查找
问题：空间如何分配？类别应该分多细？
解决问题方法的效率， 跟数据的组织方式有关
例2：写程序实现一个函数PrintN，使得 传入一个正整数为N的参数后，能顺序 打印从1到N的全部正整数
void PrintN ( int N ) { int i; for ( i=1; i<=N; i++ ){ printf(“%d\n”, i ); } return; } void PrintN ( int N ) { if ( N ){ PrintN( N – 1 ); printf(“%d\n”, N ); } return; }
二维数组？一维数组？十字链表？
数据对象集：一个MN的矩阵AMN = (aij) (i=1, …, M; j=1, …, N )由MN个三 元组< a, i, j >构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素 所在的列号。
操作集：对于任意矩阵A、B、C Matrix，以及整数i、j、M、N Matrix Create( int M, int N )：返回一个MN的空矩阵； int GetMaxRow( Matrix A )：返回矩阵A的总行数； int GetMaxCol( Matrix A )：返回矩阵A的总列数； ElementType GetEntry( Matrix A, int i, int j )：返回矩 阵A的第i行、第j列的元素； Matrix Add( Matrix A, Matrix B )：如果A和B的行、列数一 致，则返回矩阵C=A+B，否则返回错误标志； Matrix Multiply( Matrix A, Matrix B )：如果A的列数等于B 的行数，则返回矩阵C=AB，否则返回错误标志； …… 先按行加？先按列加？什么语言？
图书的摆放要使得2个相关操作方便实现：
操作1：新书怎么插入？
操作2：怎么找到某本指定的书？
例1：如何在书架上摆放图书？
方法1：随便放
操作1：新书怎么插入？
哪里有空放哪里，一步到位！
操作2：怎么找到某本指定的书？
……累死
例1：如何在书架上摆放图书？
方法2：按照书名的拼音字母顺序排放
#include <stdio.h> #include <time.h> #include <math.h> clock_t start, stop; double duration; #define MAXN 10 /* 多项式最大项数，即多项式阶数+1 */ double f1( int n, double a[], double x ); double f2( int n, double a[], double x ); int main () { int i; double a[MAXN]; /* 存储多项式的系数 */ for ( i=0; i<MAXN; i++ ) a[i] = (double)i; start = clock(); f1(MAXN-1, a, 1.1); stop = clock(); duration = ((double)(stop - start))/CLK_TCK; printf("ticks1 = %f\n", (double)(stop - start)); printf("duration1 = %6.2e\n", duration); start = clock(); f2(MAXN-1, a, 1.1); stop = clock(); duration = ((double)(stop - start))/CLK_TCK; printf("ticks2 = %f\n", (double)(stop - start)); printf("duration2 = %6.2e\n", duration); return 0; }
f ( x ) i 0 i x i
9
让被测函数重复运行充分多次，使得测出的总的时钟打点 间隔充分长，最后计算被测函数平均每次运行的时间即可!
#include <stdio.h> #include <time.h> #include <math.h>
……
#define MAXK 1e7 /* 被测函数最大重复调用次数 */
……
int main () {
……
start = clock(); for ( i=0; i<MAXK; i++ ) /* 重复调用函数以获得充分多的时钟打点数*/ f1(MAXN-1, a, 1.1); stop = clock(); duration = ((double)(stop - start))/CLK_TCK/MAXK; /* 计算函数单次运行的时间 */ printf("ticks1 = %f\n", (double)(stop - start)); printf("duration1 = %6.2e\n", duration);
Clifford A.Shaffer，《数据结构与算法分析》
“数据结构（data structure）是计算机中存储、组织 数据的方式。通常情况下，精心选择的数据结构可以 带来最优效率的算法。”
中文维基百科
例1：如何在书架上摆放图书？
例1：如何在书架上摆放图书？
例1：如何在书架上摆放图书？
操作1：新书怎么插入？
新进一本《阿Q正传》……
操作2：怎么找到某本指定的书？
二分查找！
例1：如何在书架上摆放图书？
方法3：把书架划分成几块区域，每块区域指定摆放 某种类别的图书；在每种类别内，按照书名的拼音 字母顺序排放
操作1：新书怎么插入？
先定类别，二分查找确定位置，移出空位
操作2：怎么找到某本指定的书？
第一讲 基本概念
浙江大学 陈 越
1.1 什么是数据结构
官方统一定义—— 没有……
“数据结构是数据对象，以及存在于该对象的实例和 组成实例的数据元素之间的各种联系。这些联系可以 通过定义相关的函数来给出。”
Sartaj Sahni，《数据结构、算法与应用》
“数据结构是ADT（抽象数据类型 Abstract Data Type）的物理实现。”
例3：写程序计算给定多项式 在给定点 x = 1.1 处的值 f(1.1)
f ( x ) i 0 i x i
9
double f1( int n, double a[], double x ) { int i; double p = a[0]; for ( i=1; i<=n; i++ ) p += (a[i] * pow(x, i)); return p; } double f2( int n, double a[], double x ) { int i; double p = a[n]; for ( i=n; i>0; i-- ) p = a[i-1] + x*p; return p; }