《数据结构期末考试(2005-2006学年第一学期).doc》由会员分享，可在线阅读，更多相关《数据结构期末考试(2005-2006学年第一学期).doc（6页珍藏版）》请在金锄头文库上搜索。
1、南昌航空工业学院20052006学年第一学期 期末考试课程名称：数据结构 B卷题号一二三四合计满分30103030100实得分班级- 学号- 姓名-一、填空题（每空1.5分，共30分） 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的 。 数据结构是一门研究 的程序设计问题中计算机的操作对象以及它们之间的 等等的学科。 带头结点的单向链表L为空的判定条件是 ；非空的循环单链表head的尾结点p满足条件 。 栈和队列是两种特殊的线性表，栈的特点是 ，栈的典型应用有 和 。 在具有n个单元的循环队列中，队列满时共有 个元素。 若串的长度不能确定，可采用动态存储结构，为串值分
2、配一个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储空间中的位置，称该结构为 。 稀疏矩阵一般的压缩存储方法有两种，即 和十字链表。 二维数组A1020采用列序为主方式存储，每个元素占10个存储单元，且A00的存储地址是2000，则A612的地址是 。 一棵高度为h的满二叉树共有 个终端结点。 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是 。 具有8个顶点的有向完全图有 条弧。 在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 。 对线性表进行二分查找时，要求线性表必须以 方式存储，且结点按关键字 排列。 在分块查找方法中，首先查找索引，然后再查找相应的 。 与快速排
3、序和堆排序相比，归并排序的最大特点是，它是一种 的排序方法。二、判断题（每小题1分，共10分）若正确，填入“T”，否则填入“F”。（ ）线性表的逻辑顺序与存储顺序总是一致的。（ ）一个栈的入栈序列是12345，则栈的输出序列12345是不可能的。（ ）将递归算法转换成对应的非递归算法时，通常需要使用栈。（ ）设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。（ ）二维数组是其数据元素为线性表的线性表。（ ）线索二叉树是一种逻辑结构。（ ）深度为K的完全二叉树至少有2K-1个结点。（ ）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。（ ）若查找表的长度为n，则顺序查找
4、法的平均查找长度为（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
5、15 18 12 20 50 输入一个正整数序列100，50，302，450，66，200，30，260，建立一棵二叉排序树，要求： 画出该二叉排序树； 画出删除结点302后的二叉排序树。 设有一组关键字：19，01，23，14，55，20，84，27，68，采用哈希函数：H（key）=key mod 7，采用开放地址法的线性探测再散列方法解决冲突。要求：在011的散列地址空间中对该关键字序列构造哈希表。0 1 2 3 4 5 6 7 8 9 10 11 一组序列的关键码为：28、19、27、49、56、12、10、25要求： 利用快速排序的方法，写出以第一个记录为基准得到的一次划分结果； 利
6、用堆排序的方法，写出建立的初始大堆。四、算法设计题（共30分）使用类C写出实现算法的函数，并加以适当的注解。 假设有两个按元素值非递增有序排列的线性表LA和LB，请编写算法将LA表和LB表合并成一个按元素值非递增有序排列的线性表LC。假设线性表的存储结构描述如下：#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量以一数据元素存储长度为单位SqList;试设计算法在按元素值非递增有序排列的
7、带头结点单向链表head中，删除值相同的多余元素。假设该链表的存储结构描述如下：typedef struct LNODE ElemType data;struct LNODE *next;*LinkList; 试设计算法计算一棵给定二叉树上所有结点数目。假设二叉树的存储结构描述如下： typedef struct BiTNodeTElemType data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/BiTNode,*BiTree；南昌航空工业学院20052006学年第一学期 期末考试课程名称：数据结构 B卷参考答案一、填空题： 存储结构 非数值计算
8、关系和操作 L-next=NULL p-next=head 先进后出 表达式求值 实现递归过程 n-1 堆/堆结构 三元组表 3260 2h-1 9 56 1 顺序 有序 块 插入排序/直接插入排序 稳定 二、判断题：F F T F T F T F T T三、解答下列各题 ：A B I C G J M D E H K L F 先序:A B C D E F G H I J K L M 1 9 20 6 10 15 12 10039 61 19地 20的 26 3511 15和 17个 18于 1有 10是 01 的 00 地 111 于 110 个 101 和 1001 是 1000 有 100 50 30230 66 200 450 260100 50 26030 66 200 450 0 1 2 3 4 5 6 7 8 9 10 11 1401238419552027685649 27 28 19 12 10 25 25 19 27 10 12 28 56 49 该序列不是一个堆。建成的初始大根堆如下： 56 49 27 28 19 12 10 25 或：四、算法设计：（以下答案不唯一） void MergeList_Sq(SqList La,SqList
