数据结构(函01计专升本)(考).doc

专业_ 班级_ 学号_ 姓名_ 高职 华东交通大学20012002第二学期考试卷数据结构课程 开卷 课程类别：必修一、 单选题：（每小题1.5分，共15分）1. 假设某算法语句总的执行次数为T(n)=3n4+2n+n,那么该算法的时间复杂性量级为_。A) O(2) B) O(n) C) O(n4) D) O(1)2. 在顺序线性表（a1,a2,a29,a30）中，在a20之前插入一个新的结点，需要将_个结点后移。A) 11 B) 20 C) 19 D) 10 3. 若一个采用顺序存储方式的先行表中，若表的第一个元素的存储地址是100，每个元素的长度为4，则第5个元素的地址是A)112 B)116 C)120 D)1244. 带头结点的单链表为空的判断条件是 。A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULL5. 一个栈的入栈序列是A、B、C、D、E，则栈的不可能输出序列是 A) EDCBA B) DECBA C) DCEAB D)ABCDE6. 深度为K的二叉树最多有_个结点。A) 2K B) 2K1 C) 2K 1 D) 2K +17. 二叉树上,若度为2的结点个数为18,则叶子数为_D_。A)17 B)18 C)20 D)198. 设数组Datan+1作为循环队列Sq的存储空间,front为队首指针,rear为队尾指针,则执行出队操作的C语言语句为_。A)front=front+1 B)front=(front+1)%nC)front=(front+1)%(n+1) D)rear=(rear+1)%n9. 一棵满二叉树,同时又是一棵_。A)二叉排序树 B)完全二叉树 C)非完全二叉树 D)哈夫曼树10. n个顶点的有向完全图的弧数为_。A) n (n-1) B) nn C) 2n D) n (n-1) /2 二、 填空题：(每小题1分,共10分)1. 数据结构包括那三方面的内容： 、 、 。2. 一个有n个元素的线性表，采用顺序存储方式。若删除第i (1in)个元素时，需要向前移动 个元素；若在第 i (1in)个元素前插入一个元素，需要向后移动 个元素3. 数据元素之间有四类基本结构,它们是：集合 线性结构 树形结构 _ _。4. 线性表的单链表存储结构用C语言可定义为：Typedef struct Lnode datatype data; *next; Lnode,*LinkList;5. 栈操作的原则是 ；队列的操作原则是 。6. 在二叉树链表上实现中序遍历的递归算法：void inorder (BiTree r) if (r!=NULL) inorder(rlchild); visit(r)； ； 7. n个顶点的连通图的生成树有 条边。8. 深度优先搜索遍历类似于树的 遍历;广度优先搜索遍历类似于树的 遍历。三、 判断题（判断下列各题是否正确，若正确在括号里打“”，错误的打“”，每小题1分，共10分）1、如果两个串含有相同的字符，则这两个串相等。（ ）2、数组可以看成线性表结构的一种推广，因此可以对它进行插入，删除等运算。 （ ）3、（ ）4、在栈满的情况下不能作进栈运算，否则产生“上溢”。 （ ）5、（ ）6、对任意一个图，从它的某个顶点出发，进行一次深度优先搜索或广度优先搜索，即可访问图的每个顶点。（ ）7、一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（ ）8、一个图的邻接矩阵表示法是唯一的，而邻接表表示法是不唯一的。（ ）9、数据的逻辑结构与数据元素本身的内容和形式无关。 （ ）10、二叉树是深度为2的有序树。 （ ）四、 简答题：（每小题8分 共16分）1 什么是最小生成树？并叙述使用普里母（prim）算法构造最小生成树的思想。 2 稀疏矩阵压缩存储采用的三元组顺序表是线性表吗？为什么？五、 作图题（按题目要求写出结果）（共24分）BCDEFBG1 写出如下图所示二叉树的先序遍历序列、中叙遍历序列、后叙遍历序列2 画出下面邻接表所表示的图，并写出从A点开始广度优先遍历该图的结果。（9分）A D B F D B A D C E D E E F 3已知在一份电文中只使用了7个字符A、B、C、D、E、F、G，其频率分别为5,29,7,8,14,20,17,试写出每个字符所对应的哈夫曼编码。 六、 写算法：（共25分