ch4-学生.doc

一、单选题1以下数据结构中，（）是非线性数据结构。树字符串队栈2若某线性表中最常用的操作是存取第i个元素和查找第i个元素的前趋元素，则采用（）存储方式最节省时间。顺序表单链表双链表单循环链表3在以下的叙述中，正确的是（）。线性表的顺序存储结构优于链表存储结构线性表的顺序存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构适用于频繁插入/删除数据元素的情况线性表的链表存储结构优于顺序存储结构4. 对于单链表，以下说法错误的是（）。指向链表的第一个结点的指针，称为头指针单链表的每一个结点都被一个指针所指每个结点的指针指向它的直接后继结点尾指针具有标识单链表的作用，故常用尾指针来命名单链表5在一个单链表中，若删除p所指结点的后续结点，则执行（）。p-next= p-next-next；p= p-next;p-next= p-next-nextp-next= p-next;p= p-next-next6在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。s-next=p; p-next=s;s-next=p-next; p-next=ss-next=p-next; p=s;p-next=s; s-next=p7在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。s-next=p-next; p-next=s;p-next=s-next; s-next=pq-next=s; s-next=p;p-next=s; s-next=q8字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。145689一个顺序存储的线性表第一个元素的存储地址是100，每个元素的占用2个字节的存储空间，则第5个元素的地址是（）。11010810012010对于线性表，在下列哪种情况下应当采用链式存储结构（）。经常需要随机地存取元素经常需要进行插入和删除操作表中元素需要占据一片连续的存储空间表中元素的个数不变11树最适合用来表示（）。有序数据元素无序数据元素元素之间具有分支层次关系的数据元素之间无联系的数据12二叉树的第k层的结点数最多为（）。2k-12K+12K-12k-113栈的插入和删除操作在（）进行。栈顶栈底任意位置指定位置143个节点构成一颗二叉树，有（）种可能。125415先序序列为ABC的不同二叉树有（）种不同形态。3 45616设某棵二叉树中有2000个节点，则该二叉树的最小高度为（）。9 10111217以下说法正确的是（）。数据元素是数据的最小单位数据项是数据的基本单位数据结构是带有结构的各数据项的集合数据结构是带有结构的数据元素的集合18单链表的一个存储结点包含（）。指针域和链域 指针域或链域数据域和指针域 指针域和链域19如果栈采用顺序存储结构，则入栈操作时（）。必须判别栈是否满 必须判别栈是否空判别栈元素的类型对栈不做任何操作20一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。e d c b a d e c b a d c e a b a b c d e21以下说法错误的是（）。二叉树可以是空集二叉树的任一结点都有两棵子树二叉树与树都属于树形结构二叉树中任一结点的两棵子树有次序之分22关于二叉树的下列说法正确的是（）。二叉树的度为2二叉树的度可以小于2每一个结点的度都为2至少有一个结点的度为223将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为（）。42 40212024设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（）个。k+1 2k 2k-1 2k+125一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（）遍历方式就可以得到这棵二叉树所有结点值的降序序列。先根 中根 后根 层次26组成数据的基本单位是（ ）。 数据项数据类型数据元素数据变量27栈和队列的共同点是（ ）。都是先进先出都是先进后出 只允许在端点处插入和删除元素 没有共同点28栈的插入和删除操作在（ ）进行。栈顶栈底 任意位置指定位置29一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=inext不会删除该链表中的结点。9（）在一棵非空二叉树的中序遍历序列中，根结点的后边是其右子树的所有结点。10（）数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。11. （）队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。12. （）完全二叉树一定存在度为1的结点。13. （）二叉树只能用二叉链表表示。14. （）在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是p-next=p-next-next。15. （）单链表从任何一个结点出发，都能访问到所有结点。16. （）若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。17. （）栈和队列都是顺序存储结构的线性结构。 18. （）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。19. （）在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。20. （）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。21. （）在线性链表中删除中间结点时，只需将被删结点释放。22. （）完全二叉树中，若一个结点没有左孩子，则它必是树叶。23. （）完全二叉树的存储结构通常采用顺序存储结构。24. （）在一颗二叉树中，假定每个节点只有左子女，没有右子女，对它分别进行前序和后序遍历，则具有相同的结果。25. （）在栈满的情况下不能作入栈运算，否则产生“上溢”。26（ ）线性表中的所有元素都有一个前驱元素和后继元素。27（ ）顺序存储方式只能用于存储线性结构28（ ）链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 29（ ）对链表进行插入和删除操作时不必移动链表中结点。30（ ）若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。31（ ）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。32（ ）完全二叉树中的叶子结点只可能在最后两层中出现。33（ ）已知一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。四、计算题1. 设有一个顺序栈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. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=1),对一棵含有N个结点的K叉树（N）、请讨论其可能的最大高度和最小高度。8. 已知一棵二叉树的中序（或中根）遍历结点排列为DGBAECHIF，后序（或后根）遍历结点排列为GDBEIHFCA。试画出该二叉树。9. 写出图中二叉树的前序，中序和后序的序列10. 已知某二叉树的前序序列为：DBACFEG，中序序列为ABCDEFG。请画出该二叉树。11