数据结构原理与分析--01343--18日下-复习资料.docVIP

数据结构原理与分析-01343-18日下-复习资料 一、填空 1.线性表是具有n个什么的有限序列（数据元素 ）。 2.邻接表的存储结构下图的深度优先遍历类似于二叉树的(先序遍历)。 3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2）。 4.某二叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树(高度等于其结点数)。 5.对于栈操作数据的原则是（后进先出 ）。 6.结点前序为xyz的不同二叉树，所具有的不同形态为(5 )。 7.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n) )。 8.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h )。 9.具有n个顶点的有向无环图最多可包含有向边的条数是(n(n-1)/2 )。 10.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是 (d ). 11. 若二叉树中度为2的结点有15个，度为1 的结点有10个，则叶结点的个数（16）。 12.对于一棵满二叉树，m个树叶，n个结点，深度为h,则(n=2h＋1-1 )。 13.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ n+1 ） 14.用邻接表表示图进行深度优先遍历时，通常用来实现算法的辅助结构是(栈 )。 15.堆的形状是一棵(完全二叉树 )。 16.若在一棵非空树中，某结点A有3个兄弟结点（包括A自身），B是A的双亲结点，则B的度为(4 )。 17.任何一个无向连通图的最小生成树(有一棵或多棵 ) 18.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点 )。 19.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( 插入排序 )。 20.对于一棵满二叉树，m个树叶，n个结点，深度为h,则(n=2h＋1-1 )。 21.具有n个顶点的有向图最多可包含的有向边的条数是(n(n-1))。 22.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树(空或只有一个结点)。 23.栈和队列的主要区别在于 (插入删除运算的限定不一样)。 24.串是（任意有限个字符构成的序列 ）。 25.对有14个数据元素的有序表R[14]进行折半有哪些信誉好的足球投注网站，有哪些信誉好的足球投注网站到R[3]的关键码等于给定值，此时元素比较顺序依次为（R[6]，R[2]，R[4]，R[3]）。 26.深度为h且有多少个结点的二叉树称为满二叉树(2h+1-1)。 27.在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（n2-2e）。 28.在一个有向图中，所有顶点的入度之和与所有顶点出度之和的倍数为(1)。 29.邻接表的存储结构下图的广度优先遍历类似于二叉树的(按层遍历)。 30.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为(2h-1)。 31.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（11） 32.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（n+1） 33.若一棵二叉树有11个度为2的结点，则该二叉树的叶结点的个数是（12）。 34.对有n个记录的表按记录键值有序建立二叉查找树，在这种情况下，其平均查找长度的量级为（O(n) ）。 35.设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和m3,则森林F对应的二叉树根结点上的右子树上结点个数是 ( m2+m3)。 36.对有18个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为（9、4、2、3）。 37.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(各自的尾结点)。 38.深度为h的满二叉树所具有的结点个数是（2h+1-1 ）。 39.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（2h-1）。 40.如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的（先根序列）。 41.有n个叶子的哈夫曼树的结点总数为（2n-1）。 42.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n))。 43.若二叉树中度为2的结点有15个，度为1 的结点有10个，则叶子结点的个数为（16）。 44.若某完全二叉树的深度为h，则该完全二叉树中具有的结点数至少是(2h－1)。 45.叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树(度等于其结点数 )。 46.初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为(n-1)。 4