第页共NUMPAGES3页广东商学院试题纸----------------------------------------------------------------------------------------------------------------一、概念选择（每小题2分，共20分）1．算法分析的目的是________。A．找出数据结构的合理性B．分析算法的效率以求改进C．研究算法中的I/O关系D．分析算法的简明易懂性2．链表不具备的特点是【】。A．可随机访问任一结点B．插入、删除不需要移动数据元素C．不必事先估计存储空间D．所需空间与其长度成正比3．顺序表的首地址是500，每个数据元素的长度为5，则第6个元素的地址是______。A．505B．506C．525D．5304．栈和队列的共同点是【】。A．都是先进先出B．都是先进后出C．没有共同点D．只允许在端点处插入和删除元素5．动态分配的顺序栈为满的判定条件是【】。A．S.top-S.base==S.stacksize;B．S.top==MAXSIZE;C．S.top==0;D．S.top==S.base;6．由3个结点可以构造出【】种不同形态的二叉树。A．2B．3C．4D．57．在一个图中，所有顶点的度数之和等于图的边数的【】倍。A．1/2B．1C．2D．48．关键路径算法用于解决【】问题。A．工程能否顺利完成B．工程完成需要的最短时间C．源点到任一顶点的最短距离D．任意两个顶点之间的最短距离9．在具有n个结点的平衡二叉排序树（BBST）中，查找某个给定关键字失败，其查找长度为【】。A．O(n)B．O(log2n)C．O(n2)D．无法确定10．下列几种排序方法中，【】是稳定的排序方法。A．希尔排序B．快速排序C．归并排序D．堆排序二、计算选择（每小题5分，共50分）1．以下代码的时间复杂度是【】。x=n;y=0;while(x>(y+1)*(y+1))y++;A．O(n)B．O(n2)C．O(log2n)D．O()2．在一个长度为n的顺序表中，在第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动【】个元素。A．iB．n-i-1C．n-iD．n-i+13．设栈S的初始状态为空，元素A,B,C,D,E,F依次进栈，其出栈的顺序是B,D,C,F,E,A，则栈的容量至少应该是【】。A．2B．3C．4D．64．一棵完全二叉树的第9层有200个叶结点，则该完全二叉树最多有【】个结点。A．256B．511C．623D．10005．一棵二叉树的中序遍历序列是{BEDFACG}，先序遍历序列是{ABDEFCG}，则对应的后序遍历序列是【】。A．EDFBGCAB.EFDBCGAC.EFDBGCAD.ABCDEFG6．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有【】个非零元素。A．n-1B．2(n-1)C．n(n-1)/2D．n27．对包含22个记录的有序表进行折半查找，当查找失败时，至少需要比较关键字【】次。A．3B．4C．5D．68．对序列{100,60,80,90,120,130,110}构造二叉排序树，为查找关键字90，分别与以下关键字序列【】进行了比较。A．100,60,80,90B．100,80,90C．100,60,90D．100,120,909．已知哈希函数为H(key)=key%11，哈希表长度为13，用线性探测再散列的方法处理冲突。表中已依次存放了关键字为22、12、24、30、52和43的6个记录，现将关键字63填入哈希表，其哈希地址是【】。A．9B．10C．11D．1210．若一组记录的关键字序列为{46,79,56,38,40,84}，则利用堆排序建立的初始堆为【C】。A．84,56,79,40,46,38B．84,79,56,46,40,38C．84,79,56,38,40,46D．79,46,56,38,40,84三、判断对错（每小题1分，共10分）1．链表方便进行随机查找操作。【】2．递归调用用到的栈不需要用户自己定义。【】3．图的深度优先遍历序列可以是不唯一的。【】4．树的先根遍历相当于对应二叉树的先序遍历。【】5．构造最小生成树的Prim算法适合用于稀疏图。【】6．求源点到其他各顶点最短路径的算法是Dijkstra算法。【】7．对二叉排序树进行平衡化处理的目的是减少平均查找长度。【】8．非同义词之间发生的地址冲突称为二次聚集。【】9．在关键字基本有序的情况下，快速排序是所有排序方法中时间性能最好的。【】10．要在1000个记录中得到按关键字有