数据结构模拟题====求助一、填空题1.对于给定的n个数据元素，可能构造出、、和四种逻辑结构。2．任何一个算法的设计取决于选定的，而算法

　　数据结构模拟题====求助

　　一、填空题

　　1.对于给定的n个数据元素，可能构造出、、

　　和四种逻辑结构。

　　2．任何一个算法的设计取决于选定的，而算法的实现依赖于采用的。

　　3、顺序存储的栈栈中元素的个数是，栈空的条件是，栈满的条件是。链栈栈空的条件是。

　　4.哈希表需要解决的问题是和。用开放地址法解决Hash冲突，冲突后Hash地址的计算公式是Hi=_。

　　5.在有n个结点的二叉链表中，空链域的个数为。

　　6.一棵高度为h的满二叉树共有个叶子结点。

　　7.由树转换为二叉树，其根节点的右子树总是。

　　8.一棵有N个叶子结点的哈夫曼树，共有个结点。

　　9.在无向图G的邻接矩阵中，求第i个结点的度的方法是。

　　10.对线性表进行二分查找(折半查找)时，要求线性表必须以方式存储，且结点按关键字排列。

　　二、判断题，若正确，填入“T”，否则填入“F”。

　　1．（）线性表的逻辑顺序与存储顺序总是一致的。

　　2.（）一个栈的入栈序列是1234，则栈的输出序列1234是不可能的。

　　3．（）一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。

　　4.（）线索二叉树是一种逻辑结构。

　　5.（）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。

　　6．（）哈夫曼树没有度为1的结点。

　　7.()用一维数组存储二叉树时，总是以前序遍历存储节点。

　　8.()前序和中序遍历用线索树方式存储的二叉树，不必使用栈。

　　9.()折半查找适用于有序表，包括有序的顺序表和有序的链表。

　　10.()快速排序的速度在所有的排序方法中为最快，而且所需附加空间也最少。

　　三、解答下列各题

　　1.设有一组关键字：{19，14，23，01，68，20，84，27，55，11，10，79}，采用哈希函数：H（key）=keymod13，采用开放地址法的线性探测再散列方法解决冲突。

　　要求：在0∽12的散列地址空间中对该关键字序列构造哈希表。

　　2.一组序列的关键码为：{49，38，65，97，76，13，27，49}

　　要求：（1）利用堆排序的方法，写出建立的初始小顶堆。

　　(2)冒泡排序第一趟排序的结果.

　　3.输入一个正整数序列{100，50，280，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴画出该二叉排序树；并指出该二叉树是否为平衡二叉树？

　　⑵画出删除结点280后的二叉排序树。

　　4.已知一棵二叉树的中序、后序序列分别如下：

　　中序：BDCAHGKFE

　　后序：DCBHKGFEA

　　要求：⑴画出该二叉树；

　　⑵写出该二叉树的先序序列。

　　四、算法设计题,使用类C语言写出实现算法的函数，并加以适当的注解。

　　巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。给出实现算法，假设线性表的存储结构描述如下：

　　#defineLIST_INIT_SIZE100

　　#defineLISTINCREMENT10

　　typedefstruct{

　　ElemType*elem;//存储空间基址

　　intlength;//当前长度

　　intlistsize;//当前分配的存储容量以一数据元素存储长度为单位

　　}SqList;