数据结构试卷(A卷)20051

1、网络教育学院数据结构试卷(A)说明：此试卷曾于2005年用于我校网络教育学院高升本（脱产）计算机专业期末考试卷;评论:考试时间：150分钟，试题难度：中等一、单项选择题(210分)1.以下说明法中正确的选项是()。A.迅速排序在最坏状况下退化为起泡排序，时间复杂度为O(n2)。B.堆排序在最坏状况下的时间复杂度为O(n2)。堆排序列是一种稳固的排序方法。基数排序是一种不稳固的排序方法。2.三维数组A456按行优先储存方法储存在内存中，若每个元素占2个储存单元，且数组中第一个元素的储存地点为120，则元素A345的储存地点为()。A.356B.358C.360D.3623.n个极点的强连通有向完

2、整图中起码含有()条有向边。A.n-1B.nC.n(n-1)/2D.n(n-1)4.在需要常常查找结点的前驱与后继的场合中，使用()比较适合。A.单链表B.双链表C.次序表D.循环链表5.20个结点完整二叉树共有()个叶子结点。A.8B.9C.10D.116.依据二叉树的定义，拥有3个结点的二叉树有()种形式。A.3B.4C.5D.67.深度为5的二叉树至多有()个结点。A.16B.32C.31D.108.静态查找表与动向查找表两者的根本差异在于()。A.它们的逻辑结构不同样B.施加在其上的操作不同C.所包括的数据元素的种类不同样D.储存实现不同样9.无向图中一个极点的度是指图中()。1A.经

3、过该极点的简单路径数B.与该极点相毗邻的极点数C.经过该极点的回路数D.与该极点连通的极点数10.已知一组重点字为25,48,36,72,79,82,23,40,16,35，此中每相邻两个为有序子序列。对这些子序列进行一趟两两合并的结果是()。A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,79,82二、填空题(210分)1.串S=”Iamaworker的长”度是_。2.进行时间复杂度剖析时，一般主要考虑最

4、坏状况时间复杂度和时间复杂度。3.8层完整二叉树结点数量范围是。4.n个结点e条弧的有向图毗邻表结构中，有个表结点和个头结点。5.字符串ABCA。（填、或许者）6.行列的基本操作原则是“先进先出”，栈的基本操作原则是。7对数组储存线性表(16,15,32,11,6,30)用迅速排序方法进行由小到大排序，若排序下标范围为05，选择元素16作为支点，调用一趟迅速排序算法后，元素16在数组中的下标位置是。8.鉴于重点字比较大小的排序算法中，排序算法的均匀时间复杂度最优。9计算方法课程主要讲解科学计算领域的程序设计方法；而数据结构课程主要研究领域的程序设计方法。三、简答题(56分)从空树起，挨次插入重

5、点字40，8，90，15，62，95，12，23，56，32，结构一棵二叉排序树。画出该二叉排序树；画出删去该树中元素值为90的结点以后的二叉排序树。请把以下序列结构成为一个堆并画出对应的二叉树表示图。23,76,47,53,41,12,85,303.若入栈元素序列为ABC,写出全部可能的出栈序列。24.二叉树以以下图所示，写出先序、中序、后序遍历结点接见序次并画出中序穿线(线索)二叉树。ABCDEFG求出以下图的重点路径，结点的最早达成时间，结点的最晚达成时间及重点活动。ss2751921435s9s7154ss6s4824画出以下图的一棵最小生成树。四、算法设计(103分)1.指针变量p指向循环单链表某结点，写出一个函数DelPriou(p)，删除结点指针p所指结点的前驱结点。（请对循环单链表数据结构进行试当说明）已知二叉链表树结点指针数据种类bitree定义以下，试写出一个递归函数，求二叉树的深度。typedefstructnodeintdata;structnode*lchild,*rchild;*