一、选择题（10道题，每题3分共30分）
1、下面算法的时间复杂度为（ ）
While(i A O(1) B O(n) C O(n2) D O(logN) 2.不带头结点的单链表first为空的判定条件是（ B ） A first= =NULL B first->link = =NULL C first->link= =first D first!= NULL 3. 设有一个广义表A( ( x, (a, b ) ), ( x, (a ,b ) , y ) ),运算Head( Head(Head(A ) ) )的执行结果为（ A ） A x B (a,b) C (x, ( a , b )) D y 4. 在一棵完全二叉书中，若编号为i的结点存在左子树，则右子树结点编号为（ ）。假定树根结点的编号为0. A. 2i B 2i-1 C 2i+1 D 2i+2 5.设有一个n*n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素 A[i][i]存放与B中（ ） 处。 A (i+3)*i/2 B (i+1)*i/2 C (2n-i+1)*i/2 D (2n-i-1)*i/2 6 .图的广度优先算法类借助的数据结构为（ B ） A 栈 B 队列 C 二叉树 D 树 7. 如果从中国人找出100个年龄最大的，那么使用下列排序算法中（ D ）算法最快 A 归并排序 B 希尔排序 C 堆排序 D 基数排序 8.散列函数应该有这样的性质，即函数值应当以 （ ）概率取其值域范围内的每一个值。 A 最大 B 最小 C 平均 D 同等 9．若待排序序列在排序前已基本递减有序，则采用（ A ）个方法比较次数比较少。 A 直接插入排序 B 快速排序 C 归并排序 D直接选择排序 10．10阶B树中，每个结点最多允许有（ ）个关键字。 A 8 B 9 C 10 D 1 1 二、填空题（8道题，每空1分共10分） 1、在顺序表中逻辑上相邻的结点而在物理位置上_______一定__相邻。 2、在一棵高度为3的二叉书中，最多含有_____85____个结点，假设根结点的高度为0. 3.在链表中进行插入和_______操作的效率比在顺序存储结构中进行相同的操作 效率搞。 4.在一棵二叉排序树中插入一个元素时，若元素的值大于根结点的值，则应把它插入到根结点的____右子树________上。 5.一棵树按照左子树-右兄弟表示法转换成对应的二叉树，则该二叉树根结点肯定没有______右____子树。 6.设双向循环链表中每个结点的结构为（data，llink，rlink），则结点*p的前驱结点的值为____p->llink__________. 7．在一棵高度为3的理想的平衡二叉树，最少还有___8____（_ 2h ）_____个结点，最多还有_____15（_2h+1-1_）_____个结点。假定树根结点为高度为1。 8.快速排序最坏情况和平均情况时间复杂度为___________和_____________. 三、判断题（10道题，每题1分共10分）（判断下列各个叙述的正误。对，在括号里面写T，错误，在括号里面写F） 1.数据项是数据的最小单位。 ( ) 2. 顺序栈与链式栈相比，一个明显的优点是通常不会出现栈满的情况。( ) 3.一棵二叉树中，假定每个结点只有左子树，没有右子树，若对他分别进行中序遍历和后序遍历，则具有相同的结果。 ( ) 4.一个广义表尾是一个广义表。 ( ) 5.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都使用。 ( ) 6.对于AOE网络，任一关键活动延迟将导致整个工程延迟完成。 ( ) 7.数据的逻辑结构与数组元素本身的内容与形式无关。 ( ) 8.当输入序列已经基本有序时，冒泡排序需要比较关键值的次数，比快速排序少。 9.若将一批杂乱无章的数据按堆结构组织起来，则堆中数据必然是按从大到小的顺序排列的。 ( ) 10.能够在链接存储的有序表进行折半查找，时间复杂度与顺序存储的时间复杂度小。 ( ) 四、运算题（5道题 每题8分共40分） 1、假定一棵二叉树的广义表表示为 A(B( ,D(G)),C(E,F))分别写出对它先序，中序，后序序列。 2、已知一个数据表为{47,25,76,32,40}，请写出在进行快速排序的过程每次划分后数据表的变化。 3、线性表的关键字集合为{113,12,180,138,92,67,94,134,252,6,70,323,60}，共有13个元素，已知散列函数为：H（k）=k mod 13，采用链接表处理冲突，试设计这种链表结构 4. 有一份电文使用5个字符：a、b、c、d、e，它们的出现频率依次为10、4、2、12、8。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。 5. 已知一个带权图的顶点集V和边集V为 V={0，1，2，3，4，5，6}； E={（0，1）19，(0，2)10，（0，3）14，（1，2）6，（1，5）5，（2，3）26，（2，4）15，（3，4）18，（4，5）6，（4，6）6，（5，6）12} 根据Dijkstra算法求顶点0到其它顶点的最短距离，并写出各路径。 五、程序设计题（1道题共10分） 设计一个用单链表作存储结构的直接插入排序算法。 数据结构 A 三、判断题（10道题，每题1分共10分）（判断下列各个叙述的正误。对，在括号里面写T，错误，在括号里面写F） 1.数据元素是数据的最小单位。 ( ) 2.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。 （ ） 3.一棵二叉树中，假定每个结点只有左子树，没有右子树，若对他分别进行中序遍历和后序遍历，则具有相同的结果。 （ ） 4.一个广义表头总是一个广义表。 （ ） 5.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都使用。 （ ） 6.对于AOE网络，任一关键 活动延迟将导致整个工程延迟完成。 （ ） 7.数据的逻辑结构与数组元素本身的内容与形式无关。 （ ） 8.当输入序列已经基本有序时，冒泡排序需要比较关键值的次数，比快速排序少。 （ ） 9.若将一批杂乱无章的数据按堆结构组织起来，则堆中数据必然是按从小到大的顺序排列的。 （ ） 10.能够在链接存储的有序表进行折半查找，时间复杂度与顺序存储的时间复杂度相同。 （ ） 四、运算题（5道题 每题8分共40分） 1、已知一棵二叉树的中序和后序如下，求改二叉树的前序序列和原图。 中序序列：c, b, d, e, a, g, i, h, j, f 后序序列：c, e, d, b, i, j, h, g, f, a 原图结构： 前序序列为： 2、已知一个数据表为{48,25,56,32,40}，请写出在进行快速排序的过程每次划分后数据表的变化。 3、设散列表长m=14，哈希函数为H(k)=k mod 11，表中一共有8个元素{15,27,50,73,49,61,37,60} ，试画出采用二次探测法处理冲突的散列表。 &&4. 有一份电文使用5个字符：a、b、c、d、e，它们的出现频率依次为5、 2、1、6、4。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。 5. 求出下图各结点最早，最晚开始时间，并求出关键活动。 1、假定一棵二叉树的广义表表示为 A(B( ,D(G)),C(E,F))分别写出对它先序，中序，后序序列。 2、知一个数据表为{47,25,76,32,4‰}，请熙出在进行快速排序的꿇程䯏次划分琎数䍮表的变化。 3、 线性表的关键字集合为{113,12,180,138,92,67,94,134,252,6,70,323,60}，共有13个元素，已知散列函数为：H（k）=k mod 13，采用链接表处理冲突，试设计这种链表结构 5.已知一个带权图的顶点集⁖和꾹集V为 V={0，1，2，3，4，5，6}； E={（0，1）19，(0，2)10，（0，3）14，（1，2）6，（1，5）5，（2，3）26，（2，4）15，（3，4）18，（4，5）6，（4，6）6，（5，6）12} 根据Dijkstra算法求顶点0到其它顶点的最短距离，并写出各路径。 五、程序设计题（1道题共10分） 试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。）下载本文
