.设有一个顺序栈S,元素s1,s2.s3.s4.s5.s6依次进栈,如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少应为多少?2.一棵有124个叶子的完全二叉树,最底层至少有多少个结点?3.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是?4.已知一棵满二叉树的结点个数为20到40之间的素数,此二叉树的叶子有多少个?5.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有多少个结点?6.深度为h的满m叉树的第k层有多少个结点?(1=<k=<h)7.高度为K的二叉树最大的结点数为?8.已知完全二叉树的第七层有10个叶子结点,则整个二叉树的结点数最多是多少?9.一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是?10.有5个元素,其入栈次序为:A,B,C,D,E,在各种可能的出栈次序中,以元素C,D最先出栈(即C第一个且D第二个出栈)的次序有哪几个?五、简答题1.数据的逻辑结构可以分为几类?哪几类?2.数据的物理结构可以分为几类?哪几类?3.说明线性表、栈与队的异同点4.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?5.设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。6.一个队列的入队序列是1,2,3,4,则队列的输出序列是什么?7.给定K(K>=1),对一棵含有N个结点的K叉树(N>0)、请讨论其可能的最大高度和最小高度。8.已知一棵二叉树的中序(或中根)遍历结点排列为DGBAECHIF,后序(或后根)遍历结点排列为GDBEIHFCA。试画出该二叉树。9.写出图中二叉树的前序,中序和后序的序列10.已知某二叉树的前序序列为:DBACFEG,中序序列为ABCDEFG。请画出该二叉树。
全文预览
