二叉树静态链表存储结构

数据结构大纲知识点一、绪论。

1. 数据结构的基本概念。

- 数据、数据元素、数据项。

- 数据结构的定义（逻辑结构、存储结构、数据的运算）- 数据结构的三要素之间的关系。

2. 算法的基本概念。

- 算法的定义、特性（有穷性、确定性、可行性、输入、输出）- 算法的评价指标（时间复杂度、空间复杂度的计算方法）二、线性表。

1. 线性表的定义和基本操作。

- 线性表的逻辑结构特点（线性关系）- 线性表的基本操作（如初始化、插入、删除、查找等操作的定义）2. 顺序存储结构。

- 顺序表的定义（用数组实现线性表）- 顺序表的基本操作实现（插入、删除操作的时间复杂度分析）- 顺序表的优缺点。

3. 链式存储结构。

- 单链表的定义（结点结构，头指针、头结点的概念）- 单链表的基本操作实现（建立单链表、插入、删除、查找等操作的代码实现及时间复杂度分析）- 循环链表（与单链表的区别，操作特点）- 双向链表（结点结构，基本操作的实现及特点）三、栈和队列。

1. 栈。

- 栈的定义（后进先出的线性表）- 栈的基本操作（入栈、出栈、取栈顶元素等操作的定义）- 顺序栈的实现（存储结构，基本操作的代码实现）- 链栈的实现（与单链表的联系，基本操作的实现）- 栈的应用（表达式求值、函数调用栈等）2. 队列。

- 队列的定义（先进先出的线性表）- 队列的基本操作（入队、出队、取队头元素等操作的定义）- 顺序队列（存在的问题，如假溢出）- 循环队列的实现（存储结构，基本操作的代码实现，队空和队满的判断条件）- 链队列的实现（结点结构，基本操作的实现）- 队列的应用（如操作系统中的进程调度等）四、串。

1. 串的定义和基本操作。

- 串的概念（字符序列）- 串的基本操作（如连接、求子串、比较等操作的定义）2. 串的存储结构。

- 顺序存储结构（定长顺序存储和堆分配存储）- 链式存储结构（块链存储结构）3. 串的模式匹配算法。

- 简单的模式匹配算法（Brute - Force算法）的实现及时间复杂度分析。

第1章绪论◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

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

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

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

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

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

◆算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间。

for ( i = 1 , i < = 10 , i++ ) x=x+c； =>O(1)for ( i = 1 , i < = n , i++ ) x=x+n； =>O(n)多嵌套一个for，则为=>O(n^2) 以此类推真题难点：i = 1，while（i < = n)i = i * 3；=>O(log3^n)i = i * 2；=>O(log2^n) 以此类推数据的逻辑结构有以下两大类：线性结构：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。

作业题（一）一、单项选择题1. 从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2. 链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比3.下面程序段的时间复杂度的量级为（）。

For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1) B．O(n)C．O(n²) D．O(n³)4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。

A．2 B．3C．4 D．65、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。

A．98 B．100C．102 D．1066、判定一个栈s（最多元素为m0）为空的条件是（）。

A．s-〉top! =0 B．s-〉top= =0C．s-〉top! =m0 D．s-〉top= =m07、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。

A．（rear-front+m）%m B．rear-front+1C．rear-front-1 D．rear-front8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。

A．连接B．求子串C．模式匹配D．判子串9、设串S1='ABCDEFG'，S2='PQRST'，函数con（x，y）返回x和y串的连接串，subs(s,i,j)返回串S的的从序号i的字符开始的j个字符组成的子串，len(s)返回串S的长度，则con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的结果是（）。

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构的定义数据结构是计算机中存储、组织数据的方式，它定义了数据元素之间的逻辑关系以及如何在计算机中表示这些关系。

提高算法效率合适的数据结构可以显著提高算法的执行效率，降低时间复杂度和空间复杂度。

简化程序设计数据结构为程序设计提供了统一的抽象层，使得程序员可以更加专注于问题本身，而不是底层的数据表示和访问细节。

便于数据管理和维护良好的数据结构设计可以使得数据的管理和维护变得更加方便和高效。

数据结构的定义与重要性线性数据结构中的元素之间存在一对一的关系，如数组、链表、栈和队列等。

线性数据结构非线性数据结构中的元素之间存在一对多或多对多的关系，如树、图等。

非线性数据结构静态数据结构在程序运行期间不会发生改变，如数组、静态链表等。

静态数据结构动态数据结构在程序运行期间可以动态地添加或删除元素，如链表、动态数组等。

动态数据结构数据结构的分类01020304在计算机科学中，数据结构是算法设计和分析的基础，广泛应用于操作系统、编译原理、数据库等领域。

计算机科学在软件工程中，数据结构是软件设计和开发的重要组成部分，用于实现各种软件功能和性能优化。

软件工程在人工智能中，数据结构用于表示和处理各种复杂的数据和知识，如神经网络、决策树等。

人工智能在大数据处理中，数据结构用于高效地存储、管理和分析海量数据，如分布式文件系统、NoSQL 数据库等。

大数据处理数据结构的应用领域0102线性表是具有n个数据元素的有限序列创建、销毁、清空、判空、求长度、获取元素、修改元素、插入元素、删除元素等线性表的定义线性表的基本操作线性表的定义与基本操作03用一段地址连续的存储单元依次存储线性表的数据元素顺序存储结构的定义可以随机存取，即可以直接通过下标访问任意元素；存储密度高，每个节点只存储数据元素顺序存储结构的优点插入和删除操作需要移动大量元素；空间利用率不高，需要提前分配存储空间顺序存储结构的缺点链式存储结构的定义01用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的链式存储结构的优点02插入和删除操作不需要移动大量元素，只需要修改指针；空间利用率高，不需要提前分配存储空间链式存储结构的缺点03不能随机存取，只能通过从头节点开始遍历的方式访问元素；存储密度低，每个节点除了存储数据元素外，还需要存储指向下一个节点的指针0102定义栈（Stack）是一种特殊的线性数据结构，其操作只能在一端（称为栈顶）进行，遵循后进先出（LIFO）的原则。

数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。

西安文理学院精品课《数据结构》教案计算机科学系韩利凯《数据结构》第一章绪论[教学目标]掌握数据结构的定义、内容、方法、描述、评价。

[重点、难点]数据结构的研究范围，研究采用的方法，算法规则描述的工具，对算法作性能评价。

[教学方法]用多媒体课件（ ppt ）以及与生活实例相结合等方法讲授，这样便于描述相关概念及学生记笔记，加深他们的印象，使基础知识掌握地比较牢固。

[学习要点]1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2. 了解抽象数据类型的定义、表示和实现方法。

3．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。

4．掌握计算语句频度和估算算法时间复杂度的方法。

1.1 什么是数据结构（定义）首先介绍数据结构的相关名词。

1.数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。

2.数据元素（Data Element）数据元素是组成数据的基本单位 ,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。

例如：学生登记表是数据，每一个学生的记录就是一个数据元素。

3.数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。

4.数据结构（DA TA Structure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。

5.数据类型(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。

6.数据抽象与抽象数据类型１）数据的抽象高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出象栈、队列、树、图等复杂的抽象数据类型。

数据结构—链表链表⽬录⼀、概述1.链表是什么链表数⼀种线性数据结构。

它是动态地进⾏储存分配的⼀种结构。

什么是线性结构，什么是⾮线性结构？线性结构是⼀个有序数据元素的集合。

常⽤的线性结构有：线性表，栈，队列，双队列，数组，串。

⾮线性结构，是⼀个结点元素可能有多个直接前趋和多个直接后继。

常见的⾮线性结构有：⼆维数组，多维数组，⼴义表，树(⼆叉树等)。

2.链表的基本结构链表由⼀系列节点组成的集合，节点（Node）由数据域（date）和指针域（next）组成。

date负责储存数据，next储存其直接后续的地址3.链表的分类单链表（特点：连接⽅向都是单向的，对链表的访问要通过顺序读取从头部开始）双链表循环链表单向循环链表双向循环链表4.链表和数组的⽐较数组：优点：查询快（地址是连续的）缺点：1.增删慢，消耗CPU内存链表就是⼀种可以⽤多少空间就申请多少空间，并且提⾼增删速度的线性数据结构，但是它地址不是连续的查询慢。

⼆、单链表[1. 认识单链表](#1. 认识单链表)1. 认识单链表（1）头结点：第0 个节点（虚拟出来的）称为头结点（head），它没有数据，存放着第⼀个节点的⾸地址（2）⾸节点：第⼀个节点称为⾸节点，它存放着第⼀个有效的数据（3）中间节点：⾸节点和接下来的每⼀个节点都是同⼀种结构类型：由数据域（date）和指针域（next）组成数据域（date）存放着实际的数据，如学号（id）、姓名（name）、性别（sex）、年龄（age）、成绩（score）等指针域（next）存放着下⼀个节点的⾸地址（4）尾节点：最后⼀个节点称为尾节点，它存放着最后⼀个有效的数据（5）头指针：指向头结点的指针（6）尾指针：指向尾节点的指针（7）单链表节点的定义public static class Node {//Object类对象可以接收⼀切数据类型解决了数据统⼀问题public Object date; //每个节点的数据Node next; //每个节点指向下⼀结点的连接public Node(Object date) {this.date = date;}}2.引⼈头结点的作⽤1. 概念头结点：虚拟出来的⼀个节点，不保存数据。

《数据结构》考试题型及分数分布一、单项选择题，15小题，占30分二、判断题，10小题，占10分三、填空题，10小题，占20分四、概念与术语解释，3小题，占9分五、分析简答及应用题，4小题，占21分六、算法设计与分析题，1小题，占10分一、单项选择题1. 线性表采用链式存储时，其地址( A )。

A：连续与否均可以 B：部分地址必须是连续的C：一定是不连续的 D：必须是连续的2. 在单链表指针为p的结点之后插入指针为s结点，正确的操作是( A )。

A：s->next=p->next；p->next=s； B：p->next=s；s->next=p->next；C：p->next=s；p->next=s->next； D：p->next=s->next；p->next=s；3．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( D )存储方式最节省运算时间。

A：单链表 B：仅有头指针的单循环链表C：双向链表 D：仅有尾指针的单循环链表4. 有10个结点的无向图至少有( B )条边才能确保其是连通图。

A：8 B：9 C：10 D：115. 初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为( D )。

A：n2 B：nlog2n C：log2n D：n－16. 从逻辑结构上可以把数据结构分成( C )A：动态结构和静态结构 B：顺序结构和链式结构C：线性结构和非线性结构 D：内部结构和外部结构7. 数据的基本单位是( B )A：数据结构 B：数据元素C：数据项 D：文件8. 在一个带表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( D )。

A：HL=p; p->next=HL; B：p->next=HL; p=HL;C：p->next=HL; HL=p->next; D：p->next=HL->next; HL->nxet=p;9. 关键路径是事件结点网络中( A )。

第1章绪论1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

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

例如：整数数据对象是集合N={0, ± 1，土2，…}，字母字符数据对象是集合C={ ‘A',‘ B',…，‘ Z', ‘a',‘ $,•••,‘ z' }, 学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2•试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。