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

更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........2004年下半年全国自考数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.A.AB.BC.CD.D答案：D2.若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）A.s-next=p-next;p-next=s;B.p-next=s;s-next=p-next;C.p-next=s-next;s-next=p;D.s-next=p;p-next=s-next;答案：A3.若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案：B4.栈的两种常用存储结构分别为（）A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构答案：A5.已知循环队列的存储空间为数组data［21］，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为（）A.5B.6C.16D.17答案：C6.已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为typedefstructnode{chardata［8］;structnode*next;}LinkStrNode;（）A.1/4B.1/2C.2/3D.3/4答案：C7.应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为（）A.7B.9C.10D.12答案：C8.二维数组A［20］［10］采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A［8］［9］的存储地址为（）A.574B.576C.578D.580答案：B9.对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（）A.（c,d）B.(d)C.bD.(b)答案：D10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（）A.ABCDEFB.ABCEFDC.ABFCDED.ABCDFE答案：D11.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（）A.AB.BC.CD.D答案：A12.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（）A.4，4，3B.4，3，3C.3，4，4D.3，3，4答案：B13.下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（）A.冒泡排序B.直接选择排序C.堆排序D.归并排序答案：A14.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）A.1.0B.2.9C.3.4D.5.5答案：B15.在下列各种文件中，不能进行顺序查找的文件是（）A.顺序文件B.索引文件C.散列文件D.多重表文件答案：C二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。1.抽象数据类型是指数据逻辑结构及与之相关的___。答案：操作2.已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的___结点。q=p;while(q-next!=p)q=q-next;答案：前驱3.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___。答案：SXSSXXSSXSSXXX4.在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的___运算。答案：子串定位（或模式匹配）5.假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为___。答案：5n-66.在含100个结点的完全二叉树中，叶子结点的个数为___。答案：507.在无向图中，若从顶点a到顶点b存在___，则称a与b之间是连通的。答案：路径8.如果排序过程不改变___之间的相对次序，则称该排序方法是稳定的。答案：关键字相同的记录9.索引顺序查找适宜对___的顺序表进行查找。答案：分块有序或有序10.文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及___。答案：布尔询问（或组合询问）三、解答题（本大题共4小题，每小题5分，共20分）1.画出下图所示二叉树的中序线索链表的存储表示。答案：说明：线索指针或标志域每错2个扣1分，扣完5分为止。2.已知图G=（V，E），其中：V={a,b,c,d,e},E={(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)}。（1）画出图G；（2）画出图G的邻接表。答案：3.已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。voidMergeSortDC(SeqListR,intlow,inthigh){∥用分治法对R［low..high］进行二路归并排序intmid;if(lowhigh){∥区间长度大于1mid=(low+high)/2;∥分解MergeSortDC(R,low,mid);∥递归地对R［low..mid］排序MergeSortDC(R,mid+1,high);∥递归地对R［mid+1..high］排序Merge(R,low,mid,high);∥组合，将两个有序区归并为一个有序区}}∥MergeSortDC答案：第1次调用Merge进行归并之后的关键字序列为：（28，55，73，91，37，64，19，82，46）（1分）第2次调用Merge进行归并之后的关键字序列为：（28，55，73，91，37，64，19，82，46）（1分）第3次调用Merge进行归并之后的关键字序列为：（28，55，73，37，91，64，19，82，46）（1分）第4次调用Merge进行归并之后的关键字序列为：（28，37，55，73，91，64，19，82，46）（1分）第5次调用Merge进行归并之后的关键字序列为：（28，37，55，73，91，19，64，82，46）（1分）4.由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。答案：说明：画出其中4棵二叉树即得5分。反之，每画错1棵二叉树扣1分。4棵二叉树都画错，则不得分。四、算法阅读题（本大题共4小题，每小题5分，共20分）1.L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在___处填入合适的内容，使其成为一个完整的算法。LinkListf30(LinkListL,intc){LinkListLc,p,pre;pre=L;p=(___);Lc=(LinkList)malloc(sizeof(ListNode));Lc-next=Lc;while(p!=L)if(p-datac){pre-next=p-next;(___);Lc-next=p;p=pre-next;}else{pre=p;(___);}returnLc;}答案：L-next(或pre-next)(1分)p-next=Lc-next(2分)p=p-next(或p=pre-next)(2分)2.设栈S=(1,2,3,4,5,6,7),其中7为栈顶元素。（1）写出调用f31(&S)后的S；（2）简述函数f31中第1个循环语句的功能。voidf31(Stack*S){QueueQ;StackT;inti=0;InitQueue(&Q);InitStack(&T);while(!StackEmpty(S))if((i=!i)!=0)Push(&T,Pop(S));elseEnQueue(&Q,Pop(S));while(!StackEmpty(&T))Push(S,Pop(&T));while(!QueueEmpty(&Q))Push(S,DeQueue(&Q));}答案：(1)S=(1,3,5,7,6,4,2),其中2为栈顶元素；(3分)（2）将栈S中的元素依次出栈，同时将第奇数次出栈的元素入栈T，第偶数次出栈的元素入队列Q。(2分)3.图的邻接矩阵表示描述如下：#defineMaxNum20∥图的最大顶点数typedefstruct{charvexs［MaxNum］;∥字符类型的顶点表intedges［MaxNum］［MaxNum］;∥邻接矩阵intn,e;∥图的顶点数和边数}MGraph;∥图的邻接矩阵结构描述阅读下列算法，并回答问题：（1）对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值；（2）简述函数f32的功能；（3）写出函数f32的时间复杂度。intf32(MGraph*G,inti){intd=0,j;for(j=0;jG-n;j++){if(G-edges［i］［j］)d++;if(G-edges［j］［i］)d++;}returnd;}答案：1）5(2分)（2）求有向图中顶点vi的入度和出度的和（或有向图中某顶点的度）（或关联于有向图中顶点vi的边的数目）(2分)（3）O(n)(1分)4.阅读下列算法并回答问题：（1）设数组L［1..8］的初值为（4，-3，7，-1，-2，2，5，-8），写出执行函数调用f33(L,8)之后的L［1..8］中的元素值；（2）简述函数f33的功能。voidf33(intR［］,intn){intx=R［1］;intlow=1,high=n;while(lowhigh){while(lowhigh&&R［high］=0)high--;if(lowhigh){R［low++］=R［high］;while(lowhigh&&R［low］0)low++;R［high--］=R［low］;更多优质自考资料尽在百度贴吧自考乐园俱乐部（）欢迎❤加入...欢迎❤交流...止不住的惊喜等着你.........}}R［low］=x;}答案：(1)(-8,-3,-2,-1,4,2,5,7)(3分)(2)将数组R中所有负数均调整到前端，同时将所有非负数调整到后端(2分)五、算法设计题（本题共10分）1.假设以二叉链表作为二叉树的存储结构，其结点结构为：依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中，参数level为函数执行过程中T当前所指结点的层次，其初值为1；*lmin与*lmax分别为叶子结点的最小层次与最大层次，它们的初值均为０。voidf34(BinTreeT,intlevel,int*lmin,int*lmax);答案：voidf34(BinTreeT,intlevel,int*lmin,int*lmax){if(T)(1分){if(!T-lchild&&!T-rchid)(1分){if(*lmin==0‖level*lmin)*limn=level;(2分)if(level*lmax)*lmax=level;(2分