数据结构试题(白明)试题+参考答案

命题人白明试卷分类（A卷或B卷）A五邑大学试卷学期2008至2009学年度第二学期课程数据结构专业班级AP0706姓名学号题号一二三四五总分得分一、单项选择题10小题，每小题1分，共10分1若一个栈的输入序列是1，2，3，N，输出序列的第一个元素是N，则第I个输出元素是_D_。A不确定BNICNI1DNI12设计一个判别表达式中左右括号是否配对的算法，采用_B_数据结构最佳。A顺序表B栈C队列D链表3设有两个串P和Q，求Q在P中首次出现的位置的运算称作_C_。A连接B求子串C模式匹配D求串长4线性表的顺序存储结构是一种_A_的存储结构。A随机存取B顺序存取C索引存取D散列存取5对于N个元素组成的线性表，建立一个有序单链表的时间复杂度是_C_。AO1BONCON2DONLOG2N6关键路径是AOE网中_A_。A从源点到终点的最长路径B从源点到终点的最短路径C最长的回路D最短的回路7已知数据元素为（34,76,45,18,26,54,92,65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为_B_。A3B5C7D98对数列（25,84,21,47,15,27,68,35,20）进行排序，元素序列的变化情况如下125，84，21，47，15，27，68，35，20220，15，21，25，47，27，68，35，84315，20，21，25，35，27，47，68，84415，20，21，25，27，35，47，68，84则采用的排序方法是_A_。A快速排序B归并排序C基数排序D希尔排序9任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序_A_。A肯定不发生改变B肯定发生改变C不能确定D有时发生变化10对特殊矩阵采用压缩存储的目的主要是为了_D_。A表达变得简单B对矩阵元素的存取变得简单C去掉矩阵中的多余元素D减少不必要的存储空间试卷编号二、判断题10小题，每小题1分，共10分（）1一个图的邻接矩阵表示是惟一的，邻接表表示也惟一。（）2设有5000个元素，希望用最快的速度挑选出前10个最大的，采用快速排序方法比采用堆排序更好。（）3在散列函数HKKMODM中，一般来讲，M应取素数。（）4从逻辑关系上讲，数据结构主要分为集合、线性结构、树结构和图结构。（）5已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第1个元素的地址为112。（）6数组QN用来表示一个循环队列，FRONT为队头元素的前一个位置，REAR为队尾元素的位置，计算队列中元素个数的公式为REARFRONTNN。（）7将数组称为随机存取结构是因为数组元素是随机的。（）8排序的主要目的时为了以后对已排序的数据进行查找。（）9在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（）10拓扑排序算法和广度优先遍历算法都能判断一个有向图是否存在回路。三、填空题10小题，每空1分，共16分1表示有100个顶点，1000条边的有向图的邻接矩阵有_1000_个非零矩阵元素。2如果要将序列（50,16,23,68,94,70,73）建成堆，只须把16与_50_交换。3具有6个顶点的无向图至少应该有_5_条边才能确保是一个连通图。4含A、B、C这3个结点的不同形态的树有_2_棵，不同形态的二叉树有_5_棵。5中缀表达式562042转换为后缀表达式为562042/，后缀表达式ABCDE转换为中缀表达式为A/BC（DE）。6已知一个有序表的关键字序列为1，8，12，25，29，32，40，62，98，当二分查找值为29的元素时，需要_1_次比较才能查找成功；若采用顺序查找时，需要_5_次比较才能查找成功。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），则该树的根结点是_C_，叶子结点共_7_个，该树的深度为_5_。8设待处理问题的规模为N，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为_O1_；若为NLOG25N,则表示成数量级的形式为_ONLOG2N_。9在由尾指针REAR指示的单循环链表中，在表尾插入一个结点S的操作序列是SNEXTREARNEXTREARNEXTS和REARS。10二叉树的前序序列和后序序列正好相反，则该二叉树一定是_高度等于其结点数_的二叉树。四、应用题共有7小题，共计50分1已知一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，画出该二叉树，并给出该二叉树的前序遍历序列，画出该二叉树对应的森林。10分解答二叉树如下（5分）对应的森林如下（3分）ECAGFDBECADBGF前序遍历序列是EACBDGF（2分）2证明对于一棵非空的二叉树，如果叶结点数为N0，度为2的结点数为N2，则有N0N21。（5分）证明设N为二叉树的结点总数，N1为二叉树中度为1的结点数，则有NN0N1N2（2分）在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有NN12N21（2分）合并两式，可以得到N0N21。（1分）3若输入序列是3，5，1，9，4，10，2，8，7，6，试画出所产生的大根堆和所对应的二叉排序树。（7分）大根堆4分二叉排序树3分134569710824已知某字符串S中共有5种字符A，B，C，D，,E，各种字符出现的频率分别是15，36，3，6，20，建立相应的哈夫曼树，对该字符串用0，1进行前缀编码，给出5种字符的哈夫曼编码，并计算其WPL。（7分）哈夫曼树4分哈夫曼编码2分WPL1分5给定表（19,14,22,01,66,21,83,27,56,13,10），按表中元素顺序构造一棵AVL树。（7分）每个平衡步骤1分。6已知某图的邻接表如下（7分）（1）分别给出从A、B点出发进行广度优先搜索的序列。（2）画出该图。解答分别给出从A、B点出发进行广度优先搜索的序列。（各2分）AABCDBBACD对应的图如下（3分）7设有一组关键字72，35，124，153，84，57需要插入到表长为12的散列表中。试设计一个适当的散列函数；用此散列函数将上述关键字插入散列表，用线性探测法解决冲突。试画出最终的散列表结构。说明哈希函数不同，数据在哈希表中的位置不同。（多解）若设HKEYKEY11（2分）则最终的哈希表结构为（3分）所有关键字求散列值（2分）01234567872153124358457A111B0C1100D1101E10WPL36404536157（3）五、算法设计题2小题，每小题7分，共14分1设计一个算法，判断一个单链表中的元素是否递增有序。TEMPLATEINTORDERNODEHNODEPH以上1分WHILEPNEXTNULLIFPDATANEXTDATAPPNEXT以上3分ELSEBREAKIFPNEXTNULLRETURN1ELSERETURN0以上3分2一棵具有N个结点