(考试资料下载)数据结构试题4

肇庆学院计算机科学与技术系数据结构2001级试卷(A)班级： 姓名： 学号： . -密-封-线- 考试时间：2003.07题号一二三四五总分分数得分一、 单项选择题（2分10=20分） 1若某线性表中最常用的操作是删除第1个元素，则不宜采用（ ）存储方式。A.单链表 B.双链表 C.单向循环链表 D.顺序表 2在一棵完全二叉树的顺序存储方式中，若编号i的结点有右孩子1，则其右孩子的编号为（ ）。A. 2i B. 2i-1 C. 2i+1 D. i/2 3. 按照二叉树的定义，具有3个结点的二叉树有（ ）种不同形态。A. 3 B. 4 C. 5 D. 6 4. 在长为n的顺序表中，删除第i个元素(1in+1)需要向前移动（ ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i 5. 一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（ ）。A. 5、4、3、2、1 B. 4、5、3、2、1C. 4、3、5、1、2 D. 1、2、3、4、5 6. 栈是一种特殊的线性表，其特殊性表现在（ ）。A. 可以顺序存储 B.只能从端点进行插入和删除 C. 可以链式存储 D. 可以在任何位置进行插入和删除 7. 一棵二叉树中，第k层上最多有（ ）个结点。A. 2k B.2k-1 C.2k D.2k-1 8. 一棵有18个结点的二叉树，其高度最小为（ ）层。 A. 4 B. 5 C. 6 D. 189. n个顶点的有向图中最多有（ ）条弧。 A. n(n-1)/2 B. n(n-1) C. n(n+1) D. n(n+1)/210.有向图中，所有顶点入度和是所有顶点出度和的（ ）倍。 A. 0.5 B. 1 C. 2 D. 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. 起泡排序是稳定的。（ F ） 9. 链式存储的线性表可以实现随机存取。（ F ）10.二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。得分三、填空题（2分8=16分）1在单链表中，若删除指针p所指结点的直接后继，则需要执行下列三条语句：q=p-next； ；free（q）；2. 在有头结点的单链表L中，指针p所指结点是最后一个结点的条件是 。3. 队是一种受限制的线性表，也叫FIFO结构，FIFO的含义是 。4. 对于栈，只能在 插入元素，只能在 删除元素。5. 数据的基本单位是 ，在计算机程序中通常作为一个整体进行考虑和处理。6. 图的遍历方式通常有 遍历和 遍历两种。得分四、简答和应用题（38分）1. （8分）某二叉树后序遍历的结果是ABCDEFG，中序遍历的结果是ADBCGFE.（1） 画出此二叉树；（2） 写出其先序遍历的结果。2. （9分）已知如图所示有向图， （1） 求各点的入度和出度；（2） 给出该图的邻接矩阵；（3） 给出该图的一个拓扑排序。3. 给出下面稀疏矩阵的三元组。（5分）4. （8分）已知序列5，3，4，8，6。（1） 以该序列为权构造一棵有5个叶子结点的Huffman树。（2） 求上边构造的Huffman树的带权路径长度WPL.5. （8分）已知如图所示的连通网。求其最小生成树（要求画出生成的过程）。V1V2V3V4V5V632243132得分五、设计题（16分）1. 编写实现“直接插入排序”的子函数，入口参数是整形数组L 和数组长度n.2. 写出统计二叉树叶子结点个数的子函数，入口参数是其根结点指针：BiTree型指针T，其中BiTree定义为：typed