3、向其屮的一个结点,选择合适的语句实现在p结点的后而插入一个结点s的操作(B)oA^p~>next二s;s->next=p->next;Bss~>next=p->next;p-〉next二s;C、p->next二s;s->ncxt二p;D、s->next=p;p->next=s;2.假设以I和0分別表示入栈和出栈操作,栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和0组成的序列。则下列序列(A)是合法的。A、TOTTOTOOB、TOOTOTTOC、IIIOIOIOD、OIIOIOIO4、空串和空格串是(B)oA、相同的B、不相同的C、不能确定5、设W为一个二维数组,其每个数据元
4、索占用6个字节,行下标范围从0到8,列下标范围从2到5,则二维数组W的数据元素共占用(C)个字节。A、480B、192C、216D、1446、假设在一棵二叉树中,度为2的分支结点个数为15,度为1的分支结点个数为30,则该二义树的结点总数为(D)oA、45B、60C、46D、617.对用邻接矩阵表示的图进行任一种遍历时,其时间复杂度为(A)。A、O(n)B、0(e)C、0(n)D、0(n+e)8.对线性表进行折半查找时,耍求线性表必须(C)oA、以顺序方式存储B、以链接方式存储C、以顺序方式存储,且结点按关键字有序排列D、以链接方式存储,冃结点按关键字冇序排列9、设散列表长m=14,散
5、列函数II(key)=key%llo表中已有4个结点:addr(⑸二4、addr(38)二5、addr⑹)二6、addr(84)=7,其余地址为空,如用二次探测再散列解决冲突,关键字为49的结点的散列地址是(D)0A、8B、3C、5D、910.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为(B)。A、79,46,56,38,40,80B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,38三、判断题(在正确的题后括号内打/,错的则打X,每小题1分,共8分)得分1.链表必须要设置一个头结
6、点。(X)2.堆排序、快速排序和希尔排序都是不稳定的排序方法。(7)3.二义树是度为2的有序树。(X)4.循环队列是指用循环链表存储的队列。(X)5.若入栈序列为abed,则出栈序列不可能为edabo(7)6.在拓扑排序过程中,如果图中已不存在无前驱的顶点了,而此时还有顶点没有输出,贝U说明图屮存在环。(7)7.平衡二叉树是指这样的二叉树:树中任一结点的左右子树深度都相同。(X)8.在任何情况下,快速排序都是最快的。(X)衆:k总!II衆!I得分四、简答题(每小题10分,共40分)1.已知二叉树如图1所示,要求:(1)将Jt转换为树,并画出该树;(2)分别写出对(1)所得到的树进行先根
7、遍历和后根遍历得到的结点序列。图2.对如图2所示的连通图,试分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskar)算法构造其最小生成树,并给出其构造过程。7图21.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,36,18,70),散列地址空间为HT[0〜12],若采用除留余数法构造散列函数H(key)二key%13和线性探测法处理冲突,试求出每个元素的散列地址,画出最后得到的散列表,并求出平均查找长度。散列地址为: