2、指结点之后插入一个s所指结点时，应执行下面的操作：s—>next=;p—>next=;6、从有序表（12,18,30,43,56,78,82,95）中依次二分查找43和56元素时，其查找长度分别为和。7、.一棵二叉树有67个结点，这些结点的度要么是0,要么是2。这棵二叉树中度为2的结点有个。8、在堆排序和快速排序中，若原始记录接近正序或反序，则选用。9、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的遍历。、单向选择题（每小题1.5分，共15分）得分1、n个顶点的强连通图中至少含有（）。A、n—l条有向边B、n条有向边C、n（n—1）/2条有向边D、n（n—1
3、）条有向边2、在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点,执行（）。-、HL=p;p->next=HL;B、p—>next=HL;HL=p;-、p—>next=HL;p=HL;D、p—>next=HL一>next;HL一>next=p;3、采用线性链表表示一个向量时，要求占用的存储空间地址（）。第6页共9页A：必须是连续的B部分地址必须是连续的C:一定是不连续的D:可连续可不连续-4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。-A：起泡排序B：堆排序C：锦标赛排序D：快速排序--5、在循环队列中用数组A[0..m-1
4、]存放队列元素，其队头和队尾指针分别为front和rear,-则当前队列中的元素个数是（）。-A:(front-rear+1)%mB:(rear-front+1)%m---C:(front-rear+m)%mD:(rear-front+m)%m--6、数组A[0..5,0..6]的每个兀素占五个字节，将其按列优先次序存储在起始地址为1000的-内存单元中，则元素A[5,5]的地址是()。-A:1175B:1180C:1205D:1210-77、已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是()I_-A:head(
5、tail(LS))B:tail(head(LS))--C:head(tail(head(tail(LS)))D:head(tail(tail(head(LS))))--8、某二叉树的刖序遍历结点为问顺序是abdgcefh,中序遍历的结点为问顺序是dgbaechf则线-其后序遍历的结点访问顺序是()0-A:bdgcefhaB:gdbecfhaC:bdgaechfD:gdbehfca、一-订-9、在一个无向图中，所有顶点的度数之和等于所有边数的()倍。--壮-A:1/2B:1C:2D:4表--10、设用s1='ABCDEFGs2='PQRST函数con(x,y)返回x和y
6、用的连接用，subs(s,i,j)超订返回用s的从序号i的字符开始的j个字符组成的子用，len(s)返回用s的长度，则con(subs勿-(s1,2,len(s2)),subs(s1,len(s2),2)的结果用是()。-题-A:BCDEFB:BCDEFGC:BCPQRSTD:BCDEFEF三、应用题（每小题8分，共32分）得分1.一棵深度为h的满m叉树具有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。若按层次从上到下，每层从左到右的顺序从1开始对全部结点编号，试计算:类（1）第k层结点数（10k&h）。（2）整棵树结点数。（3）编号为i的结
7、点的双亲结点的编号。（4）编号为i的结点的第j个孩子结点（若有）的编号第6页共9页2已知图G的邻接表如图1所示，请写出:第6页共9页(1)其从顶点v1出发的深度有限搜索序列;(2)其从顶点v1出发的广度优先搜索序列图1图G的邻接表3、以关键码序列(503,087,512,061,908,170,897,275,653,426,为例，手工执行快速排序排序算法，写出每一趟排序结束时的关键码状态：4.使用哈希函数H(key尸key%11,把一个整数值转换成哈希表下标，现要把数据1、13、12、34、38、33、27、22插入到哈希表(表1)中。(1)使用线
