2008数据结构学位考试试卷B.doc

《2008数据结构学位考试试卷B.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Ｏ八-Ｏ九学年第一学期申请广州大学学士学位抽考课程试卷（Ｂ）课程名称数据结构考试形式（闭卷）系别专业班级学号姓名试题一二三四五六总分评卷人分值2010203020100得分考试时间：2009年1月日答题时间：120分钟考试地点：考试形式：闭卷一、单项选择题(每题只有一个正确答案,每题１分,共２０分）分值20得分1．为了实现图的深度优先遍历，其非递归的深度优先搜索算法使用的一个辅助数据结构为（）。A.栈B.队列C.二叉树D.树2．设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)3．有向图的

2、一个顶点的度为该顶点的（）。A.入度B.出度C.入度与出度之和D.(入度+出度)/24．如果一个元素序列基本有序时，则选用（）方法较快。A．直接插入排序B.直接选择排序C.堆排序D.快速排序5．利用5个值作为叶节点的权生成的哈夫曼树中共计有（）个节点。A．10B.5C.9D.46．在对n个元素进行快速排序的过程中，第一次划分最多需要交换（）对元素。A．「n/2」B.n-1C.nD.n+17．在对n个元素进行直接选择排序的过程中，需要进行()趟选择和交换。A．nB.n+1C.n-1D.n/28．下列排序算法中，____算法可能会出现下面情况：初始数据有

3、序时，花费的时间反而最多。 A、堆排序B、冒泡排序 C、快速排序D、直接插入排序9．排序二叉树的_______遍历的序列是一个以关键字的递增的有序序列A、先根遍历B、中根遍历C、后根遍历D、层次遍历10．在二叉搜索树中查找一个元素时，其时间复杂度大致为（）。A．O（n）B.O（1）C.O（log2n）D.O（n2）11．一个栈的输入序列是1,2,3，则栈的不可能的输出序列是_________。A.3,2,1B.2,1,3C.3,1,2D.1,3,21．下面的二叉树中,__________是满二叉树.A.B.C.D.2．有6个结点的无向图至少应有___

4、____条边才能确保它是一个连通图。A．5B．6C．7D．83．下面程序段的时间复杂度是()for(i=0;inext;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;5．在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()A.快速排序B.堆排序C.归并排序D

5、.基数排序6．一个数组元素a[i]与（）的表示等价。A.*(a+i)B.a+iC.*a+iD.&a+i7．含有n个结点的完全二叉树的深度为()。A．[log2n]B．[log2n+1]C．[log2(n+1)]D.[log2n]+18．已知某二叉树的后序遍历结果是dabec，中序遍历结果是debac，它的前序遍历结果是()。A．acbedB．deabcC．decabD．cedba9．假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。A.a[--top]=x;B.a[top

6、--]=x;C.a[++top]=x;D.a[top++]=x;二．是非题（每题1分,正确打“√”,错误打“×”)分值10得分1．（）在单链表R结点之后插入S结点的操作是：R->next=S；S->next=R->next；2.（）栈是FIFO的线性表。3.（）哈希法是一种重要的存储方法，也是一种常用的查找方法；4．（）二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树；5．（）图的遍历结果是唯一的；6．（）最短路径是各边长度之和；7．（）二叉树第k层上的结点数目最多为2k-1(即：2^(k-1),其中k>=1)；8．（）哈夫曼树是带权路径长度最

7、短的树，路径上权值较大的结点离根较近。9．（）拓扑排序是唯一的，主要是为了得到一个线性排序序列；10．（）冒泡排序的时间复杂度是O(N2)。三．算法填空（每空2分）分值20得分1.二分查找非递归算法,在A[0]~A[n-1]区间查找关键字为k的元素。intBinsch(intA[],intn,intk){intlow=0,high=n-1;if(_____________________){intmid=(low+high)/2;if(k==A[mid])________________________;elseif(k

8、___________________;else______________________________