数据结构试题3

肇庆学院计算机科学与技术系数据结构20?级试卷(A)班级： 姓名： 学号： . -密-封-线- 考试时间：20?.?题号一二三四五总分分数得分一、 单项选择题（2分10=20分） 1若某线性表中最常用的操作是提取第i个元素及找第i个元素的前驱元素，则采用（ ）存储方式最省时间。A.单链表 B.双链表 C.单向循环链表 D.顺序表 2将含有100个结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（ ）。A. 34 B. 35 C. 33 D. 无法确定 3. 单循环链表的主要优点是（ ）。A. 不再需要头指针了B. 已知某结点的位置后，很容易找到其前驱C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表 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. 一棵5层满二叉树中，结点总数为（ ）个。A. 33 B.32 C.31 D.30 8. 下列4棵二叉树，（ ）是平衡树。 A. B. C. D.9. n个顶点的无向图中最多有（ ）条边。 A. n(n-1)/2 B. n(n-1) C. n(n+1) D. n(n+1)/210. 6个顶点的无向图中，至少有（ ）条边才能保证是一个连通图。 A. 5 B. 6 C. 7 D. 8得分二、 判断题（1分10=10分）（ ） 1. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。（ ） 2. 二叉树是树的特殊情形。（ ） 3. 存在这样的二叉树，其先序遍历与中序遍历得到的访问序列相同。（ ） 4.用一维数组存储二叉树时，总是以先序遍历的顺序存储结点。（ ） 5. 空串就是由空格组成的串。（ ） 6. 在AOE网中，一定只有一条关键路径。（ ） 7. m阶B-树每一个结点的子树个数都小于或等于m.（ ） 8. 插入排序是稳定的。（ ） 9. 顺序存储的线性表可以实现随机存取。（ ）10.二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。得分三、填空题（2分8=16分）1在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s-next=p-next； ；2. 在有头结点的单链表L中，指针p所指结点是第一个结点的条件是 。3. 栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是 。4. 对于队，只能在 插入元素，只能在 删除元素。5. 抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示： 、 和 。得分四、简答和应用题（38分）1. （8分）某二叉树先序遍历的结果是ABCDEFG，中序遍历的结果是CBDAFGE.（1） 画出此二叉树；（2） 写出其后序遍历的结果。2. （9分）已知如图所示有向图， （1） 求各点的入度和出度；（2） 给出该图的邻接矩阵；（3） 给出该图的邻接表。3. 给出下面稀疏矩阵的三元组。（5分）4. （8分）已知序列5，3，4，8，6。（1） 以该序列为权构造一棵有5个叶子结点的Huffman树。（2） 求上边构造的Huffman树的带权路径长度WPL.5. （8分）已知如图所示的AOE网。（1） 求每项活动的最早开始时间e(ai)和最迟时间l(ai);a7=2a6=1a4=3a3=2a5=4a1=3V6V5V4V2V1（2） 求其关键路径。a8=3a2=2V3得分五、设计题（16分）1. 编写实现“起泡排序”的子函数，入口参数是整形数组L 和数组长度n.2. 写出先序遍历二叉树的子函数，入口参数是其根结点指针：BiTree型指针T，其中BiTree定义为：ty