数据结构期末考试(2005-2006学年第一学期)

《数据结构期末考试(2005-2006学年第一学期)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、南昌航空工业学院2005－2006学年第一学期期末考试课程名称：数据结构B卷题号一二三四合计满分30103030100实得分班级-------------------学号--------------姓名-----------------一、填空题（每空1.5分，共30分）⒈任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的。⒉数据结构是一门研究的程序设计问题中计算机的操作对象以及它们之间的等等的学科。⒊带头结点的单向链表L为空的判定条件是；非空的循环单链表head的尾结点p满足条件。⒋栈和队列是两种特殊的线性表，栈的特点是，栈的典型应用有和。⒌在具有n个单元的循环

2、队列中，队列满时共有个元素。⒍若串的长度不能确定，可采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为。⒎稀疏矩阵一般的压缩存储方法有两种，即和十字链表。⒏二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是。⒐一棵高度为h的满二叉树共有个终端结点。⒑已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。⒒具有8个顶点的有向完全图有条弧。⒓在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。⒔对线性表进行二分查找时，要

3、求线性表必须以方式存储，且结点按关键字排列。⒕在分块查找方法中，首先查找索引，然后再查找相应的。⒖与快速排序和堆排序相比，归并排序的最大特点是，它是一种的排序方法。二、判断题（每小题1分，共10分）若正确，填入“T”，否则填入“F”。⒈（）线性表的逻辑顺序与存储顺序总是一致的。⒉（）一个栈的入栈序列是12345，则栈的输出序列12345是不可能的。⒊（）将递归算法转换成对应的非递归算法时，通常需要使用栈。⒋（）设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。⒌（）二维数组是其数据元素为线性表的线性表。⒍（）线索二叉树是一种逻辑结构。-6-⒎（）深度为K的完全二叉树至少有2K

4、-1个结点。⒏（）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。⒐（）若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。⒑（）在待排序的元素序列基本有序的前提下，效率最高的是插入排序。三、解答下列各题（每小题5分，共30分）⒈已知一棵二叉树的中序、后序序列分别如下：中序：DCEFBHGAKJLIM后序：DFECHGBKLJMIA要求：⑴画出该二叉树；⑵写出该二叉树的先序序列。⒉在一段文字中，7个常用汉字及出现频度如下：的地于个和是有2019181715101要求：⑴画出对应的Huffman树；⑵求出每个汉字的Huffman编码。⒊求出下图的一棵最小代价生

5、成树。①16②81920③6④10⑤80⑥15181220⑦50⑧⒋-6-输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴画出该二叉排序树；⑵画出删除结点302后的二叉排序树。⒌设有一组关键字：{19，01，23，14，55，20，84，27，68}，采用哈希函数：H（key）=keymod7，采用开放地址法的线性探测再散列方法解决冲突。要求：在0∽11的散列地址空间中对该关键字序列构造哈希表。01234567891011⒍一组序列的关键码为：{28、19、27、49、56、12、10、25}要求：⑴利用快速排序的方法，写出以

6、第一个记录为基准得到的一次划分结果；⑵利用堆排序的方法，写出建立的初始大堆。四、算法设计题（共30分）使用类C写出实现算法的函数，并加以适当的注解。⒈假设有两个按元素值非递增有序排列的线性表LA和LB，请编写算法将LA表和LB表合并成一个按元素值非递增有序排列的线性表LC。假设线性表的存储结构描述如下：#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量以一数据元素存储长度为单位}SqList;⒉试

7、设计算法在按元素值非递增有序排列的带头结点单向链表head中，删除值相同的多余元素。假设该链表的存储结构描述如下：typedefstructLNODE{ElemTypedata;structLNODE*next;}*LinkList;-6-⒊试设计算法计算一棵给定二叉树上所有结点数目。假设二叉树的存储结构描述如下：typedefstructBiTNode{TElemTypedata;structBiTNode*lchild;*rchild;/*