资源描述
姓名：报考专业：准考证号码：密封线内不要写题2019年全国硕士研究生招生考试初试自命题试题答案科目名称：数据结构（C语言版）（A卷B卷）科目代码：856考试时间：3小时 满分150分可使用的常用工具：无 计算器 直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。一、选择题(共15小题，每小题2分，共30分)BCDAB ADBAC ABDDC 二、填空题(共10小题，每小题2分，共20分)1. n2. s-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; /删除结点p p=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;else pre-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;else pre-next=p-next;free(p);break; /释放结点空间，退出循环 else pre=p; p=p-next; /沿链表继续查找 第 4 页 共 4 页
展开阅读全文