2008年秋数据结构试题

《2008年秋数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试题：班号：姓名：一、名词解释（每名词3分，共15分）1、ADT2、线性表3、满二叉树4、拓扑排序5、HASH表第7页（共7页）试题：班号：姓名：二、填空题（每空0.5分，共15分）1、线性表的存储结构包括(1)____________、(2)___________和(3)____________三种方式。树的存储结构可归纳为(4)____________、(5)___________和(6)____________三种方法。图的存储结构包括(7)___________和(8)_____________两种方式。2、(9)_________是一种特殊形式的线性表

2、，对于它，所有的(10)__________和(11)__________操作都在表的一端进行。(12)_________是另一种形式的线性表，对于它，所有的(13)___________操作在表的一端进行，而(14)____________操作则在表的另一端进行。3、对无向图进行先深搜索的结果，把图中所有边分成(15)__________和(16)__________两类。(15)从先深编号(17)___________的结点指向先深编号(18)__________的结点，(16)从先深编号(19)___________的结点指向先深编号(20)_______

3、____的结点。而对有向图进行先深搜索和先深编号形成先深生成森林，图中所有边被分成(21)___________、(22)___________、(23)_________和（24）_____________四类。4、在带权的有向图中，用结点表示（25）____________，边表示（26）__________，（27）____________表示活动所持续的时间，把这样的有向图关于边的活动网，简称AOE网。5、磁盘文件的归并排序主要解决以下三个方面的问题，以此提高归并的效率。(28）______________________________________

4、__________；(29)________________________________________________；(30)________________________________________________；三、简要回答下列问题（每问题5分，共40分）1、设二叉树中度为1的结点数为0，试证明该二叉树的总分支数为2(n0-1)，其中，n0为度为0（叶子）结点的数目。第7页（共7页）试题：班号：姓名：1、已知图的存储结构，给出图的深度优先（DFS）和广度优先（BFS）序列。1∧ABCDEFG∧244∧2∧13∧6∧5∧01234563、下面

5、哪一个方法可以判断出一个有向图中是否有环（回路），为什么？    (1)深度优先遍历，(2)拓朴排序，(3)求最短路径，(4)求关键路径4、试求按关键字序列（12，1，4，3，7，8，1O，2）插入生成的二叉排序树和平衡二叉树。5、求最小生成树第7页（共7页）试题：班号：姓名：1、假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27，写出a,b,c,d,e,f的Huffman（哈夫曼）编码。7、一棵二叉树的先序和中序序列分别如下，画出该二叉树。先序：ABCDEFGHIJ中序：CBEDAGHFJI8、求单源最短路

6、径，设源点为A,顶点A-E依次编号为1-5。步骤集合SwD[2](B)D[3](C)D[4](D)D[5](E)初态{1}1234第7页（共7页）试题：班号：姓名：5四、算法设计（共30分）1、已知任意排列的线性链表，结点的数据类型为整形，表头结点为Head。设计算法实现链表就地排序，重新整理该链表为升序序列的链表。（此题8分）要求：给出结点类型定义，假设链表已建立。第7页（共7页）试题：班号：姓名：已知二叉树的存储结构为二叉链表，设计算法实现二叉树按层序遍历，即从第一层到最后一层，每层从左到右顺序输出二叉树中的每个结点，同时给出每个结点所在层号及二叉树的高度。

7、（此题10分）第7页（共7页）试题：班号：姓名：3、自定义图的邻接表存储结构，并在此结构上实现计算每个顶点入度和出度的算法。要求：（1）给出结构类型定义，并进行简要说明；（2）结构类型中有存放每个顶点的入度和出度的空间；（2）实现计算每个顶点入度和出度的算法；注：假设按照你所定义结构的邻接表已经存在，不需要实现建立邻接表的算法。（此题12分）第7页（共7页）