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

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

ID:15507501

大小:72.50 KB

页数:6页

时间:2018-08-03

数据结构期末考试(2005-2006学年第一学期)_第1页
数据结构期末考试(2005-2006学年第一学期)_第2页
数据结构期末考试(2005-2006学年第一学期)_第3页
数据结构期末考试(2005-2006学年第一学期)_第4页
数据结构期末考试(2005-2006学年第一学期)_第5页
资源描述:

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

1、南昌航空工业学院2005-2006学年第一学期期末考试课程名称:数据结构B卷题号一二三四合计满分30103030100实得分班级-------------------学号--------------姓名-----------------一、填空题(每空1.5分,共30分)⒈任何一个算法的设计取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的。⒉数据结构是一门研究的程序设计问题中计算机的操作对象以及它们之间的等等的学科。⒊带头结点的单向链表L为空的判定条件是;非空的循环单链表head的尾结点p满足条件

2、。⒋栈和队列是两种特殊的线性表,栈的特点是,栈的典型应用有和。⒌在具有n个单元的循环队列中,队列满时共有个元素。⒍若串的长度不能确定,可采用动态存储结构,为串值分配一个存储空间,同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置,称该结构为。⒎稀疏矩阵一般的压缩存储方法有两种,即和十字链表。⒏二维数组A[10][20]采用列序为主方式存储,每个元素占10个存储单元,且A[0][0]的存储地址是2000,则A[6][12]的地址是。⒐一棵高度为h的满二叉树共有个终端结点。⒑已知一棵完全二叉树的第

3、5层有3个结点,其叶子结点数是。⒒具有8个顶点的有向完全图有条弧。⒓在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于。⒔对线性表进行二分查找时,要求线性表必须以方式存储,且结点按关键字排列。⒕在分块查找方法中,首先查找索引,然后再查找相应的。⒖与快速排序和堆排序相比,归并排序的最大特点是,它是一种的排序方法。二、判断题(每小题1分,共10分)若正确,填入“T”,否则填入“F”。⒈()线性表的逻辑顺序与存储顺序总是一致的。⒉()一个栈的入栈序列是12345,则栈的输出序列12345是

4、不可能的。⒊()将递归算法转换成对应的非递归算法时,通常需要使用栈。⒋()设有两个串p和q,求q在p中首次出现的位置的运算称作求子串。⒌()二维数组是其数据元素为线性表的线性表。⒍()线索二叉树是一种逻辑结构。-6-⒎()深度为K的完全二叉树至少有2K-1个结点。⒏()采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。⒐()若查找表的长度为n,则顺序查找法的平均查找长度为(n+1)/2。⒑()在待排序的元素序列基本有序的前提下,效率最高的是插入排序。三、解答下列各题(每小题5分,共30分)

5、⒈已知一棵二叉树的中序、后序序列分别如下:中序:DCEFBHGAKJLIM后序:DFECHGBKLJMIA要求:⑴画出该二叉树;⑵写出该二叉树的先序序列。⒉在一段文字中,7个常用汉字及出现频度如下:的地于个和是有2019181715101要求:⑴画出对应的Huffman树;⑵求出每个汉字的Huffman编码。⒊求出下图的一棵最小代价生成树。①16②81920③6④10⑤80⑥15181220⑦50⑧⒋-6-输入一个正整数序列{100,50,302,450,66,200,30,260},建立一棵二叉排序树

6、,要求:⑴画出该二叉排序树;⑵画出删除结点302后的二叉排序树。⒌设有一组关键字:{19,01,23,14,55,20,84,27,68},采用哈希函数:H(key)=keymod7,采用开放地址法的线性探测再散列方法解决冲突。要求:在0∽11的散列地址空间中对该关键字序列构造哈希表。01234567891011⒍一组序列的关键码为:{28、19、27、49、56、12、10、25}要求:⑴利用快速排序的方法,写出以第一个记录为基准得到的一次划分结果;⑵利用堆排序的方法,写出建立的初始大堆。四、算法设计

7、题(共30分)使用类C写出实现算法的函数,并加以适当的注解。⒈假设有两个按元素值非递增有序排列的线性表LA和LB,请编写算法将LA表和LB表合并成一个按元素值非递增有序排列的线性表LC。假设线性表的存储结构描述如下:#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量以一数据元素存储长度为单位}SqList;⒉试设计

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。