数据结构试卷(A卷).doc

网络教育学院数据结构试卷(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. 循环链表
5. 20个结点完全二叉树共有(      )个叶子结点。
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
8. 静态查找表与动态查找表二者的根本差别在于(  　　    )。
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}
二、填空题(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. 二叉树如下图所示，写出先序、中序、后序遍历结点访问次序并画出中序穿线(线索)二叉树。
s1
s2
s3
s4
s6
s8
s9
s7
s5
5
4
5
1
1
2
9
7
4
2
4

5. 求出下图的关键路径，结点的最早完成时间，结点的最晚完成时间及关键活动。
6. 画出下图的一棵最小生成树。
四、算法设计(10´3分)
1. 指针变量p指向循环单链表某结点，写出一个函数DelPriou(p)，删除结点指针p所指结点的前驱结点。（请对循环单链表数据结构进行试当说明）
2. 已知二叉链表树结点指针数据类型bitree定义如下，试写出一个递归函数，求二叉树的深度。typedef struct node { int data; struct node *lchild, *rchild; } *bitree;
3. 二叉树结点结构同上题，写一个函数，将所有叶子结点的rchild指针域按从左向右的顺序串接起来，成为一个单链表。要求函数传入根结点指针，返回最左边叶子结点指针。