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

2006年10月高等教育自学考试全国统一命题考试数据结构试题课程代码2331一'单项选择题（本大题共15小期，每小题2分，共30分）在每小SS列出的四个备选项中只有一个是符合凝目要求的，请将其代码填写在船后的括号内.借选'多选或未选均无分.1 .数据结构是（）A.一种数据类型B.数据的存储结构C.一组性侦相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合2 .算法分析的目的是（）A.辨别数据结构的合理性氏评价算法的效率C.研究蚱法中输入与输出的关系D.鉴别算法的可读性3 .在线性表的下列运算中,小改变数据元素之间结构关系的运算是<）A.插入B.删除C,排序D.定位4 .若进栈序列为I.2,3,4,5.6.且进校和出枝可以穿插进行,则可能出现的出栈序列为（>A.3.2.6.I,4.5B.3.4.2.I,6.5C.I.2.5.3.4.6D.5.6.4.2.3,I5.设舟s1.="DataStructureswithJava".s2=*it*,则子用定位函数index（s1.s2）的值为（）A.15B.16C.17D.186 .二维数组A89按行优先顺序存储,若数组元素A23的存储地址为1087,A47的存谛地址为1153.则数组元素A6的存储地址为）A.1207B.12091211D.12137 .在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A.队列B.栈C.线性表D.有序表8 .在任意一探二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（A.不一定相同B.都相同C.都不相同D.互为逆序9 .若采用孩子兄弟於表作为树的存饰结构.则树的后序遍历应采用二叉树的（）A.层次遍历算法B.前序泗历算法C.中序测历以法D.后序i历算法10 .若用邻接矩阵表示一个有向图，则其中年一列包含的"I"的个数为）A.图中每个顶点的入度B.图中好个顶点的出度C.图中孤的条数D.图中连通分房的数目11 .图的铭接矩阵我示法适用于表示A.无向图B,有向图C.胸密图D.稀确图12 .在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出G小关键字元崇,则在进行第i造排序之前,无序区中关键字元素的个数为（）A.iB.i+1C.n-iD.ni+1.13 .下列排序算法中，其时间复杂度和记录的初始排列无关的是（A.场入播序B.堆排序C.快速排序D.日泡排序14 .若有序表的关健字序列为（b.c.d.c.f.g.qqM）.则在二分查找关键字b的过程中.先后进行比较的关键字依次为（）A.f.c.bB.f.d.bC.g,c,bD.g.d.b15.若在文件中铳询年龄在60岁以上的男性及年龄在55岁以上的女性的所有记录，则宜询条件为（）A.性别="男”）CR（年龄60）（）R（性别="女"OR年龄55）B.（性别="男”OR（年龄60）AND（性别="女”）OR（年龄55C.（性别="男”AND（年龄60）OR（性别="女”AND（年龄55）D.（性别="%"）AND（年龄60AND（性别="女AND（年龄55二、埴空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案.错埴、不堪均无分。16 .称算法的时间或杂度为O(f(n),其含义是指算法的执行时间和的数状级加可.17 .在一个长度为n的总链表1.中，删除链表中*p的前驱结点的时间或杂度为。18 .假i殳为野环队列分配的向量空间为Q20.若队列的长度和认头指计(ft分别为13和17,则当前尾指针的值为.19 .设s="IAMAATH1.ETE*.1.="GOOD*,则执行下列串操作序列之后得到的MIb1.为subs1.r(sub1.s,5,2);SUbS1.NSUb2.s.6.8):strcpy(t1.0;SUCat(UQUb2);srcat(sub1.,t1.):20 .广义表的深度是指,21 .一棵含999个结点的完全二叉树的深度为。22 .含n个顶点的无向连通图中至少含有条边.23 .对我长为90«)的索引顺序表进行分块宜找,假设每一块的长度均为15,且以顺序查找确定块,则在各记录的查找概率.均相等的情况下,其查找成功的平均查找长度为“24 .若对关健字序列(43.02.8().48.26.57.15.73.21.24.66)进行一趟增量为3的希尔排序,则得到的结果为。25 .ISAM文件由主索引、和主文件现成.三、解答题(本大题共4小Jg,每小题S分，共20分)26 .某广义去的表头和表尾均为(a(b.c)，画出该广义衣的图形表示.27 .己知乂树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。(1)画出该二叉树；(2)画出与(1)求得的二叉树对应的海林(1)(2)28.1.1.知帝权图的铭接表如卜所示,其中边表结点的结构为:邻接点权值链域42071.H1.1.1.1B401.1.-Hs091>415-H3i20T08Ho1071A1.依此邻接表从顶点C出发进行深度优先诩历.(1画出由此得到的深度优先生成树;(2)写出班历过程中得到的从顶点C到其它各顶点的带权路径及其长度,(1)(2)29.从空树起，依次插入关键字37,50,42.18.48.12.56,30,23,构造-棵：叉排序树.(I)画出该二叉排序树：(2)画出从(1)所得树中删除关植字为37的结点之后的二叉排序|仁(1)(2)四、算法阅读Sfi(本大题共4小题，每小挖5分，共20分)30.已知用有序链去存储将数集合的元素。阅读算法130,并回答卜冽问即：(1)写出执行(30(a.b)的返回值，其中a和b分别为指向存储集合(2,4,5,7,9,12)和12,4,5,7.9)的链表的头指针：(2)简述算法f30的功能:(3)写出算法刖的时间复杂度。int(X1.ink1.istha,1.ink1.isihb)I/1.ink1.ist是带行头结点的的鞋表川Ia和hb分别为指向存谛两个有序整数集合的琏表的头指针1.ink1.isia,pb;a三ha->nexcpb-hb>ncxt;whi1.c(pa&&pb&&pa->daa=-ph->data)pa=pa->next:pb=pb->ncxt:>if(pa=NU1.1.&&pb=NU1.1.)returnI;e1.sereturn0;I(I)(3)31 .已知稀限矩阵采用带行表的三元组表表示,其形式说明如下:#dCfinCMaXRoW100稀说矩阵的最大行数tyedefstructiniij.v;行号、列号、元素值JTriTupIeNode;typedcfstruct(TriTupIcNodcdata)MaxSize;intRowTabMaxRow÷1.;行intm,n,t:"矩阵的行数、列数和非零元个数)RTriTupIeTabIc;下列算法珞1的功能是.以行优先的航序输入稀疏矩阵的非零元(行号、列号、元素值).建立梯疏矩阵的带行表的二元纲表存储结构，i青在空缺处填入合适内容，使其成为一个完整的算法。(注：矩阵的行、列下标均从1起计)voidCKRTriTupIcTabIc*R)i11(i.k；scanfCod%d%d",R->m.R->11R->t);R->Rowab11=():k=k/汆指示当前耕入的非零元的行号fbr(i=O;si+>SCan1.V%d%d%dw.,&R->data(i.v):whi1.c(k<R-xiatai.i):R->RowTabk=i:32 .已知二叉树的存储结构为二叉链衣，共类型定义如下:Iypedefs1.ructNodeTypc(DataTypedata;sin©NodeTyPet1.chi1.d.trchi1.<1.;)BinTNodeZBinTree;阅读总法F32,并回答卜列问题：(1)对于如图所示的二叉树，画出执行算法门2的结果;<2)筒述翼法门2的功能。BinTrccnZ(BinTrecbtI)(BinTrcebt2:iftbt1.=NU1.1.)bt2=NU1.1.;e1.seb<2=(BinTNode*)ma1.1.oc(sizeof(BinTNixie);b<2->data=b<1.->daa;M2->rchi1.d=f32(bt1.->1.chi1.d);bt2->1.chi1.d=2(bt1.->rchi1.d):)returnb12:)(I)33.假设有向图采用辐接衣友示法其定义如下：typcdc1.-StmctVertexNodeadj1.is1.(MI1.XVertexNum);i11tn.c:图的当前痍点数和弧数)A1.Graph;邻接表类型其中顶点表结点VenCXNode结构为：VCrteXfi11uedgc边去结点EdgCNodC结同为:下列算法03的功能是,对以邻接表表示的行向图进行拓扑排序。(1)阅读算法门3,并在空缺处塘入0合适的内容，使其成为一个完整的算法：3(2)对于如图所小的邻接表，将执4行算法门3后的>poI结果填入5给定的数组中.voidf33(A1.GraphGinitopo)|A-H2I4-H6,B-H6I4-H7jCT3aD-*i6I-M4EAF-H41.1.T5INT5IA1.GHintij.k.count=0:intindegrveMaxVertexNumI;EdgeNodep:"p为指向边表结点的指针QueueQ:/Q为队列Findhukgree(Gindegree);“求各顶点的入度，并置F入度向MindegreeImtQUeUe(&Q):for(i=0;i<Gn;i+)if(!indcgrce(i)EnQueue(&Q.i):whi1.c(!QueueEmpty(&Q»j=:(o>j1.=+÷count:f'ortp-Gadj1ist(j|.firs(cdgc;p;p=->ncxt)k=p->adjvcx;i1.(!(-indcgrcck1.)®)if(count<G.n)print""图G中存在有环路")：J(1)五、算法设计题（本大JSIO分）34假设以带头结点的单性友表示有序我，堆随表的类型定义如下:typcdcfstructnodc（DiitaTypedata:structk*ncxtI1.inkNode.*1.ink1.ist;编写算法，从有序表A中删除所有和有序衣B中元素相同的结点。2006年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考*X