华东交通大学2003—2004学年第2学期考试卷—承诺:我将严格遵守考场纪律,并知道考试违纪,作弊的严重性,承担由此引起的一切后果.专业班级学号学生签名:数据结构题号分数评卷人一,单选题:(每小题1.5分,共15分)1.假设某算法语句总的执行次数为T(n)=5n5+n+n,那么该算法的时间复杂性量级为_______.A)O(2)B)O(n5)C)O(n4)D)O(1)2.若长度为n的线性表采用顺序存储结构,删除它的第i数据元素之前,需要先依次向前移动_______个数据元素.()A.n-iB.n+iC.n-i-1D.n-i+13.在一个采用顺序存储方式的线性表中,若表的第一个元素的存储地址是100,每一个元素的长度为2,则第5个元素的地址是A)110B)108C)100D)1204.以下关于线性表的说法不正确的是().A,线性表中的数据元素可以是数字,字符,记录等不同类型.B,线性表中包含的数据元素个数不是任意的.C,线性表中的每个结点都有且只有一个直接前趋和直接后继.D,存在这样的线性表:表中各结点都没有直接前趋和直接后继.5.带头结点的单链表为空的判断条件是.A)head=NULLB)head->next=NULLC)head->next=headD)head!=NULL6.栈的插入和删除操作在()进行.A栈顶B栈底C任意位置D指定位置7.某堆栈的输入序列为a,b,c,d,下面的四个序列中,__________不可能是它的输出序列.()A)a,c,b,dB)b,c,d,aC)d,c,a,bD)c,d,b,a8.一棵有16结点的完全二叉树,对它按层编号,则对编号为7的结点X,它的双亲结点及右孩子结点的编号分别为A)2,14B)2,15C)3,14D)3,159.广大义表A=((),(a),(b,(c,d)))的长度为()A)2B)3C)4D)510.一棵满二叉树,同时又是一棵______________.A)二叉排序树B)完全二叉树课程三四五课程类别:必六七八九闭卷:总分一二C)非完全二叉树D)哈夫曼树二,填空题:(每小题1分,共10分)1.数据结构包括那三方面的内容:逻辑结构,,数据的运算.2.队列中允许进行删除的一端为________________.3.数据元素之间有四类基本结构,它们是:①集合②__________③树形结构④图形或网状结构.4.线性表的单链表存储结构用C语言可定义为:TypedefstructLnode{datatypedata;*next;}Lnode,*LinkList;5.栈操作的原则是;队列的操作原则是.6.在二叉树链表上实现后序遍历的递归算法:voidpostorder(BiTreer){if(r!=NULL){postorder(rlchild);;visit(r);}}7.在一个无向图中,所有顶点的度数之和等于所有边的数目的_______倍.8.深度优先搜索遍历类似于树的遍历;广度优先搜索遍历类似于树的遍历.9.三,判断题(判断下列各题是否正确,若正确在括号里打"√"错误的打,"×",每小题1分,共10分)1,如果两个串含有相同的字符,则这两个串相等.()2,数组可以看成线性表结构的一种推广,因此可以对它进行插入,删除等运算.()3,线性表只能采用顺序存储结构或者链式存储结构.()4,在栈满的情况下不能作进栈运算,否则产生"上溢".()5,程序越短,程序运行的时间就越少.()6,对任意一个图,从它的某个顶点出发,进行一次深度优先搜索或广度优先搜索,即可访问图的每个顶点.()7,一个有向图的邻接表和逆邻接表中表结点的个数一定不相等.()8,一个图的邻接矩阵表示法是不是唯一的,而邻接表表示法是唯一的.()9,数据的逻辑结构与数据元素本身的内容和形式有关.()10,二叉树是深度为2的有序树.()四,简答题:(每小题8分共16分)1.简述什么是线性表.2.简述空串与空格串有何区别?3.稀疏矩阵压缩存储采用的三元组顺序表是线性表吗?为什么?五,作图题(按题目要求写出结果)(共24分)1,画出下列二叉树的二叉链表表示图,并写出该二叉树的中序遍历序列分)(8ACBDEFGH2,画出下图所对应的邻接表,并写出从A点开始广度优先遍历该图的结果BADCEF3,假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成,这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.试构造哈夫曼树,并给出它们的哈夫曼编码.(要求左边的权值小于右边的权值)六,