2007硕试卷.doc

一、 单选题(每小题2分，共20分)1.非空的循环单链表（data表示结点的数据，link表示结点的后继指针），以first表示头结点，则链表的尾结点（由p所指向）满足 ：Ap-link = NULL； Bp = NULL； Cp-link = first； Dp = first； 2.在一个长度为n的顺序存储的线性表中，向第i个元素(1in+1)的位置插入一个新元素时，需要从后向前依次后移 个元素。A n-i B n-i+1 Cn-i-1 D i 3.根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为 。A O(lon2n) B O(n) CO(nlog2n) DO(n2)4.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为13，搜索第二个元素的概率为l6，搜索第三个元素的概率为l6，搜索不成功的概率为13，则搜索任一元素的平均搜索长度为 。A53 B2 C73 D435.栈的插入和删除操作在 进行。A栈顶 B栈底 C任意位置 D指定位置6.二叉树有 种基本形态。A2 B3 C4 D57.某算法的空间花费s(n)=1000nlog2n+0.5n2+50n1.5+100n+2000,其空间复杂度为 A. O(n) B. O(n1.5) C. O(n2) D.O(nlog2n)8.冒泡排序在最好情况下时间复杂度为 A.O(1) B.O(nlog2n) C.O(n) D.O(n2)9.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 A.243156 B.324165 C.432156 D.23516410.下列不属于内部排序的算法是 A 归并排序 B 拓扑排序 C 堆排序 D 折半插入排序二、 填空题(每空2分，共30分)1.迪杰斯特拉算法是求有向图单源最短路径的有效方法，是一种按 递增次序产生诸顶点的最短路径算法。2.已经一棵完全二叉树中共有653个结点，则该树中共有 个分支结点。3.数据的存储结构被分为顺序结构、链接结构、 和 四种。4.中缀表达式3*x+(45-6)所对应的后缀表达式为 。5.从一棵二叉搜索树中查找一个元素时，若给定值等于根结点的值，则表明 ，若给定值小于根结点的值，则继续向 查找，若给定值大于根结点的值，则继续向 查找。6.当从一个最小值堆中删除一个元素时，需要把 元素填补到 位置，然后再按条件把它逐层 调整。7.具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 和 。8.在一棵13阶的B_树中，每个非树根结点的关键字数目最少允许为 个，最多允许为 个。三、 应用题（共50分）1 （10分）利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange)(4) L4(apple), (pear), (banana), orange)(5) L5(apple, (pear, (banana), orange)2 （10分）采用直接插入排序算法, 对关键字序列(46, 32, 55, 81, 65, 11, 25, 43)按从小到大的次序进行排序, 写出每趟排序的结果，并给出总的交换次数。3 （15分）已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树，并给出后序遍历的结果。4 （15分）设一个无向图的邻接矩阵如下：1） 画出该图2） 画出由顶点A出发的深度优先搜索树3） 画出由顶点A出发的广度优先搜索树A B C D E F G HA 0 1 1 1 0 0 1 1 B 1 0 1 0 0 0 0 0C 1 1 0 1 1 0 0 0D 1 0 1 0 1 1 0 1E 0 0 1 1 0 1 0 0F 0 0 0 1 1 0 1 0G 1 0 0 0 0 1 0 1H 1 0 0 1 0 0 1 0四算法设计题（共50分）1 （15分）有n个无序整数（n0，且可能重复）存放在单链表中，请用插入排序方法重新排序，并且删除链表内重复的元素。函数原型为：struct LinkList int data； LinkList *next; ;void Sort(LinkList *h)2 （20分）若用二叉链表作为二叉树的存储表示，试针对以下问题编写算法：(1) 统计二叉树中叶结点的个数。(2) 以二叉树为参数，交换每个结点的左子女