《数据结构原理与分析--01343--18日下-复习资料》由会员分享，可在线阅读，更多相关《数据结构原理与分析--01343--18日下-复习资料（21页珍藏版）》请在金锄头文库上搜索。
1、数据结构原理与分析数据结构原理与分析-01343-18-01343-18 日下日下- -复习复习资料资料一、填空一、填空1.线性表是具有 n 个什么的有限序列（数据元素 ） 。2.邻接表的存储结构下图的深度优先遍历类似于二叉树的(先序遍历)。3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（2） 。4.某二叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树(高度等于其结点数)。5.对于栈操作数据的原则是（后进先出 ） 。6.结点前序为 xyz 的不同二叉树，所具有的不同形态为(5 )。7.设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n)
2、)。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=2h1-1 )。13.在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（ n+1 ）14.用邻接表表示图进行深度优先遍历时，通常用来
3、实现算法的辅助结构是(栈 )。15.堆的形状是一棵(完全二叉树 )。16.若在一棵非空树中，某结点 A 有 3 个兄弟结点（包括 A 自身） ，B 是 A 的双亲结点，则 B 的度为(4 )。17.任何一个无向连通图的最小生成树(有一棵或多棵 )18.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点 )。19.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( 插入排序 )。20.对于一棵满二叉树，m 个树叶，n 个结点，深度为 h,则(n=2h1-1 )。21.具有 n 个顶点的有向图最多可包含的有向
4、边的条数是(n(n-1)。22.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树(空或只有一个结点)。23.栈和队列的主要区别在于 (插入删除运算的限定不一样)。24.串是（任意有限个字符构成的序列 ） 。25.对有 14 个数据元素的有序表 R14进行折半搜索，搜索到 R3的关键码等于给定值，此时元素比较顺序依次为（R6，R2，R4，R3） 。26.深度为 h 且有多少个结点的二叉树称为满二叉树(2h+1-1)。27.在含 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为（n2-2e） 。28.在一个有向图中，所有顶点的入度之和与所有顶点出度之和的倍数为(1)。29.
5、邻接表的存储结构下图的广度优先遍历类似于二叉树的(按层遍历)。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 中有三棵树，第一、第二和第三棵的
6、结点个数分别为 m1,m2 和 m3,则森林 F 对应的二叉树根结点上的右子树上结点个数是 ( m2+m3)。36.对有 18 个元素的有序表作二分（折半）查找，则查找 A3的比较序列的下标为（9、4、2、3） 。 37.若要在 O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(各自的尾结点)。38.深度为 h 的满二叉树所具有的结点个数是（2h+1-1 ） 。39.设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（2h-1） 。40.如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的先根序列就
7、是 T2 中结点的（先根序列） 。41.有 n 个叶子的哈夫曼树的结点总数为（2n-1） 。42.设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为(O(n)。43.若二叉树中度为 2 的结点有 15 个，度为 1 的结点有 10 个，则叶子结点的个数为（16） 。44.若某完全二叉树的深度为 h，则该完全二叉树中具有的结点数至少是(2h1)。45.叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树(度等于其结点数 )。46.初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为(n-1)。47.接表表示图进行广度优先遍历时，为实现算法通常采用的辅
8、助结构是(队列)。48.用冒泡排序法对序列18,16,14,12,10,8从小到大进行排序，需要进行的比较次数是(15)。49.有 n 个顶点的图采用邻接矩阵表示，则该矩阵的大小为（n*n） 。50.6 个顶点的无向图成为一个连通图至少应有边的条数是（5） 。51.单链表中，增加头结点的目的是为了（方便运算的实现） 。52.在线索二叉树中,结点(*t)没有左子树的充要条件是(t-ltag=1)。53.按照二叉树的定义,具有 3 个结点的二叉树有多少种(5)。54.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序
9、方法是（快速排序）55.二分查找法要求查找表中各元素的键值必须是(递增或递减 )。56.线性表的长度是指（表中的元素个数）57.将长度为 m 的单链表连接在长度为 n的单链表之后的算法的时间复杂度为(O(n)。58.有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值为 82 的结点时，查找成功的比较次数是（4） 。.59.若在一棵非空树中，某结点 A 有 3 个兄弟结点（包括 A 自身） ，B 是 A 的双亲结点，则 B 的度为（4） 。60.深度为 h 的满二叉树具有的结点个数为（2h+1-1） 。61.用二叉链表存储树，则根结点的右指针是（
10、空） 。62.个无向图中，所有顶点的度数之和等于所有边数（1）倍。63.单链表表示的链式队列的队头在链表的什么位置（链头） 。64.线性表的长度是指（表中的元素个数 ）65.某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树(空或只有一个结点)。66.在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（n+1） 。67.一个具有 n 个顶点 e 条边的无向图中，采用邻接表表示，则所有顶点的邻接表的结点总数为（2e） 。68.链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。69.对于键值序列72,73,71,23,94,16,5,68,76,103用筛选法
11、建堆，开始结点的键值必须为(94)。70.在图形结构中，每个结点的前驱结点数和后续结点数可以有(任意多个)。71.对有 n 个记录的有序表采用二分查找，其平均查找长度的量级为(O(log2n)。72.在一棵高度为 h(假定树根结点的层号为 0)的完全二叉树中，所含结点个数不小于(2h)。73.若一棵二叉树有 10 个叶结点，则该二叉树中度为 2 的结点个数为 9。74.设有一个顺序栈 S，元素S1，S2，S3，S4，S5，S6 依次进栈，如果6 个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为 3。75.对于一棵二叉树，设叶子结点数为 n0,次数为 2 的结点数为
12、n2,则 n0 和 n2 的关系是 n0= n21。76.若一棵二叉树有 12 个叶结点，则该二叉树中度为 2 的结点个数为 11。77.二叉树的存储结构有顺序存储结构和链式存储结构。78.深度为 h 且有 2k-1 个结点的二叉树称为满二叉树。(设根结点处在第 1 层)。79.图的深度优先搜索方法类似于二叉树的先序遍历 。80.哈夫曼树是带权路径长度最小的二叉树。 81.在线索二叉树中，线索是指向结点在某遍历次序下的前驱或后继结点的指针。 82.栈可以作为实现递归函数调用的一种数据结构 。83.一般树的存储结构有双亲表示法、孩子兄弟表示法和孩子链表表示法。84.将数据元素2,4,6,8,10
13、,12,14,16,18,20 依次存于一个一维数组中，然后采用折半查找元素12，被比较过的数组元素的下标依次为5，7，6 。 。85.图的深度优先遍历序列不是唯一的。86.若二叉树的一个叶子结点是某子树的中根遍历序列中的第一个结点，则它必是该子树的后跟遍历中的第一个结点。87.图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被 _ 访问一次。 88.在一个图中，所有顶点的度数之和等于所有边的数目的 2 倍 。89.由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树 。90.在有序表(12,24,36,48,60,72,84)中二分查找关键字 72 时所需进行的关键字比较次数为
14、2。 91.设根结点的层数为 0，定义树的高度为树中层数最大的结点的层数加 1，则高度为 k 的二叉树具有的结点数目，最少为k，最多为 2k-1。92.在直接插入排序、直接选择排序、分划交换排序、堆排序中稳定的排序方法有直接插入排序。93.具有 100 个结点的完全二叉树的叶子结点数为 50。94.普里姆(Prim)算法适用于边稠密图。95.在有 n 个叶子结点的哈夫曼树中,其结点总数为 2n-1。96.将一棵树转换成一棵二叉树后，二叉树根结点没有右子树。97.矩阵采用压缩存储是为了节省空间98.若连通网络上各边的权值均不相同，则该图的最小生成树有 1 棵。99.设无向图 G 的顶点数为 n，
15、则要使 G 连通最少有 n-1 条边。100.栈和队列的共同特点是插入和删除均在端点处进行。101.克鲁斯卡尔(Kruskar)算法适用于边稀疏图。102.若连通图的顶点个数为 n，则该图的生成树的边数为 n-1。103.图的存储结构最常用的有邻接矩阵和邻接表。104.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。105.队列中允许进行插入的一端称为队尾。106.拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在环。107.在有序表(15,23,24,45,48,62,85)中二分查找关键词 23 时所需进行的关键词比较次数为 2。108.树中所有结点的度等于所有结点数加（-1）
16、。109.在一个具有 n 个顶点的完全无向图的边数为 (n(n-1)/2)。110.用分划交换排序方法对包含有 n 个关键的序列进行排序，最坏情况下执行的时间杂度为(O(n2)111.一棵高度为 h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h)。112.若长度为 n 的非空线性表采用顺序存储结构，删除表的第 i 个数据元素，首先需要移动表中数据元素的个数是（n-i） 。113.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点)。114.若一棵二叉树具有 45 个度为 2 的结点，6 个度为 1 的结点，则度为 0 的结点个数是（46） 。115.在一个有向图中，所有顶点的入度之和等于所有边数（4）倍。116.设输入序列为 A,B,C,D,借助一个栈不可以得到的输出序列是(D,A,B,C )。117.一维数组 A 采用顺序存储结构，每个元素占用 6 个字节，第 6 个元素的起始地址为 100，则该数组的首地址是（70） 。118.设 a
