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

2011年1月高等教育自学考试全国统一命题考试数据结构试题课程代码：02331一、单项选择题(本大题共IS小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，话将其代码填写在题后的括号内.错选、多选或未选均无分。1 .下列选J中与数据存储结构无关的术语是()A.除序表H.链表C.琏队列D.栈2 .将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是(>A.n-IB.nC.2n-1D.2n3 .已知循环队列的存储空间大小为m.队头指针front指向认头元素,队尾指针rear指向认尾元素的下一个位置,则向队列中插入新元素时,修改指针的操作是()A.rear=(rear-I)%m:B.front=(front+1)%m:C.front=(front-1)%m;D.rcar=(rear+1.)%m;4 .递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是A.地校B.多难数组C队列D.线性表5 .设有两个串P和q其中q是p的子串，则求q在P中首次出现位置的算法称为()A.求子中B.邓联接C申匹配D.求申长6 .对于广义表A,若head（八）等于Iai1.（八）,则表A为()A.()B.()C.().()D.()X).()工行一株具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反,则该二叉构一定是()A.结点均无左孩子的二叉树B.结点均无右孩子的二叉树C高度为n的二叉树D.存在度为2的站点的二叉树8 .若一棵二叉树中度为I的结点个数是3,度为2的结点个数是4.则该二叉树叶子结点的个数是()B.5D.8A.4C.79 .下列叙述中锚误的是(A图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次B.图的泌历可以采用深度优先遍历和广度优先遗历C图的广度优先遍历只适用于无向图1>图的深度优先遍历是一个递归过程IO.已知有向图GNV.E).其中V=V1.V2.V3.V4>>E=(<V1.V2><V1.V3>.<V2.V3>.<V2,V4>.<V3,V4>,图G的拓扑序列是<)A.VI.V2.V3.V4C.VI,V3M,V2B.V1.V3,V2,V4D.V1,V2,V4.V311.平均时间复杂度为(Xn1.og")的稳定排序算法是<)A.快速排序C归并排序B.堆排序D.日泡排序12 .己知关键字序列为，22.83,46.75.18.68.30),对其进行快速排序,第一题划分完成后的关键字序列是(>A.(18,22,30,46,51,68,75,83)C.(46.30.22J8.51.75.68.83)B.(30,18,22,46,51,75,83,68)D<30,22JX.46.51.75.68.83)13 .某索引顺序友共有元素395个,平均分成5块.若先对索引表采用顺序杏找.再对块中元素进行顺序查找,则在等概率情况下,分块查找成功的平均查找长度是()A.43B.79C198D.20014.在含右IO个大键字的3阶B树中进行代找，至多访问的结点个数为(A.2B.3C.4D.515.1SAM文件系统中采用多级索引的目的是(A.提高检索效率C.减少数据的冗余B.提高存储效率D.方便文件的修改二、填空题本大观共10小题，每小Sfi2分，共20分)请在每小迤的空格中填上正确答案.错填、不填均无分.16 .数据结构由数据的逻辑结构、存储结构和数据的一三部分组成.17 .在单链表中某结点后插入个新结点，需要修改个结点指针域的值。18 .设校S的初始状态为宽，若元素a、b、c、d、e、f依次进校，得到的出栈序列是b、d、c、f、e、a,则栈S的容Ift至少是.19 .长度为零的小称为.20 .广义表G=(ab.(c.d,(c.0),G)的氏度为21 .一棵树T采用孩子兄弟流表存储，如果树T中某个站点为叶子结点，则该结点在：房钺表中所对应的站点一定是.22 .一个有n个顶点的无向连通图，最少有条边。23 .当恃排关摄字序列基本有序时.快速排序、简单选择排序和直接插入排序三种持序方法中.运行效率城高的是.24 .在一棵深度为h的具有n个结点的二叉排序树中，青找任一结点的攒多比较次数是25 .不定长文件指的是文件的大小不固定。三. 解答题(本大题共4小题，每小题5分，共20分)26 .已知一棵二叉排序树(结点伯大小按字母啾序)的前序遍历序列为EBACDFHG.请回答下列问题：1)画出此二叉持序树：(2)若将此二又持序树仔作森林的二叉链表存储，诂画出对应的煤林。27 .己却有向图的邻接表如图所示，请回答下面问题：(1)给出该图的辐接矩阵：(2)从结点A出发，写出该图的深底优先遍历序列,28 .已知待排记录的关键字序列为25,96.11.63.57,78,44,请回答下列问题r(1)同出堆排序的初始堆(大根堆)：(2)国出第二次里建堆之后的堆.29 .已知关健字序列为(56.23.41.79.38.62,18).用欣列函数H(kcy)=kcy%1.1.将其散列到散列表HTIO.10中，采用线性探测法处理冲突。谛回答卜列问题：(I)Si出敢列存储后的波列表：(2)求在等概率情况下杳找成功的平均施找长度，四. 算法阅读题(本大题共4小题，每小题5分，共20分)30 .阅读下列程序.voidCMXintA.intn)(inti.j.m;for(i=1.；i<n；i+)for(j=0:j<i:j+)m=(i*n+j):i*n+j1.=Aj*n+iiAj*n*i1.=m:回答下列问题:123耨其按行优先存于一维数姐A中,给出执行函数调已知矩!许B=456789FHfKXA,3)后矩阵B的值:(2)简述函数刖的功能.31 .假设以二叉锥友表示二叉树.其类型定义如下：(ypcdefstructnodechardata;structnode*khi1.d,srchi1.d:左右孩子指针)eBinTrces阅读下列程序。Voicini(BinTrccT)(InitStack(三);初始化一个堆栈Swhi1.e(T!SiackEnipiy(三)(whi1.e(T)(Push(S.T);T=T>1.chi1.d:)if(!StackEmpty(三)请写出执行OI(T)的输出结果：(2)筒述算法门I的功能.32 .问该下列程序.voidf32(intA.intn)(i11ti.j.n*=1.t;for(i=0;i<n-1.&&in;i+)(for(j=0：j<n：j+)printf(*,%d”.Aj):pri11tft"nw)：m=0；for(j=1.;j<n-i;j+)if(A(i-1.1.>AjJ)I1.=A(j-1.);AU-U=A1.j:A(jJ=t;m=1.；)I回答何题：已知整型数组A网34.26.15.89.42),写出执行函数调用132(A3)后的输出结果。33 .J知腋序表的表结构定义如卜：#dcfincMAX1.ENI(X)>pcdcfintKcyIypc;typcdcfstruct(KcyTypekey:InfbTyPeo<berinfb:)Node1.,pe:(VpcdctNodcTypcSq1.iMMAX1.EN;阅读下列程序.Intt33(Sq1.istR,NodcTypcX,intp,intq)(intm;if(p>q)return-I;m=(p+q)/2：if(Rm.kcy=X.kcy)returnm:if(Rm.key>X.key)return3(R.X.p.m-1.);e1.sereurnf33(R,X.m+1.,q);I请回答下列向题：若有序的顺序及R的关犍字序列为(25,13,26,55,80,105),分别写出X.kcy=1.8和X.kcy=26时，执行函数两用C3(R'X,0.6)的函数返阿伯.(2)简述算法自3的功能.五、算法设计题(本题IO分)34 .假设用带头结点的单循环链表衣示线性表，单链表的类型定义如下：rypcdcfstructnodeintdata:structnode*next:)1.inkN<1.c.1.ink1.ist;S写程序，求头指针为head的单砧环琏表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0,并给出所写算法的时间女朵度。函数原型为：f1.oatt34(1.ink1.isthead):绝密启用前编号：1642011年1月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）1.D2,B6.B7.C11.C12.D二'填空现（本大IS共IO小题16. 运算（或操作）17. 218. 319. 空中20. 421. 左子朝为空22. n-123. Jt接播入排序24. h三、解答H（本大艘共4小题,26. （I）【泮分参学】错I个结点扣13.D4,5.C8.B9.C10.A13.A14.B15.A.每小题2分,共20分）每小就5分,共20分）（3分）分，扣完3分为止.一、单项选择邈（本大题共15小题，每小鹿2分,共30分）（2分）O1.1.OOOI1.0000001010010-0（3分）【评分参考懵I个Ift字扣1分，扣完3分为止.（2） ABCED【评分参与】第I个字符扣I分,扣完2分为止.28. （I）（96,63.78.25,57,11,44）（亦可出对应的地形式.）【评分参考】个关键字位笈扣I分,扣完3分为止.（2） （63,57.44,25,11,78,96）（亦可通出对应的堆形式.）【评分参考】恬1个关键字位置扣I分,扣完2分为止.29. <1）（2分）（3分）01_23456789IO-56I2jT79丁3841j（4分）【评分参考】错I个关键字位置加1分,扣完4分为止.AS1.=I1/7（I分）四、算法阅谡盘（本大题共4小敏，福小甄5分.共20分）I47、30.（I）258（3分）369【评分参考】错1个数字扣I分，扣完3分为止.（2）算法功相是求矩阵的传置（2分3.（i）Cbedfagh（4分）【评分参考】出I个站点位置扣I分,扣完4分为止.（2）中序遍历二叉树（I分）32 .输出结果：3426158942（I分）2615344289（2分1526344289（2分）3