数据结构试卷(A卷)2005.1

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

A.356B.358C.360D.3623.n个顶点的强连通有向完全图中至少含有()条有向边。

A.n-1B.nC.n(n-1)/2D.n(n-1)4.在需要经常查找结点的前驱与后继的场合中，使用(

)比较合适。A.单链表

B.双链表

C.顺序表

D.循环链表5.20个结点完全二叉树共有(

)个叶子结点。A.8

B.9C.10

D.116.按照二叉树的定义，具有3个结点的二叉树有(

)种形式。

A.3

B.4

C.5

D.67.深度为5的二叉树至多有(

)个结点。A.16

B.32

C.31

D.108.静态查找表与动态查找表二者的根本差别在于(

)。A.它们的逻辑结构不一样

B.施加在其上的操作不同

C.所包含的数据元素的类型不一样D.存储实现不一样9.无向图中一个顶点的度是指图中()。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}二、填空题(210分)1.串S=”Iamaworker”的长度是________。2.进行时间复杂度分析时，一般主要考虑最坏情况时间复杂度和时间复杂度。3.8层完全二叉树结点数目范围是。4.n个结点e条弧的有向图邻接表结构中，有个表结点和个头结点。5.字符串"ABC""A"。（填＜、＞或者者＝）6.队列的基本操作原则是“先进先出”，栈的基本操作原则是。7．对数组存储线性表(16,15,32,11,6,30)用快速排序方法进行由小到大排序，若排序下标范围为0~5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置是。8.基于关键字比较大小的排序算法中，排序算法的平均时间复杂度最优。9．《计算方法》课程主要讲授科学计算领域的程序设计方法；而《数据结构》课程主要研究领域的程序设计方法。三、简答题(56分)1.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。

(1)画出该二叉排序树；

(2)画出删去该树中元素值为90的结点之后的二叉排序树。2.请把如下序列构造成为一个堆并画出对应的二叉树示意图。23,76,47,53,41,12,85,303.若入栈元素序列为ABC,写出所有可能的出栈序列。4.二叉树如下图所示，写出先序、中序、后序遍历结点访问次序并画出中序穿线(线索)二叉树。s1s1s2s3s4s6s8s9s7s5545112974245.求出下图的关键路径，结点的最早完成时间，结点的最晚完成时间及关键活动。6.画出下图的一棵最小生成树。四、算法设计(103分)

1.指针变量p指向循环单链表某结点，写出一个函数DelPriou(p)，删除结点指针p所指结点的前驱结点。（请对循环单链表数据结构进行试当说明）2.已知二叉链表树结点指针数据类型bitree定义如下，试写出一个递归函数，求二叉树的深度。typedefstructnode{intdata;structn