试卷代号:1010中央广播电视大学2009座位号2010学年度第二学期\"开放本科\"期末考试数据结构试题2010年7月题号一一一一一一四五/-i、-总分分数得分i评卷人-、单项选择题(在括号内填写所选择的标号。每小题2分，共18分}1.输出一个二维数组b[m][o]中所有元素的时间复杂度为()。A.0(0)B.O(m+o)C.0(0D.2)Oem祷0)2.在一个长度为n的顺序存储的有序表中搜索值为x元素时，其时间复杂度最好情况为()。A.00)C.O(lOg20)B.O(Jn)D.0(0)3.当利用大小为n的数组顺序存储一个战时，假定用top==n表示钱空，则向这个战插入一个元素时，首先应执行()语句修改top指针。A.top十十pB.top-一;C.top=O;4.在一棵树中，()没有前驱结点。D.top=1;A.树枝结点C.树根结点B.叶子结点D.单分支结点715.已知一棵树的边集表示为{
,,,,,)。假定树根结点的深度为0。,，}，则该树的深度为(A.2C4R3D.5)条边。6.n个顶点的连通图中至少含有(A.n-1RnC.n(n-I)/2D.n(n-I))条边。7.对于一个具有n个顶点的无向图，该图最多有(A.Cn-1n(n十I)/2B.n(n-I)/2D.n(n-I)8.在采用开散列法(即链接法〉解决冲突时，每一个散列地址所链接的同义词子表中各个表项的()的值都相同。A.关键码B.非关键码C散列函数D.某个域9.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与()有关。A.nB.mn祷mC.n/m得分|评卷人D.二、填空题(在横线处填写合适的内容。每小题2分，共14分}1.在链表中进行数据元素的插入和删除不需要移动结点，只需要改变相应结点的的值。2.队列是一种限定在表的一端插入，而在另一端删除的线性表，它又被称为表。3.如果一个过程直接地调用自己，则称这个过程是一个的过程。。假定4.假定一棵三叉树(即度为3的树)的结点个数为25，则它的最小高度为树根结点的高度为0。725.在一个堆的顺序存储中，若一个元素的下标为i(i~O)，则它的左子女元素的下标为。6.根据n个元素建立一棵二叉搜索树的时间复杂度大致为7.快速排序在最坏情况下的空间复杂度为。得分|评卷人三、判断题(在每小题后面的括号内打对号\"~\"表示叙述正确或打叉号\"X\"表示叙述错误。每小题2分，共14分)1.在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。()2.用非递归方法实现递归算法时一定要使用临时数据棋。()3.在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行中序遍历和后序遍历，将具有相同的结果。()4.在顺序表中进行顺序搜索时，若各元素的搜索棋率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。())5.快速排序算法在平均情况下的时间复杂度为O(nlog2时。(6.直接选择排序是一种不稳定的排序方法。()7.在具有n个结点的二叉树的链接存储中，所有结点的指针域的总数小于2n个。()得分|评卷人四、运算题{每小题6分，共30分)1.假定一棵普通树的广义表表示为a(b(时，c(f，g，d»，试分别写出对其进行先根和按层遍历的结果。先根:按层:2.假定一维数组a[10]中存储着有序表(15，26，34，39，45，56，58，63，74，76)，试根据折半搜索所对应的判定树，给出该判定树中叶子结点数，以及在等概率情况下的平均搜索长度。叶子结点数:平均搜索长度:733.已知一个图的顶点集V和边集G分别为:V={O,1,2,3,4,5};E={(O，口，(1，2)，(1，3)，(2，的，(2，日，(3，5)};假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点2出发进行深度优先搜索和广度优先搜索所得到的顶点序列。深度优先搜索序列:广度优先搜索序列:4.已知一个带权图的顶点集V和边集G分别为:V={O,1,2,3,4,5};E={(O，1)19，(O，2)10，(O，3)14，口，2)6，(1，5，)5，(2，3)26，(2，4)15，(4，5)8};试根据迪克斯特拉(Dijkstra)算法求出从顶点O到其余各顶点的最短路径长度。顶点:最短路径长度:O12345O山FE如tt要卜←Al啤集合如nu14o。nnu0quqL，-L6,\",FDPOJ。哇A。O结出进行归并书序的过h-的据AA町拥中每Fi中-一时rm数口臼表ω)间)眈u2指n哇A也哇0oou)α)u)u)74程得分|评卷人五、算法分析题{每小题8分，共16分}1.指出下面算法的功能，假定f为单链表的表头指针，在算法中的getLink()函数返回结点指针域link的值，getData()函数返回结点数据域data的值。ElemTypeFF(ListNode祷f)if(f==NULL)return0;elsereturnFF(f一>getLink())+f一>getDataO;算法功能:2.该算法功能为t从表头指针为L的单链表中删除与X值相同的所有结点。单链表中的结点结构为(data，link)。阅读算法，在划有横线的上面填写合适的内容。voidpurge_linkst(ListNode快&.L,intX)if(L==NULL)return;ListNode铃p，祷pI，势p2;p=pl=newListNode;pI一>link=p2=L;while(p2)if(p2一>data==X){pI一>link=p2一>link;deletep2;else{pl=p2;L=p一>link;deletep;75得分|评卷人六、算法设计题(8分)已知f为单链表的表头指针，单链表中的结点结构为(data，link)，并假定每个结点的值均为大于O的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最小值，若单链表为空则返回数值0。intMin(LinkNode76。势;试卷代号:1010中央广播电视大学20092010学年度第二学期\"开放本科\"期末考试数据结构试题答案及评分标准(供参考)2010年7月-、单项选择题{在括号内填写所选择的标号。每小题2分，共18分}l.D2.A3.B4.C5.B6.A7.B8.C9.C二、填空题(在横线处填写合适的内容。每小题2分，共14分}1.指针域2.先进先出3.递归4.35.2i十16.0(nlog2n)7.O(n)三、判断题{在每小题后面的括号内打对号\"..J\"表示叙述正确或打叉号\"X\"表示叙述错误。每小题2分，共14分)1.错2.错3.对4.对5.对6.对7.错四、运算题(每小题6分，共30分}1.先根:a，b，e，c，f，g，d//3分按层:a，b，c，e，f，g，d//3分2.叶子结点数:3//3分平均搜索长度:29/10//3分3.深度搜索序列:2，1，0，3，5，4//3分广度搜索序列:2，1，4，5，0，3//3分774.每个数据1分，全对给6分。顶点:OO116210314425521最短路径长度25.分步给分，共6分(0)<30182015381244534686J(1)[1830J[1520J[1238J[4453J[4686J//1分(2)[15182030J[12384453J[4686J//1分(3)[1215182030384453J[4686J//2分(4)[12151820303844465386J//2分五、算法分析题(每小题8分，共16分)1.求出井返回链表f中所有结点的值之和。2.p2=pl一>link、p2=p2一>link(或p2=pl一>link)六、算法设计题(8分)评分标准:按注释酌情给分。int如1in(LinkNode祷f)if(f==NULL)return0;//1分if(f一>link==NULL)returnf一>data;//2分inttemp=Min(f一>link);//4分if(f一>datadata;//6分elsereturntemp;//8分78//每空4分