数据结构习题一、选择题1．数据结构中，与所使用的计算机无关的是数据的（ ）。A．存储结构 B．物理结构 C．逻辑结构 D

数据结构习题
一、选择题
1．数据结构中，与所使用的计算机无关的是数据的（ ）。
A．存储结构 B．物理结构 C．逻辑结构 D．物理和存储结构
2．下面有关数据的存储结构的叙述中，正确的是（ ）。
A．顺序存储方式只能用于存储线性结构
B．顺序存储方式的优点是存储密度大，且插入和删除运算效率高
C．链表的每一个结点都恰好包含一个指针
D．栈和队列的存储方式既可以顺序存储，也可以采用链式存储方式
3．下列叙述中正确的是（ ）。
A．线性表是线性结构 B．栈与队列是非线性结构
C．线性链表是非线性结构 D．队列是后进先出的线性表
4．链表不具有的特点是（ ）。
A．可随机访问任一元素 B．插入和删除不需要移动元素
C．不必事先估计存储空间 D．所需空间与线性表长度成正比
5．栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是（ ）。
A．ABCED B．DBCEA C．CDABE D．DCBEA
6．若进栈序列为1，2，3，4，则（ ）不可能是出栈序列。
A．1，2，3，4 B．4，3，2，1 C．3，4，2，1 D．2，4，3，1
7．在深度为8的满二叉树中,叶子结点的个数为（ ）
A．63     B．64     C．127     D．128
*8．已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。A．cedba B． acbed C． decab D．deabc
9. 设有下列二叉树:

对此二叉树中序遍历的结果为___
A)ABCDEF B)DBEAFC
C)ABDECF D)DEBFCA
10. 下列关于栈的叙述中正确的是____
A)在栈中只能插入数据 B)在栈中只能删除数据
C)栈是先进先出的线性表 D)栈是先进后出的线性表
11. 下列关于队列的叙述中正确的是___
A)在队列中只能插入数据 B)在队列中只能删除数据
C)队列是先进先出的线性表 D) 队列是先进后出的线性表
12. 对长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为___
A)N+1 B)N C)(N +1)/2 D)N/2
13. 在计算机中,算法是指___
A)查询方法 B)加工方法 C)解题方案的准确而完整的描叙 D)排序方法
二、填空题
1．栈的基本运算有三种：入栈、退栈和【 】。
2．对长度为N的线性表进行顺序查找，当查找失败时比较次数为【 】。
3．在长度为N的线性表中进行二分查找，在最快的情况下，需要比较的次数为【 】。
4．设待排数据元素的关键字为（67，24，14，22，33，15，11，15），用选择法将其按升序排序，需要比较的次数为【 】。
5．某二叉树中度为2的结点有12个，则该二叉树中有 【 】个叶子结点。
6．设一棵二叉树中有3个叶子结点，有6个度为1的结点，则该二叉树中总的结点数为【 】 个。
*7．在深度为5的完全二叉树中，度为2的结点数最多为【 】个。
8．对下列二叉树进行前序、中序和后序遍历的结果分别是【 】 、【 】和 【 】 。
前序遍历 FCADBEG、中序遍历 ACBDFEG 后序遍历 ABDCGEF
9. 在深度为5的满二叉树中,叶子结点的个数为【 】

一、选择题
1．C
2．D
解析：A．完全二叉树可以用数组存储，树是非线性结构
B．链表且插入和删除运算效率高
C．链表也有双向链表 ，有两个指针域
3．A
4．A．顺序表可随机访问任一元素
5．D
6．这道题你是不是弄错了 全都对啊
7．D 满二叉树 ：结点总数目N=2^H -1 H为数高度 ，求出结点总数为255
满二叉树，只有度为0 和度为2 的结点，度为0 的结点等于度为1 结点数目+1 因此选D
8．C 这题不用画图就可做出来， 后序遍历序列是dabec，------》得到根节点是：c
前序遍历；根左右 所以第一个一定是c 只有A项符合
9. A 虽然你没给图 但是一般都是A相 因为见过好多这个题 中序遍历和层次遍历结果一样
10. D
11.C
12.B 在最坏情况:比较次数为___每次查找都要从第一个比较到最后一个，都要遍历N次 ：
总的比较次数N*N,平均比较次数就是N
13. C
二、填空题
1．出栈
2．n/2+n/(n+1) 1+2+3……n+n)/(n+1)=．n/2+n/(n+1)
3．1
4．设待排数据元素的关键字为（67，24，14，22，33，15，11，15），用选择法将其按升序排序，需要比较的次数为【 】。
5．13
6．11 3+6+2=11
*7．15 方法 同选择题 上那个满二叉树
8．无图
9. 16 和第七题一样的方法