三、判断题
1、线性表中所有数据元素的类型必须相同。（ ）
2、栈是一种线性结构。（ ）
3、二叉树中第i层上最多有2i（i≥1）个结点。（ ）
4、任何无环的有向图，其结点都可以排在一个拓扑序列里。（ ）
5、折半查找算法在查找时进行的比较次数最大为相应二分判定树的深度。（ ）
6、线性表中的数据元素是有序的。（ ）
7、队列是一种非线性结构。（ ）
8、K层满二叉树非叶子结点总数为2K-1。（ ）
9、无向图的生成树是连通的。（ ）
四、应用题
1、某二叉树的节点数据采用顺序存储表示如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
E A F D H C G I B
（1） 试画出此二叉树的图形表示；
（2） 试给出对该二叉树进行中序遍历的次序；
（3） 写出节点D的双亲节点及左、右孩子节点；
（4） 将此二叉树看作森林的二叉树表示，试将它还原为森林。
2、设待排序记录的关键字为{49，38，65，97，76，13，27，49}，请给出分别按以下排序方法得到的第一趟排序结果。
（1）希尔排序（第一趟排序时增量为4）
（2）冒泡排序（大数下沉）
（3）快速排序（以49作为枢轴）
（4）2-路归并排序
3、一个线性表为 B=（12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36），设哈希表为 HT[0..12] ，哈希函数为 H （ key ） = key % 13 ，并用线性探测法解决冲突，请画出哈希表，并计算等概率情况下查找成功的平均查找长度。
4、已知一棵二叉树的前序遍历的结果序列是 ABDGCEHFIJ ，中序遍历的结果是 DGBAEHCIFJ ，试画出这个二叉树，并写出这棵二叉树的后序遍历结果。
二、填空题
1、从逻辑结构看，线性表是典型的 线性结构 ______，树是典型的 非线性结构
2、数据的两种不同的存储结构是__顺序储存结构___和____链式储存结构___。
3、如果将线性链表__________结点的指针域改为存放链表中____________结点的地址值，就使得整个链表构成一个环形，这样的链表称为线性循环链表。
4、设有二维数组A[0..5,0..9]，其每个元素占三个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[4,4]的存储地址为 ，按列优顺序存储，元素A[4,4]的存储地址为 。
5、栈又称为_____________________表，队列又称为____________________表。
6、对于任意非空的二叉树，若其结点数为n，则总分支数为______________；第i层上最多有_______________个结点。
7、一棵高度为5的二叉树中最少含有 个结点，最多含有 个结点。
8、在无向图中，若每一对顶点之间都有路径，则称此图为__________________；若每一对顶点之间都有一条边，则称此图为_________________。
9、在无向图中，顶点的___________是指以该顶点为弧头的弧的数目；顶点的___________则指以该顶点为弧尾的弧的数目。
10、数据的四类基本的结构是：集合、_______________、树形结构和_______________。
11、数据的两种不同的存储结构是____________________和___________________。
12、如果将线性链表的最后一个结点的指针域改为存放链表中第一个结点的地址值，这样的链表称为_______________；如果链表中每个结点都具有两个指针域，其中一个指针指向其后继结点，另一个指针指向其前驱结点，则称这种链表为_______________。
13、栈操作满足“_______________”原则；队列操作满足“_______________”原则。