搜索
学院：专业：学号：姓名：教学班号：云南农业大学2010—2011学年上学期期末考试数据结构试卷（A卷）（课程代码3111003）本试题满分100分，考试时间120分钟。题号一二三四五六七八总分得分阅卷人一．选择题。（每小题2分，共40分）1．组成数据的基本单位是（）。(A)数据项(B)数据类型(C)数据元素(D)数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={1，2，2，3，3，4，4，1}，则数据结构A是（）。(A)线性结构(B)树型结构(C)图型结构(D)集合3．数组的逻辑结构不同于下列（）的逻辑结构。(A)线性表(B)栈(C)队列(D)树4．二叉树中第i(i≥1)层上的结点数最多有（）个。(A)2i(B)2i(C)2i-1(D)2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。(A)p-next=p-next-next(B)p=p-next(C)p=p-next-next(D)p-next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。(A)6(B)4(C)3(D)2第1页（共7页）密封线装订线7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。(A)100(B)40(C)55(D)808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。(A)3(B)4(C)5(D)19．根据二叉树的定义可知二叉树共有（）种不同的形态。(A)4(B)5(C)6(D)710.设有以下四种排序方法，则（）的空间复杂度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序11．下面关于线性表的叙述错误的是（）。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现12．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m13．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M14．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。(A)BADC(B)BCDA(C)CDAB(D)CBDA15．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-116．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。(A)9(B)10(C)11(D)12第2页（共7页）17．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。(A)n-1(B)n(C)n+1(D)2n-118．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，819．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，8520．下面程序的时间复杂为（）for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)二．填空题。（每空1分，共15分）。1.通常从四个方面评价算法的质量：_________、_________、_________和_________。2.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）3.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。4.数据的物理结构主要包括_____________和______________两种情况。5.完全二叉树中第5层上最少有__________个结点，最多有_________个结点。6.数据的最小单位是。7.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。第3页（共7页）三．阅读算法题（第1题10分，第2题5分，共15分）。1.LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L-next){q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。2.阅读以下二叉树操作算法，指出该算法的功能。TemplatecalsstypevoidBinTreeType：：unknown(BinTreeNodeType*t){BinTreeNodeType*p=t,*temp;if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}该算法的功能是：___________________________四．算法、设计题。（每题题10分，共30分）。1.写出选择法排序的算法或程序。（5分）2.设计在单链表中删除值相同的多余结点的算法。（10分）3.已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，.试写出这棵二叉树的后序遍历结果；并生成此二叉树；利用生成的二叉树对1001011001010110加密，写出密文。（15分）第4页（共7页）云南农业大学2010—2011学年上学期期末考试数据结构试卷（A卷）（课程代码3111003）答题卡班级：学号：姓名：题号一二三四总分得分阅卷人一．选择题。（每小题2分，共40分）12345678910CCDCACCBBB11121314151617181920DBCAACBCAB二．填空题。（每空1分，共15分）。12正确性易读性强壮性高效率有序34ABDECFDBEAFCDEBFCA顺序存储结构链式存储结567116数据项O(n2)O(nlog2n)三．阅读算法题（第1题10分，第2题5分，共15分）。1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）2.交换二叉树的左右子树的算法第5页（共7页）四．算法、设计题。（每题10分，共30分）。1.FORI=1TON-1FORJ=I+1TONIFA(I)A(J)T=A(I)A(I)=A(J)A(J)=TENDIFNEXTJNEXTI3.后续遍历为：EDCBIHJGFA加密后密文为：343743572四．算法、设计题。（共30分）。1.写出冒泡法排序的算法或程序。（5分）2.设有两个有序集合A和B，要求设计生成有序集合C=A∪B，其中集合A、B和C用链式存储结构表示。（10分）3.已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，(1)写出这棵二叉树的后序遍历结果；(2)生成此二叉树；(3)利用生成的二叉树对1001011001010110加密，写出密文。（15分）1.解:voidbubble(intr[n]){for(i=1;i=n-1;i++){for(exchange=0,j=0;jn-i;j++)，if(r[j]r[j+1]){temp=r[j+1];r[j+1]=r[j];r[j]=temp;exchange=1;}if(exchange==0)return；}}第6页（共7页）2:typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next){for(q=hb;q!=0;q=q-next)if(q-data==p-data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-next=hc;hc=t;}}}3:后续遍历为：EDCBIHJGFA加密后密文为：343743572二．判断题。（每小题2分，共20分）。1.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）6．层次遍历初始堆可以得到一个有序的序列。（）7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）8．线性表的顺序存储结构比链式存储结构更好。（）9．中序遍历二叉排序树可以得到一个有序的序列。（）10.快速排序是排序算法中平均性能最好的一种排序。（）12345678910对对对对错错对错对对第7页（共7页）第8页（共页）第9页（共页）第10页（共页）第11页（共页）第12页（共页）