2019年湖北武汉科技大学数据结构(C语言)考研真题及答案.pdf

2012019 9年湖北武汉科技大学数据结构年湖北武汉科技大学数据结构(C C语言语言)考研真题及答案考研真题及答案一、选择题(共 15 小题，每小题 2 分，共 30 分)1.计算算法的时间复杂度是属于一种（）的方法。A）事前统计B）事前分析估算C）事后统计D）事后分析估算2.数据的逻辑结构可以分为（）。A）静态结构和动态结构B）物理结构和存储结构C）线性结构和非线性结构D）虚拟结构和抽象结构3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A）必须是连续的B）部分地址必须是连续的C）一定是不连续的D）连续不连续都可以4.线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要好处是（）。A）使空表和非空表的处理统一B）可以加快对表的遍历C）节省存储空间D）可以提高存取表元素的速度5.若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为（）。A）1 和 5B）2 和 4C）4 和 2D）5 和 16.对二叉树 T 中的某个结点 x，它在先根序列、中根序列、后根序列中的序号分别为 pre（x），in（x）、post（x），a 和 b 是 T 中的任意两个结点，下列选项一定错误的是（）。A）a 是 b 的后代且 pre（a）post（b）C）a 是 b 的后代且 in（a）in（b）D）a 在 b 的左边且 in（a）next=L;L=s;3.rear=(rear+1)%(m+1)4.95.1116.n2+n37.O(eloge)8.深度优先9.54/1610.79，56，38三、判断题(对的答错的答，共 10 小题，每小题 2 分，共 20 分)四、综合应用题(共 5 小题，每小题各 8 分，共 40 分)1.（1）(4 分)k=2(i-1)+(j+1)%2（2）(2 分)i=k/2+1(2 分)j=k/2+k%2+1-k/2/22.（1）(2 分)AOV 网（2）(2 分)DFS 序列：V1，V2，V6，V5，V4，V3（3）(2 分)BFS 序列：V1，V2，V4，V3，V6，V5（4）(2 分)拓扑序列：V1，V2，V4，V3，V5，V63.（1）(1 分)先序：ABDGCEHFI(1 分)中序：GDBAEHCFI(1 分)后序：GDBHEIFCA（2）(5 分)顺序存储示意图123456789101112131415ABCDEFGHI4.（1）(4 分)m(k-1)+1因为 T 中只存在度为 0 和 k 的结点。N=n0+nk=B+1=k*nk+1-n0=(k-1)nk+1(nk 就是 m)（2）(2 分)最多：(kh-1)/(k-1)除第 h 层外，第 1 到 h-1 层的每个结点的度都是 k，即满 k 叉树。N=k0+k1+k2+kh-1=(kh-1)/(k-1)(2 分)最少：k(h-1)+1除第 1 层外，每层都有 k 个结点，其中 1 个分支节点和 k-1 个叶子即：N=（h-1）k+15.（1）(4 分)画出哈希表012345678910111214168275519208479231110121431139113（2）(2 分)成功时的平均查找长度：（1+2+1+4+3+1+1+3+9+1+1+3）/8=30/12=5/2（3）(2 分)失败时的平均查找长度（1+2+3+4+5+6+7+8+9+10+11+12+13）/13=91/13=7五、算法设计题(共 4 小题，每小题 10 分，共 40 分)1.void Fun(DbLinkList&L)Tail=L-Left;p=L-Right;i=1;while(p&p!=Tail)if(i%2=0)q=p;/删除结点 pp=p-next;p-Left=q-Left;q-Left-Right=p;q-Right=Tail-Right;/插入到 Tail 之后q-Left=Tail;Tail-Right-Left=q;T-Right=q;else p=p-Right;i+;2.int Match(char*s)char smaxsize;int top=0,i=0;while(si!=#)switch(si)case(:case:case:stop+=si;i+;break;/入栈case):if(stop-1=()top-;i+;break;else printf(“不匹配”);return 0;case:if(stop-1=)top-;i+;break;else printf(“不匹配”);return 0;case:if(stop-1=)top-;i+;break;else printf(“不匹配”);return 0;case#:if(top=0)printf(“匹配成功”);return 1;else printf(“不匹配”);return 0;default:i+;/读入其它字符，不作处理3.int Leaf(CSTree*T)if(T=NULL)return 0;int front=1,rear=1;/front,rear 是队头队尾元素的指针int last=1;/last 指向树中同层结点中最后一个结点int temp=0;/叶子结点数Qrear=T;/Q 是以树中结点为元素的队列while(frontfirstchild=NULL)temp+;while(p!=NULL)/层次遍历if(p-firstchild)Q+rear=p-firstchild;/第一子女入队p=p-nextsibling;/同层兄弟指针后移if(frontlast)last=rear;/本层结束,last 移到指向下层最右结点处return temp;4.void DeletEdge(AdjList g,int i,int j)p=gi.firstarc;pre=NULL;/删顶点 i 的边结点(i,j),pre 是前驱指针while(p)if(p-adjvex=j)if(pre=NULL)gi.firstarc=p-next;elsepre-next=p-next;free(p);break;/释放结点空间，退出循环else pre=p;p=p-next;/沿链表继续查找p=gj.firstarc;pre=NULL;/删顶点 j 的边结点(j,i)while(p)if(p-adjvex=i)if(pre=NULL)gj.firstarc=p-next;elsepre-next=p-next;free(p);break;/释放结点空间，退出循环else pre=p;p=p-next;/沿链表继续查找