(考试资料下载)数据结构试题3参考答案

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