栈、队列、串、数组和广义表  习题
一、选择题
  1  一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（  B  ）。
  A. 2 3 4 1 5    B. 5 4 1 3 2    C. 2 3 1 4 5      D. 1 5 4 3 2
2若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是(  D  )。
    A. i        B. n-i        C. n-i+1      D. 不肯定
  3  若用一个大小为6的数组来实现循环队列，且当前rear和front的值别离为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值别离为多少？( B )
A. 1和 5        B. 2和4          C. 4和2        D. 5和1 
  4  设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出
栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是(  C  )。
A． 6          B. 4          C. 3          D. 2
  5  设有两个串p和q，其中q是p的子串，求q在p中第一次出现的位置的算法称为（  C  ）
A．求子串      B．联接      C．匹配        D．求串长
  6  设有一个10阶的对称矩阵A，采用紧缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每一个元素占一个地址空间，则a85的地址为（  B  ）。
A. 13              B. 33                C. 18              D. 40
  7  已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是(  C  )。
    A. head(tail(LS))                    B. tail(head(LS))
C. head(tail(head(tail(LS)))          D. head(tail(tail(head(LS))))
  8 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ D ），nextval数组的值为  （ F ）。
A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2    B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1    D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1    F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
二、填空题
  1  在作进栈运算时应先判别栈是不是_(1)满_;在作退栈运算时应先判别栈是不是_(2)空_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)n_。
  2  设循环队列寄存在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为__return(sq.data(sq.front))；sq.front=(sq.front+1)%(M+1)；_____，若用捐躯一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)%(M+1)==sq.front；_。
  3  串是一种特殊的线性表，其特殊性表此刻__(1) 其数据元素都是字符__；串的两种最大体的存储方式是__(2) 顺序存储__先序中序后序遍历二叉树、__(3) 和链式存储__；两个串相等的充分必要条件是__(4) 串的长度相等且两串中对应位置的字符也相等__。
  5  已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_(d,e)_。
第5章  树
一、单项选择题
1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（  ）个。
2.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（  ）个。
3.假定一棵三叉树的结点数为50，则它的最小高度为（  ）。
A.3
4.在一棵二叉树上第4层的结点数最多为（  ）。
5.用顺序存储的方式将完全二叉树中的所有结点逐层寄存在数组中]，结点R[i]如有左孩子，其左孩子的编号为结点（  ）。
A. R[2i+1]    B. R[2i]C. R[i/2]        D. R[2i-1]
6.由权值别离为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（  ）。
7.线索二叉树是一种（  ）结构。
A. 逻辑        B. 逻辑和存储    C. 物理            D. 线性
8.线索二叉树中，结点p没有左子树的充要条件是（  ）。
A. p->lc=NULL                B. p->ltag=1 
C. p->ltag=1 且p->lc=NULL      D. 以上都不对
9.设n ,m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（  ）。
A. n在m右方                B. n在m 左方
C. n是m的先人                  D. n是m的子孙
10.若是F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（  ）。
A. 中序        B. 前序            C. 后序            D. 层顺序
11.欲实现任意二叉树的后序遍历的非递归算法而没必要利用栈，最佳方案是二叉树采用（  ）存储结构。
A. 三叉链表    B. 广义表        C. 二叉链表        D. 顺序
12.下面叙述正确的是（  ）。
A. 二叉树是特殊的树
B. 二叉树等价于度为2的树
C. 完全二叉树必为满二叉树
D. 二叉树的左右子树有顺序之分
13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对顺序（  ）。
A. 不发生改变                B. 发生改变
C. 不能肯定                      D. 以上都不对
14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（  ）。
A. 1B. 2C. 3D. 4
15.按照先序序列ABDC和中序序列DBAC肯定对应的二叉树，该二叉树（  ）。
A. 是完全二叉树                B. 不是完全二叉树
C. 是满二叉树                    D. 不是满二叉树
二、判断题
1.二叉树中每一个结点的度不能超过2，所以二叉树是一种特殊的树。        （　）
2.二叉树的前序遍历中，任意结点均处在其子女结点之前。                （　）
3.线索二叉树是一种逻辑结构。                                        （　）
4.哈夫曼树的总结点个数（多于1时）不能为偶数。                    （　）
5.由二叉树的先序序列和后序序列可以唯一肯定一颗二叉树。            （　）
6.树的后序遍历与其对应的二叉树的后序遍历序列相同。                （　）
7.按照任意一种遍历序列即可唯一肯定对应的二叉树。                    （　）
8.满二叉树也是完全二叉树。                                        （　）
9.哈夫曼树必然是完全二叉树。                                        （　）
10.树的子树是无序的。                                            （　）
三、填空题
1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为__3___，树的深度为__4__，终端结点的个数为____6，单分支结点的个数为___1___，双分支结点的个数为_1_____，三分支结点的个数为_2______，C结点的双亲结点为_a______，其孩子结点为___f___和__g_____结点。
2. 设F是一个丛林，B是由F转换取得的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。
3. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。
4. 由带权为3，9，6，2，5的5个叶子结点组成一棵哈夫曼树，则带权路径长度为___。
5. 在一棵二叉排序树上按_______遍历取得的结点序列是一个有序序列。
6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。
7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。
8. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。
9. 由三个结点组成的二叉树，共有____种不同的形态。
10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包括的结点数至少为____。
11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。
12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。
13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。
14. 哈夫曼树是指________________________________________________的二叉树。
15. 空树是指________________________，最小的树是指_______________________。
16. 二叉树的链式存储结构有______________和_______________两种。
17. 三叉链表比二叉链表多一个指向______________的指针域。
18. 线索是指___________________________________________。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。