数据结构全真模拟试卷

1、真诚为您提供优质参考资料，若有不当之处，请指正。全真模拟试卷（1）一、单项选择题1、线性表是具有n个_的有限序列(n0)。A表元素B字符C数据元素D数据项2、栈和队列都是_。A顺序存储的线性结构B链式存储的线性结构C限制存取点的线性结构D限制存取点的非线性结构3、若对n阶对称矩阵A以行序列为主序方式将其上三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij(inext=s;s-prev=p;p-prev=s;s-next=p-next;B p-next-prev=s;p-next=s;s-prev=p;s-next=p-nextC s-prev

2、=p;s-next=p-next;p-next=s;p-next-prev=sD s-prev=p;s-next=p-next;p-next-prev=s;p-next=s2、一个栈的入栈序列为A,B,C,D,E,则栈的不可能的出栈序列是_。A.ABCDE B.EDCBA C.DECBA D.DCEAB3.二叉树在线索化后，仍不能有效解决问题是_。A. 先序线索二叉树中求先序后继B. 中序线索二叉树中求中序后继C 中序线索二叉树中求中序前驱D 后序线索二叉树中求后序后继4.若一个具有N个顶点，K条边得无向图时一个森林（NK）,则该森林中必有_课树。A.1B.NC.KD.N-K5.以下存储结构中

3、，不是树的存储结构的是_。A.双亲存储结构B.顺序存储结构C.孩子链存储结构D.孩子兄弟链存储结构6.若G是一个具有36条边得非连通无向图（不含自回路和多重边），则图G至少有_个顶点。A.11B.10C.9D.87.当图采用邻接矩阵存储时，深度优先搜索算法的时间复杂度为_,广度优先搜索算法的时间复杂度为_，其中n为图的顶点数，e是图的边树。A. O(n2),O(n2)B.O(n2 ),O(n+e)C.O(n+e),O(n2)D.O(n+e),O(n+e)8.若采用链XXX法构图散列表，散列函数为H（key）=key MOD 17 ，则需17个链表。这些链的链首指针构成一个指针数组，数组的下标范

4、围为_。A.017B.117C.016D.1169.若用冒泡排序方法对序列10,14,26,29,41,52,从大到小排序，需进行_次比较。A.3B.10C.15D.2510在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在_位置上。A.n/2B.n/2-1C.1D.n/2+2二、综合应用题41.已知如图所示的AOE网，求：每项活动的最早发生时间（ve）和最迟开始时间（vl）完成此工程最少需要多少单位时间？关键活动与关键路径。42.已知下列各种初始状态（长度为n）元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较（要求排序后的文件按关键字从小到大顺序排列）？关键

5、字自小到大有序（key1key2key2.keyn）。奇数关键字顺序有序，偶数关键字顺序有序（key1key3.,key2key4）前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序（key1key2keym+2keyn,m为中间位置）。全真模拟试卷（4）一、单项选择题1.对于一个头指针为head的带头结点的但链表，判定该表为空表的条件是_。A. head = =NULLB. head-next = =NULLC. head-next = = headD. head!=NULL2.一个栈的入栈元素序列是1.2.3.4.5，若允许出栈操作可在任意可能的时刻进行，则下面的序列中，不可能出现

6、的出栈序列是_。A.3.4.2.5.1B.2.5.4.1.3C.2.3.1.4.5D.3.5.2.4.13.用s表示入栈操作，x表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序相应的s和x的操作串为_。A.SXSSXSXXB.SXSXSSXXC.SXSSXXSXD.SXSSSXXX4.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是_。A.二叉排序树B.哈夫曼树C.堆D.AVL树5.由元素序列（27.16.75.38.51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为_。A.27B.38C.5

7、1D.756.根据使用频率，为5个字符设计的哈夫曼编码不可能时_。A.111.110.10.01.00 B.000.001.010.011.1C.001.000.10.01.11 D.110.100.101.11.17.如图所示，从顶点A出发，如按照广度优先搜索法进行遍历，可能得到的一种顶点序列为_。A.ABECDF B.ACFEBDC.ABCDEF D.ABDFEC8.对AOE网的关键路径，下面的说法_是正确的。A.提高关键路径的一个关键活动的速度，必然使整个工程缩短工期B完成工程的最短时间是从始点到终点的最答案路径的长度。C一个AOE网的关键路径只有一个，但关键活动可有多个。D任何一项活动

8、持续时间的改变都可能会影响关键路径的改变。9.关于杂奏查找不正确的有_。采用链XXX法解决冲突是，查找任一个元素的时间是相同的。采用链XXX法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的。用链XXX法解决冲突冲突易引起聚集现象。再哈希法不易产生聚集A.1 B.2 C.3 D.410.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是_。A. 直接插入排序B起泡排序C直接选择排序D快速排序二、综合应用题41.利用两个栈S1和S2来模拟一个队列。若不存在栈溢出问题，则请写出用栈的操作来实现队列的插入和删除的算法。42以下图为例，按dijkstra算法计算得到从顶点A

9、到其他各个顶点的最短路径和最长路径长度。全真模拟试卷（5）一、单项选择题1.以下关于先性表的描述，正确的是_。A线性表中并不是所有元素都有一个直接前驱和一个直接后继B线性表的顺序存储结构插入和撒谎年初是效率太低，因此它不如链式存储结构好。C线性表的链式存储结构的元素随机访问效率太低，因此它不如顺序存储结构好D顺序存储方式的优点是存储密度大，且插入，删除运算效率高。2.用链接方式存储的队列，在进行删除运算是_。A仅修改头指针B仅修改尾指针C头尾指针都有修改D头尾指针可能都要修改3.一棵深度为4的完全二叉排序树，最少有_个结点。A.4 B.8 C.15 D.64.在常用的描述二叉排序树的存储结构中

10、，关键字值最大的结点_。A.左子树一定为空B右子树一定为空C左右子树均为空D左右子树均不为空5.以下关于邻接矩阵的描述，正确的是_。A无向图的邻接矩阵中非0元素数就是该图的边数B无向图的邻接矩阵中非0元素就是该图所有顶点的度之和C有向图的邻接矩阵中第i行的非0元素之和是第i个顶点的入度D有向图的邻接矩阵中第i行的非0元素之和是第i个顶点的出度6.有向图的所有拓扑排序序列有_个。A.2 B.4 C.6 D.77.折半查找有序表（4.6.10.12.20.30.50.70.88.100），若查找元素58，则它将依次与表中元素_比较大小，查找结果是失败。A.20.70.30.50 B.30.88.7

11、0 C.20.50 D.30.88.50.708.下列关于m阶B-树的说法错误的是_。A根结点至多有m棵子树B所有叶子都在同一层次上C非叶结点至少有m/2（m为偶数）或m/2+1（m为奇数）棵子树D根结点中的数据是有序的9.若不考虑基数排序，则在排序过程中，主要的两种基本操作是_。A比较和交换B比较和移动C选择和交换D选择和移动10.归并排序中，归并的趟数是_。A.O(n)B.O（log2n）CO（nlog2n）DO（n2）二、综合应用题41请利用栈的基本操作写出复制一颗二叉树的非递归算法。要求以二叉链表作为二叉树的存储结构。设栈已定义：initstack（S），push(S,e)，stack

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

13、.若栈采用顺序存储方式存储，现两栈共享空间V【m】，top【i】代表第i个栈（i=1,2）栈顶，栈空时栈1的底在v0,top1=0,栈2的底在Vm-1,top2=m-1,则栈满的条件是_。Atop1=top2 B.top1+1=top2 C.top1+top2=m D.top1-1=top23.设计一个判别表达式中左，右括号是否配对出现的算法，采用_数据结构最佳。A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈4.已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为A.B.C.D.E.F.G.H,该完全二叉树的后序遍历序列为_。A.HDEBFGCA B.HEDBF

14、GCA C.HDEBAFGC D.HDEFGBCA5.由带权1.3.5.6.9的5个叶子结点生成的哈夫曼树的带权路径长度为_。A.50 B.52 C.55 D.606.无向图G有16条边，有3个4度顶点，4个3度顶点，其余顶点的度数都小于3，则G中至少有_个顶点。A.12 B.11 C.10 D.157.采用邻接表存储的图的广度优先遍历算法类似于树的_。A中根遍历B先跟遍历C后跟遍历D按层次遍历8.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是_，对于查找成功，它们的平均查找长度是相同的。A相同的B不同的C无法确定的D以上都不对（不要）9

15、.下面关于B-树和B+树的叙述中，不正确的是_。AB-树和B+树都是平衡的多叉树BB-树和B+树都可用于文件的索引结构CB-树和B+树都能有效地支持顺序检索DB-树和B+树都能有效地支持随机检索10第i趟处理是将Ai+1,An中关键字最小者与Ai（i=1,2,.,n-1）进行交换的排序算法为_。A.快速排序B.选择排序C.冒泡排序D.插入排序二、综合应用题41.已知q是一个非空顺序队列，s是一个顺序栈，请设计一个算法，实现将队列q中所有元素逆置。42.已知无向图G=（V,E）的邻接表，给出求图G的联通分量个数的算法。全真模拟试卷（7）一、单项选择题1.以下关于线性表采用链式存储时删除结点运算的

16、描述，正确的是_。A带头结点的线性删除结点时，不需要更改头指针B带头结点的线性链表删除第一个结点时，需要更改头指针C不带头结点的线性链表删除第一个结点时，需要更改头指针D不带头结点的线性链表删除第一个结点时，不需要更改头指针2.若循环队列以数组QOm-1作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=（rear+1）Mod m 进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是_。A.rear-length B.(rear-length+m)Mod m C.(1+rear+m-length)Mod m D.m-length3.

17、如以顺序方式存储二叉树，每个结点占用一个存储单元，则深度为m的单左支二叉树共浪费_个存储单元。A2m-1-m B2m-1-m-1C2m-m-1D2m-m+14.在度为m的哈夫曼树中，其中结点个数为n，则非叶结点的个数为_。A|n/m|-1 B.|(n-1)/(m-1)| C.|n/(m-1)|-1 D.|(n+1)/(m+1)|5.下面关于图的存储的叙述中，正确的是_。A用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关B用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存

18、储图，占用的存储空间数只与图中边数有关，而与结点个数无关6.在有向图G的扩扑中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是_。AG中有弧 B.G中有一条从Vi到Vj的路径CG中没有弧 D.G中有一条从Vj到Vi的路径7.当n足够大时，在按值有序的顺序表中进行折半查找，在查找概率相等的情况下，其查找成功的平均查找长度是_。A（n+1）/2Bn/2 C.log2(n+1)-1 D. log2(n+1)8.二叉查找树的查找效率与二叉树的树形有关，在_是其查找效率最低。A结点太多B完全二叉树C呈单支树D结点太复杂9.对一组数据（84.47.25.15.21）排序，数据的排列次序在排序的过程中的

19、变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 ，则采用的排序是_。A选择B冒泡C快速D插入10.数据序列（8,9,10,4,5,6,20,1,2,）只能是下列排序算法中的_的两趟排序后的结果。A选择排序B冒泡排序C插入排序D堆排序二、综合应用题41.某通信系统只可能有A.B.C.D.E.F.这6种字符，其出现的概率分别为0.1,0.4,0.04,0.16,0.19,0.11,试画出相应的哈夫曼树，并设计哈夫曼编码。42.设有五个数据do,for,if,repeat,while,它们排在一个有

20、序表中，其查找概率分别为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,如下图所示。试画出对该有序表采用顺序查找是的判定树和采用折半查找时的判定树分别计算顺序查找时的查找成功和不成功的平均查找长度，以及折半查找是的查找成功和不成功的凭据查找长度。判定是顺序查找好？还是折半查找好？全真模拟试卷（8）一、单项选择题1.某线性表中最常用的操作时在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。A单链表B仅有头指针的单

21、循环链表C双链表D仅有尾指针的单循环链表2.循环队列存储在数字Am中，则入队时的操作为_。A.rear=rear+1B.rear=(rear+1)%(rear-1)C.rear=(rear+1)%mD.rear=(rear+1)&(m+1)3.以下_方法不能将线性表中元素逆序。A将此线性表表中元素依次全部入栈，在全部出栈，再全部通过一个队列B将此线性表中元素依次全部通过一个队列、再全部入栈、再全部出栈C将此线性表中元素依次全部入栈、再全部出栈、再全部入栈、再全部出栈D将此线性表中元素依次全部通过一个队列、再全部入栈、再全部出栈、再通过一个队列4.一个具有1025个结点的二叉树的高h为_。A11

22、 B.10 C.111025 D.1010245.设森林F中有三棵树，第一，第二，第三，棵树的结点个数分别为N1,N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是_。A.N1 B.N1+M2 C.N3 D.N2+N36.在n个顶点的无向连通图的生成树中，包含顶点数_，顶点中的最小度数是_。An,0 B.n,1 C.n-1,0 D.无法确定7.下列说法不正确的是_。A图的遍历是从给定的源点出发每一个顶点仅被访问一次B遍历的基本算法有两种：深度遍历和广度遍历C图的深度遍历不适用于有向图D图的深度遍历是一个递归过程（不要）8.在二叉平衡序树上成功地找到一个结点（设结点个数为n），在平均情

23、况的最坏情况下的时间复杂性分别是_。AO(log2n),O(n)BO(n),O(n)CO(log2n),O(n2)DO(log2n), O(log2n)9、排序方法有许多种，插入排序法从未排序的序列中依次取出元素，与已排序列(初始时为空)中的元素的作比较，将其放入已排序序列的正确位置上；选择排序法从未排序的序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换，起泡排序和快速排序是基于这类方法的两种排序方法；_法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。A归并排序BShell排序C堆排序D基

24、数排序10、设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、起泡排序和归并排序方法对其进行排序(按递增顺序)，最省时间和最费时间的排序方法是_。A堆排序，起泡排序B快速排序，归并排序C起泡排序，快速排序D起泡排序，归并排序二、综合应用题41、使用普里姆（Prim）算法生成下图的一个最小生成树，并写明每一步的状态。42、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记

25、录的关键码比该记录的关键码小？假使针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。（1）给出适用于计数排序的数据表定义。（2）使用C语言编写实现计数排序的算法。（3）对于有n个记录的表，关键码比较次数是多少？（4）与简单选择排序相比较，这种方法是否更好？为什么？全真模拟试卷（9）一、单项选择题1、设双向链表的结点结构为（prior,data,next），其中prior和next均为指针域，已知指针px指向该链表中的结点x，设定结点x有前去和后继，若删除结点x，并释放所占的空间，则需要执行以下 语句。A) px -prior -next=px -next

26、;px-next -prior=px-prior ;free(px)B) px -prior -next=px -prior ;px-next -prior=px-next ;free(px)C) px -prior -prior=px -next ;px-next -next=px-prior ;free(px)D) px -next -prior=px -next ;px-prior -next=px-prior ;free(px) 2、一个循环队列Q最多可存储m个元素，已知其头尾指针分别是front和rear，则判定该循环对列为满的条件是 。A) Q.rear Q.front = = m

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

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

29、ront rear +m)% m D)(rear -front)%m3、设在某树中，结点M、N是结点P上的第i、i+1个孩子，则在此树的二叉树表示中，结点M与N的关系是 。A）M、N具有同一双亲 B）M是N的左孩子C）N是M的左孩子 D）N是M的右孩子4、以下的叙述中，正确的是 。A）强连通有向图的任何顶点到其他所有顶点都有弧B）任意图顶点的入度等于出度C）有向完全图一定是强连通有向图D）有向图的边集的子集和顶点集的子集可构成原有向图的子图5、如下图所示，已知某个深度优先搜索序列为A*F*，则可能的序列为 。ABDFEC ABCFDE ACEFBD ACEFDB ADCFEB ADBFECA)

30、、和 B)和 C)、 D)、6、适用于折半查找的表的存储方式及元素排列要求为 。A）链接方式存储，元素无序 B）链接方式存储，元素有序C）顺序方式存储，元素无序 D）顺序方式存储，元素有序（不要）7、一个m阶B 树中，每个结点最少有 个儿子结点。A）m B)m/2 C) 2 D)m/28、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用 。A）求关键路径的方法 B）求最短路径的DIJKSTRA方法C）深度优先遍历算法 D）广度优先遍历算法9、在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是 。A）直接插入排序 B）堆排序 C）快速排序 D）起泡排序10、就

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

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

33、的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、D）可以， B）、C）不行。问：为什么要设计队列？它有什么独特用途？离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）；操作系统中的作业调度（一个CPU执行多个作业）；3. 简化程序设计。(1)假溢出顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。(2)如何解决顺序队列的假溢出问题？可采取四种方法：1)采用循环队列； 2)按最大可能的进队操作次数设置顺序队列的最大元素个数； 3)修改出队算法，使每次出队列后都把队列中

34、剩余数据元素向队头方向移动一个位置；)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。顺序循环队列的队空和队满判断问题新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三：使用一个计数器记录队列中元素个数（即队列长）；判队满：count0 & rear=front 判队空：count=0加设标志位，出队时置,入队时置,则可识别当前front=rear属于何种情况判队满：tag=1 & rear=front 判队空：tag=0 & rear=front 少用一个存储单元判队满： fro

35、nt=(rear+1)%MaxQueueSize 判队空： rear=front问：空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串.堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。模式匹配（定位） 设有主串S和子串T（将S称为目标串，将T称为模式串），在主串S中，从位置start开始查找，如若在主串S中找到一个与子串T相等的子串，则返回T的第一个字符在主串中的位置，否则返回-1。2、算法目的 确定主串中所含子串第一次出现的位置（定位）

36、 3、算法种类 BF算法 （又称古典的、经典的、朴素的、穷举的） KMP算法1、二叉树的带权路径长度：从二叉树根结点到所有叶子结点的路径长度与相应叶子结点权值的乘积（WPL）WPL = ?wklk 2、例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码（如二进制编码）令d=00，i=01，a=10，n=11，则：WPL12bit(7524）36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：WPL2=1bit72bit5+3bit(2+4)=353、对权值进行合并、删除与替换4、

37、若集合X上的关系R是自反的、对称的和传递的，则称关系R是集合X上的等价关系。5、树转二叉树举例：方法：加线抹线旋转 6、讨论2：二叉树怎样还原为树？要点：逆操作，把所有右孩子变为兄弟！1.1数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。1.2计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作的学科。程序设计好算法好结构1.3数据类型：指一个类型和定义在这个类型上的操作集合。例：C语言（基本类型：整型、浮点型、字符型等构造类型：

38、数组、结构、联合、指针、枚举等）抽象数据元素：抽象定义的、没有实际含义的数据元素。抽象数据类型：用户自己定义的数据类型。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。逻辑结构、存储结构和运算合称为三要素。表示为： Data_Structure=（D, R） 其中，D元素有限集，R关系有限集1.4抽象数据类型：用户自己定义的数据类型。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。或按照一定逻辑关系组织，并按一定存储方法存储的数据的集合，且需要定义一系列运算。形式定义表示为： Data_Str

39、ucture=（D, R）其中，D元素有限集，R关系有限集数据结构的三要素：逻辑结构、存储结构和运算。1.5数据逻辑结构（本质）定义：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。1.6数据的物理结构定义：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。1.7抽象数据类型(Abstract Data Type)：是一个数学模型以及定义在该模型上的一组操作。由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。1.8算法概念：算法是一个有限的指令集，遵循指令流可以完成特定

40、的功能。算法基本特征：有穷性：算法经有限步后结束。确定性：下一步必须是明确的。可行性：每一是可以执行的。1.9评价指标正确性可读性健壮性高效率与低存储量需求(见课本P20)1.0若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , , an） 特点 只有一个首结点和尾结点；特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是 的。线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-(1)顺序存储结构:它是使用一片XXX连续的有限内存单元空间

41、存储数据元素的一种计算机存储数据方法。特点：(任意两个在逻辑上相邻的数据元素在物理位置上也必然相邻)逻辑上相邻的元素，物理上也相邻。(2)链式存储结构:它是把数据元素和指针定义成一个存储体，使用指针把发生联系的数据元素链接起来的一种计算机存储数据方法。特点：(任意两个在逻辑上相邻的数据元素在物理上不一定相邻，数据元素的逻辑次序是通过链中的指针链接实现的)逻辑上相邻元素,物理上不一定相邻。栈“上溢”在栈满时还进行入栈运算，必定会产生空间的溢出,栈“下溢”当栈空时仍进行出栈运算，必定会产生空间的溢出。例1：堆栈是什么？它与一般线性表有什么不同？ 堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进

42、行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。一般线性表 堆栈逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈运算规则：随机存取 运算规则：后进先出(LIFO)树的度树的深度(或高度)所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）性质3: 对于任何一棵非空的二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）证明： 二叉树中全部结点数nn0+n1+n2(叶子数1度结点数2度结点数)又二叉树中全部结点数nB+1 ( 总分支数根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支）而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必有2个)三式联立可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1性质4: 具有n个结点的完全二叉树的深度k必为?log2(n+1)?-1(假定k为0时表示此二叉树仅有根结点）证明：根据性质2，深度为k的二叉树最多只有2k+1-1个结点，且完