数据结构期末试题 (D卷).doc

曲阜师范大学计算机科学学院试题2008级20092010学年 第一学期数据结构期末试题 (D卷)一、 选择题(10题1分=10分)1. 算法指的是_。A. 对特定问题求解步骤的一种描述，是指令的有限序列B. 计算机程序C. 解决问题的计算方法D. 数据处理2. n个元素组成的线性表，建立一个有序单链表的时间复杂度是_。A. O(1) B. O(n)C. O(n2) D. O(nlog2n)3. 已知一维数组A.采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是_。A. 108 B. 180 C. 176 D. 1124. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是_。A. 54321 B. 45321 C. 43512 D. 12345 5. 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点则有_成立。A. n=h+m B. h+m=2n C. m=h-1 D. n=2m-16. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A.1 A.n中，结点A.i若有左子树，则左子树的根结点是_。 A. A2i-1 B. A2i+1 C. Ai/2 D. A2i7. 线索二叉树中某结点R没有左孩子的充要条件是_。A. R.lchild.=NULL B. R.ltag=0 C. R.ltag=1 D. R.rchild=NULL8. 已知一个AOV网如图所示，不可能的拓扑序列是_。A. v0 v1 v5 v2 v3 v6 v4 B. v0 v1 v5 v2 v6 v3 v4 C. v1 v0 v5 v6 v2 v3 v4 D. v0 v1 v5 v6 v2 v3 v49. 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过_。A.1 B. n/2 C. n-1 D. n10. 设无向图G=(V, E)和G =(V, E )，如果G 是G的生成树，则下面的说法中错误的是（ ）。A. G 为 G的子图 B. G 为 G的连通分量C. G 为G的极小连通子图且V = V D. G 是G的一个无环子图二、 填空题(20空1分=20分)1. 数据的存储结构主要有顺序存储结构和链接存储结构两种基本方法，不论哪种存储结构，都要存储两方面的内容：_和_。2. 算法的描述方法通常有自然语言、_、_和伪代码四种。其中，伪代码被称为算法语言。3. 在一般情况下，一个算法的时间复杂度是_的函数。4. 在表长为n的顺序表中，等概率情况下，插入和删除一个元素平均需移动_个元素，具体移动元素的个数与表长和_有关。5. 设单链表中指针p 指向结点A.，若要删除A.的后继结点（假设A.存在后继结点），则需修改指针的操作为_。6. 表达式A.*(B.+C.)-D.的后缀表达式是_。7. 数组Qn用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为_。8. 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A105的存储地址是1000，则元素A1510的存储地址是_。9. 稀疏矩阵一般压缩存储方法有两种，分别是_和_。10. 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是_。11. 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为_。12. 评价基于比较的排序算法的时间性能，主要标准是_和_。13. 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为_。14. 一组记录的关键码为46, 79, 56, 38, 40, 84，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。15. 一棵5阶B- 树中，除根结点外，每个结点的子树树目最少为_，最多为5。三、 判断题(10题1分=10分)1. 基于某种逻辑结构之上的基本操作，其实现是唯一的。【 】2. 设p，q是指针，若p=q，则*p=*q。【 】3. 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【 】4. 稀疏矩阵压缩存储后，必会失去随机存取功能。【 】5. 栈可以作为实现过程调用的一种数据结构。【 】6. 已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。【 】7. 二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。【 】8. 如果某种排序算法是不稳定的，则该排序方法没有实际应用价值。【 】9. 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。【 】10. m阶B_树中任何一个结点的左右子树的高度都相等。【 】四、 综合问答题(5题8分=40分)1. 分析以下各程序段，并用大O记号表示其执行时间。2. 对给定的一组权值W（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。3. 最小生成树指的是连通网中所有生成树中权值之和为最小的生成树。下图中是一个无向带权图，各结点按字母顺序存储。请按Kruskal算法求最小生成树。要求正确画出求解过程。4. 已知散列表的空间为014，表长为15。将关键字序列（19，14，23，01，68，20，84，27，55，11，10，79）按散列函数H(key)=key%13 和线性探测法处理冲突构造所得的哈希表，并求出在等概率情况下的查找成功和查找不成功的平均查找长度。5. 已知一个AOE网如下图所示。（1）列出所有关键路径和关键活动。（2）写出求解过程。提示：事件的最早发生时间vek，事件的最迟发生时间vlk，活动的最早开始时间ek，活动的最迟开始时间lk。五、 算法设计题(2题10分=20分)1. 设两个带头结点的单链表L1和L2分别表示两个集合，设计算法判断L1是否为L2的子集, 要求算法声明为：bool IsSubset(N