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和线性探测法处理冲突，试求出每个元素的散列地址，画出最后得到的散列表，并求出平均查找长度。散列地址为：
