数据结构试题(白明)A卷.doc

试卷编号命题人： 白明 试卷分类（A卷或B卷） A 五邑大学 试 卷学期： 2008 至 2009 学年度 第 二 学期课程： 数据结构 专业： 班级： AP0706 姓名： 学号： 题号一二三四五总分得分得分一、单项选择题(10小题，每小题1分，共10分)1若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n ，则第i个输出元素是_。A不确定Bn-iCn-i-1Dn-i+12设计一个判别表达式中左右括号是否配对的算法，采用_数据结构最佳。A顺序表B栈C队列 D链表3设有两个串p和q，求q在p中首次出现的位置的运算称作_。A连接B求子串C模式匹配D求串长 4线性表的顺序存储结构是一种_的存储结构。A随机存取B顺序存取C索引存取D散列存取 5对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是_。AO(1) BO(n)CO(n2)DO(nlog2n)6关键路径是AOE网中_。A从源点到终点的最长路径B从源点到终点的最短路径C最长的回路D最短的回路 7已知数据元素为（34,76,45,18,26,54,92,65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为_。A3B5C7D9 8对数列（25,84,21,47,15,27,68,35,20）进行排序，元素序列的变化情况如下：(1) 25，84，21，47，15，27，68，35，20(2) 20，15，21，25，47，27，68，35，84(3) 15，20，21，25，35，27，47，68，84(4) 15，20，21，25，27，35，47，68，84则采用的排序方法是_。A快速排序B归并排序C基数排序D希尔排序 9任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序_。A肯定不发生改变B肯定发生改变C不能确定D有时发生变化 10对特殊矩阵采用压缩存储的目的主要是为了_。A表达变得简单B对矩阵元素的存取变得简单C去掉矩阵中的多余元素D减少不必要的存储空间得分二、判断题(10小题，每小题1分，共10分)（ ）1 一个图的邻接矩阵表示是惟一的，邻接表表示也惟一。（ ）2 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用快速排序方法比 采用堆排序更好。（ ）3 在散列函数H(k)=k mod m 中，一般来讲，m应取素数。（ ）4 从逻辑关系上讲，数据结构主要分为集合、线性结构、树结构和图结构。（ ）5 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第1个元素的地址为112。（ ）6 数组Qn用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为(rearfrontn)%n。（ ）7 将数组称为随机存取结构是因为数组元素是随机的。（ ）8 排序的主要目的时为了以后对已排序的数据进行查找。（ ）9 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（ ）10 拓扑排序算法和广度优先遍历算法都能判断一个有向图是否存在回路。得分三、填空题(10小题，每空1分，共16分)1表示有100个顶点，1000条边的有向图的邻接矩阵有_个非零矩阵元素。2如果要将序列（50,16,23,68,94,70,73）建成堆，只须把16与_交换。3具有6个顶点的无向图至少应该有_条边才能确保是一个连通图。4含A、B、C这3个结点的不同形态的树有_棵，不同形态的二叉树有_棵。5中缀表达式(5620)(42)转换为后缀表达式为_，后缀表达式A BC D E 转换为中缀表达式为_。6已知一个有序表的关键字序列为1,8,12,25,29,32,40,62,98，当二分查找值为29的元素时，需要_次比较才能查找成功；若采用顺序查找时，需要_次比较才能查找成功。7已知一棵树T的边集为（I,M）,（I,N）,（E,I）,（B,E）,（B,D）,（C,B）,（G ,J）,（G ,K）,（A,G）,（A,F）,（H,L）,（A,H）,（C,A），则该树的根结点是_，叶子结点共_个，该树的深度为_。8设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为_；若为nlog25n, 则表示成数量级的形式为_。 9在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是s-next=rear-next; rear-next=s;和_。10二叉树的前序序列和后序序列正好相反，则该二叉树一定是_的二叉树。得分四、应用题(共有7小题，共计50分)1 已知一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，画出该二叉树，并给出该二叉树的前序遍历序列，画出该二叉树对应的森林。(10分)，2 证明：对于一棵非空的二叉树，如果叶结点数为n0，度为2的结点数为n2，则有n0=n2+1。（5分）3 若输入序列是3，5，1，9，4，10，2，8，7，6，试画出所产生的大根堆和所对应的二叉排序树。（7分）4已知某字符串S中共有5种字符(A，B，C，D，,E)，各种字符出现的频率分别是15，36，3，6，20，建立相应的哈夫曼树，对该字符串用0，1进行前缀编码，给出5种字符的哈夫曼编码，并计算其WPL。（7分） 5给定表（19,14,22,01,66,21,83,27,56,13,10）,按表中元素顺序构造一棵AVL树。（7分） 6已知某图的邻接表如下：（7分）（1） 分别给出从A、B点出发进行广度优先搜索的序列。（2） 画出该图。7设有一组关键字72，35，124，153，84，57需要插入到表长为12 的散列表中。试设计一个适当的散列函数；用此散列函数将上述关键字插入散列表，用线性探测法解决冲突。试画出最终的散列表结构。（7分）得分五、算法设计题(2小题，每小题7分，共14分)1设计一个算法，