2005年下半年全国自考数据结构真题及答案

更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2005年下半年全国自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上()A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合答案：D2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为（）A.n-i+1B.iC.i+1D.n-i答案：D3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）A.head==NULLB.head-next==NULLC.head!=NULLD.head-next==head答案：A4.引起循环队列队头位置发生变化的操作是（）A.出队B.入队C.取队头元素D.取队尾元素答案：A5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）A.2，4，3，1，5，6B.3，2，4，1，6，5C.4，3，2，1，5，6D.2，3，5，1，6，4答案：D6.字符串通常采用的两种存储方式是（）A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储D.散列存储和顺序存储答案：C7.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为（）A.mB.n-mC.n-m+1D.n答案：C8.二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为（）A.429B.432C.435D.438答案：A9.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（）A.(e,f)B.((e,f))C.(f)D.()答案：B10.下列图示的顺序存储结构表示的二叉树是（）A.AB.BC.CD.D答案：A11.n个顶点的强连通图中至少含有（）A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边答案：B12.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（）A.(19，23，56，34，78，67，88，92)B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)D.(19，23，67，56，34，78，92，88)答案：D13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（）A.4B.5C.8D.9答案：C14.由同一关键字集合构造的各棵二叉排序树（）A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同答案：B15.ISAM文件和VSAM文件的区别之一是（）A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构D.前者的存储介质是磁盘，后者的存储介质不是磁盘答案：C二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。1.数据的逻辑结构在计算机存储器内的表示，称为数据的___。答案：存储结构2.删除双向循环链表中*p的前驱结点(存在)应执行的语句是___。答案：P-prior=p-prior-prior;(1分)p-prior-next=p;(1分)(或p-prior-prior-next=p;(1分)p-prior=p-prior-prior;(1分))3.栈下溢是指在___时进行出栈操作。答案：栈空4.已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t),strlen(t))后的返回值为___。答案：“EFGH”5.去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的___。答案：表尾6.已知完全二叉树T的第5层只有7个结点，则该树共有___个叶子结点。答案：117.在有向图中，以顶点v为终点的边的数目称为v的___。答案：入度8.当关键字的取值范围是实数集合时，无法进行箱排序和___排序。答案：基数9.产生冲突现象的两个关键字称为该散列函数的___。答案：同义词10.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中___。答案：已有m个同义词的记录（或：已有m个记录；或：已满）三、解答题（本大题共4小题，每小题5分，共20分）1.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式；(3)设m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。答案：（1）quelen=m(1分)（2）quelen=0(1分)（3）35(1分)（4）(rear-quelen+1+m)%m(2分)2.已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。答案：(每错一个结点扣1分，扣完5分为止)3.画出下图所示有向图的所有强连通分量。答案：该图的强连通分量分别为：4.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。答案：（1）4713652(3分)（2）初始关键字4713652一次划分后得（231）4（657）(1分)继续划分后得（1）2（3）（5）6（7）(1分)（说明：答案不唯一，只要满足题目要求均得分。）四、算法阅读题（本大题共4小题，每小题5分，共20分）1.阅读下列算法，并回答问题：(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；(3)简述算法的功能。voidf30(SeqList*L,DataTypex){inti=0,j;while(iL-length&&xL-data［i］)i++;if(iL-length&&x==L-data［i］){for(j=i+1;jL-length;j++)L-data［j-1］=L-data［j］;L-length--;}else{for(j=L-length;ji;j--)L-data［j］=L-data［j-1］;L-data［i］=x;L-length++;}}答案：（1）（3，7，11，14，15，20，51）(2分)（2）（4，7，14，20，51）(1分)（3）当非递减顺序表中存在元素x时，从表中删除该元素；否则将x保序插入到顺序表中。(2分)2.已知图的邻接表表示的形式说明如下：#defineMaxNum50//图的最大顶点数typedefstructnode{intadjvex;//邻接点域structnode*next;//链指针域}EdgeNode;//边表结点结构描述typedefstruct{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;//顶点表结点结构描述typedefstruct{VertexNodeadjlist［MaxNum］;//邻接表intn,e;//图中当前的顶点数和边数}ALGraph;//邻接表结构描述下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。typedefenum{FALSE,TRUE}Boolean;Booleanvisited［MaxNum］;voidDFSForest(ALGraph*G){inti;for(i=0;iG-n;i++)visited［i］=___;for(i=0;iG-n;i++)if(!visited［i］)DFSTree(G,i);}voidDFSTree(ALGraph*G,inti){EdgeNode*p;visited［i］=TRUE;p=G-adjlist［i］.firstedge;while(p!=NULL){if(!visited［p-adjvex］){printf(″%c,%c″,G-adjlist［i］.vertex,G-adjlist［p-adjvex］.vertex);___;}___;}}答案：FALSE(1分)DFSTree(G,P-adjvex)(2分)p=p-next(2分)3.阅读下列算法，并回答问题：(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；(2)写出上述函数调用过程中进行元素交换操作的总次数。voidf32(intR［］,intn){inti,t;for(i=0;in-1;i++)while(R［i］！=i){t=R［R［i］］;R［R［i］］=R［i］;R［i］=t;}}答案：(1)L［8］={0,1,2,3,4,5,6,7,}(3分)(2)共进行5次元素交换。(2分)4.答案：（1）NULL(1分)（2）p-next=H［j］(2分)（3）p=q(2分)五、算法设计题（本大题10分）1.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子指针structnode*parent;//指向双亲的指针}BinTNode;typedefBinTNode*BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况，简要叙述实现求后继操作的方法；(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。答案：1）分两种情况讨论①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止，则该结点为*px在中序序列中的后继；(2分)更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........②当*px的右子树为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点为*px在中序序列中的后继。(2分)（2）BinTreef34(BinTreepx){BinTreeq=px-rchild;if(q!=NULL){／／沿左孩子往下查找px=q;(1分)while(px-lchild!=NULL)(1分)px=px-lchild;(1分)}else{／／沿双亲指针链向上查找while(px!=NULL&&px-rchild==q){(1分)q=px;(1分)px=px-parent;(1分)}}returnpx;／／返回所找到的中序序列后继结点的指针／／或者无