当前位置：文档之家 › 南京大学数据结构(商琳)chapter1

南京大学数据结构(商琳)chapter1

  • 格式：ppt
  • 大小：351.50 KB
  • 文档页数：52

下载文档原格式

  / 52

合集下载

第1章-概论数据结构

第1章-概论数据结构

void PrintN ( int N ) { int i; for ( i=1; i<=N; i++ ) printf(“%d\n”, i ); return; }
void PrintN ( int N ) { if ( !N ) return; PrintN( N – 1 ); printf(“%d\n”, N ); return; }
直接法快了一个数量级！
int main () { /* 不在测试范围内的准备工作写在 clock()调用之前*/ 为什么会这样？ start = clock(); /* 开始计时 */ function(); /* 把被测函数加在这里 */ stop = clock(); /* 停止计时 */ duration = ((double)(stop - start))/CLK_TCK;/* 计算运行时间 */ /* 其他不在测试范围的处理写在后面，例如输出duration的值 */ return 0; }
11/25
第1章 概论
§3.3 复杂度的渐进表示法
如何来“度量”一个算法的时间复杂度呢？
首先，它应该与运行该算法的机器和编译器无关； 其次，它应该与要解决的问题的规模 n 有关；
（有时，描述一个问题的规模需要多个参数）
再次，它应该与算法的“1步”执行需要的工作量无关！
所以，在描述算法的时间性能时，人们只考虑宏观渐近性质， 即当输入问题规模 n“充分大”时，观察算法复杂度随着 n 的 “增长趋势”： 当变量n不断增加时，解决问题所需要的时间的增长关系。 比如：线性增长 T(n) = c· n 即问题规模n增长到2倍、3倍……时，解决问题所需要的时间T(n)也 是增长到2倍、3倍……（ 与c无关 ）

《数据结构》课件

《数据结构》课件

查找操作
顺序查找
二分查找
链表查找
在顺序存储结构的线性表中，查找操 作需要从线性表的第一个节点开始， 逐个比较节点的数据域，直到找到目 标数据或遍历完整个线性表。时间复 杂度为O(n)。
在有序的顺序存储结构的线性表中， 查找操作可以采用二分查找算法。每 次比较目标数据与中间节点的数据域 ，如果目标数据大于中间节点，则在 右半部分继续查找；否则在左半部分 查找。时间复杂度为O(log n)。
数据结构是算法的基础。许多算法的实现需要依赖于特定的数据结构， 因此掌握常见的数据结构是编写高效算法的关键。
数据结构在解决实际问题中具有广泛应用。无论是操作系统、数据库系 统、网络通信还是人工智能等领域，数据结构都发挥着重要的作用。
数据结构的分类
根据数据的逻辑关系，数据结构可以分为线性结构和非线 性结构。线性结构如数组、链表、栈和队列等，非线性结 构如树形结构和图形结构等。
04
数据结构操作
插入操作
顺序插入
在顺序存储结构的线性表中，插入操作 需要找到插入位置的前驱节点，修改前 驱节点的指针，使其指向新节点，然后 让新节点指向后继节点。如果线性表的 第一个节点是空节点，则将新节点作为 第一个节点。
VS
链式插入
在链式存储结构的线性表中，插入操作需 要找到插入位置的前驱节点，修改前驱节 点的指针，使其指向新节点。如果线性表 的第一个节点是空节点，则将新节点作为 第一个节点。
图
01
02
03
04
图是一种非线性数据结构，由 节点和边组成，其中节点表示 数据元素，边表示节点之间的
关系。
图具有网络结构，节点之间的 关系可以是任意复杂的，包括
双向、单向、无向等。

数据结构第1章

数据结构第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）：在一种程序设计语

电子教案 《数据结构(C++版)(第二版)》-李根强

电子教案 《数据结构(C++版)(第二版)》-李根强
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会 不断变化。但有时我们想知道它变化时呈现什么规律，为此，引入时间复杂度概 念。 设两T个(n正)的的一常个数辅A和助B函（数其为中g(An≤)B，）定，义使为得当An≤大于等≤BT于g均((nn某))成一立足，够或大有的正整=A数，nlinm0（时Tg((其nn，)) 中存A在 为常数），则称g(n)是T(n)的同数量级函数。把T(n)表示成数量级的形式为：T(n)= Ｏ(g(n)),其中大写字母Ｏ为英文Order（即数量级）一词的第一个字母。
（10）C++的作用域 在C++中，每个变量都有一个作用域。在函数内声明的变量，仅能在该函数内部有 效，在类中声明的变量，可以在该类内部有效。在整个程序中都能使用的变量， 为全局变量，否则称为局部变量。若一个全局变量与一个局部变量同名，则该范 围内全局变量不起作用。若要使之起作用，可以使用域操作符∷来实现。
5
1.1.2 基本术语
1．数据（data） 数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。 例如：数字、字母、汉字、图形、图像、声音都称为数据。
2．数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位，但它还可以分割成若 干个具有不同属性的项（字段），故不是组成数据的最小单位。
【例1-5】设有一个线性表（a1,a2,a3,a4,a5），它的抽象描述可表示为 D=(K,R)，其中K={a1,a2,a3,a4,a5}，R={<a1,a2>,<a2,a3>,<a3,a4>,<a4,a5>}，则 它的逻辑结构的图形描述如下。
a1

数据结构第一章2

数据结构第一章2

◆ 删除
线性表的删除运算是使长度为n的 线性表的删除运算是使长度为 的 线性表（ 线性表（a0,a1,…,ai-1,ai, ai+1,…,an-1)变成长 变成长 度为n-1的线性表 的线性表（ 度为 的线性表（a0,a1,…,ai-1,ai+1,…,an-1)。 。
0 1
┇
a0 a1
┇
0 1
┇
逻辑操作：设L为 List 型的线性表 为
ListInitiate(L) //构造一个空的线性表L。 ListLength(L) //返回线性表L中的当前元素个数。 ListInsert(L,i,x) //在线性表L的第i个位置前插入一个值
为x 的新元素，插入成功返回1，失败返回0。 0≤i≤n，插入后表L的长度为n+1。
┇ MaxSize-1 -
插入过程动态演示
插入算法： 插入算法：
int ListInsert(SeqList *L, int i, DataType x) { int j; if ( L->size>=MaxSize) //若表空间溢出，退出运行 若表空间溢出， 若表空间溢出 { printf(“表已满不能插入！\n”); return 0; } 表已满不能插入！ 表已满不能插入 if ( i<0‖i>L->size) //非法位置，退出运行 非法位置， ‖ 非法位置 { printf(“i值不合法！\n”); return 0; } 值不合法！ 值不合法 for ( j=L->size; j>i; j--) L->list[j]=L->list[j-1]; //元素后移 元素后移 L->list[i]=x; //插入 插入x 插入 (L->size)++; //表长加 表长加1 表长加 return 1; }

数据结构1

数据结构1

24
1.3 算法评价 1、算法的性能标准 正确性 可读性 效率 健壮性 空间复杂度
25
1.3 算法评价 2、算法的效率 算法的后期测试

算法的事前估计
该语句的执行次数.
(1)频度
26
例 以迭代方式求累加和的函数
float sum ( float a[ ], int n ) { float s = 0.0; for ( int i = 0; i < n; i++ ) s += a[i]; return s; }
集合
例 DS=(D,S) D={d1, d2, d3, d4,d5,d6 ,d7} S={R} d1 R , d2 R , d3R , d4 R , d5 R , d6 R , d7 R d1 d2 d3
d4
d5
d6
d7 集合特点： 结构中的数据元素只具有“ 同属于一个集合”的关系
算法描述 算法评价 与算法描述有关的C++知识
4
数据结构讨论的范畴
6845678是谁的电 话？ 太难找了！
电话号码本1 党政机关 党政机关 党政机关 党政机关 党委总机 4811122
大专院校 大专院校
党委总机 4811122 党委总机 4811122 党委总机 4811122 宣传部 4811234 宣传部 4811234 宣传部 4811234 宣传部 4812345 4811234 组织部 组织部 4812345 组织部 4812345 组织部 4812345
党政 机关
单专院校
预 料卫生
交通 y运输
内 蒙 古党委
内 蒙 古政 府
内 蒙 古大学
内 蒙古财 经学院

南京林业大学2022年[数据结构]考研真题

南京林业大学2022年[数据结构]考研真题

南京林业大学2022年[数据结构]考研真题一．是非题判断下列各题是否正确，正确的在括号内打 “√”，错的打“×”。

每小题2分，共20分。

1.数据的逻辑结构独立于计算机，物理结构依赖于计算机。

（）2.线性表、栈和队列的逻辑结构完全相同。

（）3.顺序存储方式只能用于存储线性结构。

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

（）5.先根遍历树和先序遍历与该树对应的二叉树，其结果不同。

（）6.外部排序与外部设备的特性无关。

（）7.不使用递归，也可以实现二叉树的先序、中序和后序遍历。

（）8.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。

（）9. 有回路的图不能进行拓扑排序。

（）10. 二叉排序树的查找和折半查找的时间性能相同。

（）二．单项选择题A.规则B.集合C.结构D.运算2．对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时大约要移动表中的______个元素。

A.n/2B.(n+1)/2C.(n-1)/2D.n3．线性表采用链式存储时，其地址______。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续与否均可以4．设有一个空栈，栈顶指针为1000H（十六进制，下同，且设每个入栈元素需要1个单位存储空间），现有输入序列为1，2，3，4，5，经过PUSH，PUSH ，POP，PUSH，POP，PUSH，POP，PUSH后，栈顶指针是______。

A.1002HB.1003HC.1004HD.1005H5．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是______。

Ａ. 4 B．5C．6 D．76．数组A[0..5,0..6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是______。

2018年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题【圣才出品】

2018年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题【圣才出品】

2018年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题（回忆版）赞个人品，趁热回忆下真题。

今年的题感觉和17年的难度差不多，数据结构依旧没有算法题（准备了那么多呀），除了软工题型也都是之前见过的题型，唯独操作系统的那个UNIX进程的那个，是期末试卷的一道选择题，当时看时就没懂，也就没印象了。

软工的题型一直很活，很少有原题，两道大题蒙着答的。

总的来讲都是比较基础的，有很多原题，期末试卷中那些难的题都没有考。

名词解释感觉重在理解名词的含义，没必要死背，考前各科整理了n多个名词解释，一直因为这个性价比最低的背不下来感到没谱，结果考试要么是比较简单的（如计网的），要么是压根就没整理到的（OS的就没整理到）。

PV算法的话感觉把课件上那几个都掌握了，也就没问题了（注:我是跨考的，有些语言描述可能不规范，望谅解）数据结构（45分）一、填空（3×5）1．一个t叉树，有n个叶子节点，s个非叶子节点，写出n和s的关系2．快速排序最坏情况下时间复杂度3．给出二叉树前序序列和中序序列，写出后序序列4．赫夫曼树，n个叶子节点，求总的节点个数5．一个平衡二叉树，加入一个关键字后，重新调整为平衡二叉树二、大题（10×3）1．对关键码序列{23，17，12，61，26，8，70，75，53}，用堆排序方法进行排序，画出排序过程中所建的初始堆，以及输出前三个关键码过程的示意图。

（要求建立的堆为任一父母结点的关键码都小于其子女结点的关键码）2．请画出往下图的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码100后得到的B-树。

3．按Dijkstra方法计算从顶点1到其它顶点的最短路径。

按路径递增顺序写出先后计算出的最短路径（包括起止点和途径各点）及该路径长度。

软件工程（45分）一、问答题（5×5）1．说明下工程和科学的区别（政治题走错片场了吧？）2．什么是集成测试，什么是单元测试，单元测试用例和集成测试用例有什么区别3．功能性需求和非功能性需求4．写出四个体系结构视角5．质量模型的可用性二、大题（10×2）1．一个购房评估系统，一个类中含有两个功能，一个是输入存款、月工资、月花销、想要购房面积……完后得出可以购房的面积和首付款，另一个功能是根据面积和首都得出一个各小区的的房价列表，供用户参考，问这种设计合理吗？不合理的话画出设计类图并写出类的定义（含属性和方法）2．一个计算税费的问题，根据什么一堆经济的指标什么印花税、公证费、契税、委托办理手续费、房屋买卖手续费啥的，计算出税费，各地的计算方法不同，要求能够灵活扩展，按照一种设计模式设计，画出设计类图并写出关键接口定义。

(NEW)南京大学《842数据结构、软件工程、操作系统和计算机网络》历年考研真题汇编

(NEW)南京大学《842数据结构、软件工程、操作系统和计算机网络》历年考研真题汇编
件工程部分）
2007年南京大学软件基础一考研 真题（操作系统、数据结构部
分）
2007年南京大学软件基础三考研 真题（操作系统、数据结构部
分）
2008年南京大学软件基础一考研 真题（含操作系统、数据结构部
分）
2008年南京大学软件基础二考研 真题（操作系统、数据结构部
二、算法题 1 长度为n的数组a[0…n－1]，编写一个算法在O（n）的时间复杂
度内将数组中所有负数放在非负数前面。
2 已知first为不带表头结点的单链表的表头指针（如下图所 示），链表中存储的都是整型数据，试写出求所有结点的data域平均值 的递归函数。（软院05年数据结构期末题）
3 假设以数组Q[m]存放循环队列中的元素，同时以rear和length分 别指示环形队列中的队尾位置和队列中所含元素的个数，试用C＋＋语 言写出一个程序，给出该循环队列的类声明，给出队空条件和队满条 件，并写出相应的插入元素（Add）和删除（Delete）元素的算法（用 类模板，函数模板形式写）（软院04年考研原题）
目 录
1996年南京大学计算机考研真题（操作系统、数据结构部分） 1997年南京大学计算机考研真题（操作系统、数据结构部分） 1998年南京大学计算机考研真题（操作系统、数据结构部分） 1999年南京大学计算机考研真题（操作系统、数据结构部分） 2000年南京大学计算机考研真题（操作系统、数据结构部分） 2001年南京大学计算机考研真题（操作系统、数据结构部分） 2002年南京大学计算机考研真题（操作系统、数据结构部分） 2003年南京大学计算机考研真题（操作系统、数据结构部分） 2004年南京大学软件基础一考研真题（操作系统、数据结构部分） 2004年南京大学软件基础三考研真题（操作系统、数据结构部分） 2005年南京大学软件基础一考研真题（操作系统、数据结构部分） 2005年南京大学软件基础二考研真题（操作系统、数据结构部分） 2006年南京大学软件基础一考研真题（操作系统、数据结构、软件工程 部分） 2007年南京大学软件基础一考研真题（操作系统、数据结构部分） 2007年南京大学软件基础三考研真题（操作系统、数据结构部分）

数据结构知识点全面总结—精华版

数据结构知识点全面总结—精华版

第1章绪论内容提要：◆数据结构研究的内容。

针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

数据——所有能被计算机识别、存储和处理的符号的集合。

数据元素——是数据的基本单位，具有完整确定的实际意义。

数据对象——具有相同性质的数据元素的集合，是数据的一个子集。

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。

◆算法的定义及五个特征。

算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。

①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。

时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。

◆用计算语句频度来估算算法的时间复杂度。

第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

通过指针来实现！◆线性表的操作在两种存储结构中的实现。

数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。

核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2)插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i 位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。

数据结构第一章概论

数据结构第一章概论
要求具备的知识：
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。您的内容已经简明扼要，字字珠玑，但信息却千丝万缕、错综复杂，需要用更多的文字来表述；但请您尽可能提炼思想的精髓，否则容易造成观者的阅读压力，适得其反。正如我们都希望改变世界，希望给别人带去光明，但更多时候我们只需要播下一颗种子，自然有微风吹拂，雨露滋养。恰如其分地表达观点，往往事半功倍。当您的内容到达这个限度时，或许已经不纯粹作用于演示，极大可能运用于阅读领域；无论是传播观点、知识分享还是汇报工作，内容的详尽固然重要，但请一定注意信息框架的清晰，这样才能使内容层次分明，页面简洁易读。如果您的内容确实非常重要又难以精简，也请使用分段处理，对内容进行简单的梳理和提炼，这样会使逻辑框架相对清晰。
1.3 算法和算法分析 数据的运算是通过算法描述的。
(1)有穷性：在有限步(或有限时间)之后算法终止。 例.{ i=0；s=0； while (i<10) s++； i++； } (2)确定性：无二义性。 例.{ x=5；y=10； z=x+++y； printf(“%d,%d,%d”,x,y,z)； } x+++y 解释为：x + (++y)？ (x++)+ y？
数据顺序存储结构和链式存储结构（物理结构，存储表示,物理表示）
7.数据类型（data type)--- 是一个值的集合和定义在这个值上的一组操作的总称。 用数据类型定义数据结构。 (1)原子类型(如：int,char,float等) (2)结构类型(如：数组,结构,联合体等） 8.抽象数据类型(Abstract Data Type)---- 与计算机的实现无关的数据类型。 形式定义： ADT 抽象数据类型名 { 1.数据对象； 2.数据关系:一个或多个关系； 3.一组基本操作/运算 } ADT 抽象数据类型名 注意：常用DataType表示抽象元素类型。

数据结构与算法课件：DS01_第1章绪论1

数据结构与算法课件：DS01_第1章绪论1

min=max[0]; for(i=1; i<G.VerticesNum(); i++) // 查max数组 的最小值及其位置
if(max[i]<min){ min=max[i]; pos=i; }
if(min==INFINITY) {cout<<“此图不连通”<<endl; return -1; }
B1
0
8
∞
4
3
B2
13
0
∞
17
8
B3
6
7
0
10
2
B4
∞
∞
∞
0
∞
B5
5
5
∞
9
0
吉林大学珠海学院 计算机系
11
算法抽象：股市的传言
#include <iostream> #include <string> using namespace std; #define MAX 102 #define INFINITY 65536 int BrokerToPassMomour(Graph & G) { int **D;
int max[G.VerticesNum()]; int min=0, pos=0; for(int i=0; i<G.VerticesNum(); i++) max[i]=-1; Floyd(G, D); ----接下页
吉林大学珠海学院 计算机系
2020/9/28
1212
算法抽象：股市的传言
for(i=0; i<G.VerticesNum(); i++) //每行最大值存在max数组 for(int j=0; j<G.VerticesNum(); j++) if(D[i][j]>max[i]) max[i]=D[i][j];

数据结构讲义第一章绪论

数据结构讲义第一章绪论

注：一个抽象数据类型确定了一个模型，但将模型的实 现细节隐藏起来；它定义了一组运算，但将运算 的实现过程隐藏起来。
用抽象数据类型的概念来指导问题的求解过程：
数学模型 非形式算法
抽象数据模型 伪语言程序
数据结构 可执行程序
§ 1.3 抽象数据类型
ADT的定义格式 ADT <ADT名> { 数据对象:<数据对象的定义> 结构关系:<结构关系的定义> 基本操作:<基本操作的定义> }ADT <ADT名>
初始化数据结构；
Destroy( )
销毁数据结构；
Get (i )
查找第 i 个元素；
Insert (i , b ) 在第 i 个位置插入元素 b ；
Delete( i )
删除第 i 个元素；
Traverse( )
遍历整个数据结构
§ 1.3 抽象数据类型
用C语言实现抽象数据类型ADT 用标准C语言表示和实现ADT描述时，主要
§ 1.2 数据结构的基本概念
数 据：描述客观事物的数字、字符以及一切 能够输入到计算机中，并且能够被计 算机程序处理的符号的集合。
数据是一个广义的概念，可以指普通的数据 （可参加算术运算），也可以指符号（源程序、 产品名称等）或数字化了的声音、图形、图像等。
§ 1.2 数据结构的基本概念
数据元素：数据(集合)中的一个个"个体"，是组 成数据的"基本单位"。
a2 d4 d1
a1 d1 d2
list
a1
a2
a4 d5 d3
a3 d3 … d4
a3
…
a30 ∧
§ 1.3 抽象数据类型

数据结构(1-2-3章)课后题答案解析

数据结构(1-2-3章)课后题答案解析
西北大学可视化技术研究所
q=p; p=p->next; b->next=q; q->next=B; b=b->next; } else {//分出其他字符结点 q=p; p=p->next; c->next=q; q->next=C; c=c->next; } } }//结束
西北大学可视化技术研究所
A．双向链表
B．双向循环链表
C．单向循环链表 D．顺序表
（4）下列选项中， D 项是链表不具有的特点。
A．插入和删除运算不需要移动元素
B．所需要的存储空间与线性表的长度成正比
C．不必事先估计存储空间大小
D．可以随机访问表中的任意元素
西北大学可视化技术研究所
(5)在链表中最常用的操作是删除表中最后一个结点和 在最后一个结点之后插入元素，则采用 C 最 节省时间。
西北大学可视化技术研究所
8.假设两个按元素值递增有序排列的线性 表A和B，均以单链表作为存储结构，请 编写算法，将A表和B表归并成一个按元 素值递减有序排列的线性表C，并要求利 用原表（即A表和B表的）结点空间存放 表C。
西北大学可视化技术研究所
算法描述：要求利用现有的表A和B中的结 点空间来建立新表C，可通过更改结点的next 域来重新建立新的元素之间的线性关系。为保 证新表递减有序可以利用头插法建立单链表的 方法，只是新建表中的结点不用malloc，而只 需要从A和B中选择合适的点插入到新表C中即 可。
西北大学可视化技术研究所
1.3填空题： （1）变量的作用域是指 变量的有效范围 （2）抽象数据类型具有 数据抽象 、 信息隐 蔽 的特点。 （3）一种抽象类型包括 数据对象 、 结构 关系 和 基本操作 。

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版)课后习题答案

2015.3目录第1章绪论 (1)第2章线性表 (5)363345第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

录)，其他的结点则各有一个也只有一个直接前趋和直接后继。

学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。

这些学生记录在计算机中的存储表示就是存储结构。

如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。

即相同的逻辑结构，可以对应不同的存储结构。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

答案：（1）集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。

例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。

（2）线性结构数据元素之间存在一对一的关系。

例如，将学生信息数据按照其入学报到的时间先后顺其中树结构和图结构都属于非线性结构。

四类基本逻辑结构关系图4．存储结构由哪两种基本的存储方法实现？答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。

但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

所以链式存储结构通常借助于程序设计语言的指针类型来描述。

5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构答案：C（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A．存储结构 B．存储实现C．逻辑结构 D．运算实现答案：C（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;答案：O(1)解释：程序的执行次数为常数阶。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。