南昌大学-数据结构-2010～2011学年第一学期期末试卷与答案A

第1页共11页南昌大学2010～2011学年第一学期期末考试试卷试卷编号：(A)卷课程编号：课程名称：数据结构考试形式：闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人签名题分20303020100得分考生注意事项：1、本试卷共8页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题(每题1分，共20分)得分评阅人1.算法必须具备输入、输出和___________。A.计算方法B.排序方法C．解决问题的有限运算步骤D.程序设计方法2.设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是___________。A．23415B.54132C．23145D.154323.用链表表示线性表的优点是___________。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4.若某线性表的常用操作是取第i个元素及其前趋元素，则采用___________。存储方式最节省时间A.顺序表B.单链表C.双链表D.单向循环第2页共11页5.串是任意有限个___________。A.符号构成的序列B.字符构成的序列C.符号构成的集合D.字符构成的集合6.设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为___________。A.23B.33C.18D.407．在一个单链表中，若p结点不是最后一结点。在p结点之后插入s结点的正确是。A.s-next=p;p-next=s;B.s-next=p;p=pC.s-next=p-next;p-next=s;D.p-next=s;s-next=p;8.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为。A.24B.25C.23D.无法确定9.在一棵二叉树中有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有个结点A、79B、76C、56D、8110.深度为5的二叉树至多有个结点。A.16B.32C.31D.1011．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是_________。A.直接选择排序B.直接插入排序C.快速排序D.起泡排序12．二分查找要求节点。A．有序、顺序存储B.有序、链接存储C．无序、顺序存储D.无序、链接存储13．在一个无向图中，所有顶点的度数之和等于图的边数的倍A．1/2B.1C.2D.414.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是_________________A.插入排序B.冒泡排序C.快速排序D.归并排序15．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有______________个A.33B.34C.32D.30第3页共11页16．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为_______________。A.60B.66C.67D.5017.对一棵二叉排序树进行____________遍历得到的结点序列是一个有序序列。A.前序B.中序C.后序D.层序18．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，______________次比较后查找成功。A.1B.2C.4D.819．就平均查找速度而言，下列几种查找速度从慢至快的关系是___________。A.顺序折半哈希分块B.顺序分块折半哈希C.分块折半哈希顺序D.顺序哈希分块折半20.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用______________排序法。A.冒泡排序B.快速排序C.堆排序D.选择排序二、填空题(每空2分，共30分)得分评阅人1.设r指向单链表最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是r-next=s;r=s;____【1】_______。2.数据的逻辑结构分为两大类，它们是线性结构和____【2】___。3．已知循环队列用数组data[n]存储元素值，用front,rear分别作为头尾指针，则当前元素个数为_____【3】____。4.一棵二叉树有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有【4】个结点；若完全二叉树共有100个结点，则其叶子结点数为【5】。5.在带头结点单链表L中，表空的条件是____【6】_____。6.在一个长度为n的顺序表中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移____【7】___个元素。7.设一个链栈的栈顶指针为ls，栈中结点格式为info│link，栈空的条件是____【8】___。若栈不空，则退栈操作为p=ls；____【9】______；free(p)。8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，___【10】____最省时间，___【11】___最费时间。9.图的遍历方式通常有【12】遍历和【13】遍历两种。第4页共11页10.下面是将键值为X的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedefstructnode*pnodestructnode{intkey;pnodeleft,right;}voidsearchinsert(intx;pnodet);//t为二叉排序树根结点的指针//{if(____【14】______){p=malloc(size);p-key=x;p-left=null;p-right=null;t=p;}elseif(xt-key)searchinsert(x,t-left)else_______【15】_________;三、应用题(每小题5分，共30分)得分评阅人1.对于下面的稀疏矩阵，画出其三元组法存储表示(假设下标从0开始)。00140000000-6070000240001800015000027.2.已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA第5页共11页3.给定权值{5,10,12,15,30,40},构造相应的哈夫曼树，并写出他的带权路径长度。4.已知一个无向图的邻接表为:画出这个图，并以V1为出发点，对图进行广度优先搜索，写出遍历序列。5.已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉排序树。第6页共11页6.有一组键值27,84,21,47,15,25,68,35,24,采用快速排序方法由小到大进行排序，请写出每趟的结果。四、算法设计题(每小题10分，共20分)得分评阅人1.试写出逆转线形单链表的算法，单链表节点的类型定义如下。Typedefstructnode{elemtypedata;//数据域structnode*next;//指针域}第7页共11页2.采用顺序结构存储串，设计一个算法strcmp(s,t)实现串的比较，串的比较以词典方式进行，当s大于t时，返回1，当s等于t时，返回0，当s小于t时，返回-1，顺序串的类型定义如下：#defineMaxsizeTypedefstructsqstring{charch[Maxsize];//存放串字符；intlen;//存放串的实际长度；}第8页共11页数据结构A卷答案一、选择题（每小题1分，共20分）得分评阅人二、填空题（每空2分，共30分）得分评阅人【1】r→next=null【2】非线性结构【3】（rear-front+n）%n【4】79【5】51【6】l→next=null【7】n-i+1【8】ls==null【9】ls=ls→link【10】冒泡【11】快速【12】深度【13】广度【14】t=null【15】searchinsert(x,t→right)三、应用题(每小题5分，共30分)得分评阅人1.1C2B3C4A5B6B7C8C9A10C11C12A13C14B15A16C17B18C19B20C021414-6207252433184115第9页共11页2.3.Wpl=5*3+10*3+12*3+15*3+30*2+40*2=2664.以V1为出发点，对图进行广度优先搜索V1-V2-V4-V5-V3V1V2V5V4V330405100001512222ABCDEFHGJKIL第10页共11页5.6.24，25，21，15，【27】，47，68，35，8415，21，【24】，25，【27】，35，【47】68，84四、算法设计题(每小题10分，共20分)得分评阅人1.node*Revers(node*head){node*p,*q;p=head-next;head-next=NULL;while(p!=NULL){q=p;p=p-next;q-next=head-next;head-next=q;}returnhead;}2.intstrcmp(sqstring*s,sqstring*t){inti,minlen;if(s→lent→len)minlen=s→len;elseminlen=t→len;i=0;4625783729627012第11页共11页while(iminlen){if(s→ch[i]t→ch[i])return(-1);elseif(s→ch[i]t→ch[i])return(1);elsei++;}if(s→len==t→len)return(0)elseif(s→lent→len)return(-1)elsereturn(1);}