资源描述：
《数据结构试题(白明)试题 参.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、试卷编号命题人： 白明 试卷分类（A卷或B卷）A五邑大学试卷学期：2008至2009学年度第二学期课程： 数据结构 专业： 班级：AP0706 姓名： 学号： 题号一二三四五总分得分一、单项选择题(10小题，每小题1分，共10分)1．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是____D________。A．不确定B．n-iC．n-i-1D．n-i+12．设计一个判别表达式中左右括号是否配对的算法，采用_____B______数据结构最佳。A．顺序表B．栈C．队列D．链表3．设有两个串p和q
2、，求q在p中首次出现的位置的运算称作___C_____。A．连接B．求子串C．模式匹配D．求串长4．线性表的顺序存储结构是一种_____A______的存储结构。A．随机存取B．顺序存取C．索引存取D．散列存取5．对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是____C_____。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)6．关键路径是AOE网中____A______。A．从源点到终点的最长路径B．从源点到终点的最短路径C．最长的回路D．最短的回路7．已知数据元素为（34,76,45,18,26,54,92,65），按照依次插入
3、结点的方法生成一棵二叉排序树，则该树的深度为_____B______。A．3B．5C．7D．98．对数列（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_____。A．快速排序B．归并排序C．基数排序D．希尔排序9．任何一棵二叉树的叶子结点在前序、中序、后序
4、遍历序列中的相对次序____A_____。A．肯定不发生改变B．肯定发生改变C．不能确定D．有时发生变化10．对特殊矩阵采用压缩存储的目的主要是为了___D____。A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间二、判断题(10小题，每小题1分，共10分)（×）1．一个图的邻接矩阵表示是惟一的，邻接表表示也惟一。（×）2．设有5000个元素，希望用最快的速度挑选出前10个最大的，采用快速排序方法比采用堆排序更好。（√）3．在散列函数H(k)=kmodm中，一般来讲，m应取素数。（√）4．从逻辑关系上讲，数据结构主
5、要分为集合、线性结构、树结构和图结构。（√）5．已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第1个元素的地址为112。（√）6．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为(rear－front＋n)%n。（×）7．将数组称为随机存取结构是因为数组元素是随机的。（√）8．排序的主要目的时为了以后对已排序的数据进行查找。（√）9．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（×）10．拓扑排序算法和广度优先遍历算法都能判断一个有向
6、图是否存在回路。三、填空题(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．中缀表达式(56－20)／(4＋2)转换为后缀表达式为56#20-4#2+/，后缀表达式AB／CDE＋×－转换为中缀表达式为A/B
7、-C*（D+E）。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，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为
8、__O(1)__；若为n×log25n,则表示成数量
