数据结构试卷(A卷)2005.1.docVIP

网络教育学院数据结构试卷(A) 说明：此试卷曾于2005年用于我校网络教育学院高升本（脱产）计算机专业期末考试卷; 点评:考试时间：150分钟，试题难度：中等 一、单项选择题(2?10分) 1. 下列说明法中正确的是( 　　)。 A. 快速排序在最坏情况下退化为起泡排序，时间复杂度为O(n2)。 B. 堆排序在最坏情况下的时间复杂度为O(n2)。 C. 堆排序列是一种稳定的排序方法。 D. 基数排序是一种不稳定的排序方法。 2. 三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为( 　　 )。 A. 356 B. 358 C. 360 D. 362 3. n个顶点的强连通有向完全图中至少含有( 　　)条有向边。A. n-1 B. n C. n(n-1)/2 D. n(n-1) 4. 在需要经常查找结点的前驱与后继的场合中，使用(?　　???? )比较合适。 A. 单链表?????????? B. 双链表?????????? C. 顺序表?????????? D. 循环链表(????? )个叶子结点。 A. 　8??????????????B. 　9　　　　C. 　10??????????? ??D. 　11 6. 按照二叉树的定义，具有3个结点的二叉树有(????? )种。 A.　3????????? B.　4 ?????????C.　5????????? D.　6 7. 深度为5的二叉树至多有(????? )个结点。 A.16????????? B.32????? ????C.31????????? D.10(??　　??? )。 A.它们的逻辑结构不一样????????????? B.施加在其上的操作不同???? C.所包含的数据元素的类型不一样 D.存储实现不一样 A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )。 A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35} C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82} 二、填空题(2?10分) 1. 串S=”I am a worker”的长度是________。 2. 进行时间复杂度分析时，一般主要考虑最坏情况时间复杂度和 时间复杂度。 3. 8层完全二叉树结点数目范围是 。 4. n个结点e条弧的有向图邻接表结构中，有 个表结点和 个头结点。 5. 字符串ABC A 。（填＜ 6. 队列的基本操作原则是“先进先出”，栈的基本操作原则是　　　　　　　　　　　。 7．对数组存储线性表(16, 15, 32, 11, 6, 30)用快速排序方法进行由小到大排序，若排序下标范围为0~5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置是　　　　　。 8. 基于关键字比较大小的排序算法中，　　　　　排序算法的平均时间复杂度最优。 9．《计算方法》课程主要讲授科学计算领域的程序设计方法；而《数据结构》课程主要研究 　　　领域的程序设计方法。 三、简答题(5?6分) 1. 从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。(1)画出该二叉排序树；(2)画出删去该树中元素值为90的结点之后的二叉排序树。 2. 请把如下序列构造成为一个堆并画出对应的二叉树示意图。 　23, 76, 47, 53, 41, 12, 85, 30 3. 若入栈元素序列为ABC, 写出所有可能的出栈序列。 4. 二叉树如下图所示，写出先序、中序、后序遍历结点访问次序并画出中序穿线(线索)二叉树。 5. 求出下图的关键路径，结点的最早完成时间，结点的最晚完成时间及关键活动。 6. 画出下图的一棵最小生成树。 四、算法设计(10?3分)1. 指针变量p指向循环单链表某结点，写出一个函数DelPriou(p)，删除结点指针p所指结点的前驱结点。（请对循环单链表数