2004年10月全国自考数据结构(02331)试题及答案

1/72004年10月全国自考数据结构试题课程代码：(02331)一、单项选择题(本大题共15小题，每小题2分，共30分)1．下列各式中，按增长率由小至大的顺序正确排列的是(D)A．n，n！，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100，logn,2n,nn2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是(A)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;3．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向(B)A．各自的头结点B．各自的尾结点C．各自的第一个元素结点D．一个表的头结点，另一个表的尾结点4．栈的两种常用存储结构分别为(A)A．顺序存储结构和链式存储结构B．顺序存储结构和散列存储结构C．链式存储结构和索引存储结构D．链式存储结构和散列存储结构5．已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为(C)A．5B．6C．16D．176．已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为(C)typedefstructnode{chardata[8];structnode*next;}LinkStrNode;A．1/4B．1/2C．2/3D．3/47．应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为(C)A．7B．9C．10D．128．二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为(B)A．574B．576C．578D．5809．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是(D)2/7A．（c,d）B．(d)C．bD．(b)10．已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为(D)A．ABCDEFB．ABCEFDC．ABFCDED．ABCDFE11．一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为(A)A．O(n)B．O(e)C．O(n+e)D．O(n2)12．在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为(B)A．4，4，3B．4，3，3C．3，4，4D．3，3，413．下列排序方法中，最好与最坏时间复杂度不相同的排序方法是(A)A．冒泡排序B．直接选择排序C．堆排序D．归并排序14．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于(B)A．1.0B．2.9C．3.4D．5.515．在下列各种文件中，不能进行顺序查找的文件是(C)A．顺序文件B．索引文件C．散列文件D．多重表文件二、填空题(本大题共10小题，每小题2分，共20分)16．抽象数据类型是指数据逻辑结构及与之相关的（操作）。17．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点*p的（前驱）结点。q=p;while(q-next!=p)q=q-next;18．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为（SXSSXXSSXSSXXX）。19．在文本编辑程序中查找某一特定单词在文本中出现的位置，可以利用串的（子串定位）运算。20．假设以行优先顺序将一个n阶的5对角矩阵压缩存储到一维数组Q中，则数组Q的大小至少为（5n-6）。21．在含100个结点的完全二叉树中，叶子结点的个数为（50）。3/722．在无向图中，若从顶点a到顶点b存在（路径），则称a与b之间是连通的。23．如果排序过程不改变（关键字相同的记录）之间的相对次序，则称该排序方法是稳定的。24．索引顺序查找适宜对（分块有序或有序）的顺序表进行查找。25．文件的检索操作可按检索条件不同分为下列四种询问，它们是简单询问、范围询问、函数询问及（布尔询问）。三、解答题(本大题共4小题，每小题5分，共20分)26．画出下图所示二叉树的中序线索链表的存储表示。E00D01B00C10K11A11F11t27．已知图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的邻接表。答：(1)abdec(2)a14∧0b02∧1c14∧2d14∧3e32∧43032顶点表边表28．已知自顶向下的二路归并排序的算法如下所示，按此算法对关键字序列（55，28，73，91，37，64，19，82，46）进行排序，列出算法执行过程中前5次调用Merge函数进行归并之后的关键字序列。voidMergeSorDC(SeqListR,intlow,inthigh){//用分治法对R[low..high]进行二路归并排序intmid;if(lowhigh){//区间长度大于14/7mid=(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)第2次调用Merge进行归并之后的关键子序列为:(28,55,73,91,37,64,19,82,46)第3次调用Merge进行归并之后的关键子序列为:(28,55,73,91,37,64,19,82,46)第4次调用Merge进行归并之后的关键子序列为:(28,37,55,73,91,64,19,82,46)第5次调用Merge进行归并之后的关键子序列为:(28,55,73,91,37,64,19,82,46)29．由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。请画出4棵含1，2，3，4，5，6六个元素且以1为根、深度为4的二叉排序树。答：136425146352146325154362四、算法阅读题(本大题共4小题，每小题5分，共20分)30．L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。LinkListf30(LinkListL,intc){LinkListLc,p,pre;pre=L;p=(1);5/7Lc=(LinkList)malloc(sizeof(ListNode));Lc-next=Lc;while(p!=L)if(p-datac){pre-next=p-next;(2);Lc-next=p;p=pre-next;}else{pre=p;(3);}returnLc;}答：(1)L-next(2)p-next=Lc-next(3)p=p-net31．设栈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)将栈S中的元素依次出栈，同时将第奇数次的元素入栈T，将第偶数次的元素入队列Q。32．图的邻接矩阵表示描述如下：#defineMaxNum20//图的最大顶点数typedefstruct{charvexs[MaxNum];//字符类型的顶点表intedges[MaxNum][MaxNum];//邻接矩阵intn,e;//图的顶点数和边数}MGraph;//图的邻接矩阵结构描述6/7阅读下列算法，并回答问题：（1）对于下列图G的邻接矩阵，写出函数调用f32(&G,3)的返回值；0110000011010000010011110（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)10(2)求有向图顶点Vi的出度和入度和(3)0(n)33．阅读下列算法并回答问题：（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];}}7/7R[low]=x;}答：(1)(-8,-3,-2,-1,4,2,5,7)(2)将数组R中所有负数调整到前端，同时将所有非负数调整到后端。五、算法设计题(本大题10分)34．假设以二叉链表作为二叉树的存储结构，其结点结构为：lchilddatarchild依照如下给定的函数f34的原型，编写求二叉树T中叶子结点所在的最小层次与最大层次的函数。其中，参数level为函数执行过程中T当前所指结点的层次，其初值为1；*lmin与*lmax分别为叶子结点的最小层次与最大层次，它们的初值均为０。voidf34(BinTreeT,intlevel,int*lmin,int*lmax);答：voidf34(BinTreeT,intlevel,int*lmin,intlmax){if(T){if(!T-lchild&&!T-rchild){if(*lmin==0||level*lmin)*lmin=level;if(level*lmax)*lmax=level;}else{f34(T-lchild,level+1,lmin,lmax);f34(T-rchild,level+1,lmin,lmax);}}}