1、姓名：报考专业：准考证号码：密封线内不要写题2019年全国硕士研究生招生考试初试自命题试题科目名称：数据结构（C语言版）（A卷B卷）科目代码：856考试时间：3小时 满分150分可使用的常用工具：无 计算器 直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。一、选择题(共15小题，每小题2分，共30分)1. 计算算法的时间复杂度是属于一种（ ）的方法。A）事前统计 B）事前分析估算 C）事后统计 D）事后分析估算2. 数据的逻辑结构可以分为（ ）。A）静态结构和动态结构 B）物理结构和存储结构C）线性结构和非线性结构 D）虚
2、拟结构和抽象结构3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）连续不连续都可以4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。A）使空表和非空表的处理统一 B）可以加快对表的遍历C）节省存储空间 D）可以提高存取表元素的速度5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear 和front的值分别为（ ）。A）1和5 B）2和4 C）4和2 D）5和16. 对二叉树T中的
3、某个结点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)+
4、(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- n
5、0=(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
6、+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 Matc
7、h(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(“不匹配”)
8、; 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+
9、; 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; /沿链表继续查找 第 9 页 共 9 页
