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

第1页共11页南昌大学南昌大学南昌大学南昌大学2010201020102010～～～～2011201120112011学年第一学期期末考试试卷学年第一学期期末考试试卷学年第一学期期末考试试卷学年第一学期期末考试试卷试卷编号：((((AAAA))))卷课程编号：课程名称：数据结构考试形式：闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人签名题分20202020303030303030303020202020100100100100得分考生注意事项：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-607000024000180001500002.已知一棵二叉树的中序序列和后序序列分别如下，请画出该二叉树。中序序列：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页数据结构AAAA卷答案一、选择题（每小题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.1111C2222B3333C4444A5555B6666B7777C8888C9999A10101010C11111111C12121212A13131313C14141414B15151515A16161616C17171717B18181818C19191919B20202020C021414-6207252433184115第9页共11页2.3.3.3.3.3040510015122=5*3+10*3+12*3+15*3+30*2+40*2=266pl=5*3+10*3+12*3+15*3+30*2+40*2=266pl=5*3+10*3+12*3+15*3+30*2+40*2=266pl=5*3+10*3+12*3+15*3+30*2+40*2=2664.4.4.4.V1V2V5V4V3以V1为出发点，对图进行广度优先搜索V1-V2-V4-V5-V3V1-V2-V4-V5-V3V1-V2-V4-V5-V3V1-V2-V4-V5-V3ABCDEFHGJKIL第10页共11页5.5.5.5.46257837296270126.6.6.6.24242424，25252525，21212121，15151515，【27272727】，47474747，68686868，35353535，8484848415151515，21212121，【24242424】，25252525，【27272727】，35353535，【47474747】68686868，84848484四、算法设计题(每小题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;第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);}