3、++)A[i][j]=0;A)O(m)B)O(n)C)O(m*n)D)O(m/n)4.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（）个元素。A)n-iB)n-i+1C)n-i-1D)i5.选项（）是栈和队列的共同点。A)后进先出B)先进先出C)先进后出D)只允许在端点处进行插入和删除6.在一棵具有n个结点的二叉树的第i层上，最多可有（）个结点。A)2iB)2i-1C)2i-1D)2n7.如果二叉树T2是由树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的（）。A)先序B)中序C)后序D)无对应关系8
4、.利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。A)38B)58C)29D)559.在一个具有n个结点的无向图中，若具有e条边，则所有顶点的度数之和为（）。A)nB)eC)2eD)n+e10.判断一个有向图是否有环（回路）的方法是（）。A)求结点的度B)拓扑排序C)求关键路径D)求最短路径二、填空题1.数据的逻辑结构分为线性结构和非线性结构，栈属于线性结构，树属于结构。2.如右图所示的双向链表中，欲在*p前插入一个结点*s，请在下面的空格处填入正确的语句。s->prior=p->prior;p->prior=s
5、;s->next=p;1.一个结点的子树的个数称为该结点的。2.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0和n2之间具有性质。3.树根的层次是1，则深度为8的完全二叉树至少有个结点，拥有100个结点的完全二叉树的最大层次数是。4.二叉树的先序和中序遍历序列分别是ABCDEFGH，CBEDFAGH，则后序遍历序列是。5.图的遍历算法有和广度优先搜索遍历算法。6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的数据时次比较成功。7.对于关键字序列：12、13、11、
6、18、60、15、7、20、25、100，用筛选法建堆，必须从值为的关键字开始。一、简答题1.什么是栈？栈对数据进行入栈和出栈操作的原则是什么？2.什么是二叉排序树？3.简述冒泡排序的基本思想。4.使用Prim（普里姆）算法构造出下图的一棵最小生成树，请写出该最小生成树产生的每一步。5.根据下图所示的AOE网（顶点v1,v2,v3,v4,v5,v6表示事件；弧A,B,C,D,E,F,G,H表示活动），请回答以下问题：(1)求出所有事件的最早发生时间与最迟发生时间。(2)列出所有关键活动。1.已知下图所示的二叉树是由某森林转换而来，请画出其原来的森林2.从
7、空树开始，(1)画出按以下次序向3阶B-树中插入关键码后建立的树（不用写建树的过程，只写最终建立的树）。依次插入的关键字是：20，30，50，52，60，68，70。(2)画出基于第（1）步建立的3阶B-树，删除关键字50之后的B-树。(3)画出基于第（2）步执行之后产生的B-树，删除关键字68之后的B-树。3.设记录的关键字（key）集合是：K={15,25,26,4,5,20,3,12,2}(1)设Hash表表长m=16，选取Hash函数的方法为“除留余数法”，其函数形式为H(key)=keyMOD15，处理冲突的方法为“线性探测再散列”，请依次取K
8、中各值，构造出满足所给条件的Hash表，画出该哈希表的存储结构图；(2)写出基于
