数据结构试题2009秋本科A

1、一 填空题（共20分，每空1分）1设单链表的结点结构为（data,next），next为指针域。已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需执行一下语句：（ py-next = px-next ；）（ px-next = py ）。2设无向图G的顶点数为n，图G最少有（ n-1 ）边；最多有（n(n-1)/2 ）边。若G为有向图，有n个顶点，则图G最少有（ n-1）边；最多有（n(n-1) ）边。3设有一空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是（ 5,

2、4,1 ）。4由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（ ）5由a，b，c三个结点构成的二叉树，共有（ 5 ）种不同的结构。6在线性表的散列存储中，处理冲突有（ ）和（ ）方法。7在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ 6 ），在整个排序过程中共需进行（ 8 ）趟就可以将排序完成。8数据结构是研究数据的（ ）和（）以及它们之间的相互关系。9. 散列法要解决的两个关键问题是（ 散列函数 ）和（ 冲突 ）。10.外部排序需要考虑的三个关键问题分别是（多路归并以减少归并次数）、（并行操

3、作的缓冲区处理尽量使输入与输出与CPU工作重叠）和（初始并归段的生成）。二判断题（对的填，错的填，共10分，每题1分）1在线性结构中，每个结点都有一个直接前驱和一个直接后继。（ ）2在链式存储的栈的头部必须要设头结点。（ ）3在二叉树中插入结点，则该项二叉树便不再是二叉树。（ ）4由二叉树结点的先序序列和后序序列可以唯一确定一棵二叉树。（ ）5树的父链表示就是用数组表示树的存储结构。（ ）6任何二叉树都唯一对应一个森林，反之亦然。（ ）7顺序存储方式只能用于存储线性结构。( )8用循环链表作为存储结构的队列就是循环队列。( )9算法分析的目的是分析算法的易读性（ ）。10一组记录的关键字为（4

4、6,79,56,38,40,84）,则利用快速排序的方法，以第一个记录为基准元素得到的一次划分结果为40,38,46,56,79,84（ ）。三选择题（共10分，每题1分）1快速分类在_的情况下不利于发挥其长处。A. 待分类的数据量太大 B. 待分类的数据相同值过多C. 待分类的数据已基本有序 D. 待分类的数据值差过大.2已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多为 。A39 B52 C111 D1193设森林中有三棵树，第一、第二和第三棵树中的结点个数分别为m1、m2和m3。那么在由该森林转化成二叉树中根结点的右子树上的结点个数是 。Am1+m2

5、Bm2+m3 Cm3+m1 Dm1+m2+m34 设结点x和y是二叉树中任意的两个结点。在该二叉树的前序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x和y的关系是 。Ax是y的左兄弟 Bx是y的右兄弟 Cx是y的祖先 Dx是y的后裔5采用邻接表存储的图的广度优先遍历类似于二叉树的A先序遍历 B中序遍历 C后序遍历 D层次遍历6使用DFS算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是 。 A逆拓扑有序 B拓扑有序 C无序的 D都不是7散列函数有共同的性质，即函数值应当以 概率取其值域的每一个值。A最大 B最小 C平均 D同等8对长度为10的顺序表进行查

6、找，若查找前面5个元素的概率相同，均为1/8。查找后面5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为 。 A5.5 B5 C39/8 D4/39若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序方法只能是 。A起泡排序 B插入排序 C选择排序 D二路归并排序10堆是一种有用的数据结构，例如排序码序列 就是一个堆。A16，72，31，23，94，53 B94，53，31，72，16，23C16，53，23，94，31，72 D16，31，23，94，53，72四、简答题（共20分，每题5分 ）1什么是线性表？线

7、性表的两种存储结构(顺序存储结构和链接存储结构)各有哪些优缺点?2输入23, 25, 28, 10, 9, 16, 12, 18, 13, 20，给出构造平衡二叉树的过程。3已知下图所示的无向图，试画出（1）以D为搜索起点的先深生成树；（2）以D为搜索起点的先广生成树。4有一份电文中共使用五个字符:a，b，c，d，e，它们的出现频率依次为8，14，10，4，18，请构造出相应的哈夫曼(Huffman)树(约定左子树根结点的权小于等于右子树根结点的权),求出每个字符的哈夫曼编码。五综合应用题（共40分）1已知一个带表头结点的单链表，结点的结构为（data,link）。假设该链表只给出了表头指针l

8、ist，在不改变链表的前提下请设计一个尽可能有效的算法，查找链表中倒数第k个位置上的结点（k为正数）。若查找成功，算法输出该结点的域的值，并返回1，否则只返回0.要求：（1）描述该算法的基本思想；（2）描述该算法的详细实现步骤；（3）根据算法的基本设计思想和详细实现步骤，采用程序设计语言描述算法，关键之处请给出简要注释。（10分）2. 给出二叉树的数据结构定义，设计算法，实现二叉树的层序遍历（可以使用书中定义的ADT操作）。（10分）3.试设计一个算法， 判断一个无向图G是否为一棵树。若是一棵树，则算法返回1，否则返回0。(10分)4设顺序表中的元素依次为017，094，154，170，275

9、，503，509，512，553，612，677，765，897，908。试画出对其进行折半查找时的判定树，并计算查找成功的平均查找长度和查找不成功的平均查找长度。（10分）一、名词解释（每名词3分，共15分）1、ADTADT包括数据元素，数据关系以及相关操作2、线性表线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。3、满二叉树：除叶节点外其余节点都有两个孩子节点的二叉树4、拓扑排序将无环路有向图排成一个线性序列，使得当从定点i到j存在一条边时，则在线性序列中将i排在j的前面5、HASH表根据关键码

10、直接访问的数据结构。也就是说它通过将关键码值映射到一个表中的一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表二、填空题（每空0.5分，共15分）1、 线性表的存储结构包括(1)_静态存储_、(2)动态存储和(3) _静态链表三种方式。树的存储结构可归纳为(4)双亲表示法、(5)孩子表示法_和(6)左右链表示法三种方法。图的存储结构包括(7)邻接矩阵和(8)邻接链表_两种方式。2、 (9)栈是一种特殊形式的线性表，对于它，所有的(10)插入和(11删除操作都在表的一端进行。(12)队列是另一种形式的线性表，对于它，所有的(13)_删除操作在表的一端进行，而(

11、14)_插入操作则在表的另一端进行。3、 对无向图进行先深搜索的结果，把图中所有边分成(15)_和(16)_两类。(15)从先深编号(17)_的结点指向先深编号(18)_的结点，(16)从先深编号(19)_的结点指向先深编号(20)_的结点。而对有向图进行先深搜索和先深编号形成先深生成森林，图中所有边被分成(21)_、(22)_、(23)_和（24）_四类。4、 在带权的有向图中，用结点表示（25）_事件，边表示（26）_活动，（27）边上的权值表示活动所持续的时间，把这样的有向图关于边的活动网，简称AOE网。5、 磁盘文件的归并排序主要解决以下三个方面的问题，以此提高归并的效率。(28）多路

12、归并以减少归并次； (29)并行操作的缓存区处理使输入输出尽可能的与CPU工作重叠； (30)初始归并段的生成_；三、简要回答下列问题（每问题5分，共40分）1、 设二叉树中度为1的结点数为0，试证明该二叉树的总分支数为2(n0-1)，其中，n0为度为0（叶子）结点的数目。2、 已知图的存储结构，给出图的深度优先（DFS）和广度优先（BFS）序列。1ABCDEFG244213650123456 3、下面哪一个方法可以判断出一个有向图中是否有环（回路），为什么？ (1)深度优先遍历，(2)拓朴排序，(3)求最短路径，(4)求关键路径 4、 试求按关键字序列（12，1，4，3，7，8，1O，2）插

13、入生成的二叉排序树和平衡二叉树。5、求最小生成树6、 假设字符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、一棵二叉树的先序和中序序列分别如下，画出该二叉树。 先序： A B C D E F G H I J 中序： C B E D A G H F J I8、 求单源最短路径，设源点为A, 顶点A-E依次编号为1-5。步骤集合SwD2(B)D3(C)D4(D)D5(E)初态112345四、算法设计（共30分）1、 已知任意排列的线性链表，结点的数据类型为整形，表头结点为Head。设

14、计算法实现链表就地排序，重新整理该链表为升序序列的链表。（此题8分）要求：给出结点类型定义，假设链表已建立。2、 已知二叉树的存储结构为二叉链表，设计算法实现二叉树按层序遍历，即从第一层到最后一层，每层从左到右顺序输出二叉树中的每个结点，同时给出每个结点所在层号及二叉树的高度。（此题10分）3、自定义图的邻接表存储结构，并在此结构上实现计算每个顶点入度和出度的算法。 要求：（1）给出结构类型定义，并进行简要说明； （2）结构类型中有存放每个顶点的入度和出度的空间； （2）实现计算每个顶点入度和出度的算法； 注：假设按照你所定义结构的邻接表已经存在，不需要实现建立邻接表的算法。 （此题12分）

15、一、 名词总结：ADT：抽象数据型是一个数学模型和在该模型上定义的操作的集合线性表： 线性表是由n(n0)个相同类型的元素组成的有序集合。栈：线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。是限定只在表尾进行插入和删除操作的线性表。栈又称为后进先出的线性表。队列：将线性表的插入和删除操作分别限制在表的两端进行，和栈相反，队列是一种先进先出的线性表。串：线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。 广义表：由零个原子，或若干个原子或若干个广义表组成的有穷序列。 树：1、一个结点x组成的集x是一株树(Tree)，这个

16、结点x也是这株树的根。2、假设x是一个结点，T1，T2，Tk是 k 株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，Tk。这些边也叫做分支，T1，T2，Tk称作根x的树之子树。 二叉树：有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树。 满二叉树：深度为k且有2k 1个结点的二叉树称为满二叉树。 完全二叉树：深度为 k 的，有n个结点的二叉树，当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应，称之为完全二叉树。 线索二叉树：若结点p有左孩子，则p-lc

17、hild指向其左孩子结点，否则令其指向其（中序）前驱。若结点p有右孩子，则p-rchild指向其右孩子结点，否则令其指向其（中序）后继。 堆：如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最大堆。同样，如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉树为最小堆。 选择树：一棵选择树是一棵二叉树，其中每一个结点都代表该结点两个儿子中的较小者。这样，树的根结点就表示树中最小元素的结点。 二叉排序树：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：1、若它的左子

18、树非空，则左子树上的所有结点的值均小于它的根结点的值。2、若它的右子树非空，则右子树上的所有结点的值均大于或等于它的根结点的值。3、它的左右子树分别为二叉排序树。 图：一个图G=（V，E）是一个由非空的有限集 V和一个边集E所组成的。若E中的每条边都是顶点的有序对（v , w），就说该图是有向图（directed graph，digraph）。若E中的每条边是两个不同顶点无序对，就说该图是无向图，其边仍表示成（v, w）。 开放树：连通而无环路的无向图称作开放树。 最小生成树：设G=( V, E )是一个连通图，E中每一条边(u, v)的权为C(u, v)，也叫做边长。图G的一株生成树(spa

19、nning tree)是连接V中所有结点的一株开放树。将生成树中所有边长之总和称为生成树的价(cost)。使这个价最小的生成树称为图G的最小生成树。 无向图双连通分量：设 Vi 是 Ei 中各边所连接的点集（1ik）, 每个图Gi = ( Vi , E i ) 叫做 G 的一个双连通分量。 双连通图：若对V中每个不同的三元组v,w,a；在v和w之间都存在 一条不包含 a 的路，就说G是双连通的 强连通性：设G =（V, E）是一个有向图，称顶点v ,wV是等价的，要么v = w；要么从顶点 v 到 w 有一条有向路 ，并且从顶点 w 到 v 也有一条有向路。 拓扑排序：给定一个无环路有向图G=

20、(V,E) , 各结点的编号为v=(1,2, ,n)。要求对每一个结点 i 重新进行编号，使得若 i 是 j 的前导，则有Labelilabelj。即拓扑分类是将无环路有向图排成一个线性序列，使当从结点 i 到结点 j 存在一条边，则在线性序列中，将 i 排在 j 的前面。 AOE网：在带权的有向图中，用结点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络,简称AOE网。 关键路径：在AOE网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从源点到汇点具有最大长度的路径称为关键路径。查找表：由同一类型的数据元素（或纪录）构成的集合。关键字：数据元素中某一数据项的值，用以表示一个数据元素。 AVL树：AVL树或者是一颗空二叉树，或者具有如下性质的二叉查找树： 其左子树和右子树都是高度平衡的二叉树，且左子树和右子树高度之差的绝对值不超过1。 B-树：B-树是一种非二叉的查找树除了要满足查找树的特性，还要满足以下结构特性：一棵 m 阶的 B- 树：（1）树的根或者是一片叶子(一