第二次测试题A-数据结构（C语言）

数据结构（C语言）第二次测试A 满分：100分，完成时间：45分钟

一、选择题：（每题4分，共28分）

1、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是_________的二叉树。 (A)空或只有一个结点 (B)高度等于其结点数 (C)在任一结点无左孩子 (D)任一结点无右孩子 2、n个顶点的无向图的邻接表中结点总数最多有( )个。 (A) 2n (B) n (C) n/2 (D) n(n-1) 3、设连通图G的顶点数为n，则G的生成树的边数为( )。 (A) n (B) n-1 (C) 2n (D) 2n-1

4、如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G},数据元素之间的关系为R={,,,< D, C >,< G, E>,< G, F >},则该数据结构是一种 。 (A)线性结构 (B)树结构 (C)图结构 (D)链表结构 5、具有20个结点的二叉树，其深度最多为 。

(A)4 (B)5 (C)6 (D)20 6、设一颗二叉树共有50个叶子结点（终端结点），则共有 个度为2的结点。

(A)25 (B)49 (C)50 (D)51

7、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ） A） e B）2e C） n2-e D）n2-2e

二、填空题：（每题2分，共12分）

1、一棵哈夫曼树是由5个叶子结点形成的，该哈夫曼树总共有 个结点。 2、如果一个有向图有5个顶点，则它最多有 条弧。 3、设有1000个元素，用二分法查找时，最大比较次数是 。

4、折半查找有序表(2,4,6,12,20,28,38,50,70,100),若查找表中元素12,它依次与表中元素___________________比较大小；若查找55，它依次与表中元素___________________比较大小。

5、深度为8的完全二叉树至少有______个叶子结点。 三、应用题：（40分）

1、写出图1的先序、中序、后序、层次遍历的序列（10分） 2、画出图2的邻接矩阵、邻接表、逆邻接表（15分）

B AC EBCD

F

DEFA

G?2

?1

3.给定一组数列（15,8,10,21,6,19,3）分别代表字符A,B,C,D,E,F,G出现的频度，试画出哈夫曼树，计算带权路径长度WPL，给出各字符的编码值。（15分） 四、算法设计题（20分）

编写算法对一个非零整型数组中（一共n 个元素）的元素进行位置调整，将所有负数放在下标较低的一端，将所有正数放在下标较高的一端。要求时间复杂度为O（n）。 void aElement(int a[],int n);