欢迎来到天天文库
浏览记录
ID:61487764
大小:50.00 KB
页数:6页
时间:2021-02-05
《2008数据结构学位考试试卷B.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、O八-O九学年第一学期申请广州大学学士学位抽考课程试卷(B)课程名称数据结构考试形式(闭卷)系别专业班级学号姓名试题一二三四五六总分评卷人分值2010203020100得分考试时间:2009年1月日答题时间:120分钟考试地点:考试形式:闭卷一、单项选择题(每题只有一个正确答案,每题1分,共20分)分值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(k8、___________________;else______________________________
8、___________________;else______________________________
此文档下载收益归作者所有