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

数据构造原理与分析-133-18日下-复习资料一、填空1.线性表是具有个什么的有限序列（数据元素 ）。2.邻接表的存储构造下图的深度优先遍历类似于二叉树的(先序遍历)。3在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加(2）。4.某二叉树的前序和后序序列正好相反,则该二叉树一定是什么二叉树(高度等于其结点数)。5对于栈操作数据的原则是（后进先出 ）。6.结点前序为z的不同二叉树,所具有的不同形态为(5 )。7.设长度为n的链队列用单循环链表表达,若只设头指针，则入队操作的时间复杂度为（O(） )。.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不不不小于(h ）。9具有n个顶点的有向无环图最多可包具有向边的条数是(n(n-1)2 ）。10.因此在初始为空的队列中插入元素a，b,c，后来，紧接着作了两次删除操作，此时的队尾元素是(d).11. 若二叉树中度为的结点有15个，度为1 的结点有10个，则叶结点的个数（16）。对于一棵满二叉树,m个树叶，n个结点，深度为h，则(=h+-1 )。13在一棵具有个结点的二叉树中,所有结点的空子树个数等于（ +1 ）14.用邻接表表达图进行深度优先遍历时，一般用来实现算法的辅助构造是(栈 )。1.堆的形状是一棵(完全二叉树 )。若在一棵非空树中，某结点有个兄弟结点（涉及A自身）,B是的双亲结点,则B的度为( )。17.任何一种无向连通图的最小生成树(有一棵或多棵 ).在非空二叉树的中序遍历序列中，二叉树的根结点的左边应当(只有左子树上的所有结点)。19排序措施中,从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的对的位置上的措施，称为( 插入排序 )。20.对于一棵满二叉树，m个树叶,个结点,深度为h，则(n=211 ）。21.具有n个顶点的有向图最多可涉及的有向边的条数是(n(n-1)。2.某二叉树的前序和后序序列正好相似，则该二叉树一定是什么样的二叉树(空或只有一种结点)。23.栈和队列的重要区别在于 （插入删除运算的限定不同样）。24串是（任意有限个字符构成的序列 ）。.对有14个数据元素的有序表4进行折半搜索,搜索到R的核心码等于给定值,此时元素比较顺序依次为（R6，R2,4,R3)。26深度为h且有多少个结点的二叉树称为满二叉树(h1-1)。27.在含n个顶点e条边的无向图的邻接矩阵中,零元素的个数为(n-2e）。28在一种有向图中,所有顶点的入度之和与所有顶点出度之和的倍数为(1)。9.邻接表的存储构造下图的广度优先遍历类似于二叉树的(按层遍历)。30.设高度为h的二叉树上只有度为和度为2的结点,则此类二叉树中所涉及的结点数至少为（2-1）。31.若一棵二叉树具有0个度为2的结点,5个度为的结点，则度为的结点个数是（11)32.在一棵具有n个结点的二叉树中,所有结点的空子树个数等于(n+1)33若一棵二叉树有11个度为的结点,则该二叉树的叶结点的个数是（)。3.对有n个记录的表按记录键值有序建立二叉查找树,在这种状况下，其平均查找长度的量级为(O(n） )。35.设森林F中有三棵树，第一、第二和第三棵的结点个数分别为1,m2和3,则森林F相应的二叉树根结点上的右子树上结点个数是 ( m+3)。6.对有18个元素的有序表作二分(折半)查找,则查找A3的比较序列的下标为（9、4、2、3）。 37.若要在O（1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设立一种指针，分别指向（各自的尾结点）。38.深度为h的满二叉树所具有的结点个数是（2h+1-1)。39.设高度为的二叉树上只有度为和度为的结点,则此类二叉树中所涉及的结点数至少为(h-）。40.如果T2是由有序树转换而来的二叉树，那么中结点的先根序列就是T2中结点的(先根序列)。4.有n个叶子的哈夫曼树的结点总数为(2n-1）。42.设长度为的链队列用单循环链表表达，若只设头指针，则入队操作的时间复杂度为(O()。3.若二叉树中度为2的结点有15个，度为1 的结点有10个,则叶子结点的个数为（16）。4若某完全二叉树的深度为h，则该完全二叉树中具有的结点数至少是(2-1)。4.叉树的前序和后序序列正好相反,则该二叉树一定是什么二叉树(度等于其结点数 )。4.初始序列已经按键值有序时,用直接插入算法进行排序,需要比较的次数为（1)。4.接表表达图进行广度优先遍历时，为实现算法一般采用的辅助构造是（队列)。48.用冒泡排序法对序列8,16,14,12,，从小到大进行排序，需要进行的比较次数是（15)。49有n个顶点的图采用邻接矩阵表达，则该矩阵的大小为（n*）。5.6个顶点的无向图成为一种连通图至少应有边的条数是()。51单链表中，增长头结点的目的是为了（以便运算的实现)。2.在线索二叉树中,结点(*t)没有左子树的充要条件是(-lta=）。53.按照二叉树的定义,具有个结点的二叉树有多少种(5)。5.看待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作,直到子序列为空或只剩一种元素为止。这样的排序措施是（迅速排序）5.二分查找法规定查找表中各元素的键值必须是(递增或递减 ）。5.线性表的长度是指(表中的元素个数）57.将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为(O()。58.有一种有序表为1，3，9,12，32,1，45,2,75,77,82，95,100，当二分查找值为8的结点时，查找成功的比较次数是（4)。59若在一棵非空树中,某结点A有3个兄弟结点(涉及自身），B是A的双亲结点,则的度为（4)。0.深度为h的满二叉树具有的结点个数为(2h+1-1）。61.用二叉链表存储树,则根结点的右指针是（空）。62.个无向图中,所有顶点的度数之和等于所有边数(1）倍。3.单链表表达的链式队列的队头在链表的什么位置(链头）。64线性表的长度是指(表中的元素个数 )65.某二叉树的前序和后序序列正好相似,则该二叉树一定是什么样的二叉树（空或只有一种结点)。66.在一棵具有个结点的二叉树中,所有结点的空子树个数等于(n+)。67.一种具有n个顶点e条边的无向图中,采用邻接表表达,则所有顶点的邻接表的结点总数为(2e）。6.链栈和顺序栈相比，有一种较明显的长处是（一般不会浮现栈满的状况)。69.对于键值序列72,73，71，23,5,68,7,13用筛选法建堆,开始结点的键值必须为(94)。70.在图形构造中,每个结点的前驱结点数和后续结点数可以有(任意多种)。1.对有n个记录的有序表采用二分查找,其平均查找长度的量级为（O(log2n)。72.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不不不小于(2h)。73.若一棵二叉树有10个叶结点,则该二叉树中度为的结点个数为9。4.设有一种顺序栈，元素S1，2，S3,S，S5，S依次进栈,如果6个元素的出栈顺序为S2，3，S，S6，S5,1，则顺序栈的容量至少应为3。75.对于一棵二叉树，设叶子结点数为n0,次数为2的结点数为n,则和2的关系是= n2+。6若一棵二叉树有12个叶结点,则该二叉树中度为2的结点个数为1。77二叉树的存储构造有顺序存储构造和链式存储构造。7深度为h且有-1个结点的二叉树称为满二叉树。(设根结点处在第1层)。7.图的深度优先搜索措施类似于二叉树的先序遍历。80.哈夫曼树是带权途径长度最小的二叉树。 1.在线索二叉树中,线索是指向结点在某遍历顺序下的前驱或后继结点的指针。82.栈可以作为实现递归函数调用的一种数据构造 。83.一般树的存储构造有双亲表达法、孩子兄弟表达法和孩子链表表达法。84.将数据元素2,4，6,，10,12,14,6,18,2依次存于一种一维数组中，然后采用折半查找元素,被比较过的数组元素的下标依次为5，7，6 。8.图的深度优先遍历序列不是唯一的。86若二叉树的一种叶子结点是某子树的中根遍历序列中的第一种结点，则它必是该子树的后跟遍历中的第一种结点。87.图的遍历是指从图中某一顶点出发访问图中所有顶点且使每一顶点仅被 _ 访问一次。 88.在一种图中，所有顶点的度数之和等于所有边的数目的2倍 。89由一棵二叉树的后序序列和中序序列可唯一拟定这棵二叉树 。0在有序表(12,24,36,48,60,2,84)中二分查找核心字2时所需进行的核心字比较次数为2。 91.设根结点的层数为,定义树的高度为树中层数最大的结点的层数加1,则高度为k的二叉树具有的结点数目，至少为k，最多为2-1。9在直接插入排序、直接选择排序、分划互换排序、堆排序中稳定的排序措施有直接插入排序。9.具有00个结点的完全二叉树的叶子结点数为0。94.普里姆（Prim)算法合用于边稠密图。95.在有n个叶子结点的哈夫曼树中,其结点总数为2-1。6.将一棵树转换成一棵二叉树后,二叉树根结点没有右子树。9矩阵采用压缩存储是为了节省空间98.若连通网络上各边的权值均不相似，则该图的最小生成树有1棵。99.设无向图G的顶点数为,则要使G连通至少有-条边。00.栈和队列的共同特点是插入和删除均在端点处进行。01.克鲁斯卡尔（rusar)算法合用于边稀疏图。2.若连通图的顶点个数为n，则该图的生成树的边数为n1。103.图的存储构造最常用的有邻接矩阵和邻接表。104.由一棵二叉树的前序序列和中序序列可唯一拟定这棵二叉树。0.队列中容许进行插入的一端称为队尾。16.拓扑排序输出的顶点数不不小于有向图的顶点数,则该图一定存在环。10.在有序表(15，23,24,45,8,62，85)中二分查找核心词23时所需进行的核心词比较次数为2。08.树中所有结点的度等于所有结点数加(-1)。109在一种具有n个顶点的完全无向图的边数为 （n）/2)。1.用分划互换排序措施对包具有n个核心的序列进行排序，最坏状况下执行的时间杂度为（O（2)11.一棵高度为h（假定树根结点的层号为0)的完全二叉树中，所含结点个数不不不小于（)。12若长度为n的非空线性表采用顺序存储构造，删除表的第个数据元素，一方面需要移动表中数据元素的个数是（n-）。113在非空二叉树的中序遍历序列中，二叉树的根结点的左边应当（只有左子树上的所有结点）。.若一棵二叉树具有4个度为2的结点，6个度为的结点，则度为0的结点个数是（4）。115.在一种有向图中,所有顶点的入度之和等于所有边数（）倍。116.设输入序列为A,B,C,D，借助一种栈不可以得到的输出序列是(D,A，B,C )。17.一维数组A采用顺序存储构造,每个元素占用个字节,第6个元素的起始地址为100,则该数组的首地址是(70）。118.设abcde以所给的顺序进栈,若在进栈操作时,容许退栈操作,则下面得不到的序列为（cbdef）。19.一般状况下，将递归算法转换成等价的非递归算法应当设立(堆栈）。10.若长度为n的非空线性表采用顺序存储构造,删除表的第i个数据元素,i的合法值应当12.是（C. 1n)。12若某线性表中最常用的操作是取第i个元素和删除最后一种元素，则采用什么存储方3.式最节省时间（顺序表）。14.一组记录的核心字为5， 80, 55，0, 4， 5,则运用堆排序的措施建立的初始堆为（85, 0, 5,40, 2,45)。125.设有6000个无序的元素,但愿用最快的速度挑选出其中前5个最大的元素，最佳选用(堆排序)法。12.排序措施中,从未排序序列中挑选元素,将其放入已排序序列的一端的措施，称为(选择排序）。127带头结点的单链表ea为空的判断条件是（ead-net=NULL)。18.在一种单链表中,若删除（*)结点的后继结点,则执行(p-next=pnext-next）。129.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于(n+1)3.有向图中,以顶点v为终点的边的数目，称为顶点v的（入度)。31.若频繁地对线性表进行插入和删除操作，该线性表应当采用的存储构造是(链式）。12.设一种栈的输入序列是 ,2,4，5，则下列序列中，是栈的合法输出序列的是（1 )。33.有数据3，30,37，2,45，4,从空二叉树开始逐个插入数据来形成二叉查找树，若但愿高度最小，则应选择下面输入序列是（,24,12,0,5,5,96）。14二叉树的第层上最多具有结点数为（2I)。135稀疏矩阵一般采用的压缩存储措施为（三元组表)。136.某二叉树的前序和后序序列正好相似，则该二叉树一定是什么样的二叉树（空或只有一种结点)。137.若长度为n的线性表采用顺序存储构造，在表的第个位置插入一种数据元素，需要移动表中元素的个数是（-+）。138.设有数组Ai，数组的每个元素长度为3字节,i的值为 到8 ，j的值为1 到1,数组从内存首地址B开始顺序寄存,当用以列为主寄存时，元素5，8的存储首地址为（B10)。139.二维数组6的每个元素占个单元，将其按行优先顺序存储在起始地址为000的持续的内存单元中,则元素A45的存储地址为(345)。10.一种具有n个顶点的图采用邻接矩阵表达,则该矩阵的大小为（n*n)。41.若字符串“234567”采用链式存储，假设每个字符占用个字节，每个指针占用2个字节，则该字符串的存储密度为（3.）。1.若在一棵非空树中，某结点A有3个兄弟结点(涉及A自身)，B是A的双亲结点,则的度为(3)。43.设有三个元素X,Y，Z顺序进栈（进的过程中容许出栈)，下列得不到的出栈排列是(ZXY）。144.树形构造的特点是:一种结点可以有 (多种直接后继)。14.使具有30个顶点的无向图成为一种连通图至少应有边的条数是（2)。146使具有9个顶点的无向图成为一种连通图至少应有边的条数是（)。47.在顺序表(n足够大）中进行顺序查找,其查找不成功的平均长度是（1 )。48设树T的度为4,其中度为，3和4的结点个数分别为4,1 则中的叶子数为（8)。19.栈的插入和删除操作进行的位置在（栈顶）。150.若一棵二叉树具有0个度为2的结点,个度为1的结点，则度为0的结点个数是(1)。1一棵线索二叉树的线索个数比链接个数多(2)个。52.在循环 链表中,从任何一结点出发都能访问到表中的所有结点。153.在n个结点的顺序表中插入一种结点需平均移动n/2 个结点。 154.循环队列的引入,目的是为了克服假溢出 。155.若连通网络上各边的权值均不相似，则该图的最小生成树有棵 。5.二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历。15若一棵二叉树有15个叶结点,则该二叉树中度为2的结的点个数为。158设某二叉树的后序遍历序列为ABKCBPM，则可知该二叉树的根为M 。159数据构造的三个方面:数据的逻辑构造、物理构造、运算。60.每个结点只有一种链接域的链表叫做单链表。61.构成串的数据元素只能是字符。162.具有n个结点的二叉树采用链接构造存储,链表中寄存NULL指针域的个数为(n+1)。163在一种无向图中，所有顶点的度数之和等于所有边数（）倍。164设二叉树根结点的层次为,一棵高度为 的满二叉树中的结点个数是(2h+1)。165.将一棵有50个结点的完全二叉树按层编号，则对编号为2的结点x，该结点（有左孩子,无右孩子)。1.树(或树形)的定义是什么？答：一种树（或树形）就是一种有限非空的结点集合T，其中有一种特别标出的称为该树之根rot(T）的结点;其他（除根外)的结点划提成个不相交集合，并且这些集合的每一种又都是树。16在图形构造中，每个结点的前驱结点数和后续结点数可以有(任意多种 )。16.什么是树的途径长度?答:树的途径长度是指从根结点到树中每个叶结点的途径长度之和。二、选择1.若某线性表中最常用的操作是取第个元素和删除最后一种元素，则采用什么存储方式最节省时间()。A. 顺序表 B. 单链表. 双链表. 单循环链表.在下述的排序措施中,不属于内排序措施的是（)。A.插入排序法 B选择排序法C.拓扑排序法归并排序法3.下列四个核心词序列中,不是堆的序列为（C)。A.05,23,16,8,94,72,1,73 05,6,23，68,94,72，71，7305,2，1,94,72，1，6 D.05,2,16,68，7,71,72,4 4.下列排序算法中，某一趟结束后未必能选出一种元素放其最后位置上的是（ )。. 堆排序 冒泡排序C.迅速排序.直接插入排序.用孩子兄弟链表表达一棵树,若要找到结点x的第5个孩子，只要先找到x的第一种孩子,然后(D)。A.从孩子域指针持续扫描5个结点即可B从孩子域指针持续扫描个结点即可C.从兄弟域指针持续扫描5个结点即可D从兄弟域指针持续扫描4个结点即可.链栈和顺序栈相比，有一种较明显的长处是(A)。A一般不会浮现栈满的状况 B.一般不会浮现栈空的状况C插入操作更加以便 D.删除操作更加以便7.任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（C)。. 肯定发生变化 . 有时发生变化C 肯定不发生变化. 无法拟定8排序措施中，从未排序序列中挑选元素,将其放入已排序序列的一端的措施，称为(D）。A.希尔排序 冒泡排序 C. 插入排序选择排序9.堆是一种什么排序(B)。A.插入 B. 选择C.互换D.归并.下列排序措施中不稳定的排序是 ()。A.直接插入排序 . 冒泡排序 C 堆排序 . 归并排序11.一种无向连通图的生成树是具有该连通图的所有顶点的 （A)。.极小连通子图 B. 极大连通子图C. 极小子图 极大子图12如下陈述中对的的是（A ）。A.串是一种特殊的线性表B.串的长度必须不小于零B.串中元素只能是字母D.空串就是空白串13迅速排序不利于发挥其长处的状况是()。A 待排序数据量太大 待排序数据相似值过多 待排序数据已基本有序D待排序数据值差过大14.性表中采用折半查找法查找元素,该线性表必须满足(C)。 元素按值有序 采用顺序存储构造 C 元素按值有序，且采用顺序存储构造 D 元素按值有序，且采用链式存储构造15.r在排序前已按元素键值递增顺序排列，则比较次数较少的排序措施是(A) 。.直接插入排序 B.迅速排序 .归并排序D选择排序16一种递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运营时间来看,一般递归过程比非递归过程（B).较快B较慢 C相似D不拟定1如果待排序序列中两个数据元素具有相似的值，在排序后它们的位置发生颠倒,则称该排序是不稳定的。不稳定的排序措施是(D)。A起泡排序 B归并排序C.直接插入法排序 D简朴选择排序1.将一棵有5个结点的完全二叉树按层编号,则对编号为5的结点,该结点(B)。无左、右孩子 有左孩子,无右孩子C.有右孩子,无左孩子 D有左、右孩子9.若某链表最常用的操作是在最后一种结点之后插入一种结点和删除最后一种结点,则采用那种存储方式最节省时间(）。A. 单链表 B. 双链表C.带头结点的双循环链表 D.单循环链表2.下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最后位置上的算法是(D ）。. 归并排序 B. 直接插入排序C. 迅速排序 D.冒泡排序 21.树形构造最适合用来描述（C)。A 有序的数据元素 无序的数据元素C 数据元素之间具有层次关系的数据D 数据元素之间没有关系的数据22.设有700个无序的元素,但愿用最快的速度挑选出其中前个最大的元素,最佳选用措施是()。A.冒泡排序B.迅速排序C 堆排序 D.基数排序链表不具有的特点是(A)。A.可随机访问任一元素 B.插入删除不需要移动元素.不必事先估计存储空间 D所需空间与线性表长度成正比24若待排序对象序列在排序前已按其排序码递增顺序排序,则比较次数至少的措施排序是（A)。直接插入排序 B.迅速排序C.归并排序 D直接选择排序5.下列核心字序列中是堆的序列为()。A.16,72,31,3，94,53 B. 9,23,72,16,53B.16,53,94,31,72D16,23,5，31，4,726.下列四个核心字序列中,那个序列不是堆()。 05,2，16,68,94,72,71,3 B. 05,16,2,6,9,72,71,3 C.,23,16，73,9,71，68 . 05,23，1，68,73,71,72,94 27.下面4个序列中,满足堆的定义是（）。A. 1,7,4,76,85，97 . 7,3，27,49,76,85,1,97C. 1,6,49,27，38,8,97 D3,27,3，7,49,5,7,728.采用线性探查法解决冲突所构成的散列表上进行查找，也许要探测到多种位置，在查找成功状况下，所探测的这些位置上的键值(D）。A. 一定都是同义词B. 一定都不是同义词 C 都相似 . 不一定都是同义词9性表中采用折半查找法查找元素，该线性表必须满足（C)。A 元素按值有序 B 采用顺序存储构造 C 元素按值有序,且采用顺序存储构造 D 元素按值有序，且采用链式存储构造三、简答.对于一种队列,如果输入项序列由1,3,4所构成,试给出所有也许的输出序列。答：1,2,3,。将体现式（ab） +d-(e+g)h 改写成后缀体现式。答：后缀体现式为:ab+c*d+eg+*- 3对于一种栈,给出输入序列A,B,C，试给出所有也许的输出序列。答：解：输出序列为:ABC，CB,AC,BAC,BA。将算术体现式a+b*(/e)转为后缀体现式。答: .ae/+*+5.由权值为，5，9,1的五个叶子结点构造一棵哈夫曼树，请问该树的带权途径长度是多少?答：权值为5。6. 由二叉树的前序和后序遍历序列能否唯一拟定一棵二叉树。若不能请举出反例。答：不能唯一拟定一棵二叉树。如下图。123123.求出下图所示有向图的邻接矩阵。V0V4V3V2V1213457答:有向图的邻接矩阵为: 0 2 7 1 0 0 5 0 3 4 0 0 1 2 3 4012348有个顶点的无向连通图至少有多少条边？有个顶点的有向连通图至少有多少条边？答:有个顶点的无向连通图至少有n-条边，有个顶点的有向连通图至少有n条边。.下面列举的是常用的排序措施:直接插入排序，起泡排序，迅速排序,直接选择排序,堆排序，归并排序。试问，哪些排序措施是稳定的?答:起泡排序， 直接插入排序,归并排序是稳定的。10.为什么说树是一种非线性构造?树中的每个结点除了根结点外,其他每个结点有一种直接前驱，但有多种直接后继，因此说树是一种非线性构造。11已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A，B， D, , ，G, ,I,J中序序列：C, B, A, F, E, D, ， H, G答:后序序列为:C， B， , E, I, J， , G， D，A1试述顺序存储和链式存储的区别及各自的优缺陷。答：数组占用持续的内存空间,链表不规定结点的空间持续。1)插入与删除操作:由于数组在插入与删除数据时需移动大量的数据元素,而链表只需要变化某些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。 2)内存空间的占用状况：因链表多了一种指针域，故较挥霍空间,因此,在空间占用方面，数组优于链表。)数据的存取操作:访问链表中的结点必须从表头开始,是顺序的存取方式,而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此,在数据存取方面，数组优于链表。4） 数据的合并与分离:链表优于数组，由于只需要变化指针的指向 13 将体现式（(+b）c*(d+e)-f)*(h)改写成后缀体现式。答:后缀体现式为：b+cde*-h+*1将算术体现式a(b+c）-d转为后缀体现式。答: abc+*d1求出下图所示有向图的邻接表。V0V4V3V2V1213457答：有向图的邻接表为：V0V1V2V3V4122741353403Head16试找出中序序列和后序序列相似的所有二叉树。答：空树或缺右子树的单支树。17.用邻接矩阵存储一种涉及000个顶点和100条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？答:该图的邻接矩阵中有100*00个元素。该图的邻接矩阵中有个非零元素。18.画出下图中二叉树的顺序存储构造示意图。13715答:二叉树的顺序存储构造示意图为：13715 A0 A2 A6 A149.写出中缀体现式-(B/）*的后缀形式。答：中缀体现式A-(+C/D)*E的后缀形式是：CD/+E*-。2 为什么用二叉树表达一般树？ 答:树的最直观表达是为树中结点设立指向子结点的指针域,对k叉树而言，每个结点除aa域外，尚有k个链接域。这样,对一种有n个结点的叉树来说，共有n*k个指针域，其中n-1个不空,此外n(k-1)+1个指针域为空，因此,空链接域的比例约为(1)/k ，于是导致大量的空间挥霍。然而，如果采用二叉树表达一棵n个结点的树,则树中共有2n个链接域，其中未用到的有1个,占所有指针域的比例约为/，空间挥霍少诸多。此外,由于任何树型构造都可以转换成二叉树,因此，一般用二叉树表达树型构造。 1.请指出一组权值（7,5，2，)相应的哈夫曼树的带权途径长度。答:哈夫曼树的带权途径长度是35。2试找出前序序列和中序序列相似的所有二叉树。解答：空树或缺左子树的单支树。23完全二叉树用什么数据构造实现最合适，为什么?答：完全二叉树用一维数组实现最合适。由于完全二叉树保存在一维数组中时,数组内没有空洞，不存在空间挥霍问题；此外,顺序存储方式下,父子结点之间的关系可用公式描述,即已知父(或子）结点寻找子(或父）结点只需计算一种公式,访问结点以便。但采用链表存储时就存在空间挥霍问题，由于每个结点要此外保存两个链接域，并且寻找结点也不容易。2.求出下图所示无向图的邻接矩阵。V0V1V2V301230 1 1 11 0 0 11 0 0 11 1 1 00 1 2 3答:无向图的邻接矩阵为: 539132541805513571221183025.请构造权值为 5,1，21，,18,3，4 的哈夫曼树。答：哈夫曼树为：2.我们已经懂得，树的先根序列与其相应的二叉树的先根序列相似,树的后根序列与其相应的二叉树的中根序列相似。那么运用树的先根遍历顺序与后根遍历顺序，能否唯一拟定一棵树？请阐明理由。答:能。由于树的先根序列与其相应的二叉树的先根序列相似，树的后根序列与其相应的二叉树的中根序列相似,而二叉树的先根序列与二叉树的中根序列能唯一拟定一棵二叉树，因此运用树的先根遍历顺序与后根遍历顺序，能唯一拟定一棵树。2请给出如下图所示的权图的邻接矩阵。V0V4V3V2V1213457答:解：0 2 7 1 0 0 5 0 3 4 0 0 1 2 3 40123428已知一棵二叉树的中序和前序序列如下,求该二叉树的后序序列。中序序列：c，b,d，,a,g,i，h，j，f前序序列:a,b，c,d，e,，g,i，j答：该二叉树的后序序列为:c,e,，,j,h,g,f,a9. 对半查找与否适合于以链接构造组织的表?答:对半查找不适合于以链接构造组织的表。0.请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。答：中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。3.把下图中的森林转化为一棵二叉树。12684735解答: 森林转化成的二叉树如下图。126847353.指出一般树的存储构造有哪几种?答:树的存储构造有双亲表达法、孩子链表表达法和孩子兄弟表达法 33.试找出前序序列和后序序列相似的所有二叉树。答:空树或只有根结点的二叉树。34.线性表有两种存储构造:一是顺序表，二是链表。试问：如果有n个线性表同步并存，并且在解决过程中各表的长度会动态变化，线性表的总数也会自动地变化。在此状况下，应选用哪种存储构造？ 为什么？答：选链式存储构造。它可动态申请内存空间,不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O5.求出下图所示无向图的邻接表。V0V1V2V3V0V1V2V31320303021Head答:无向图的邻接表为：36.已知一种图如下所示,若从顶点0出发求出其广度优先搜索序列。03425167解答： 广度优先搜索序列：012346737.一组记录的核心字为(52, 56， 2, 12, 69, 85， 33, 48, 0),给出迅速排序的过程。解答：解：52， ， 26, 12,69， 85,33,48, 70第一趟排序 33, ,2, 12, 52, 8, 6, 56, 0第二趟排序 26, 12, ， 4, , 69, 6, 7, 85第三趟排序 1,26， 33, 8, , 56, 0, , 85第四趟排序 12， 26, 33, 4, 52, 56, 70, 69, 85第五趟排序 2, 6,33,48， 52, 56,7,69, 53.下面列举的是常用的排序措施:直接插入排序，起泡排序，迅速排序,直接选择排序，堆排序，归并排序。试问，哪些排序措施是稳定的?起泡排序, 直接插入排序,归并排序是稳定的。3.已知一棵二叉树的前序和中序序列,求该二叉树的后序序列。前序序列:,B, , , ，, G, H， I， J中序序列:, A, F, ，D, , H, J， G答:后序序列为:C,B, F, E, I, J, H,G， D, A0把下图中的二叉树转化成森林。1268473512684735答案:给定表（43,3,5，6，64,32,8，41），按数据元素在表中的顺序构造一棵二叉查找树，并求其平均查找长度。解答：根据给定表(4,36,56,，64，32,），构造的二叉查找树如下图；其平均查找长度为：3/8。648324165636434将下图中的二叉树,转换成相应的森林。ABCHFDJEILKGNM答:森林转化成的二叉树如下图。JCHEKFILNMABDG43.知二叉树按中根遍历所得到的结点序列为DGEHFIJK， 按后根遍历所得到的结点序列为DCEBFHKJIA，画出该树形构造，并按中根遍历序列进行线索化。答:HKFGCIBAJED4对于下图所示的二叉树,试分别写出先根遍历、中根遍历该树所得到的先根序列、中根序列。GFEDCBALKJIH答:先根遍历的结点序列：BEIJDK，中遍历的结点序列:EICJBGDKLA46.把下图中的二叉树转化成森林。1268473512684735答：二叉树转化成的森林如下图。一组记录的核心字为(5， 6, 26, 12, ， 85, ， 48, 70)，给出迅速排序的过程。解答：解：2,56, 26,12, 69,85, 33, 48, 0第一趟排序 33, 48，2, 1, 52, 85, ， 6,70第二趟排序 26,12, 3,48， 52, 69， 5, 70, 5第三趟排序 12, 6， 3, 48,2, 5， 7, 6， 85第四趟排序 12, 26,33,4, 2, 5， 0, 6,85第五趟排序 12, 26, 3,8,2, 56，0，69， 858 设记录的核心字集合key=51,28，38,86，70,90,7，30，4,5，试写出对e进行渐减增量排序（增量 5，3，)时，各趟排序结束后的成果。解答:各趟排序结束后的成果。初始状态:51 28 38 86 70 90 7 3 40 25第一趟排序(d=5): 51 30 4 25 90 8 38 6 70第二趟排序（=3): 28 7 3 2 86 51 8 90 0第三趟排序(=1): 7 5 28 30 8 40 50 86 90）49有一棵二叉树如下图所示,分别指出其前序、中序遍历的结点序列。ABHGFEDCIJ答:它的前序序列为:ABDFGHIJ,它的中序序列为：CDBAFGIHJ。50.已知8个记录，相应的核心词为:25,84,21,47,15，2,8,，写出迅速排序的第一趟排序过程图示。答:初始键值序列25 4 21 47 1 27 68 35 20 第一次互换 5 4 1 475 27 6 35 20 i=2 j第二次互换25 20 21 47 1 2 6 35 84 j扫描交叉2520 21 5 47 27 35 8 iR与Rj互换 5 221 7 27 68 35 8 Rm j分划表 15 20 2 5 4 27 6 35 5给定表（0，9，56，3，73,23）,按数据元素在表中的顺序构造一棵二叉查找树。答：二叉排序树如下。4095639862373有二叉树先序序列为：ABCDEF,中序序列为：BAEDF，试画出该二叉树。答:二叉树如下图。ACDFEB5.给定表(40,36,56,6,64,7,8,2),按数据元素在表中的顺序构造一棵二叉查找树,并求其平均查找长度。答:二叉查找树如下，平均查找长度为。4036566486237353.根据下图给出的二叉树,求出先序、中序遍历的结点序列。acedfb答：先序遍历为：adce 中序遍历为：dbaf 54 一组记录的核心字为(50,79，8，56,32,41,85）,给出运用重建堆措施建立的初始堆（堆顶最大),并给出堆排序的过程。 答:1）建立的初始堆为: 85，79,50,56,32，1，2)堆排序的过程如下：8579328504156（C）第2次互换8541328505679（B）第1次互换8413256507985（A）初始建堆8579565041832（f）第5次互换8579565032841（e）第4次互换8579568324150（D）第3次互换8579565041328（g）第6次互换5答:把下列森林转化为一棵二叉树。12684735答： 森林转化成的二叉树如下图。1268473556.已知数据序列为,5,9,2,6,31,4,对该数据序列进行排序，试写出冒泡排序每趟的成果。答: 初始键值序列2 5 9 20 6 124 第一趟排序5 9 1 6 24 31 第二趟排序 5 6 2 4 1第三趟排序5 9 2224 1第四趟排序 5 6 9 2 20 2 57给定表(40，6，55,6,6,77,9，41）,按数据元素在表中的顺序构造一棵二叉查找树,并求其平均查找长度。答：构造的二叉查找树如下图，其平均查找长度为11/。4035556496417758. 对于下图所示的二叉树,试分别写出先根遍历、中根遍历和后根遍历该树所得到的先根序列、中根序列和后根序列。GFEDCBALKJIH解答:先根遍历的结点序列：ABCIFJDGHKL中遍历的结点序列：EICGKLA后根遍历的结点序列:IFCKHDBA59.已知数据序列为12,，9，2,31,24，对该数据序列进行排序，试写出归并排序每趟的成果。解答：初始键值序列12 5 9 2 6 3 2第一趟排序 5 1 9 0 6 31 第二趟排序 5 9 2 6 31 第三趟排序 6 9 2 0 4 31()60.序表(,2， 17, 19, 2, 25, , 36,45,49,58）中，用二分法查找核心词3,进行多少次比较后查找成功？写出查找过程。 解答：通过次比较查找成功。查找过程如下：5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=11m=6i=1（A）第1次与25进行比较j=115, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58i=7m=9（B）第2次与45进行比较5, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=8i=7m=7（C）第3次与30进行比较i=85, 12, 17, 19, 23, 25, 30, 36, 45, 49, 58j=8m=8（D）第4次与36进行比较61.一组记录的核心字为（52, 5, 26，1, 6， 85, 33,8, 70）,给出迅速排序的过程。 解答:2， 56， 26， 12, 9, 85,33, 8， 7第一趟排序 33, 48，6, 12, 2， 85,69，56,7第二趟排序 26, 12, 3,48, 5, 9,5， 7, 5第三趟排序 1, 26, 3, 48, 5， , 70,9， 5第四趟排序 12， 6, 3， 4， 5, 56, 70, , 85第五趟排序 12, 6,33, 48， 2， 6，70, 69，862.已知某二叉树的后序序列为：DEFG，中序序列为:ACGEDF,给出它的前序序列。 解:它的前序序列为:GCABFED。6.根据下图给出的二叉树，求出中序和后序遍历的结点序列。acedfb解答：中序遍历为：dbaefc后序遍历为：dbfeca0342516764. 已知一种图如下所示,若从顶点0出发求出其深度优先搜索序列。 解答：深度优先搜索序列:17566给定表(5,6,56，6，64,32,8,41）,按数据元素在表中的顺序构造一棵二叉查找树。解答：按数据元素在表中的顺序构造一棵二叉查找树为:6483241656364566.找出所有这样的二叉树形,其结点在先根顺序遍历和中根顺序遍历下的排列是同样的。答： 为空树，或为任一结点至多只有右子树的二叉树。下面程序段的时间复杂度是 O(m） 。r (it i=1;i=；+) r (n j=;j=m;j+) aij=0；67.设有序顺序表为 10,20， 0， 40, ,60, ， 8,采用折半查找时,查找成功和查找失败的平均查找长度分别是多少？答:涉及这个元素的二叉鉴定树为:3010204070608050很明显，查找成功的平均比较次数是;查找失败的平均比较次数是。6.给定表（3,6,56,6,64,2,8，41），按数据元素在表中的顺序构造一棵二叉查找树,并求其平均查找长度。解答：根据给定表(4,3，6,6,64,2,8,4），构造的二叉查找树如下图；其平均查找长度为：23/8。64832416563643