数据结构期末考试（2005－2006学年第一学期）.doc

南昌航空工业学院2005-2006学年第一学期期末考试
课程名称:数据结构 B卷
题号
一
二
三
四
合计
满分
30
10
30
30
100
实得分
班级------------------- 学号-------------- 姓名-----------------
一、填空题(,共30分)
⒈任何一个算法的设计取决于选定的数据(逻辑)结构,而算法的实现依赖于采用的。
⒉数据结构是一门研究的程序设计问题中计算机的操作对象以及它们之间的等等的学科。
⒊带头结点的单向链表L为空的判定条件是;非空的循环单链表head的尾结点p满足条件。
⒋栈和队列是两种特殊的线性表,栈的特点是,栈的典型应用有
和。
⒌在具有n个单元的循环队列中,队列满时共有个元素。
⒍若串的长度不能确定,可采用动态存储结构,为串值分配一个存储空间,同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置,称该结构为。
⒎稀疏矩阵一般的压缩存储方法有两种,即和十字链表。
⒏二维数组A[10][20]采用列序为主方式存储,每个元素占10个存储单元,且A[0][0]的存储地址是2000,则A[6][12]的地址是。
⒐一棵高度为h的满二叉树共有个终端结点。
⒑已知一棵完全二叉树的第5层有3个结点,其叶子结点数是。
⒒具有8个顶点的有向完全图有条弧。
⒓在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于。
⒔对线性表进行二分查找时,要求线性表必须以方式存储,且结点按关键字排列。
⒕在分块查找方法中,首先查找索引,然后再查找相应的。
⒖与快速排序和堆排序相比,归并排序的最大特点是,它是一种的排序方法。
二、判断题(每小题1分,共10分)若正确,填入“T”,否则填入“F”。
⒈( )线性表的逻辑顺序与存储顺序总是一致的。
⒉( )一个栈的入栈序列是12345,则栈的输出序列12345是不可能的。
⒊( )将递归算法转换成对应的非递归算法时,通常需要使用栈。
⒋( )设有两个串p和q,求q在p中首次出现的位置的运算称作求子串。
⒌( )二维数组是其数据元素为线性表的线性表。
⒍( )线索二叉树是一种逻辑结构。
⒎( )深度为K的完全二叉树至少有2K-1个结点。
⒏( )采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。
⒐( )若查找表的长度为n,则顺序查找法的平均查找长度为(n+1)/2。
⒑( )在待排序的元素序列基本有序的前提下,效率最高的是插入排序。
三、解答下列各题(每小题5分,共30分)
⒈已知一棵二叉树的中序、后序序列分别如下:中序:D C E F B H G A K J L I M
后序:D F E C H G B K L J M I A
要求:⑴画出该二叉树;
⑵写出该二叉树的先序序列。

⒉在一段文字中,7个常用汉字及出现频度如下:的地于个和是有
20 19 18 17 15 10 1
要求:⑴画出对应的Huffman树;
⑵求出每个汉字的Huffman编码。
⒊求出下图的一棵最小代价生成树。
① 16 ②
8 1 9 20
③ 6 ④ 10 ⑤ 80 ⑥
15 18 12 20
⑦ 50