02331数据结构200710真题及答案.docx
2007年10月高等教育自学考试全国统一命题考试数据结构试卷(课程代码2331)本试卷共12页，满分100分；考试时间150分钟，一、单项选择题(本大题共15小题，每小题2分，共30分)在每小翅列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选'多选或未选均无分。1.下面程序段的时间复杂度为s=0;for(i三1;i<n;i÷÷)for(j=i;j<i;j+)ij;A.O(I)B.O(1.ogn)C.0(n)D.O(n2)2 .已如指针P和q分别指向某单钺表中第一个站点和最后一个结点,假设指针，指向另,个单锌衣中某个结点,则在8所指结点之后插入上述链衣应执行的语句为【】A.q->ncxt三->11cxt;*->next=p;B.->next=p；q->next三->next；C.p->next=->next;s->ncxteq；D.->next-q；p->next=$->next；3 .在计算机内实现递归算法时所需的辅助数据结构是【】A.栈B.队列C.树D.图4 .假设以数祖Am存放循环Am的元素，已知队列的长度为IengIh,指针rear指向认足元泰的下一个存储位置。则认头元素所在的存储位置为【】A.(rear-1.ength+m+1)%mB.(rear-1.ength+m)%mC.(rear-1.ength+m-1)%mD.(rear-1.ength)%m5 .通常将链串的结点大小设置为大于I是为了【】A提高串匹配效率B.提而存储密度C.便于插入悚作D.便于删除操作6 .带行表的三元组表是稀疏矩阵的一种【】A.顺序存储结构B.琏式存储结构C.索引存储结构D.散列存储结构7 .灰头和表尾均为空表的广义表是()A()B.()C.()D.(),()8 .用二又集表表示具有n个结点的二义树时他为空的指针域的个数为【】A.n-1.B.nC.n+1.D.2n9 .为便于判别有向图中是否存在回路，可借助于【】A.广度优先搜索算法B.最小生成树算法C.设短路径算法D.拓扑排序算法10 .连通网的最小生成树是其所有生成树中1A.顶点柒最小的生成树B.边集呆小的生成椅C.顶点权值之和最小的生成树D.边的权(ft之和最小的生成树11 .按排序过程中依据的原则分类，快速排序网于【】A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法12 .下列关城字序列中.构成小根堆的是A. (84.46.62,41,28，58,15,37B. (84.62.58.46.41.37.28,15|C. I5.28.46.37.84.41,58.62)D. (15.28.46.37.84.58.62.41|13 .在长度为32的有序农中进行二分查找时，所衢进行的关健字比较次数总多为【】.4B.5C.6D.7U.也设在构建散列表时,采用线性探测解决冲突.若连续插入的n个关键字都是同义诃.期查找其中最后插入的关键字时，所需进行的比做次数为【】A.n-1B.nC.n+1.D.n+215 .散列文件也称为【】A.顺序文件B.索引文件C.Ii接存取文件D.间接存取文件二、填空题(本大题共10小题，每小题2分，共20分)话在每小题的空格中填上正确答案。错填、不填均无分，16 .数据的逻辑结构描述数据元素之间的.与存储方式无关.17 .在一个长度为100的顺序去中删除第10个元素时，需移动个元素.18 .队列的翻尾位置通常是随着操作而变化的.19 .两个空中联接褥到的中的长度为.20 .设对称矩阵A压缩存偌在觉数组B中，其中矩阵的第一个元素au存储在B0,元素an存储在B(1.则矩阵元素a”存储在B中。21 .已知一棵哈夫曼树含有60个叶子结点.则该的中共有一个非叶子结点.22 .如图所示的有向图中含仃个强连通分录。题22图23 .已知一祖关键字为“5,36,28.97,24,78,47,52.13,86),其中每相邻两个关键字构成一个有序子序列，对这线子序列进行一朝两两归并的结果是24 .从空树起，依次捅人关雄字H.27.35,48.52.66和73构造所得的二叉排序树,在等概率杳我的假设下，查找成功时的平均查找长度为，25 .控制区间和控制区域是文件的逻辑存储单位。三、解答题(本大题共4小题，每小题5分，共20分)26 .利用广义衣的head和tai1.操作.可从广义表1.=(a.b),(c.<1)中分斛得到原子C其操作表达式为hcad(hcad(tai1.(1.):分别写出从下列广义表中分解得到b的操作衣达式.(1.)1.I=(a.b,c.(1)：(2)1.2=(（八）.(b),(C),(d)(1)(2)27 .画出与如图所示森林对应的：叉树，叁27图28 .己知有向图G的定义如下：G=(V,E)V=a.b.c.d.c)E=<a.b>,<a,c>,<b.c>.<b,d>.<c.d>,<e,c>,<e,d>)(1)画IHG的图形；(2)写出G的全部拓扑序列，(1)(2)29 .已知3阶B一树如图所示.题29图(1)口出招关犍字88插入之后的B-W：(2)百山将关键字47和66依次插入之后的B-H.(1)(2)四、算法阅读题(本大题共4小题，每小题5分，共20分)30 .叙设某个不设头指针的无头结点单向街环链友的尺度大于I,S为指向柢友中某个结点的指针。算法f30的功能是，州除井返回链表中指针S所指结点的前矍,请在空缺处地入合适的内容，使其成为完整的算法。typedefst>ctnode|Dd1.aTypcdae；stnjctnodenext;IUnk1.ist；Da1.aTypef30(1.ink1.iB1.s)Unk1.istpre,p;DataTypcc；pre»s;p三s->ncx1.;whi1.e(QJ)IPreMp；(2)；pre->next一一一一。)；c=p->daU;frcc(p)；returne；I,(1)(2)(3)31.前法f31的功能是滑空带头结点的链队列Q,清在空缺处填入合适的内容，使其成为一个完拈的算法。typedefstctnode|DauTypcdatastructnodenexi；IQueucNodc；typcdcfstructQucueNodefront；队头指针QucueNoderear；队尾指针IUnkQoeue;void3J(1.inkQucueQ)QueueNodep,$；P=(1J；whi1.e(pJ=NU1.1.)s=P；P三p->ncxt;frec();2=NU1.1.；O->rear=(3)(1)(2)32. 'K己的顺序率HSinng作为率的存储结构该类型实现的小操作函数原型说明如Nvoidstrinit(HSthngs)；置s为空串intstr1.e11(HString»);/求串S的长度Voidstrcpy(HStringIo1HStringfrom)；将申from包制到申tovoids1.rcat(HStrin8to,HStringfem);将申from联接到串to的末尾intStrcmp(HStringsi,HStrings2)；比较中4和2的大小,当31<2,s1.=82或81>s2时，返回值小于0,等于O或大于OHStringsubstr(HStrings1.inti1.intm)；返回申s中从第i(0WiWstrisCAm)个字符起长度为m的子申阅读下列算法f32,并回答问题：(1)设甲SJabCdabar,T="bcd-，V=bcdT,写出执行f32(S,T,V)之后的S;(2)管述算法f32的功能。voidf32(HStringS,HStringT,HS<nngV)|intm,n,o,i；HSthngnews；strinit(news)；n三str1.en(三);m三Strfen(T)；posi三0；WhiIe(i<三n-m)if(fttrcmp(>ubstr(S9i9m)tT)!三0)i÷*；e1.seIStrCM(news,SUbS<r(S,pos.i-ps);trcat(ncws,V)pot三i三i÷m；I.I.BtrCat(news.MUbStr(S,pos9n-pos);stcpy(S.news)；I(1)33.假谀以二叉链衣作为二叉树的存储结构，其类里定义如下:typedefstructnodechardau；structnode!chi1.d.rchi1.d；左右孩子指针IBinTNodetBinTroe;阅读下列算法f33.并回答问题：(I)巳知如图所示的二叉树以T为指向根结点的指针，叠出执行f3：W;(2)简述算法f33的功能。0voidf33(BinTreeT)I迨(T)I©f33(T->1.chi1.d)sA33(T>>rchiM)jQif(!T->1.chi1.d)&&->rc<i)ITT->khiM-T->rdu1.d;©©T->rchiM-NU1.1.;购33图五、算法设计题（本大SgIO分）X.假设以带头结点的总能衣发示才序表，歧镰上的类型定义如下:typcdeftnctnodeintdata；SUVCtnodeTICXt;IUnkNodetUnk1.iet：编写律法，输入n个等数构造一个无案值不相同的递堵有序链表（即相同的整数只取一个）.算法的函数原型给定为Unk1.iUf34（inin）j纳密启用前编号：2412007年10月高等教育自学考试全国统一命题考试6,数据结构试题答案及评分参考（课程代码2331）1.D2.A3.A4.B5.B6.A7.B8.C9.D10.D11.C12.D13.C14.B15.C二、填空剧（本大IS共10小题.每小JS2分，共20分）16.造然关系（成关系）/v*浮17.906小18.人队一、单项选择题（本大题共”小题，每小题2分,共30分）020.1721.5922.223. 115,28,36,97,24,47,52.78,13,86|24. 4c25. VSAM/A'Afc三、解答题(本大SS共4小题.每小膻5分,共20分)26. (I)he»d(UiI(1.1.)（说明：每错一个掾作扣I分，扣完2分为止）（2） head（hea<i（ui1.（hcad（1.2）（3分）（说明：每错一个操作扣I分，扣完3分为止）（说明：关健
