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

你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。==============================================================================PAGE命运如同手中的掌纹，无论多曲折，终掌握在自己手中==============================================================科目名称：数据结构1Ｏ八-Ｏ九学年第一学期申请广州大学学士学位抽考课程试卷（Ｂ）课程名称数据结构考试形式（闭卷）系别专业班级学号姓名试题一二三四五六总分评卷人分值2010203020100得分考试时间：2009年1月日答题时间：120分钟考试地点：考试形式：闭卷一、单项选择题(每题只有一个正确答案,每题１分,共２０分）分值20得分为了实现图的深度优先遍历，其非递归的深度优先搜索算法使用的一个辅助数据结构为（）。A.栈 B.队列 C.二叉树 D.树设无向图的顶点个数为n，则该图最多有（）条边。A.n-1 B.n(n-1)/2 C.n(n+1)/2 D.n(n-1)有向图的一个顶点的度为该顶点的（）。A.入度B.出度C.入度与出度之和D.(入度+出度)/2如果一个元素序列基本有序时，则选用（）方法较快。A．直接插入排序B.直接选择排序C.堆排序D.快速排序利用5个值作为叶节点的权生成的哈夫曼树中共计有（）个节点。A．10B.5C在对n个元素进行快速排序的过程中，第一次划分最多需要交换（）对元素。A．「n/2」B.n-1C.nD.n+1在对n个元素进行直接选择排序的过程中，需要进行()趟选择和交换。A．nB.n+1C.n-1D.n/2下列排序算法中，____算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

A、堆排序 B、冒泡排序

C、快速排序 D、直接插入排序排序二叉树的_______遍历的序列是一个以关键字的递增的有序序列A、先根遍历 B、中根遍历 C、后根遍历 D、层次遍历在二叉搜索树中查找一个元素时，其时间复杂度大致为（）。A．O（n）B.O（1）C.O（log2n）D.O（n2）一个栈的输入序列是1,2,3，则栈的不可能的输出序列是_________。A.3,2,1B.2,1,3C.3,1,2D.

下面的二叉树中,__________是满二叉树.A.B.C.D.有6个结点的无向图至少应有_______条边才能确保它是一个连通图。A．5B．6C．7D．8下面程序段的时间复杂度是()for(i=0;i<n;i++)for(j=1;j<m;j++)A[i][j]=0；A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是()A.快速排序B.堆排序C.归并排序D.基数排序一个数组元素a[i]与（）的表示等价。A.*(a+i) B.a+i C.*a+i D.&a+i含有n个结点的完全二叉树的深度为()。A．[log2n]B．[log2n+1]C．[log2(n+1)]D.[log2n]+1已知某二叉树的后序遍历结果是dabec，中序遍历结果是debac，它的前序遍历结果是()。A．acbedB．deabcC．decabD．cedba假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未满，当元素x进栈时所执行的操作为（）。A.a[--top]=x;B.a[top--]=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．（）哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。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<A[mid])__________________________; else______________________________;}else_______________________________;}}2、下面函数的功能是返回二叉树BT中值为X的节点所在的层号,空树的层号为0,根节点的层号为1,以此类推： intNodeLevel(BinTreeNode*BT,intx){ if(BT==NULL)return0; elseif(BT->data==X)______________; else{ intc1=NodeLevel(BT->left,x); if(c1>=1); intc2= if()return; else return0;}}四．应用题（每题10分,共30分）分值30得分1、已知图的邻接矩阵,请画出该图,并画该图的邻接表。 0∞∞∞∞∞ 32012∞∞18 ∞∞0∞66∞ 4135∞0∞∞ ∞∞∞350∞ 56∞∞282302.以下面数据(5，6，7，8，9，10，15，18，2232)作为叶子结点的权值构造一棵哈夫曼树，并计算其带权路径长度。3．对于给定的一组键值：15、61、79、39、57、86、45、73、22、23，画出二路归并排序的各趟排序结果。五．编写算法（每题10分）