数据结构练习题
1、在数据结构中，从逻辑上可以把数据结构分成
A、 动态结构和静态结构B、紧凑结构和非紧凑结构先序中序后序遍历二叉树
B、 线性结构和非线性结构D、内部结构和外部结构
2、线性表的顺序存储结构是一种_____的结构，线性表的链式存储结构是一种____的存储结构
A、 随机存取B、顺序存取C、索引存储D、散列存取
3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址____
A、 必须是连续的B、部分地址必须是连续的
B、 一定是不连续的D、连续或不连续都可以
4、在下列叙述中，正确的是____
A、 线性表的顺序存储结构优于链表存储结构
B、 二维数组是其数据元素为线性表的线性表
C、 栈的操作方式是先进先出
D、 队列的操作方式是先进后出
5、一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___
A、110  B、108  C、100  D、120
6、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是____
A、edcba  B、decba  C、dceab  D、abcde
7、一个栈的入队序列是1，2，3，4，则队列的输出序列是____
A、4，3，2，1  B、1，2，3，4  C、1，4，3，2  D、3，2，4，1
8、判定一个栈ST空的(最多元素为m0)为空的条件是_____
A、ST->top!=0  B、ST->top= =0
C、 ST->top!=m0  D、ST->top= =m0
9、判定一个栈(最多元素为m0)为满的条件是_____
A、ST->top!=0  B、ST->top= =0
D、 ST->top!=m0  D、ST->top= =m0
10、判定一个队列QU(最多元素为m0)为空的条件是_____
A、 QU->rear-QU->front= =m0
B、 QU->rear-QU->front-1= =m0 
C、 QU->front= =QU->rear
D、 QU->front= =QU->rear+1
11、判定一个队列QU(最多元素为m0)为空的条件是_____
A、QU->rear-QU->front= =m0
B、QU->rear-QU->front-1= =m0 
C、QU->front= =QU->rear
D、QU->front= =QU->rear+1
12、判定一个循环队列QU(最多元素为m0)为空的条件是_____
A、QU->rear-QU->front= =m0
B、QU->rear-QU->front-1= =m0 
C、QU->front= =（QU->rear+1）%m0
D、QU->front! =（QU->rear+1）%m0
13、判定一个循环队列QU(最多元素为m0)为满的条件是_____
A、QU->rear-QU->front= =m0
B、QU->rear-QU->front-1= =m0 
C、QU->front= =（QU->rear+1）%m0
D、QU->front! =（QU->rear+1）%m0
14、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_____
A、（rear-front+m）%m   
B、rear-front+1
C、rear-front-1
E、 rear-front
15、如下图所示的4棵二叉树中，____不是完全二叉树。
     
      A                B                C                D
16、在线索二叉树中，t所指结点没有左子树的充要条件是______
A、t->left=null              B、t->ltag=1
C、t->ltag=1且t->left=null    D、以上都不对
17、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法___
A、正确                  B、错误
18、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____
A、正确                  B、错误
19、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____
A、正确                  B、错误
20、如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2种结点的___
A、前序            B、中序          C、后序          D、以上都不是
21、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2种结点的___
A、前序            B、中序          C、后序          D、以上都不是
22、在以非空二叉树的中序遍历序列中，根结点的右边_____。
A、只有右子树上的所有结点              B、只有右子树上的部分结点
C、只有左子树上的部分结点              D、只有左子树上的所有结点
23、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____
A、不发生改变          B、发生改变      C、不能确定      D、以上都不对
24、对一个满二叉树，m个树叶，n个结点，深度为h，则____。
A、n=h+m              B、h+m=2n        C、m=h-1        D、n=2 h - 1
25、如下图8.11所示的t2是由有序树t1转换而来的二叉树，那么树t1有____个叶结点
                    a
                b        e
          c        f          h
                d      g    i      j
二、填空题
1、在线性结构中，第一个结点____前驱结点，其余每个结点有且只有_____个前驱结点；
最后一个结点____后续结点，其余每个结点有且只有____个后续结点。
2、在树形结构中，树根结点没有_____结点，其余每个结点有且只有_____个前驱结点；叶子结点没有____后续结点，其余每个结点的后续结点可以_____。
3、线性结构中元素之间存在_____关系，树形结构中元素之间存在_____关系，图形结构中元素之间存在_____关系。
4、算法的五个重要特性是____、____、____、____、____。
5、下列程序段的时间复杂度是_____
i=1;
while(i<=n)
    i=i*3;
6、向一个长度为n的顺序表的第i个元素(1<=i<=n+1)之前插入一个元素时，需向后移动___个元素。
7、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动___个元素。
8、向栈中压入元素的操作是先_______，后_________。
9、对栈进行退栈时的操作是先_______，后_________。
10、在一个循环队列中，队首指针指向队首元素的______位置。
11、从循环队列中删除一个元素时，其操作是先______，后______。
12、在具有n个单元的循环队列中，队满时共有______个元素。
13、设有两个串p和q，求q在p中首次出现的位置的运算称作______。
14、设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度，则con(subs(s1,2,len(s2))，subs(s1,len(s2),2))的结果串是______。
15、空串是______，其长度等于____；空格串是_____，其长度等于_____。
16、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_____。
17、按照二叉树的定义，具有3个结点的二叉树有____种。
18、深度为5的二叉树至多有_____个结点。
19、深度为k的完全二叉树至少有_____个结点，至多有___个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_____
三、简答题
1、 对于一个栈，给出输入项及其输入顺序A,B,C。试给出全部的可能的输出序列(要有出入栈的过程分析)。
2、 现按中序遍历二叉树的结果为abc，问有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
3、 已知一棵树如图所示，画出其孩子兄弟表示。
4、 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。
5、 画出以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树,并计算其带权路径长度。
e
a
f
d
g
c
j
h
i
b
6、 二叉树结点数值采用顺序存储结构，如下图所示。
(1)、画出二叉树表示；
(2)、写出前序遍历，中序遍历和后序遍历的结果； 
(3)、写出结点值c的父结点，其左、右孩子；
(4)、画出把此二叉树还原成森林的图；
7、有一份电文中共使用5个字符：a、b、c、d、e，它们出现的频率依次为4、7、5、2、9，
试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的次序构造)，并求出每个字符的哈夫曼编码。

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