资源描述:
《数据结构原理与分析--01343--18日下-复习资料》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、数据结构原理与分析-01343-18日下-复习资料一、填空1.线性表是具有n个什么的有限序列(数据元素)。2.邻接表的W储结构下图的深度优先遍历类似于二叉树的(丸序遍历)。3•在一棵二叉树的二义链表中,空指针域数等于非空指针域数加S4.某二义树的前序和后序序列正好相反,则该二叉树一定是什么二叉树(高度等于其结点数)。5•对于栈操作数据的原则是(后进先出)。6•结点前序为xyz的不同二叉树,所只有的不同形态为(5).7.设长度为n的链队列用单循坏链表表示,若只设头指针,则入队操作的时间复杂度为(0(n))。&在一棵髙度为h(假定树根结点的层号为0)的完全二叉树中,所含结
2、点个数不小于(2h)o9•具有n个顶点的有向无环图最务可包含有向边的条数是(n(n-l)/2),10.因此在初始为空的队列中插入元索弘b,c,d以后,紧接看作了两次删除操作,此时的队尾元素是(d).11.若二叉树中度为2的结点有15个,度为1的结点有10个,则叶结点的个数(16).12•对于一棵满二叉树,in个树叶,n个结点,深度为h,WJ(n=2h+l-l)。13.在一棵具有n个结点的二叉树中,所有结点的空子树个数等于(n+1)11.用邻接表表示图进行深度优先邂历时,通常用來实现绰法的辅助结构是(栈)o15.堆的形状是一棵(完全二叉树)«16.若在一棵非空树中,某结
3、点A有3个兄弟结点(包扌iSA白身人B是A的双亲结点,则B的度为(4)o17•任何一个无向连通图的最小生成树(有一棵或多棵)18.在非空二叉树的中序遍历序列中.二叉树的根结点的左边应该(只有左子树h的所有结点)。19•排序方法中,从未排序序列中依次取出元素与己排序序列中的元素进行比絞,将其放入已排序序列的正确位置上的方法,称为(插入排序).20•对于一棵满二叉树,in个树叶,n个结点,深度为h,KiJ(n=2h+l-l).21.具有n个顶点的有向图最务可包含的有向边的条数是(n(n-l))。22.某二叉树的前序和后序序列iE好相同,则该二叉树一定是什么样的二叉树(空或
4、只有一个结点)。23•栈和队列的主要区别在于(插入删除运算的限定不一样)。24.串是(任意有限个字符构成的序列)。25.对有14个数据元素的有序表R[14]进行折半捜囊,捜索到R[3]的关键码等于给定值,此时元素比较顺序依次为(R〔6],R[2],R[4],R[3])。26.深度为h且有多少个结点的二叉树称为满二叉树(2h+lT>°27•在含ri个顶点e条边的无向图的邻接矩阵中,零元素的个数为(n2-2e)o2&在一个有向图中,所有顶点的入度之和与所有顶点出度之和的倍数为(1)。29.邻接浚的存储结构下图的广度优先遍历类似于二叉树的(按层遍历几30.设高度为h的二叉树
5、上只冇度为0和度为2的结点,则此类二叉树中所包含的结点数至少为(2h-l).31•若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(11)32.在-•棵具有n个结点的二叉树中,所有结点的空子树个数等于(屮1)33.若一棵二叉树有11个度为2的结点,则该二叉树的叶结点的个数是(12)。34.对有n个记录的表按记录键值有序建立二叉查找树,在这种悄况下,其平均査找长度的最级为(0(n)人35•设森林F中有三棵树,第一、笫二和笫三棵的结点个数分别为ml.m2和m3.则繰林F对应的二叉树根结点上的右子树上结点个数是(m2+m3}。36.对有18个元素的
6、有序表作二分(折半)查找,则査找A[3]的比较序列的下标为(9、4、2、3)。37•若要在0(1)的时间复杂度上实现两个循环链表头尾相接,则应对两个循环链表各设宜一个指针,分别指向(乞白的尾结点)。38.深度为h的满二叉树所具有的结点个数是(2h»l-l39.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为(2X1)。40.如果T2是由有序树T转换而来的二叉树,那么T中结点的先根序列就是T2中结点的(先根序列九•11.有n个叶子的哈夫曼树的结点总数为(2n-l).42.设长度为n的链队列川单循坏链表表示,若只设头指针,则入队操作的时间复
7、杂度为(0(n))o43.若二叉树中度为2的结点有15个,度为1的结点有10个,则叶子结点的个数为(16).•14•若某完全二叉树的深度为h,则该完全二叉树中具有的结点数至少是(2h-l)。45.叉树的前序和后序序列正好相反,则该二义树一定是什么二叉树(度等于其结点数)。•16•初始屏列已经按键值有序时,用辽接插入算法进行排字,需要叱较的次数为(n-1)«47.接表表示图进行广度优先遇历时,为实现算法通常采用的辅助结构是(队列)。佃•用目泡排序法对序列{18,16,14,12,10,8}从小到大进行排序,需要进行的比较次数是仃5几49.Un个顶点的图