fccjxxw.com
非常超级学习网 学习超级帮手
当前位置:首页 >> >>

中南大学数据结构97-06真题集


追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

《数据结构与算法分析》教学大纲

课程编号: 课程名称:数据结构与算法分析 学 分: 4 总学时:64 实验学时:10 课内上机学时:10 先修课程要求:离散数学,C 语言程序设计。 适应专业:计算机科学与技术,计算机应用技术。 参考教材:数据结构与算法分析(A Practical Introduction to Data Structures and Algorithm Analysis/Second Edition) ,Clifford A. Shaffer 著,电子工业出版社,2002 年。 一、课程在培养方案中的地位、目的和任务 数据结构与算法分析是计算机科学与技术, 计算机应用技术, 电子信息工程和信息安全 等专业的基础课程,主要讨论抽象数据类型、数据结构和算法的复杂度分析。本课程为操作 系统、 计算机图形学和数据库原理等后续课程提供必要的基础知识, 是深入学习计算机软件 技术的必要条件。 设置本课程的目的是让软件开发人员了解和掌握抽象数据类型、 数据结构 和算法复杂度分析等方面必要的概念、 原理和方法。 本课程的任务是使学生掌握设计基本的 和常用的数据结构、 学会对算法进行时间和空间复杂度分析, 并为其他专业课程的学习打下 基础。 二、课程的基本要求 通过对本课程的学习,要求学生 1. 掌握抽象数据类型和数据结构的概念; 2. 掌握算法分析的概念和方法; 3. 掌握线性表、栈和队列和基本概念和操作; 4. 掌握二叉树和树的概念和操作; 5. 掌握排序技术; 6. 掌握检索技术; 7. 熟悉索引技术; 8. 掌握图的概念与方法。 三、课程的基本内容以及重点难点 本课程的基本内容: 1. 数据结构与算法概述; 2. 算法分析; 3. 线性表、栈和队列; 4. 二叉树; 5. 树; 6. 内排序; 7. 外排序; 8. 检索; 9. 索引技术; 10.图;

-1-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

11.线性表和数组高级技术。 本课程的重点: 1. 算法分析; 2. 线性表、栈和队列 3. 二叉树; 4. 内排序; 5. 检索; 6. 索引技术; 7. 图。 本课程的难点: 1.算法分析; 2.快速排序、归并排序和基数排序算法; 3.散列的概念和方法; 4.B 树和 B+树; 5.最短路径问题; 6.最小支撑树计算。
四、 实验要求

要求能够实现线性表、栈和队列,实现 Huffman 树,实现快速排序、归并排序和基数排 序算法,实现散列方法,实现最短路径问题求解和最小支撑树求解。
五、 课程学时分配

章节 1 3 4 5 6 7 8 9 10 11 12 算法分析

内容 数据结构与算法概述 C++介绍(补充) 线性表、栈和队列 二叉树 树 内排序 文件管理和外排序 检索 索引 图 线性表和数组高级技术

学时 2 2 8 8 8 2 8 2 6 4 10 4

其中实验 (上机学时)

备注

2 2 2 2 2

六、考核方式 闭巻考试。

七、制订执笔者:陈学工
审核者(教研室主任或研究所所长): 批准者(教学院长):

-2-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 1997 年数据结构
一. 是非题(共 5 分) 1、哈夫曼树是外部路径长度最小的扩展二叉树。 2、在表示某工程的 AOE 网中,加速其关键路经上的任意关键活动均可缩短整 个工程的完成时间。 3、二叉树是度为 2 的有序树。 4、在任意一棵二叉排序树中删除一个分支节点,接着又将该结点插入到二叉 排序树中,则所得到的二叉排序树和删除前的二叉排序树相同。 5、队列和栈都是运算受限的线性表,只允许在表的两端进行运算。 二. 填空题(每空 2 分,共 10 分) 1、对于 7 个元素的集合(1,2,3,4,5,6,7)进行快速排序,具有最小比 较和交换次数的初始排列次序为( ) 2、设 G 为具有 N 个顶点的无向连通图,则 G 中至少有( )条边。 3、设有 N 个结点的完全二叉树顺序存放在向量 A[1:N]中,其下标值最大的分 支结点为( ). 4、设循环队列存放在向量 sq.data[0:M]中,则队头指针 sq.front 在循环意 义下的出队列操作可表示为( ) ,若用牺牲一个单元的办法来区分队 满和队空(设队尾指针为 sq.rear), 则队满的条件为( ) 。 三、简答题(每题 3 分,共 15 分) 1、设有三维数组 A[-2:4,0:3,-5:1]按列序存放,数组的起始地址为 1210, 试求 A(1,2,3)所在的地址。 2、在迷宫问题中求路径可用哪些结构实现,你认为求最短路经有哪种结构比 较合适,为什么? 3、在查找和排序算法中,监视哨的作用是什么? 4、直接在二叉排序数中查找关键字 K 与在中序遍历输出的有序序列中查找关 键字 K,其效率是否相同?输入关键字有序序列来构造一棵二叉排序树, 然后对此树进行查找,其效率如何?为什么? 5、设 S1,S2 为串,请给出使 S1//S2=S2//S1 成立的所有可能的条件(//为连 接符) 。 四.单选题(每题 2 分,共 10 分) 1. 在文件 “局部有序” 和文件长度较小的情况下, 最佳内部排序方法是 ( ) : A. 直接插入排序 B. 起泡排序 C. 简单选择排序 D.SHELL 排序 2.以 T 为根的二叉树的值定义为:V(T)=V(TL)+1 当 V(TL)=V(TR)时, V(T)=MAX(V(TL),V(TR)) 当 V(TL)<>V(TR)时,其中 TL 和 TR 分别是二叉树 T 的左、右子树。空树的值为 0,此时应用(A)遍历法求二叉树 T 的值。 下面以 a 为根的二叉树的值 V(a)=V(b)。 A:(1)前序 (2)中序 (3)后序 B:(1)0 (2)1 (3)2 (4)3 (5) 4
-3-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

3、顺序查找法适用于查找顺序存储或链式存储的线性表, 平均比较次数为 (A) , 二分法查找只适用于查找顺序存储的有序表,平均比较次数为(B) 。在此假 定 N 为线性表中结点数,且每次查找都是成功的。 A、B: (1)N+1 (2)2logN (3)logN (4)N/2 (5)NlogN (6)N*N 五. 综合题 1、 设有三对角矩阵 A[1:N][1:N], 将其三对角线上的元素逐行地存于 B[1:3N-2] 中,使得 B[K]=A[i][j], 求: (1)用 i,j 表示 K 的下标变换公式, (2)用 K 表示 i,j 的下标变换公式。 (10 分) 2、证明:由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。 (10 分) 3、试利用 Dijkstra 算法求下图中从顶点 1 到其它各顶点间的最短路径,写出执 行算法过程中各步的状态。 (10 分)

4、 试推导含 12 个结点的平衡二叉树的最大深度, 并画出一棵这样的树。 (10 分) 5、假设某线性表的关键字序列为(61,2378,789,345,8423,1125,890,776, 4683,553,213,8679,12287) ,按装填因子=13/17,将关键字存入散列表中, 散列函数为 H(k)=k mod 17,H(k)=(k mod 15)+3,试采用双散列函数探测法处理 冲突,画出相应的散列表,并计算在等概率下查找成功的平均查找长度。编写将 一棵二叉树中序线索画的算法。 (10 分) 要求: (1)结点结构; (2)变量说明; (3)具体算法。 (用 C 或 PASCAL 均可)

-4-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 1998 年数据结构
一. 判断题( 10 分) 1. 设模式串的长度为 m,目标串的长度为 n,当 n≈m 且处理只匹配一次时,朴素的匹配 (即子串定位函数)算法所花的时间可能更少。 2. 后序线索二叉树是不完善的,要对它进行遍历,还要使用栈。 3. 采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录 的所在位置置空,因为这会影响以后的查找。 4. 插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常 使用。 5. 文件是记录的集合,每个记录由一个或多个数据项组成,因而一个文件可看作由多 个记录组成的数据结构。 6. 堆排序所须的时间与待排序的记录个数无关。 7. 磁盘的优点是容量比磁带大。 8. 用邻接矩阵 A 表示图,判定任意两顶点 V1 和 V2 之间是否有长度为 m 的路径相连, 只要检查 Am 的第 I 行,第 j 列的元素是否为 0 即可。 9. 虽然信息项序列的顺序不一样,但依次生成的二叉排序树却是一样的。 10. 当待排序的元素很大时,为了交换元素的位置,移动元素要占用较多的时间,这是 影响时间复杂度的主要因素。 二、填空题(20 分) 1. 在磁带上的顺序文件中插入新的记录时,必须( ) 。 2. 对于含 N 个顶点 E 条边的无向连通图,利用 Prim 算法生成最小代价生成树其时间复杂 度为( ) ,利用 Kruskal 算法生成最小代价生成树其时间复杂度为( ) 。 3. 哈夫曼树是( ) 。 4. 所需读写的扇区旋转到磁头下方的所需时间称为( ) 。 5. 快速排序在( )的情况下最易发挥其长处。 6. 索引顺序文件是最常用的文件组职之一,通常用( )结构来组织索引。 7. 如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用( )查 找方法。 8. 当广义表中的每个元素都是原子时,广义表便成了( ) 。 9. 有向图 G 可拓扑排序的判别条件是( ) 。 三、选择题 (18 分) 1. 某二叉树 T 有 n 各界点,设按某种顺序对 T 中的每个结点进行编号,编号为 1,2,… , n,且有如下性质:T 重任一节点 V,其编号等于左子树上的最小编号减 1,而 V 的右子 树的结点中,其最小编号等于 V 左子树上结点的最大编号加 1。这时是按( )编号的。 A、 中序遍历序列 B、前序遍历序列 C、 后序遍历序列 D、层次顺序 2. 如果把某作业工程表示成网络的话, 则如图 1 所示,其中各箭头上的数字表示所需天数。 (1)事件 5 的最早完成时间是( )天。 (2)事件 4 的最迟开始时间是( )天。 (3) 关键路径是( ) 。 A、15 B、19

-5-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

C、23 E、30 G、34 I、1?4?7?9?10

D、27 F、32 H、1?2?5?6?10 J、1?4?7?8?9?10

3. 动态存储管理系统中,通常可有( )种不同的分配策略。 A、1 B、2 C、3 D、4 E、5 4. 已 知 广 义 表 : A=(a,b), B=(A,A), C=(a,(b,A),B), 求 下 列 运 算 的 结 果 : tail(head(tail(C))) =( )。 A、 (a) B、 A C、a D、(b) E、b F、(A) 四、简答题 (每题 6 分, 共 30 分) 1. 一棵有 n(n>0)个结点的 d 度树, 若用多重链表表示, 树中每个结点都有 d 个链域, 则在 表示该树的多重链表中有多少个空链域? 为什么? 2. 试提出三种判断一个图是否有圈的方法. 3. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 4. 对一个有 t 个非零元素的 Am*n 矩阵, 用 B[0..t][1..3]的数组来表示,其中第 0 行的 三个元素分别为 m,n,t, 从第一行开始到最后一行, 每行表示一个非零元素;第一列为 矩阵元素的行号, 第二列为其列号,第三列为其值。对这样的表示法,如果需要经常 进行该操作—确定任意一个元素 A[i][j]在 B 中的位置并修改其值,应如何设计算法可 以使时间得到改善? 5. 在内排序的过程中, 通常需要对待排序的关键字集合进行多遍扫描。 采用不同排序方法, 会产生不同的中间结果。设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键字按字母 序的升序重新排列,请分别给出对该序列进行冒泡排序,初始步长为 4 的希尔排序,二 路归并排序及以第一个元素为分界元素的快速排序的第一趟扫描的结果,并给出对该序 列作堆排序时初始建堆的结果。 五、算法设计题

-6-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

1. 试写一个判别给定二叉树是否为二叉排序树的算法。(12 分) 2. 求图的中心电的算法。设 V 是有向图 G 的一个顶点,我们把 V 的偏心度定义为:max(从 w 到 v 的最短距离/w 是 g 中所有顶点),如果 v 是有向图 G 中具有最小偏心度的顶点, 则称顶点 v 是 G 的中心点。 (10 分)

-7-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 1999 年数据结构
一、判断题(10 分) 1. 线性数据结构,物理上可以采用顺序连续存储结构,也可以采用链式存储结构。 2. 栈和队列逻辑上是线性结构。 3. 单枝二叉树不是完全二叉树。 4. 输入序列为 a1 a2 a3 a4,利用一个堆栈可以得到输出序列 a1 a4 a2 a3。 5. N 个记录的直接插入排序,对记录关键字的总比较次数,最多为(n+2)(n-1)/2。 二、填空题(10 分) 1.从链式堆栈中弹出一个结点,其操作序列为: 、 、 、 。 2.二叉树中第 i 曾最多有 个结点,深度为 k 的二叉树最多有 个结点。 3.图的存储方式,常用下列 、 、 几种方式。 4.内部排序,常用排序方法有 、 、 、 、 几类。 三、双向非循环链表表头指针为 head,写出将表中值为 x 和 y 的两个结点交换位置的算法。 (15 分)

四、将下图(15 分) 1.用邻接表表示; 2.写出该图在邻接表表示下的广度 优先遍历次序; 3.写出该图的所有拓扑有序序列。

B E A C

F

D 五、给出一组记录关键字: (15 分) 12,8,9,15,7,16,13,4,10,20,11,14 ① 写出用快速排序排序时,第一趟排序结果是 ② 用 shell 排序时,写出排序第一趟排序结果是 ③ 用堆排序时,写出(画出)第一趟排序结果 六、写出根是指针为 BT 的二叉树中,计算左、右子树叶结点个数的算法(即分别统计左、 右子树叶结点个数) (15 分) 七、用 Floyid 算法,求出下图中每对结点尖的最短路径长度。 (16 分)

-8-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

6 A 5 4 2 4 B 2 C 6 3 D

-9-

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2000 年数据结构
一、填空题(30 分) 1. 数据结构课程主要研究数据的 结构、 结构, 并给出一组 及其相应算法, 并评价算法的优劣。 2.输入序列为 ABCDE,通过一个堆栈,不可能得到的输出序列有 、 、 、 等。 3.A、B、C 三结点为线性链表中的相邻结点,p 指针指向 A 结点,写出将 B、C 结果交换 位置的操作序列 、 、 、 、 、 。 4.已知双枝树的高度为 H,求该树最多结点个数为 ,第 H 层最多有 个结点。该 树用具有左、右两个 Link 的结点的链式结构存储时,共有 个 Link 域为空。 5.字符串的快速匹配算法(KMP 算法)中,匹配的模式串右移位数依赖于模式本身,若 K 为模式串字符序号,f(k)为失败函数,当模式串 p=abcab 时,求:f(2)= , f(4)= ,f(5)= 。 6.某二维数组 M(1… m,1… n) ,以列为主行用向量方式存储,写出求元素 M(i,j)的 地址公式 。 7.用结点表示事件,有向边表示活动,权表示活动持续时间的 AOE 网表示工程,从起点 到终点路径长度 的路径称为关键路径,关键活动、关键事件必然处在某条 路径 上。某活动的最早、最迟发生时间 称为关键活动。 8.在快速排序算法中,元素的个数为 n,问平均比较次数的时间复杂度为 ,最坏情 况下为 。堆排序的最坏情况下的时间复杂度为 。 9.在 hash 查找中,关键字为 k1,k2 值 ,而两个 hash 函数值 H(k1) ,H(k2) , 这种现象称为 。 10.环形队列中,起始地址为 100,存放元素最多 100 个,每个元素占 3 个单元,指向当前 第 1 元素的头指针 H=370,问该队列最后一个单元地址号为 ,删除 15 个元素后 H= 。 二、下图为数据流图,弧表示数据流,圆圈表示加工,请用结点表示数据流和加工的链式结 构,描述该数据流图。 (15 分) P2

P1

P3

P5

P4

- 10 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

三、在双枝树中,将数据为 x 的结点,插入数据为 A 的叶结点,作为其右孩子,写出完成 该项操作的非递归算法?在该算法中同时求出该树插入后的高度?(12 分) 四、已知有序表共有 10 个元素,采用折半查找,问找到每个元素的比较次数各为多少? (10 分) 五、给定一组关键字序列:12,8,9,15,7,16,13,4,10,20,11,14。请给出用快速 排序、堆排序、希尔排序(渐减增量序列 q=6,3,2,1)各自的第一趟、第二趟排序 结果(18 分) 。 六、阅读下列关于求无向连通图生成树(支撑树)的说明和流程图,填充流程图中 a—e 框, 使之成为完整的流程图。 (15 分) 说明: 给定的无向连通图结点从 1 开始编号到 n; 该图的邻接矩阵存放在数组 E[1: n,1:n] 中;求出的生成树的边存放在数组:T[1:n-1,1:2]中;生成树的每个结点的先驱结点 存放在数组 p[1:n]中。 例如:无向图的结点为生成树的根,执行该流程图结果为: 3 4

1

2 5

6

T:

1

2

3

4

5

1 2

2 1

2 3

3 4

2 5

5 6

- 11 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

树根号 → u 1 → i i+1 → i a

﹤ i=n ? ≧
u → p[u]

0 → k

1 → v

E[u,v]=1?


v+1→v


P[v]=0?

≠ b v=n?
k+1 → k u → T[k,1] v → T[k,2]



<
d

=

c

1 → i

=
e
i+1 → i

1=n? < ≥ 结束
- 12 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2001 年数据结构
一、填空(15 分) 1. 某顺序存储表中有 90000 个元素,按其关键字升序排序,设对每元素进行查找的概率相 同,且各元素的关键字互不相同,则用顺序查找法时,平均比较次数为 ,最大比 较次数为 . 2. 循环顺序队列中,头指针指向队列中第一个元素,尾指针指向当前队中的最后一个元素, 其判空条件为 ,满条件为 。 3. 倒排文件的主要优点是 。 4. 有关键字系列{3,7,6,9,8,1,4,5,2},进行排序时的最小交换次数为 . 5. 有二维数组 A,行下标范围为 0 到 8,列下标范围为 1 到 5,每个数组元素用相邻的四字 节存储,存储器按字节编址,设数组的基地址为 100,则在行优先时,A[5,3]的第一字节 地址为 ;列优先时,A[2,4]的第一字节地址为 6.设广义表 L=( () , () ) ,则 head(L)是 ;tail(L)是 . 7. 在一棵 m 阶 B+树中, 若在某结点中插入一个新关键字而引起该结点分裂, 则此结点中原 有的关键字的个数是 8. 深度为 k(根层数:1)的完全二叉树至少有 个结点,至多有 个结点。 9. 某二叉树结点的中序序列为 A,B,C,D,E,F,G,后序序列为 B,D,C,A,F,G, E,则该二叉树结点的前序序列为 ,该二叉树转化为森林后,森林中包括 棵树。 二、选择题(16 分) 1. 若长度为 n 的线性表采用顺序存储结构,在其第 i 个位置插入一个新元素的算法的平均 时间复杂度为() 。 (1≤ i≤ n+1) A、O(0) B、O(1) C、O(n) D、O(n?) 2. 利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排 序树以后,查找元素 35 要进行( )元素间的比较。 A、4 次 B、5 次 C、7 次 D、10 次 3. 具有 n 个顶点的有向图最多有( )条边。 A、n B、n(n-1) C、n(n+1) D、n? 4. ( )的遍历仍需要栈的制止。 A、前序线索树 B、中序线索树 C、后序线索树 D、所有线索树 5.依 KMP 算法,字符串“ababaabab”的 next(j)为( ) A、 (0,1,1,1,3,4,1,2,1) B、 (0,1,1,1,4,2,1,3,1) C、 (0,1,2,1,1,4,2,1,1) D、 (0,1,1,2,3,4,2,3,4) 6.栈输入序列为(A,B,C,D) ,不可能得到的输出序列有( ) A、 (A,B,C,D) B、 (D,C,B,A) C、 (A,C,D,B) D、 (C,A,B,D) 7.假定有 k 个关键字互为同义词,若用线性探测法把这 k 个关键字存入散列表中,至少要 进行( )次探测?

- 13 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

A、k-1 B、k C、k+1 D、k(k+1)/2 8.下述( )二叉树满足:从任意结点出发到根的路径上所经过结点序列按关键字有序: A、二叉排序树 B、哈夫曼树 C、AVL 树 D、堆 三、现有 M 个学生参加学校的课程辅修班,因学校对各学科专业要求不一样,辅修科目及 数目各不相同,但每生最多允许辅修 5 门课,共有 N 门课允许辅修,这 N 门课由 K 个 教师主讲,每个教师最多主讲 3 门课。现欲对学生的辅修情况进行管理,请为下列问题 设计存储结构,并画图示意。 (12 分) 1) 若 M=10000,N=30000,K=10000,试设计存储结构使得 a. 能很方便地查询每个学生所辅修的科目、考试成绩及任课教师情况; b. 能很方便地查询每个任课教师的任课情况; c. 能很方便地查询、统计每个科目的认可教师情况; d. 能很方便地统计每一科目的所有辅修学生成绩情况; e. 容易修改某学生的辅修科目、任课教师及考试成绩情况。 2) 若仅考虑某班情况,既只有 5 个学生参加辅修,涉及 7 门课程,3 个教师,又该如 何考虑上述问题。 四、给出一组关键字 T=(12,2,16,30,8,28,4,10,20,6,18) ,希望排序为非递减 序列。试写出: (18 分) 1)分别写出希尔排序(增量为 5,3,2,1)的第一、二趟结束后的状态。 2)快速排序(选第一个记录为枢轴(分隔) )第一趟结束后的状态。 3)堆排序(大顶堆)第一趟、第二趟结束后的状态。 五、考虑下图 G=(V,E) ,其中 V=(A,B,C,D,E,F,G) ; (12 分) 1)从顶点 A 出发,求它的深度优先生成树; 2)从顶点 E 出发,求它的广度优先生成树; 3)根据普里姆(Prim)算法,求它的最小生成树。

A 5 B 6
1

4 C

2
D

3

E 5

3

F 1 G
- 14 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

六、设一单向链表的头指针为 head,链表的记录中包含着整数类型的 key 域,试设计算法, 用最少时间将此链表的记录按照 key 递增的次序进行就地排序 (即仅仅通过修改指针方 式完成排序) 。 (12 分) 七、设分类二叉树中结点的结构为: left data right

其中,left,right 分别给出结点的左右儿子结点的地址,data 类型为整数。已知分类二 叉树根结点地址为 root,且它的所有结点的 data 域之值互不相等。试设计一个算法,加 入 data 域值为 x 的结点,并求出该结点在树中的层次(设根结点的层次数为 1) 。 (15 分)

- 15 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2002 年数据结构
一、填空(20 分) 1.分别采用堆排序、快速排序、插入排序和归并排序对初始状态为递增序列的表排序,最 省时间的是 算法,最费时间的是 算法。 2.在有 n 个顶点的有向图中,每个顶点的度最大可达 。 3.二叉树中叶结点数为 50,仅有一个孩子的结点数为 30,则总结点数为 。 4.已知栈的输入序列为 1,2,3,… ,n,输出序列为 a1,a2,… an,a2=n 的输出序列共 有 种。 5.直接选择排序算法在最好情况下所作的交换元素的次数为 。 6.如果有 n 个顶点的图是一个环,则它有 棵生成树。 7.数组 A[1… 10,-2… 6,2… 8]的元素按行顺序存储,第一个元素的首地址为 100,每个元 素的长度为 3,则元素 A[5,0,7]的存储地址为 。 8.已知二叉树如左图,则: 其中序遍历的序列为 A 其后序遍历的序列为 。 9.设有关键码序列{Q,H,C,Y,W,A, M,S,R,D,F,X},要按照字符的次 序进行排序, 若采用初始步长为 4 的 Shell 排序,则第一趟扫描的结果是 ; 若采用以第一个元素为分界元素的快速 排序法,则第一趟扫描的结果是 。 10.在栈顶指针为 HS 的链栈中,判定栈空 的条件 。 11. 两个串相等的充要条件是 和 。 12.已知一个图的邻接矩阵表示,计算第 i 个结点的入度的方法是 。 J

B

F

C

G

H

D

I

E

K

二、单项选择题(15 分) 1. 若单链表中最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则 采用( )存储方式最节省时间。 A、单链表 B、双向链表 C、单循环链表 D、带头结点的双循环链表 2.在有 n 个叶子结点的 Huffman 树中,其结点总数为( ) A、n B、2n C、2n-1 D、2n+1 3.对于关键字系列{12,13,11,18,60,15,7,18,25,100},用筛选法建堆,必须从

- 16 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

关键字为( )的结点开始。 A、100 B、12 C、60 D、15 4.若某二叉树的前序序列和后序序列正好相反,则该二叉树一定是( )二叉树。 A、空或只有一个结点 B、高度等于其结点树 C、任一结点无左孩子 D、任一结点无右孩子 5.设循环队列中数组的下标范围是 0… m-1,已知其队头指针 front 指向当前队头元素,队 尾指针 rear 指向队尾元素的下一个位置,则当前队列中的元素个数为( ) A、(rear-front+m) mod m B、(rear-front+1) mod m C、rear-front D、rear-front+1 6.下列排序算法中, ( )每一趟都能选出一个元素放在其最终位置少年宫,并且是不稳定 的。 A、快速排序 B、希尔排序 C、直接插入排序 D、直接选择排序 7.已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为 ABC*+DE/-,其前缀形式为 ( ) 。 A、-A+B*C/DE B、-A+B*CD/E C、-+*ABC/DE D、-+A*BC/DE 8.广义表 A=(a,b,(c,d),(e,(f,g))) ,则下面式子的值为( )Head(Tail(Head(Tail(Tail(A))))), 其中 Head(L) ,Tail(L)分别取广义表 L 的表头和表尾。 A、 (g) B、 (d) C、c D、d 9.一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是( ) A、23415 B、54132 B、23145 D、15432 10.数据表中有 10000 个元素,如果仅要求求出其中最大的 10 个元素,则采用()排序算 法最节省时间。 A、堆 B、希尔 C、快速 D、直接选择 11. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点, 则此类二叉树中所包含的结点数至 少为( ) 。 A、2h B、2h-1 C、2h+1 D、h+1 12.在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要( )条边。 A、n B、n+1 C、n-1 D、n/2 13.设 HASH 表长 m=14,HASH 函数为 key MOD 11(MOD 为求模运算) ,在存放完关键 字 15,38,61,84 后,存放关键字 49,若采用线性探测法解决冲突时的地址为( ) 。 A、8 B、3 C、5 D、9 14.非空的循环单链表 head 的尾结点*p 满足( ) A、p->next= =NULL B、p= =NULL C、p->next=head D、p=head 15.在事件网络中关键路径是( )
- 17 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

A、从源点到汇点的最短路径 B、从源点到汇点的最长路径 C、最长的回路 D、最短的回路 三、设有一段正文:CAST,CATS,SAT,AT,A,TASA,其中使用的字符集 set={C,A, S,T}。请用哈夫曼算法设计一套 set 中字符的二进制编码,使上述正文的二进制内部表 示最短,并且采用这种编码时,字符间不用分割符就能识别。要求: (10 分) 1)画出哈夫曼树,并求其 WPL; 2)给出 set 中字符的编码表。 3)将上述正文译成二进制编码。 四、一个连通图表示一个通信网络,如右图所示。其中,顶点表示网络中的通信站点,边 表示网络中的通信线路,则(16 分) 1)从顶点①出发的深度优先生成树; 2)设每条边延迟时间为 a,每中间结点的延迟时间为 b,求从结点①至其它各点中的最 长和最短时间 3) 在原来的图中至少补充几条边, 使其中某一站点失效时整个通信网络仍然保持畅通 4)指出图中哪几个顶点是关结点(即万一它失效则通讯网络发生故障) 1 2

3 4 6 3

5

7 10

9

五、设有序顺序表中的元素依次为 017,094,154,170,275,503,509,512,553,612, 677,765,897,908。试分别画出对其进行顺序查找和折半查找时的判定树,并分别计 算查找成功的平均查找长度(10 分) 。 六、已知有 n 个选手 P1,P2,Pn 参加一项比赛,每对选手之间非胜即负,试设计算法求出 一个选手系列 P1′,P2′,...,Pn′,使得 Pi+1′(1≤i<n) (15 分) 七、试设计一个查找算法 Locate 实现下述要求。设有一个带表头结点的双向链表 L,每个 结点有 4 个数据成员:指向前驱结点的指针 prior,指向后继结点的指针 next,存放数 据的成员 data 和访问频度 freq。 所有结点的 freq 初始时都为 0。 每当在链表上进行一 次 Locate(L,x)操作时,令元素值为 x 的结点的访问频度 freq 加 1,并将该结点前移, 链接到与它的访问频度大于或相等的结点后面, 使的链表中所有结点保持按访问频度递 减的顺序排列,以使访问频度的结点总靠近表头。 (14 分)

- 18 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2003 年数据结构
一、判断题(20 分) 1. 数据元素是数据的基本单位。 2. 在一个没有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链 表的长度无关。 3. 在双向链表中,从当前结点出发可以访问到链表中任意一个结点。 4. 用不带头结点的单链表表示队列,若队头指针指向队头结点,队尾指针指向队尾结点, 则在进入队列操作时,队头和队尾指针都可能要修改。 5. 若采用只设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为 O(1) 。 6. 稀疏矩阵压缩存储后,仍具有随机寸取的功能。 7. 如果某二叉树的先序序列和中序序列相同,则该二叉树中除叶子结点外的所有结点都没 有左子数。 8. 先序线索二叉树中任意结点 x,若 x 无左子树,则 x 的先序直接后继为 x 的右线索所指 的结点。 9. 采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路) 。 10. 若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则一定不存在该图的拓扑有 序序列。 11. 当各边上权值均相等时,广度优先搜索算法可以用来解决单源点最短路径问题。 12. 用邻接矩阵表示图时,矩阵元素的个数只与顶点个数有关,而与边数无关。 13. 如果完全二叉数从根结点开始按层次遍历的输出序列为 1,2,3,4,5,6,7,则该完全二叉树是 二叉排序树。 14. 在非空的平衡二叉树中插入一个结点,原有结点至少一个结点的平衡因子会改变。 15. 直接选择排序的时间复杂度与关键字的初始排序无关。 16. 快速排序在最坏情况下的时间复杂度比堆排序的性能差。 17. 如果某深度大于 2 的二叉树除最下面的两层的结点的度小于 2 外,其他层的结点的度均 为 2,则该二叉树为完全二叉树。 18. n 个结点的无向图,若不允许结点到自身的边,也不允许结点到结点的多重边,则边的 总数为 n(n-1)/2,则该无向图一定是连通图。 19. 由树的二叉链表存储结构可知,树和二叉树之间存在一对一的对应关系。 20. 满二叉树可能不是完全二叉树,完全二叉树也可能不是满二叉树。 二、选择题(20 分) 1.数据结构在计算机内存储器中的表示是指() A、数据结构 B、数据元素之间的关系 C、数据的逻辑结构 D、数据的物理存储结构 2.静态链表中指针表示的是() A、下一个元素的地址 B、内存储器的地址 C、下一个元素在数组中的位置 D、左链或右链指向的元素的地址 3.若长度为 n 的线性表采用顺序存储结构,则在表中第 i 个位置(1≤ i≤ n+1)插入一个新元素 的算法的时间复杂度为() A、O(0) B、O(1) C、O(n) D、O(n? )

- 19 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

4.一个栈的输入序列为 ABCDE,则不可能出现的输出序列为() A、ABCDE B、EDCBA C、CABED D、BADCE 5.数组 A[0… 5][0… 6]的每个元素占 10 个单元,将其按行优先的次序存储在起始地址为 10000 的连续内存单元中,则元素 A[2,3]的地址是() A、10080 B、10090 C、10150 D、10170 6.对二叉树的结点从 1 开始连续编号,要求每个结点的编号大于其左孩子(如果有的话) 的编号,而小于其右孩子(如果有的话)的编号,则可以采用()次序的遍历实现二叉树 的结点编号。 () A、先序 B、中序 C、后序 D、层次遍历 7.树的后根遍历序列等同于该树对应的二叉树的() A、先序 B、中序 C、后序 D、层次遍历 8.某二叉树结点的中序序列为 BDAECF,后序序列为 DBEFCA,则该二叉树对应的森林包 括()棵树。 A、1 B、2 C、3 D、4 9.关键路径是 AOE 网中() A、从始点到终点的最短路径 B、从始点到终点的最长路径 C、从始点到终点的边数最多的路径 D、从始点到终点的边数最少的路径 10.在有向图的邻接表存储表示中,顶点 V 在链表结点中出现的次数是() A、顶点 V 的入度 B、顶点 V 的出度 C、顶点 V 的度 D、依附于顶点 V 的边的数目 11.下列二叉排序树中查找效率最高的是() A、平衡二叉数 B、二叉查找树 C、没有左子树的二叉排序树 D、没有右子树的二叉排序树 12.若在线性表中采用折半查找法查找元素,则该线性表应该() A、元素按值有序 B、元素按值有序,且采用顺序存储结构 C、元素按值有序,且采用链式存储结构 D、采用顺序存储结构 13.下面在关于 B-树和 B+树的叙述中,不正确的是() A、它们都是平衡的多分树 B、它们都可用于文件的索引结构 C、它们都能有效地支持随机检索 D、它们都能有效地支持顺序检索 14.既希望查找性能高,又希望线性表能够动态变化的查找方法是() A、顺序查找 B、索引顺序查找 C、折半查找 D、哈希查找 15.设有 10000 个无序记录,希望用最快速度从中选择前 10 个关键字最小的记录,在以下 排序方法中采用哪一种最好() A、快速排序 B、希尔排序 C、直接插入排序 D、简单选择排序 16.若需在 O(n log n)的时间内时间内对数组的排序,且要求排序是稳定的,则可选择() A、快速排序 B、基数排序 C、堆排序 D、归并排序
- 20 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

17.在有 n 个叶子结点的哈夫曼树中,非叶子结点的总数是() A、n-1 B、n C、2n-1 D、2n 18. 有 n 个结点的完全二叉树采用顺序存储结构时, 从根结点开始对其按曾系顺序进行编号 (设根结点编号为 1) ,下列说法错误的是() A、当 1≤ i≤ n/2 时,结点 i 的左子女是结点 2i,否则结点 i 没有左子女。 B、当 1≤ i≤ (n-1)/2 时,结点 i 的右子女是结点 2i+1,否则结点 i 没有右子女。 C、当 1≤ i≤ n 时,结点 i 的父母是结点└ i/2 ┘. D、当 i 为偶数且 1<i<n 时,结点 i 的右兄弟是结点 i+1,否则结点 i 没有右兄弟。 19.下列有关图的说法错误的是() A、在有向图中,出度为 0 的结点称为叶子。 B、用邻接矩阵表示图,容易判断任意两个结点之间是否有边相连,并求得各结点的度。 C、按深度方向遍历图和先根次序遍历树类似,得到的结果是唯一的。 D、若有向图 G 中从结点 V i 到结点 V j 有一条路径,则在图 G 的结点的线性序列中结点 V i 必在结点 V j 之前的话,则称为一个拓扑序列。 20.下面有关在中序线索树中找指定结点的先序后继的问题时,说法错误的是() A、当指定结点不是树叶时,若指定结点有左子女,则左子女是它的先序后继,若指定结 点没有左子女,则右子女是它的先序后继。 B、当指定结点是树叶时,若指定结点是“某结点 X”的左子树中按先序遍历列出的最后 一个结点,且该结点 X 又是右子女,则指定结点的先序后继就是该结点 X 的右子女。 C、当指定结点是树叶是,若指定结点虽然是“某结点 X”的左子树中按先序遍历列出的 最后一个结点,但该结点 X 没有右子女,则指定结点没有先序后继。 D、当指定结点是树叶时,若指定结点不是任何结点的左子树中按先序遍历列出的最后一 个结点,则指定结点先序后继为根结点。 三、填空题(20 分) 1.数据的逻辑结构主要有四种: ( ) ,线性结构,树型结构和图状结构。 2.线性链表不能随机存取元素的原因是:要得到元素的存储地址,必须( ) 。 3.判断带头结点的双向循环链表 L 是否为空的条件是( ) 。 4.已知一循环队列的存储空间为[m… n],其中 n>m,队头和队尾指针分别为 front 和 rear, 则此循环队列判满的条件是( ) 。 5.设广义表 L=( () , () ) ,则 Tail(L)是( ) 。 6.已知二叉树的先序序列为 ABDCE,中序序列为 BDACE,则其后序序列为( ) 。 7.一般树可转换为二叉树是基于树的( )表示法。 8.从概念上将,树和二叉树是两种不同的数据结构,将树转换为二叉树的两个基本目的是: (1) ( ) ; (2)可以将树的基本操作转化为二叉树的基本操作。 9.N 个顶点的无向连通图用邻接矩阵表示时,该矩阵至少有( )个非零元素。 10.在 n 个顶点的非空无向图中,最多有( )个连通分量。 11.哈希表与其它结构的查找表的区别是:哈希表的查找有哈希函数和( )确定记录的 存储位置,而其它结构的查找表通过比较确定。 12.N 个结点的用于折半查找的判定树,表示查找失败的外部结点共有( )个。 13.在使用索引顺序查找(分块查找)时,除表本身外,尚需建立一个索引表,用来存放每 一数据块中最大的( )和该块的起始地址。 14.哈希函数有一个共同性质,即为了( ) ,函数值应按相同的概率取其值域中的每
- 21 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

一个值。 15.在一棵 m 阶B- 树中,若在某结点中插入一个新的关键字而引起该结点分裂,则此结 点中原有的子树的个数为( ) 。 16.由森林和二叉树之间的转换规则可知,根据森林的先序和中序遍历的定义,可知森林的 先序和中序与其对应的二叉树的( )对应。 17.长度为零的串称为( ) 。 18.在稀疏矩阵的三元组顺序表存储结构中,除表示非零元的三元组表以外,还需要表示矩 阵的行数、列数和( ) 。 19.如果待排序记录的数量很大,以致于内存一次不能容纳全部记录,在待排序过程中尚需 对外存进行访问,这样的排序称为( ) 。 20.设图中顶点数为 n,Floyd 提出的所有点对键最短路径算法的时间复杂度为( ) 。 四、试编写在带头结点的双向链表 L 第 i 个位置之后插入元素 x 的算法。要求给出双向链表 L 的结点结构的描述,算法基本思想及算法。 (10 分) 五、一个双端队列 Q 是限定在线性表的两端(LEFT 端和 RIGHT 端)都可以进行插入和删 除操作的线性表。队空的条件是 LEFT=RIGHT。若采用顺序存储结构表示双端队列。 (1)定义双端队列的存储结构; (2)给出在指定端 L(代表左端)和 R(代表右端) 进行插入(QueueInsert)和删除(QueueDelete)操作的基本思想和算法描述。要求: 当队满是,正好有一个元素空间没有存放元素;插入和删除元素时不允许移动元素。设 L 和 R 是枚举类型 QueueOperationTag 中的两个枚举常量。 (10 分) 六、设主串 S 为“aababcaabbcabbaabc” ,模式串 T 为“aabbcabbaa” 。 (10 分) 1.计算模式串 T 的 next 函数值; 2.不写出算法,只画出利用 KMP 算法进行模式匹配时每一趟的匹配过程。 七、设二叉树采用二叉链表存储,试编写按层次遍历输出二叉树结点的算法(为简单起见, 设二叉树的数据元素为整数) 。要求写出二叉树结点的存储结构、算法的基本思想及算 法。 (10 分) 八、已知深度为 h 的二叉树,以一维数组 BT[0… 2h -2]作为其存储结构。试编写一算法。求 该二叉树中叶子结点的个数。为简单起见,设二叉树中元素结点为非负整数。要求写出 算法基本思想及相应的算法。 (10 分) 九、以邻接表作存储结构实现从源点到其余各顶点的最短路径的 Dijkstra 算法。要求给出图 的邻接表存储结构、算法的基本思想及算法。 (20 分) 十、待排序关键字序列为{20,30,70,40,80,10,90,60,50},试分别采用直接插入排 序、堆排序、2-路归并排序和快速排序,将之排列成递增有序序列。要求给出每一种排 序过程的图示。不要求给出排序算法。快速排序时设选择第一个记录为枢轴。 (20 分)

- 22 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2004 年数据结构
一、填空题(10 分) 1. 链表是一种采用( )存储结构的线性表。 A、顺序 B、星式 C、链式 D、网状 2.广义表( a, (a,b) , (d,e) , ( (a) ,c) )长度是( ) A、3 B、4 C、5 D、6 3.一个有 28 条边的非连通无向图至少有( )个顶点。 A、7 B、8 C、9 D、10 4.关键字部分有序时,最佳内部排序法是( ) A、直接插入 B、冒泡 C、简单选择 D、归并 5.Hash 函数应当以( )取其值域的每个值。 A、最大概率 B、最小概率 C、平均概率 D、等概率 二、概念及计算题(77 分) 1. 给定权集:3,4,11,2,16,19。试构造对应的 Huffman 树,并求该树的带权外部路 径长度和与每个权值所对应字符的编码。 2. 试给出下列二叉树的中序线索二叉树。

3. 求下图的相邻矩阵表示和一棵最小生成树,与边相关的数字为边的权值。

4. 已知主串为 “adbadabbaabadabbadada” , 模式串为 “adabbadada” , 求模式串的 next 和 nextval 值,并画出 KMP 算法匹配的全过程。

- 23 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

5. 关键码值序列{25,23,16,68,94,72,71,73},如果采用堆排序,它是否为堆?如 果不是堆,请把其调整成堆。 6. 用 Dijkstra 算法求出下列带权有向图中 a 到各顶点的最短路径,并给出运算过程中 dist 向量的变化状况。

7. 已知有序表的 12 个关键字为 A,B,… ,L,其相应的权值分别为 8,2,3,4,9,3, 2,6,7,1,1,4,试构造次优查找树并计算它的 PH 值。 8. 设 p=11,用除留余数法求关键字{39,13,33,26,138,44,24}的哈希地址。用链地 址法处理冲突。并给出最后的哈希表。 9. 给出将如图所示的 5 阶 B- 树中关键字 47 删去后的 B- 树。

10、假定待排序文件的关键字为{288,371,260,531,287,235,056,299,018,023}, 采用链式存贮。试给出上述关键字基数排序算法的排序过程。 11、设一次输入输出操作的物理块大小为 150,每次可对 750 个记录进行内部排序,那么, 对含有 150000 个记录的磁盘文件进行 4-路平衡归并排序时,试计算需进行输入输出操 作次数。 三、算法题(63 分) 1. 试编写将两个有序链表并为一个有序链表的算法。 2. 假设在二叉链表的结点中增设两个域: parent 域以指示其双亲结点; flag 域 (取值为 0… 2) 以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以次存储结构编 写不用栈进行后序遍历的递推形式的算法。 3. 试编写折半查找的递归算法。 4. 采用三元组顺序表存储表示,试编写求稀疏矩阵的快速转置算法。 5. 给定一棵用链表表示的二叉树,其根结点为 root,试写出求二叉树的深度的算法。 6. 在一个含有 n 个顶点、边上带权值的图中,如何选择一个点,才能使该点到离该点最远 的点之间的边的权值和最小?试设计一个算法解决之,并举例说明。 (13 分)

- 24 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2005 年数据结构
一、单项选择题(20 分) 1、在数据结构中,从逻辑上可以将之分为( ) A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、内部结构和外部结构 D、线性结构和非线性结构 2、一个栈的入栈序列为 A,B,C,D,E,则栈的不可能的出栈序列是( ) A、ABCDE B、EDCBA C、DECBA D、DCEAB 3、设有两个串 S1 和 S2,求 S2 在 S1 中首次出现的位置的运算称作( ) 。 A、求子串 B、判断是否相等 C、模型匹配 D、连接 4、下列排序算法中, ( )算法可能会出现下面的情况:初始数据有序时,花费的时间反而 最多。 A、快速排序 B、堆排序 C、希尔排序 C、冒泡排序 5、对于一个具有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为( ) 。 2 2 A、(n-1) B、n C、n-1 D、n 6、下述几种排序方法中,要求内存量最大的是( ) 。 A、归并排序 B、快速排序 C、插入排序 D、选择排序 7、一棵非空的二叉树的先序序列和后序序列正好相反,则该二叉树一定满足( ) 。 A、其中任意一个结点均无左孩子 B、其中任意一个结点均无右孩子 C、其中只有一个叶子结点 D、其中度为 2 的结点最多为一个 8、求最短路径的 FLOYD 算法的时间复杂度为( ) 。 A、O(n) B、O(n+e) 2 C、O(n ) D、O(n3) 9、对矩阵压缩存储是为了( ) 。 A、方便运算 B、方便存储 C、提高运算速度 D、减少存储空间 10、数组通常具有的两种基本操作是( ) 。 A、查找和修改 B、查找和索引 C、索引和修改 D、建立和删除 二、简单填空题(20 分) 1、将一棵有 100 个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行 编号,根结点的编号为 0,则编号为 50 的结点的右孩子编号为( ) 。 2、广义表(A,B,C,D)的表尾是( ) 。 3、 在一棵二叉树中, 度为 0 的结点即叶子结点的个数为 n0, 度为 2 的结点的个数为 n2, n0 与 n2 之间存在的关系为( ) 。 4、n 个顶点的连通图至少有( )条边。 5、在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是( ) 。
- 25 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

6、队列的特性是( ) 。 7、直接选择排序算法在最好情况下所做的交换元素的次数为( ) 。 8、若以{4,5,6,7,8}为叶子结点的树值构造哈夫曼树,则其带权路径长度是( 9、如果具有 n 个顶点的图是一个环,则它有( )棵生成树。 10、设根的层次为 1,则有 64 个结点的完全二叉树的深度为( ) 。

) 。

三、判断正误题(10 分) 1、串长度是指串中不同字符的个数。 2、二叉树只能采用二叉链表来存储。 3、二叉树按照某种顺序线索化之后, 任一个结点均有指向其前趋结点或者后继结点的线索。 4、图 G 的一棵最小代价生成树的代价未必小于图 G 的其它任何一棵生成树的代价。 5、在链队列中,即使不设置尾指针也能进行入队操作。 四、简单问答题(60 分) 1、什么是抽象数据类型?有何特点?试以一种常用的抽象数据类型举例说明。 2、给出带头结点的双向链表的结点的数据类型描述,作图表示出在双向链表中插入一个结 点的各种情况。设双向链表按结点的数据域有序排列。 3、编写逆向输出不带头结点的单向链表中数据域的递归算法。设表中有 4 个结点,从表头 至表尾其数据域分别为 10,30,20,40,作图表示出该算法的执行过程。设该链表的结 点的数据类型的名称为 list,结点的数据域和指针的名称分别为 data 和 next,不必写出 list 的定义。 4、作图表示出向空的二叉查找树(二叉排序树)依次插入数据域为 10,50,30,90,40 这五个数据元素的过程,然后分别给出序、中序、后序遍历该二叉树的输出结果。 6、设开放定址哈希表的表长为 10,表中元素的编号从 0 到 9,设初始时表为空。作图表示 出采用二次探测处理冲突时,将关键字 89,18,49,58,69 依次插入到该表中的过程。 同时要求对每一步给出简要的说明。 [说明]试卷中无第 5 小题 五、算法设计题(40 分) 1、有关堆排序: (1)给出堆的定义及其数据结构定义; (2)给出堆排序算法的基本思想, 并以图例予以说明(要求不少于 6 个待排序元素) ; (3)用伪语言描述该算法; (4)给出 算法在最坏情况下的时间复杂性分析。 2、AVL 树是任一个结点的左、右子树高度相差不超过 1 的二叉查找树。设 AVL 树的结点 的数据及部分操作的原型定义如下: Struct AvlNode; typedef struct AvlNode *Position; typedef struct AvlNode *Avltree; AvlTree MakeEmpty (AvlTree T); AvlTree Insert (ElementType X, AvlTree T); AvlTree Delete (ElementTypeX, AvlTreeT); ……
- 26 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

Struct AvlNode{ Element Type Element; AvlTree Left; AvlTree Right; Int Height; }; 其中,Heitht 表示结点在该 AVL 树中的高度。设空树的高度的 0;只有一个结点的 AVL 树 的高度 1,且假设下面的操作用于取得某一结点在树中的高度值: Static int Height(Position P) { If (P=NULL) Return 0; Else Return P->Height; } 本题要求: (1)由于向 AVL 树中插入一个结点时可能需要做平衡化处理,试描述各种不同 情形的平衡化处理的基本思想,要求辅以图形化说明; (2)使用伪代码编写上述原型中的插 入操作 Insert 的递归算法, 如果该算法中需要调用某些子算法, 且某些子算法具有对称或者 说镜像的特性,则这样的子算法只需要书写一个。

- 27 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

中南大学 2006 年数据结构
一、判断题(10分) 1.抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 2.循环链表的特点是表中最后一个结点的指针域指向头结点(如无头结点则指向表中第一 元结点),整个链表形成一个环。 3.设主串长度为n,模式串长度为m,则子串定函数的时间复杂度在最坏的情况下为O(n*m)。 因此子串定位函数没有实际的使用价值。 4.线性表可以看成是广义表的特例。如果广义表中的每个元素都是原子,则广义表便成为 线性表。 5.由二叉树的先序遍历序列和后序遍历序列并不能唯一确定这棵树,因为不知道树的根结 点是哪一个。 6.二叉树采取顺序存储结构时,总是以先序遍历顺序存储结点。 7.具有n个顶点的强连通图至少由n条弧。 8.具有n个顶点的有向图中的顶点的最大度为n-1。 9.顺序查找只适用于顺序存储表示的线性表,而不适用于链接存储表示的线性表。 10.在直接选择排序中,关键字比较次数与记录的初始排列顺序无关。
二、单项选择题(10分) 1.算法指的是( ) A、使用某种程序设计语言编写的计算机程序 B、解决问题的某种计算方法 C、某种常用的查找或排序方法 D、解决问题的有限操作序列 2.线性表是( ) A、一个有限序列,可以为空 C、一个有限序列,不能为空 A 、Head(Tail(LS)) C 、Head(Tail(Head(Tail(LS)))) A、4 C、6 调用该算法( )次 A、1 C、k 三、概念填空题(10分) 1.下面程序段的时间复杂度为________。 for(i=1;i<=n;i++){ x++; for(j=0;j<=(3*n);j++)
- 28 -

B、一个无限序列,可以为空 D、一个无限序列,不能为空 B、Tail(Head(LS)) D、Head(Tail(Tail(Head(LS)))) B、5 D、7

3.已知广义表LS=((a,b)),(c,d,e)),则运用Head和Tail函数取出LS中原子d的运算是( )

4.假设一棵三叉树的结点数为50,则他的最小高度为( )

5.已知一个图中包含k个连通分量。如果按照深度优先搜索算法(DFS)遍历所有顶点,则必须 B、k-1 D 、k+1

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

y++; } 2.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点,则它必定也是该子树 的_________序列中的最后一个结点。 3.无向图中的一个极大连通子图称为它的一个________。 4._____________排序不需要进行记录关键字间的比较。 5.一个索引文件中的索引都是按照__________有序排列的。 四、算法填空题(10分) 1.设带头结点的双向链表的存储结构如下: typedef struct DuLNode{ *prior; *next; ElemType data; Struct DuLNode Struct DuLNode }DuLNode,*DuLinkList; 设头结点的指针为Head,并设其中有一个结点的指针为p。下面的算法将p与其左边(前面)的 一个结点进行交换,请补充完整。 Status swap(DuLNode *Head,*p) { DuLNode *p; q=p->prior; if(q=Head){ printf(“ Cannnot swap!\n” ); return FALSE; } /*删除p结点*/ q->next=p->next; if(p->next!=NULL) ______________。 /*把p插入到q的左边(前面)*/ q->prior->next=p; p->prior=_______________, p->next=________________; q->prior=p; /*至此成功的做了交换*/ return TRUE; } 2、下面是稀疏矩阵的三元组顺序表存储结构描述; #define MAXSIZE typedef struct { 100 //最大非零元素个数 /*p结点为链表中第一个元素结点,不能进行交换*/

- 29 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

int

i,

j; e;

// 行下标和列下标

ElemType }Triple;

typedef struct { Triple data[MAXSIZE+1]; //约定一行序为主 //非零三元组表,data[0]未用 int mu,nu,tu; //矩阵的行数,列数和非零元个数 }TSMatrix; 下面的算法将稀疏矩阵M转置后存储在稀疏矩阵T中,请补充完整。 Status TransposeSMatrix(TSMatrix M,TSMatrix &T){ T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; If(______________){ q=1; for(col=1;col<=M.nu;++col) for(p=1;p<=M.tu;++p) if(M.data[p].j=col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; __________________ } } return OK; }//TransposeMatrix 五、简单应用(20*2) 1.有关树的存储结构。树的三种常用的存储结构是双亲表示法,孩子链表表示发法,以及孩 子兄弟表示法(又称二叉链表表示法)。试使用某种类程序设计语言如C语言分别描述这几 种存储结构,分别做图表示出下图所示的树的存储表示,并且分别指出这几种存储结构的 主要优缺点。

- 30 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

A

B

C

D

E

F

G

H

2.有关图的广度优先搜索算法(BSF)。设图采用邻接表表示,并且设每个顶点对应的单向链表 中的结点按照其邻接点域的植的升序排列。 试使用某种类程序设计语言如类C语言描述图的邻 接表存储结构, 然后作图表示出下图所示的无向图从结点A开始做广度搜索时的队列的变化情 况及相应的结点访问(输出)的顺序。

A

X

H E

Y

G

P

M

J

六、简单证明题(30分) 1.证明:已知一棵度为K的树中有n1个度为1的结点,n2个度为2的结点,……,nk个度为k的结 点, k 则该树中叶子结点的个数n0=1+∑(i-1)ni。 i=1 2.证明:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最 小权值(代价)的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)最小生成树。 七、算法设计题(40分) 1.设计有关二叉查找树(Binary Search Tree)的算法。试用某种类程序设计语言如C语言描述
- 31 -

追求卓越,挑战极限,从绝望中寻找希望,人生终将辉煌!

二叉查找树的存储结构并且简要说明二叉查找树的特点,然后使用自然语言分别描述在二叉 查找树中插入一个结点和删除一个结点的基本思想(要求辅以图说明),最后使用某种类程 序设计语言分别写出二叉查找树中的插入算法和删除算法。 2.设计有关优先级队列(Priority Queue)的入队列和出队列算法。优先级队列与一般队列的 区别在于优先队列中的每个元素有一个域用于标志该数据元素相对于队列中其他数据元素的 优先级,入队列时优先级高的元素会被被排列在优先级底的元素的“ 前面” ,出队列时最高级 别的元素最先从队列中出来。堆(heap)可用于高效实现优先级队列。试用某种类程序设计 语言如类C语言描述堆表示的优先级队列这种存储结并说明堆的主要特点, 然后使用自然语言 分别描述基于堆的优先级队列的入队列和出队列的算法的基本思想(要求辅以图示说明), 最后使用某种类程序设计语言分别写入入队算法和出队算法。

- 32 -


更多相关文章:

非常超级学习网 fccjxxw.com

copyright ©right 2010-2021。
非常超级学习网内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图