文档介绍：二、填空题(每空 2 分) 16% 得分 1 、在单链表中,在指针 P 所指结点后面插入一个结点 S 的语句序列是: ()。 2 、设循环队列中数组的下标范围是 1~n ,头尾指针分别为 front 和 rear ,则其元素个数为() 3、已知数组 A[10][10] 为对称矩阵, 其中每个元素占 5 个单元。现将其下三角部分按行优先次序存储在起始地址为 1000 的连续的内存单元中, 则元素 A[5][6] 对应的地址为()。 4、假设以带表头结点的循环链表表示队列, 并且只设一个指针 P 指向队尾元素结点, 那么如何判断队列为空的条件是( )。 5、已知完全二叉树的第七层有 10 个叶子结点, 则整个二叉树的结点数最多是()。 6 、对于给定的一组权值 W={ 5,6,7,8,9, 10 , 15 , 18 , 22 } ,构造出具有最小带权路径长度的哈夫曼树后,其带权路径长度为()。 7 、在有 n 个顶点的有向图中,每个顶点的度最多可达( )。 8 、选择排序算法所执行的元素交换次数最多为( )。三、判断题( 每题 1 分) 10% 得分 1、( )串长度是指串中不同字符的个数 2、( )线性表的长度是线性表所占用的存储空间的大小。 3、( )在链队列中,即使不设置尾指针也能进行入队操作。 4、( )已知一棵树的先序序列和后序序列,一定能构造出该树。 5、() 删除二叉排序树中一个结点, 再重新插入上去, 一定能得到原来的二叉排序树。 6、( )对广义表 A= (a,(b,c),d )的运算 head ( tail (A) )的结果不是 b。 7、() 任一 AOE 网中至少有一条关键路径, 且是从源点到汇点的路径中最长的一条。 8、( )一个有向图的邻接表和逆邻接表中的结点个数一定相等。 9、( )给出不同的输入序列建造二叉排序树,一定得到不同的二叉排序树。 10、( )在索引顺序表的查找中,对索引表既可采用顺序查找方法,也可采用二分查找方法。四、应用题(5 小题) 28% 得分 1 、已知二叉树的中序和后序序列如下,画出该二叉树。( 6 分) 中序序列为: DCEFBHGAKJLIM 后序序列为: DFECHGBKLJMIA 2、一棵二叉排序树结构如下, 各结点的值从小到大依次为 1-8 , 请标出各结点的值。(4分) 3、设哈希表的长度为 9, 哈希函数为 H(x)=i div 3, 其中 i 为键值 x 中第一个字母在字母表中的序号,若键值的输入序列为 Jan , Feb , Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec ,用拉链法处理冲突,要求:( 7 分) (1) 构造哈希表(2) 求出等概率情况下,查找成功的平均查找长度。 4 、对下列数据表,写出采用冒泡排序算法排序的每一趟的结果。( 4 分) ( 25 , 10 , 20 , 31 ,5, 44 , 16 , 61 , 100 ,3) 5 、图 G 的邻接表如下,完成下列各题。( 9 分) (1 )画出从顶点 5 出发进行广度遍历所生成的