数据结构试题4

1、肇 庆 学 院 数 据 结 构 2 0 0 1 级 试 卷 ( A)一、单项选择题（ 2 分 10=20 分）1若某线性表中最常用的操作是删除第1 个元素，则不宜采用（）存储方式。A. 单链表B.双链表C.单向循环链表D . 顺序表2在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子1，则其右孩子的编号为（）。A. 2iB. 2i-1C. 2i+1D. i/23.按照二叉树的定义，具有 3个结点的二叉树有（）种不同形态。A、 3B. 4C. 5D. 64.在长为 n 的顺序表中，删除第i 个元素 (1 i n+1) 需要向前移动（）个元素。A. n-iB. n-i+1C. n-i-1D.

2、 i5.一个队的入队顺序是1、2、 3、4、5，则此队的出队顺序为（）。A. 5 、 4、3、2、 1B. 4 、5、3、 2、 1 C. 4、3、5、 1、 2D. 1 、 2、 3、4、56.栈是一种特殊的线性表，其特殊性表现在（）。A. 可以顺序存储B. 只能从端点进行插入和删除C. 可以链式存储D. 可以在任何位置进行插入和删除7.一棵二叉树中，第 k 层上最多有（）个结点。A. 2kB.2k-1C.2kD.2 k-18.一棵有 18 个结点的二叉树，其高度最小为（）层。A. 4B. 5C. 6D. 189. n个顶点的有向图中最多有（）条弧。A. n(n-1)/2B. n(n-1)C

3、. n(n+1)D. n(n+1)/210.有向图中，所有顶点入度和是所有顶点出度和的（）倍。A. 0.5B. 1C. 2D. 4二、判断题（ 1 分 10=10 分）（ F） 1. 在线性结构的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（ F） 2. 二叉树就是度为 2 的树。（ T） 3. 存在这样的二叉树，其后序遍历与中序遍历得到的访问序列相同。（ T） 4. 满二叉树一定是完全二叉树。（ F） 5. 由空格组成的串叫空串。（ T） 6. 在 AOE网中，可能有多条关键路径。（T） 7. m阶 B-树具有 k 个子树的非叶子结点含有k-1 个关键字。（ T） 8. 起泡

4、排序是稳定的。（ F） 9. 链式存储的线性表可以实现随机存取。（ F ） 10. 二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。三、填空题（ 2 分 8=16 分）1在单链表中，若删除指针p 所指结点的直接后继，则需要执行下列三条语句：q=pnext ； free （q）；2在有头结点的单链表L 中，指针p 所指结点是最后一个结点的条件是。3队是一种受限制的线性表，也叫FIFO 结构， FIFO 的含义是。4.对于栈，只能在插入元素，只能在删除元素。5.数据的基本单位是，在计算机程序中通常作为一个整体进行考虑和处理。6. 图的遍历方式通常有遍历和遍历两种。四、简答和应

5、用题（38 分）1.（8 分）某二叉树后序遍历的结果是ABCDEFG，中序遍历的结果是ADBCGFE.（ 1） 画出此二叉树；（ 2） 写出其先序遍历的结果。2. （9 分）已知如图所示有向图，（ 1） 求各点的入度和出度；（ 2） 给出该图的邻接矩阵；（ 3） 给出该图的一个拓扑排序。3. 给出下面稀疏矩阵的三元组。（ 5 分）0000001200001000000100001100009004. （8 分）已知序列 5，3，4，8， 6。（1）以该序列为权构造一棵有5 个叶子结点的Huffman 树。（2）求上边构造的 Huffman树的带权路径长度WPL.5. （8 分）已知如图所示的连通网。求其最小生成树（要求画出生成的过程）。3V2V5312V14V42V62V33五、设计题（ 16 分）1.编写实现“直接插入排序”的子函数，入口参数是整形数组L 和数组长度n.2.写出统计二叉树叶子结点个数的子函数，入口参数是其根结点指针：BiTree 型指针 T，其中 BiTree