02331数据结构201201真题及答案.docx

《02331数据结构201201真题及答案.docx》由会员分享，可在线阅读，更多相关《02331数据结构201201真题及答案.docx（8页珍藏版）》请在优知文库上搜索。

1、2012年1月高等教育自学考试全国统一命题考试数据结构试题课程代码：02331考生答坦注意事项:V本卷所存试卷必须在答题卡上作答，答在试卷和生稿次上的无效.2 .第一部分为选择联.必须对应试签上的题号使用？B伯策将“答驮卡”的相应代码涂照,3 .第二部分为非选择8S.必须注明大、小题号，使用05考米黑色字迹宅作答.4合理安排咨SS空间,超出冬题区域无效.一、单项选择题(本大题共15小题,每小题2分，共30分)在每小SS列出的四个备选项中只有一个是符合踵目要求的，请将其代码填写在题后的话号内.错选、多选或未选均无分。1 .每个结点有且仅有一个口接前趋和多个(或无)直接后继(第一个站点除外)的数据

2、结构称为A.树状结构B.网状结构C线性结构D层次结构算时间的存储结构是A.单链表C.仅有头指针的单循坏链表3 .已知一个栈的入栈序列是1,2.3,则P1.是AiC.n-i+14 .下面关于率的叙述中，正确的是A.串是-种特殊的雄性表C空串就是空白申2 .某线性表中最常用的操作是在最后一个元素之不插入元素和删除第一个元素，则最节省运B.双链表D.仅有尾指针的单循环链表n,其怆出序列为ap：.P3.，p.若P1.是B.n-iD.不确定B.中中元素只能是字母D.邓的长度必须大于零5.无向完全图Gn个结点则它的边的总数为A.n2B.n(n-I)C.n(nX2D.(n-I)6.若一棵二叉树有10个度为2

3、的结点，S个度为1的结点，则度为0的结点数是A.9B1.1.C.15D.不确定7,如图所示，在下面的4个序列中，小存今深度优先遍历的序列是GA.acfdcb/TB.aebdfcQCC.acd11x:-七D.acfdbc三7三8 .无论待排序列是否有序，排序算法时间复杂度椰是0(?)的排序方法是A快速排序B.归并排序C日泡排序D.直接选择排序9 .已知二叉排序树G,要输出其结点的行序序列,则采用的遍切方法是A.按层遍历B.前序遍历C.中序遍历D后序遍历IOJI1.ISAM和VSAM组织的文件椰属于A,做列文件B.索引Iffi序文件C索引非顺序文件D.多关烧字文件H.对序列(15,9.7,8.20

4、,-1.4)进行排序，第一趟排序后的序列变为(4,9,-1,8,20.7,15),则采用的排序方法是A.选择B.快速C希尔D.日泡12.当采用分块查找时数据的组织方式为A.数据分成数干块,每块内数据有序B.数据分成若干生，行块中数据个数必须相同C.数据分成若干块，斑块内数据有序，块间是否有序均可D.数据分成若干块,每块内数据不必有序，但块间必须有序3下述编码中不是前缀码的跄A.(01.10,II)B.(0.I.00.II)C.data=-IB.p-next=NU1.1.C.p-next-ncxt=hcadD.p-next=head二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格

5、1分，共20分)请在福个空格中填上正曲答案。错填、不填均无分.16 .在数据的逻辑结构和存储结构中,与计算机尢XIJ拈17 .线性发1.=(a1.,a2,，M用数组表示，假定捌除衣中任一元素的概率相同，则删除一个元素平均衢要移动元素的个数是。18 .设循环队列的容量为S0(序号从0到49),现经过一系列的入队和出队运算后，有front=,rcar=29:firont=29.rear=11：在这两种情况下.循环队列中的元索个数分别是和.19 .设T和P是两个给定的申，在T中寻找等于P的子申的过程称为.20 .已知三时角矩阵A01.0)的每个元素占2个挈元，现将其三条对角线上的元素逐行存储在起始地

6、址为KX)O的连续的内存单元中，则元素A6117J的地址为_21 .若以(4,5,6.7,8)作为叶子结点的权值构造哈夫蚣树，则共帝权路径尺度是.22 .有向图G如图所示，它的两个拓扑排序序列分别为和。23 .一组记录的关键字为(46,79.56.38,40,84),则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为“24 .已知广义表A=(x.(a,b),c.),函数hcad(hcad(tai1.（八）)的运算结果是.25 .索引顺序文件既可以顺序存取，也可以,三、解答题(本大题共4小题,卷小题5分,共20分)26 .对关键字序列(26.18.60.14,7.45.13.32)进行

7、降序的堆排序,写出构建的初始堆(小根堆)及前两梢曲建堆之后序列状态.初始堆；第一族第二检27 .设散列函数为H(key尸key%II.散列地址空间为01.0,对关键字序列(27.13,55,32,18,49,24,38.43)用戏性探食法解决冲突，构建微列表。现己有前4个关键字构建的汝列表如卜所示，请将剩余5个关键字埴入表中相应的位置，01234567891055II13III27IIIII3228 .己如一棵二叉树的前序洒历和中用溺历序列分别为：ABCDEFG和CBDAEGF,请日出此二叉树.并给出后序遍历序列29 .已知如图所示的带权无向图，请国出用普里姆算法从顶点I开始的酸小生成树的构造

8、过B29ffi四、算法阅读题(本大题共4小题，每小Jg5分，共20分)30 .阅读下列算法,并回答卜列问题：(1)简述该算法的功能：(2)写出分别输入字符中：abcba”和Fbcbdc-,四用算法解数的返回位.i11tSymineiry(Void)inii=O.j.k:.charstrXO:ScqScacks：IniiStack(As);gets(str)：whi1.e(stri!,0,)i+:f0=OWj)push(&s.s(r(j)；if(i%2!=0)k=i2+he1.sek=i/2：for(j=kiy)if(sirjJ!=poMs)return0；return1：(1)(2)31.下列

9、算法是利用二分查找方法在理濮有序表R中插入元素x并保持表R的有序性.请在空缺处埴入适当的内容，使其成为一个完整的修法，typcdcfstruct(KcyTypckey：InfbTyepoherinfb;IRecType：typcdcfRccIypcScq1.ist(MvoidBinInSCn(SCq1.iRjnt*n,RccTypcx)i11Iow=I.high=*11:intmid*i;whi1.e(1.owR(mid.key)Qj1.：e1.se：)for(i=*n:i=1.ow;i-)Ri+1.=Ri:；+(*n):I(1)(2)(3)32.阅读下列打法，并叵1答下列问咫：(I)局述该豫

10、法中标号$1所指示的循环语句的功能：(2)简述该算法中标号s2所指示的循环语句的功能。1.ink1.ist!nscrtmnodc(1.ink1.isthead,charintm)(1.inkNodetrp.*q.拿s;inii:charch：p=hcad-next:si：whi1.e(pp-data!=x)p=pnex(:if(p=NU1.1.)prin1.f(HerrortnM)：e1.se(q=p-ncxt:s2：for(i=1.;idata=ch:pncxc=s:p=s;)p-ncxt=q：returnhead：I(1)(2)33.回读下列算法，并回答下列问题；(1)该算法采用的是何种持

11、序方法？Q)竟法中的Rn+1的作用是什么？typc(fcfstruct|Key1.ypekey：InfT),pcuherinfo;IRccTypc:typcdcfRccTypcScq1.iM|M：voidMMKSeq1.isiR,imn)j7n=kk-)if(Rk.keyRk+1.key)(Rn1.=R(k:for(i=k+1.：Ri.kcyRn+1.kcyj+)Ri1.=Ri;Rfi-1.=Rn+1.sI(1)(2)五、算法设计题(本题10分)34.假设以总链表表示雄性衣，单钺表的类型定义如下：typedefstructnode(DataTypedata：Structnode*ncxt;1.

12、inkNode.*1.ink1.iM;编写总法，在一个头指针为headH.带头结点的单链表中，加除所有结点数据域值为X的结点，函数原型为：1.ink1.istdc1.nodc(1.ink1.isthead.Datatypex)编号：1葩密后用前2012年1月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考F（课程代码02331）一、第理论择Bt（本大整共IS小I1.每小S1.2分，共30：6.B11.C2.D3.C4.A7.A8.D9.C10.BIS.D12.D13.B14.A二、填空M（本大越共IO小题，督小U2分,若有为个空格.219.稹式匹配（匹配）21.69a4oXjJ后序遇

13、历序列：CDBGFEA【惮分参考】百对二叉相3分，遍历序列2分.数据结构试原答案及评分参考第11三、解答E（十大超共4小H,每小H5分，共20分）26.初妁7,14.13.26.18.45.60.32M*-a；13.14.32.26,18,4$.60,7第二座：14,18.32.26.60.45.13.75SI43I13I24：8；38I【评分B考】每堪对一个敷给I分.28.二叉树为：29.量小生成材的构造过程【部分旁】糠一步一分.四、算法圆读（本大量共4小M每小以5分，共20分）30.1）函数的功能是判断输入的字符事是否为中心对称（即冏文）（2分）J（2）输入字符串-bcbT,落效）&回1,说明是回文：西输入字符*-Mbde”则返回。值,说明不是回文.（