《数据结构试题》word版

《《数据结构试题》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构试题摘要：(6)(2分)写出将无向图的邻接表转换成邻接矩阵的算法。七.(11分)给定权值集合{15，3，14，2，6，9，16，17}.（1）（3分）用□表示外部结点，用〇表示内部结点，构造...关键词：矩阵,算法类别：专题技术来源：牛档搜索（Niudown.COM）　　本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！(山工2000年数据结构试题一·填空(9分

2、)l·(3分)执行顺序查找时，存储方式可以是，二分法查找时，要求线性表，分块查找时要求线性表，而散列表的查找，要求线性泰的存储万式是。2·(3分)在对称表的存储结构中，每个结点只包含一个指针字段和一个信息字段，这个指针字段存放的是，用和其它信息一起，既可以很快的求出它的结点，又可以很快地求出它的结点。常用的对称表有和。3。（3分）广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于。为了区分原子和表，一般用表示表，用表示原子。一个表的长度是指，而表的深度是用。二·（7分）填空并回答问题1．（2分）什仫是同以词；2．（2分）什仫是堆积；3．．（2分）为避免堆积的

3、发生，可用两遍处理的方法建立散列表，第一遍，第二遍。三·（9分）选择填空1·（4分）二维数组A的元素都是6个字符组成的串，行下标i的范圃从0到8，列下标j的范圈从l究10。从供选择的答案中选出应填入下列关于数组存储叙述中()内的正确答案。（1）存放A至少需要（）个字节；（2）A的第8列和第5行共占（）个宇节；（3）若A按行存放，元紊A[8，5]的起始地址与A按列荐放时的元素（）的起始地址一致。供选择的答案（1）a90b180c240d270e540（1）a108b114c54d60e150（1）aA[8,5]bA[3,10]cA[5,8]dA[0,9]2.(5分)排序的方法有很多种

4、，（）法从未排序的序列中依次取出元素与己排序序列中的元素比较，将其放在已排序序列的正确位置上；（）法从未排序序列中挑选元素，并将其依次放入己排序序列的一端；交换排序法是对序列中的元素进行一系列比较当被比较的两元素逆序时，进行交换。（）和（）是基于这类方法的两种排序方法，而()是比()效率更高的方法。供选择的答案a快速排序b选择排序c归并排序d冒泡排序e直接插入排序四．（5分）判断下列序列是否是堆（可以是小堆也可以是大堆），若不是堆，请将它们调整为堆。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，

5、20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80，82，85，98，100五．（16分）表插入排序的基本思想是在结点中设一指针字段，插入Ri时Rl到Ri-1己经用指针按排序码不减次序链结起夹，这时采用顺序比较的方法找到Ri应插入的位置，做链表播入。如此反复，直到把Rn插入为止。(1)(6分)请完成不列表插人的算法；l·R[0].LINK←;R[N].LINK←2循环，I以-1为步长，从到执行（1）P←R[0].LINK;Q←0(2)循环，当P〉0且时，反复执行Q←P；P←（3）R[Q].LINK←I;R

6、[I].LINK←P(2)(2分)表插入排序的最大比较次数是；（3）（2分）表插入排序的最小比较次数是；（4）（2分）记录移动的次数是；（5）（2分）需要附加的存储空间是；（6）（2分）该排序算法是否是稳定的。六.(18分)已知某图的邻接表为 (1)(2分)写出此邻接表对应的邻接矩阵；(2)(2分)写出由V1开始的深度优先遍历的序列；(3)(2分)写出由V1开始的深度优先的生成树；(4)(2分)写出由V1开始的广度优先遍历的序列；(5)(2分)写出由V1开始的广度优先的生成树；(6)(2分)写出将无向图的邻接表转换成邻接矩阵的算法。七.(11分)给定权值集合{15，3，14，2，6

7、，9，16，17}（1）（3分）用□表示外部结点，用〇表示内部结点，构造相应的Huffman树；（2）（2分）计算出它的带权路径长度；（3）（2分）写出它的Huffman编码；（4）（3分）Huffman编码常用来译码，请用语言叙述写出其译码的过程八.(16分)已知一棵二叉树的对称序和后序序列况下：对称序：GLDHBELACJFk后序：LCHDIEBJKFCA（1）（2分)给出这棵二叉树:(2)(2分)转换为对应的森林:（3）（4分）画出该森林的带右链的先根次序表示法