数据结构全真模拟测验题

1、全真模拟试卷(1)一、单项选择题1、线性表是具有n个的有限序列(n0)。表元素B.字符C.数据元素D.数据项TOCo1-5hz2、栈和队列都是。顺序存储的线性结构B.链式存储的线性结构C.限制存取点的线性结构D.限制存取点的非线性结构3、若对n阶对称矩阵A以行序列为主序方式将其上三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aj(inext=s;s-prev=p;p-prev=s;s-next=p-next;Bp-next-prev=s;p-next=s;s-prev=p;s-next=p-nextCs-prev=p;s-next=p-next

2、;p-next=s;p-next-prev=sDs-prev=p;s-next=p-next;p-next-prev=s;p-next=s2、一个栈的入栈序列为A,B,C,D,E,则栈的不可能的出栈序列是。二叉树在线索化后，仍不能有效解决问题是。先序线索二叉树中求先序后继中序线索二叉树中求中序后继C中序线索二叉树中求中序前驱D后序线索二叉树中求后序后继若一个具有N个顶点，K条边得无向图时一个森林(NK),则该森林中必有课树。以下存储结构中，不是树的存储结构的是。双亲存储结构B.顺序存储结构C.孩子链存储结构D.孩子兄弟链存储结构若G是一个具有36条边得非连通无向图(不含自回路和多重边)，则图G

3、至少有个顶点。当图采用邻接矩阵存储时，深度优先搜索算法的时间复杂度为,广度优先搜索算法的时间复杂度为，其中n为图的顶点数，e是图的边树。O(n2),O(n2)B.O(n2),O(n+e)C.O(n+e),O(n2)D.O(n+e),O(n+e)若采用链地址法构图散列表，散列函数为H(key)=keyMOD17，则需17个链表。这些链的链首指针构成一个指针数组，数组的下标范围为。A.017B.117C.016D.116若用冒泡排序方法对序列10,14,26,29,41,52,从大到小排序，需进行次比较。10在含有n个关键字的小根堆(堆顶元素最小)中，关键字最大的记录有可能存储在位置上。A.匚n/

4、2B.匚n/2-1C.1D.匚n/2+2二、综合应用题已知如图所示的AOE网，求：每项活动的最早发生时间(ve)和最迟开始时间(vl)完成此工程最少需要多少单位时间？关键活动与关键路径。已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)？关键字自小到大有序(key1key2key2.keyn)。奇数关键字顺序有序，偶数关键字顺序有序(key1key3.,key2key4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1key2keym+2keyn,m为中间位置)。全真模拟试卷（4）一、单项

5、选择题TOCo1-5hz对于一个头指针为head的带头结点的但链表，判定该表为空表的条件是。A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL一个栈的入栈元素序列是，若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出现的出栈序列是。用s表示入栈操作，x表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序相应的s和x的操作串为。若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是A.二叉排序树B.哈夫曼树C.堆D.AVL树由元素序列（）构造平衡二叉树，则首次出现的最小不平衡子树的根（

6、即离插入TOCo1-5hz结点最近且平衡因子的绝对值为2的结点）为。根据使用频率，为5个字符设计的哈夫曼编码不可能时。如图所示，从顶点A出发，如按照广度优先搜索法进行遍历，可能得到的一种顶点序列为。对AOE网的关键路径，下面的说法是正确的。提高关键路径的一个关键活动的速度，必然使整个工程缩短工期完成工程的最短时间是从始点到终点的最答案路径的长度。一个AOE网的关键路径只有一个，但关键活动可有多个。任何一项活动持续时间的改变都可能会影响关键路径的改变。关于杂奏查找不正确的有。采用链地址法解决冲突是，查找任一个元素的时间是相同的。采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间

7、是相同的。用链地址法解决冲突冲突易引起聚集现象。再哈希法不易产生聚集在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是。直接插入排序起泡排序直接选择排序快速排序二、综合应用题利用两个栈S1和S2来模拟一个队列。若不存在栈溢出问题，则请写出用栈的操作来实现队列的插入和删除的算法。42以下图为例，按dijkstra算法计算得到从顶点A到其他各个顶点的最短路径和最长路径长度。一、单项选择题以下关于先性表的描述，正确的是。线性表中并不是所有元素都有一个直接前驱和一个直接后继线性表的顺序存储结构插入和撒谎年初是效率太低，因此它不如链式存储结构好。线性表的链式存储结构的元素随机访问效率太低，因

8、此它不如顺序存储结构好顺序存储方式的优点是存储密度大，且插入，删除运算效率高。用链接方式存储的队列，在进行删除运算是。仅修改头指针仅修改尾指针头尾指针都有修改头尾指针可能都要修改一棵深度为4的完全二叉排序树，最少有个结点。在常用的描述二叉排序树的存储结构中，关键字值最大的结点左子树一定为空右子树一定为空左右子树均为空左右子树均不为空正确的是。0元素数就是该图的边数0元素就是该图所有顶点的度之和i行的非0元素之和是第i行的非0元素之和是第个。以下关于邻接矩阵的描述，无向图的邻接矩阵中非无向图的邻接矩阵中非i个顶点的入度i个顶点的出度i个顶点的入度i个顶点的出度有向图的邻接矩阵中第有向图的邻接矩阵

9、中第有向图的所有拓扑排序序列有)，若查找元素58，则它将依次与表中元素折半查找有序表(比较大小，查找结果是失败。下列关于m阶B-树的说法错误的是根结点至多有m棵子树所有叶子都在同一层次上非叶结点至少有m/2(m为偶数)或m/2+1(m为奇数)棵子树根结点中的数据是有序的若不考虑基数排序，则在排序过程中，主要的两种基本操作是A.比较和交换B.比较和移动C.选择和交换D.选择和移动归并排序中，归并的趟数是_。A.O(n)B.O(log2n)CO(nlog2n)DO(n2)二、综合应用题41请利用栈的基本操作写出复制一颗二叉树的非递归算法。要求以二叉链表作为二叉树的存储结构。设栈已定义：initst

10、ack(S)，push(S,e)，stackempty(S),Gettop(S,e),Pop(S,e)分别为栈初始化，入栈，判断栈空，获得栈顶元素，出栈等操作。函数原型如下：voidbitree-Copy(BitreeT,Bitree&U)42设有关键字序列为：50.71.80.60.55.40.25.99，用数组存储。请以堆排序方式把数据排序成递增序列，并给出建堆和每趟堆调整后的数据序列。一、单项选择题设n个元素的线性表顺序存储，若删除其第i个元素和在第i，第i+1个元素之间插入一个新元素，则分别需要移动个元素。A.n-i,n-i+1B.n-i+1,n-iC.n-i,n-iD.n-i+1,n

11、-i+1若栈采用顺序存储方式存储，现两栈共享空间V【m】，top【i】代表第i个栈(i=1,2)栈顶，栈TOCo1-5hz空时栈1的底在v0,top1=0,栈2的底在Vm-1,top2=m-1,则栈满的条件是。Atop1=top2B.top1+1=top2C.top1+top2=mD.top1-1=top2设计一个判别表达式中左，右括号是否配对出现的算法，采用数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为A.B.C.D.E.F.G.H,该完全二叉树的后序遍历序列为。由带权的5个叶子结点生成的哈夫曼树的带

12、权路径长度为。无向图G有16条边，有3个4度顶点，4个3度顶点，其余顶点的度数都小于3，则G中至少有个顶点。采用邻接表存储的图的广度优先遍历算法类似于树的。中根遍历先跟遍历后跟遍历按层次遍历对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是，对于查找成功，它们的平均查找长度是相同的。相同的不同的无法确定的以上都不对(不要)9.下面关于B-树和B+树的叙述中，不正确的是。B-树和B+树都是平衡的多叉树B-树和B+树都可用于文件的索引结构B-树和B+树都能有效地支持顺序检索B-树和B+树都能有效地支持随机检索10第i趟处理是将Ai+1,An中关键

13、字最小者与Ai(i=1,2,.,n-1)进行交换的排序算法为_。快速排序选择排序冒泡排序插入排序二、综合应用题已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。已知无向图G=(V,E)的邻接表，给出求图G的联通分量个数的算法。一、单项选择题以下关于线性表采用链式存储时删除结点运算的描述，正确的是。带头结点的线性删除结点时，不需要更改头指针带头结点的线性链表删除第一个结点时，需要更改头指针不带头结点的线性链表删除第一个结点时，需要更改头指针不带头结点的线性链表删除第一个结点时，不需要更改头指针若循环队列以数组Q0m-1作为其存储结构，变量rear表示循环队列中

14、的队尾元素的实际位置，其移动按rear=(rear+1)Modm进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是。A.rear-lengthB.(rear-length+m)ModmC.(1+rear+m-length)ModmD.m-length如以顺序方式存储二叉树，每个结点占用一个存储单元，则深度为m的单左支二叉树共浪费_个存储单元。m-1A2m-1-mB2m-1-m-1C2m-m-1D2m-m+1在度为m的哈夫曼树中，其中结点个数为n,则非叶结点的个数为。A|n/m|-1B.|(n-1)/(m-1)|C.|n/(m-1)|-1D.|(n+1)/(m+

15、1)|下面关于图的存储的叙述中,正确的是。用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关在有向图G的扩扑中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是。A.G中有弧B.G中有一条从Vi到Vj的路径C.G中没有弧D.G中有一条从Vj到Vi的路径当n足够大时,在按值有序的顺序表中进行折半查找,在查找概率相等的情况下,其查找成功的平均查找长度是。A.(n+1)/2B

16、.n/2C.log2(n+1)-1D.log2(n+1)二叉查找树的查找效率与二叉树的树形有关,在是其查找效率最低。A.结点太多B.完全二叉树C.呈单支树D.结点太复杂对一组数据()排序,数据的排列次序在排序的过程中的变化为8447251521(2)1547258421(3)1521258447(4)1521254784,则采用的排序是。A.选择B.冒泡C.快速D.插入数据序列(8,9,10,4,5,6,20,1,2,)只能是下列排序算法中的的两趟排序后的结果。A.选择排序B.冒泡排序C.插入排序D.堆排序二、综合应用题某通信系统只可能有A.B.C.D.E.F.这6种字符,其出现的概率分别为0

17、.1,0.4,0.04,0.16,0.19,0.11,试画出相应的哈夫曼树,并设计哈夫曼编码。设有五个数据do,for,if,repeat,while,它们排在一个有序表中,其查找概率分别为p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01,如下图所示。试画出对该有序表采用顺序查找是的判定树和采用折半查找时的判定树分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找是的查找成功和不成功的凭据查找长度。判定是顺序查找好？还是折半查找好

18、？一、单项选择题某线性表中最常用的操作时在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表循环队列存储在数字Am中，则入队时的操作为。A.rear=rear+1B.rear=(rear+1)%(rear-1)C.rear=(rear+1)%mD.rear=(rear+1)&(m+1)以下方法不能将线性表中元素逆序。将此线性表表中元素依次全部入栈，在全部出栈，再全部通过一个队列将此线性表中元素依次全部通过一个队列、再全部入栈、再全部出栈将此线性表中元素依次全部入栈、再全部出栈、再全部入栈、再全部

19、出栈将此线性表中元素依次全部通过一个队列、再全部入栈、再全部出栈、再通过一个队列TOCo1-5hz一个具有1025个结点的二叉树的高h为。A.11B.10C.111025D.101024设森林F中有三棵树，第一，第二，第三，棵树的结点个数分别为N1,N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是。A.N1B.N1+M2C.N3D.N2+N3在n个顶点的无向连通图的生成树中，包含顶点数，顶点中的最小度数是。A.n,0B.n,1C.n-1,0D.无法确定下列说法不正确的是。图的遍历是从给定的源点出发每一个顶点仅被访问一次遍历的基本算法有两种：深度遍历和广度遍历图的深度遍历不适用于有向

20、图图的深度遍历是一个递归过程(不要)8.在二叉平衡序树上成功地找到一个结点(设结点个数为n),在平均情况的最坏情况下的TOCo1-5hz时间复杂性分别是。2A.O(log2n),O(n)B.O(n),O(n)C.O(log2n),O(n2)D.O(log2n),O(log2n)9、排序方法有许多种,插入排序法从未排序的序列中依次取出元素,与已排序列(初始时为空)中的元素的作比较,将其放入已排序序列的正确位置上；选择排序法从未排序的序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端；交换排序方法是对序列中的元素进行一系列比较,当被比较的两元素逆序时,进行交换,起泡排序和快速排序是基于这

21、类方法的两种排序方法；法是基于选择排序的一种排序方法,是完全二叉树结构的一个重要应用。A.归并排序B.Shell排序C.堆排序D.基数排序10、设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、起泡排序和归并排序方法对其进行排序(按递增顺序),最省时间和最费时间的排序方法是。A.堆排序，起泡排序B.快速排序，归并排序C.起泡排序，快速排序D.起泡排序，归并排序二、综合应用题41、使用普里姆(Prim)算法生成下图的一个最小生成树,并写明每一步的状态。42、有一种简单的排序算法，叫做计数排序(countsorting)。这种排序算法对一个待排序的表(用数组表示)进行排序,并将排序结果存

22、放到另一个新的表中。必须注意的是,表中所有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小？假使针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序表中的合适的存放位置即为c。(1)给出适用于计数排序的数据表定义。(2)使用C语言编写实现计数排序的算法。(3)对于有n个记录的表,关键码比较次数是多少？(4)与简单选择排序相比较,这种方法是否更好？为什么？全真模拟试卷(9)一、单项选择题1、设双向链表的结点结构为(prior,data,next),其中prior和next均为指针域，已知指针px指向该链表中的结点x

23、,设定结点x有前去和后继，若删除结点x,并释放所占的空间，则需要执行以下语句。px-prior-next=px-next;px-next-prior=px-prior;free(px)px-prior-next=px-prior;px-next-_prior=px_-next;free(px)px-prior-prior=px-next;px-next-next=px-prior;free(px)px-next-prior=px-next;px-prior-next=px-prior;free(px)2、一个循环队列Q最多可存储m个元素，已知其头尾指针分别是front和rear，则判定该循环对

24、列为满的条件是。=mB)Q.rear!=Q.forntC)Q.front=(Q.rear+1)%mD)Q.front=Q.rear%m+13、用一维数组B以列优先存放带状矩阵A中的非零元素Ai,j(Kin,i-2wjwi+2),B中的第8个元素是A中的元素。第1行第3列B)第3行第1列C)第2行第1列D)第1行第2列4、有n个结点的完全二叉树采用顺序存储结构时，从根结点开始对其层次顺序进行编号(设根结点编号为1),下列说法错误的是。A)当1wiwn/2时，结点i的左子女是结点2i,否则结点i没有左子女当1wiw(n-1)/2时，结点i的右子女是结点2i+1,否则结点i没有右子女1wiwn时，结

25、点i的父母是结点i/2当i为偶数且1iai+1,则将二者交换，以后重复上述过程，直至整个数组有序。试编写实现该算法的函数。全真模拟试卷(10)一、单项选择题1、对于一个头指针为是。head的带头结点的双向循环链表，可以作为判定该线性表为空表的条件A)head=NULLC)head-next=headB)head-next=NULLD)head!=NULL2、假设以数组Am存放循环队列的元素，其头尾指针分别是front和rear,则当前队列中的元素个数为。A)(rear-ront+m)%mB)rear-front+1C)(front-ear+m)%mD)(rear-front)%mTOCo1-5

26、hz3、设在某树中，结点M、N是结点P上的第i、i+1个孩子，则在此树的二叉树表示中，结点M与N的关系是。A)M、N具有同一双亲B)M是N的左孩子C)N是M的左孩子D)N是M的右孩子4、以下的叙述中，正确的是。强连通有向图的任何顶点到其他所有顶点都有弧任意图顶点的入度等于出度有向完全图一定是强连通有向图有向图的边集的子集和顶点集的子集可构成原有向图的子图TOCo1-5hz5、如下图所示，已知某个深度优先搜索序列为A*F*，则可能的序列为。CDaBDFECgABCFDEACEFBDACEFDB(ADCFEBADBFECA)0、C2和C6B)和C4C)3、C5D)、C4、C56、适用于折半查找的表

27、的存储方式及元素排列要求为。A)链接方式存储，元素无序B)链接方式存储，元素有序C)顺序方式存储，元素无序D)顺序方式存储，元素有序(不要)7、一个m阶B树中，每个结点最少有个儿子结点。A)mB)m/2C)2D)m/2&判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用A)求关键路径的方法B)求最短路径的DIJKSTRA方法C)深度优先遍历算法D)广度优先遍历算法9、在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是A)直接插入排序B)堆排序C)快速排序D)起泡排序10、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是.A.堆排序快速排序归并排

28、序C.堆排序归并排序快速排序B.堆排序归并排序快速排序堆排序快速排序归并排序二、综合应用题41、将如下图所示的森林转换为一颗二叉树，并写出森林的两种遍历序列42、指定Hash函数H(k)=3xkmod11及线性探测地址法处理冲突，试在010的散列空间中对关键字序列(22,41,53,46,30,13,01,67)构造Hash表，并求在等查找概率下查找成功的平均查找长度。例2、一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解：1入1出，2入2出，3入3出，即123；1入1出，2、3入，3、2出，即132；1、2入，2出，3入3出

29、，即231；1、2入，2、1出，3入3出，即213；1、2、3入，3、2、1出，即321；合计有5种可能性。例3、一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？解：43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可。问：为什么要设计堆栈？它有什么独特用途？调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。设依次进入一个栈的元素序列为c,a,b,d,则可得到出栈的元素序列是：A）a,b，c，dB）c,d,a,bC）b,c,d,aD）a,c

30、,d,bA）、D）可以，B）、C）不行。问：为什么要设计队列？它有什么独特用途？离散事件的模拟（模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列）操作系统中的作业调度（一个CPU执行多个作业）；简化程序设计。（1）假溢出顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。（2）如何解决顺序队列的假溢出问题？可采取四种方法：1）采用循环队列；2）按最大可能的进队操作次数设置顺序队列的最大元素个数；3）修改出队算法,使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；4）修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动,然后方完成入队操作。顺序

31、循环队列的队空和队满判断问题新问题：在循环队列中，空队特征是front=rear;队满时也会有front=rear;判决条件将出现二义性！解决方案有三：使用一个计数器记录队列中元素个数（即队列长）；判队满：count0&rear=front判队空：count=0加设标志位，出队时置0，入队时置1，则可识别当前front=rear属于何种情况判队满：tag=1&rear=front判队空：tag=0&rear=front少用一个存储单元判队满：front=（rear+1）%MaxQueueSize判队空：rear=front问：空串和空白串有无区别？答：有区别。空串（NullString）是指长

32、度为零的串；而空白串（BlankString），是指包含一个或多个空白字符（空格键）的字符串.堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。模式匹配（定位）设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。2、算法目的确定主串中所含子串第一次出现的位置（定位）3、算法种类BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法1、二叉树的带权路径长度：从二叉树根结点到所有叶子结点的路径长度与相应叶子结点权值的乘积（WP

33、L）WPL=?wklk2、例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4,怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码（如二进制编码）令d=00,i=01,a=10,n=11，则：WPL1=2bitX（7+5+2+4）=36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：WPL2=1bitX72bitX5+3bitX（2+4）=353、对权值进行合并、删除与替换4、若集合X上的关系R是自反的、对称的和传递的，则称关系R是集合X上的等价关系。5、树转二叉树举例：方法：加线抹线旋转6、讨论2：二叉树怎样还原为树？要点：逆操作，

34、把所有右孩子变为兄弟！数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作的学科。程序设计=好算法+好结构数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：数组、结构、联合、指针、枚举等）抽象数据元素：抽象定义的、没有实际含义的数据元素。抽象数据类型：用户自己定义的数据类型。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

35、。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为：Data_Structure=（D,R）其中，D元素有限集，R关系有限集抽象数据类型：用户自己定义的数据类型。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。形式定义表示为：Data_Structure=（D,R）其中，D元素有限集，R关系有限集数据结构的三要素：逻辑结构、存储结构和运算。数据逻辑结构（本质）定义：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无

36、关，是独立于计算机的。数据的物理结构定义：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。抽象数据类型（AbstractDataType）：是一个数学模型以及定义在该模型上的一组操作。由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。算法概念：算法是一个有限的指令集，遵循指令流可以完成特定的功能。算法基本特征：有穷性：算法经有限步后结束。确定性：下一步必须是明确的。可行性：每一是可以执行的。评价指标正确性可读性健壮性高效率与低存储量需求（见课本P20）1.0若结构是非空有限集，则有且仅有一个开始结点和一个终

37、端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。t可表示为：（al,a2，,an）特点只有一个首结点和尾结点；特点除首尾结点外，其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是的。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是（1）顺序存储结构:它是使用一片地址连续的有限内存单元空间存储数据元素的一种计算机存储数据方法。特点：（任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻）逻辑上相邻的元素，物理上也相邻。（2）链式存储结构:它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法

38、。特点：（任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的）逻辑上相邻元素,物理上不一定相邻。栈“上溢”在栈满时还进行入栈运算，必定会产生空间的溢出,栈“下溢”当栈空时仍进行出栈运算，必定会产生空间的溢出。例1：堆栈是什么？它与一般线性表有什么不同？堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算与一般线性表的区别：仅在于运算规则不同。运算规则：随机存取运算规则：后进先出（LIFO）树的度一般线性表逻辑结构：1:1存储结构：顺序表、链表逻辑结构：存储结构：顺序栈、链栈堆栈树的深度（或高度）所有结点度中的最大值（Max各结点的度）

39、指所有结点中最大的层数（Max各结点的层次）性质3:对于任何一棵非空的二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）证明：二叉树中全部结点数n=n0+n1+n2（叶子数+1度结点数+2度结点数）又二叉树中全部结点数n=B+1（总分支数+根结点）（除根结点外，每个结点必有一个直接前趋，即一个分支）而总分支数B=n1+2n2（1度结点必有1个直接后继，2度结点必有2个）三式联立可得：nO+n1+n2=n1+2n2+1,即n0=n2+1性质4:具有n个结点的完全二叉树的深度k必为？log2（n+1）?-1（假定k为O时表示此二叉树仅有根结点）证明：根据性质2，深度

40、为k的二叉树最多只有2k+1-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2（k-1）+1-1nw2k+1-1，移项，有2kn+12k+1对不等式求对数，有klog2（n+1）wk+1因为k是整数，所以k=?log2（n+1）?-1一棵完全二叉树有1OOO个结点，则它必有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。正确答案：全部叶子数=?1000/2?=500个。度为2的结点=叶子总数一1=499个。因为最后一个结点编号是偶数，所以必为左子树。有1个结点只有非空左子树，有0个结点只有非空右

41、子树。例3：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点:可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素;需要预先确定数据元素的最大个数。解决问题的思路：改用另一种线性存储方式：1.11(1)单链表:构成链表的结点只有一个指向直接后继结点的指针。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。1.12讨论1.在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的

42、一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。1.13对比带头结点的单链表的插入、删除过程和不带带头结点的单链表的插入、删除过程，可以得知：若设计的单链表带头结点，则无论是在第一个数据元素结点前插入还是在其他数据元素结点前插入都不会改变头指针的数值。若设计的单链表不带头结点，则在第一个数据元素结点前插入与在其他数据元素结点前插入其算法的处理方法不同。在单链表中删除一个结点时类似。因此，单链表一般构造成带头结点的单链表。1.14讨论1：顺序存储和链式存储的区别和优缺点？顺序存储时，逻辑上相

43、邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。完全图：图G任意两个顶点都有一条边相连接；若n个顶点的无向图有n(n-1)/2条边,称为无向完全

44、图若n个顶点的有向图有n(n-1)条边,称为有向完全图2.9、回路：若路径上第一个顶点v1与最后一个顶点vm重合，则称这样的路径为回路或环。生成树：是一个极小连通子图，它含有图中全部n个顶点，但只有n-1条边。4、结点的度：结点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,结点的度等于该结点的入度与出度之和。其中结点v的入度是以v为终点的有向边的条数,记作ID(v);结点v的出度是以v为始点的有向边的条数,记作OD(v)。5、连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通

45、分量。6、强连通图：在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径，则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。7、分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度=第i行例)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。8、分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点vi的出度=第i行元素之和，OD(vi)=?Aij顶点vi的入度=第i列元素之和。ID(vi)=?Aji顶点的度=第i行元素之和+第i列元素之和,即：TD(vi)=OD(vi)+ID(vi)9、邻接矩阵：容易实现图的操作，如：求某顶点的度、判断顶点

46、之间是否有边(弧)、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。10、邻接表：分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。11、讨论：邻接表与邻接矩阵有什么异同之处？联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。区别：对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)。邻接矩阵