830数据结构2010-2016真题答案（有错）

2010参考答案一、选择题111.B2.A3.C4.A5.D6.A7.B8.A9.C10.C1.B12.C13.A14.C15.B16.D17.D18.D19.A20.A5解释：线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。二、填空题123.归并排序。.能否将关键字均匀影射到哈希空间上.一端先进后出有无好的解决冲突的方法456789.顺序存储或链式存储（1+n）/2.从任意节点出发都能访问到整个链表.时间空间.n-1n(n-1)/2.2n-1.nn三、判断题123456789111111.F.F非空才成立.F有向的非强连通图，不成立.T.F表头没有前驱，表尾没有后序.T.F先序跟后序不行，中序才行.T.F不可能0.T1.F2.T3.F4.F5.F四、应用题1．逻辑结构是从操作对象抽象出来的数学模型，结构定义中的“关系”描述的是数据元素之间的逻辑关系；物理结构是数据结构在计算机中的表示（又称,逻辑结构是指数据跟数据间是怎样联系的23．由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。(1)选择一个入度为0的顶点并输出之；(2)从网中删除此顶点及所有出边。拓扑序列1：abcdef拓扑序列2：adbcef.二叉树图如下：45.略。已经不纳入考纲.哈夫曼编码问题编码：3:000020:1010:000122:1118:00137:016.二叉排序树问题比根节点小的往左子树插，大的往右子树插。图如下：删除50这里我用第二种做法:五.算法设计题1&.算法填空（L.elem[i-1]）L.length-1++p*pL.length-1;2.设计算法:输入n个元素的值创建带头结点的单链线性表L。voidCreateList_L(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(inti=n;i>0;i--){p=(LinkList)malloc(sizeof(Lnode));scanf(&p->data);p->next=L->next;L->next=p;}}3.弗洛伊德算法或者迪杰斯特拉算法都可以解决采用弗洛伊德算法（1）采用邻接矩阵，邻接矩阵的值代表乘车费用。（2）定要自己完全理解。2011参考答案一．选择题18.C2.A3.C4.D5.B6.D7.C.C9.D10.C11.A12.D13.D14.A15.A二．填空题1234567891.线性结构非线性结构.(8,9,4,3,6,2,12,13,19,18).二叉树小顶堆.89.存入元素移动指针（严蔚敏书中入栈是这么操作，实际看自己怎么规定）.队列中仅有一个元素（或删除队列变成空）.n-1.k2.b0.n²三、判断题1234567891.T.F.T.F.T.T.T.F.F0.F四．简答题1．第一趟结果：13，27，51，55，10，49，38，65，97，75元素移动五次。2.邻接矩阵图如下：邻接表图如下：拓扑序列：abgcdfe3.关键活动和关键路径关键路径：从起点到终点的最长路径长度，这个最长的路径就叫做关键路径。关键活动：关键路径上的所有活动都是关键活动。关键活动：a1-a4-a8-a11关键路径：a-b-e-h-k4.这道题很重要。《数据结构》上有解析，请认真理解好。5（.哈夫曼树问题1）注意：规定权值较小的结点为左子树（2）由上图可得：A:00B:011C:0101D:10E:11F:01003）需要总bit数：17*2+12*3+5*4+28*2+35*2+3*4=228（需要字节数：228/8=28.5=29需要29个字节。（4）翻译后的正文是：BCBAE.哈希平均查找长度问题6五、算法填空.(1)p->next->data<=mink(2)p->next==null||p->next->data>=maxk(3)p->next=q;12.(4）v<G.vexnum(5)visit(v)(6）!QueueEmpty(Q)(7)DeQueue(Q,u)（8）EnQueue(Q,w)六、编写算法1.后序遍历二叉树voidPostOrderTraversal(BinTreeNode*BT){if(BT!=NULL){PostOrderTraversal(BT->Left);PostOrderTraversal(BT->Right);printf("%c",BT->TData);}}2/.这道题也可以参考《高分笔记》/邻接矩阵typedefstruct_graph{charvexs[MAX];//顶点集合intvexnum;//顶点数intedgnum;//边数intmatrix[MAX][MAX];//邻接矩阵}/Graph,*PGraph;/边的结构体typedefstruct_EdgeData{charstart;//边的起点charend;//边的终点intweight;//边的权重}EDatavoidkruskal(GraphG){inti,m,n,p1,p2;intlength;intindex=0;//rets数组的索引intvends[MAX]={0};//用于保存"已有最小生成树"中每个顶点在该最小树中的终点。EDatarets[MAX];//结果数组，保存kruskal最小生成树的边EData*edges;//图对应的所有边//获取"图中所有的边"edges=get_edges(G);/将边按照"权"的大小进行排序(从小到大)/sorted_edges(edges,G.edgnum);for(i=0;i<G.edgnum;i++){p1=get_position(G,edges[i].start);//获取第i条边的"起点"的序号p2=get_position(G,edges[i].end);//获取第i条边的"终点"的序号m=get_end(vends,p1);//获取p1在"已有的最小生成树"中的终点n=get_end(vends,p2);//获取p2在"已有的最小生成树"中的终点//如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路if(m!=n){vends[m]=n;//设置m在"已有的最小生成树"中的终点为nrets[index++]=edges[i];//保存结果}}free(edges)}2012参考答案一、选择题1.A2.C3.C4.B5.A6.C7.A8.D9.C10.B11.B12.C13.D14.B15.D13解释：判断对满的条件（Q.rear+1）%MAXQSIZE==Q.front，可以看出跟队列大小，头尾指针有关，所以D对。二、填空题1234567891.7.线性和非线性结构.2n-1.能否将关键字均匀影射到哈希空间上有无好的解决冲突的方法.插入和删除首结点时不必对头指针进行特殊处理.2k-12k-1.2e.p->lchild==NULL&&p->rchild==NULL.一端先进后出0．021,235,346,256,558三、判断题12345.T.F.F.T.F度是可以缩短工期的。否则是，是不能缩短整个工期的。67891.F.T.F.F先序和后序是不能确定一颗树的0.F需要1+2+……+n=(1+n)n/2个空间四、简答题.//163335，57，45，39，12，98，86，355,57，45，39，12，98，86，355,57，45，39，12，98，86，985,57，45，39，12，65，86，982.删除线性表L中大于X小于Y的节点3.按边的权值排序：3,5,12,14，15,17,25依次选取，如果不构成回路，则加入；否则，就跳过该边。最小生成树如下：45.深度优先搜索遍历：V0V1V4V2V3V5V6广度优先遍历：V0V1V2V3V4V5V6.弗洛伊德算法，请认真理解。6.五、算法填空12.(QueuePtr)malloc(sizeof(QNode))NULLQ.rear->nextp.!StackEmpty()||p!=NULLPush(S,p)Pop(S,p)p->rchild六、编写算法1.voidpreOrderTraverse(BiTreeT,int*count){if(T){//T不空/如果为叶子节点，就加1if(T->lchild==NULL&&T->rchild==NULL){/*}count++;preOrderTraverse(T->lchild,count);preOrderTraverse(T->rchild,count);}}2.设计一个图的数组表示存储结构，并编写采用数组表示法构造一个无向网的算法#defineMAX_VERTEX_NUM20typedefstructArcCell{VRTypeadj;InfoType*info;ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];}typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;GraphKindkind;}MGraph;2013参考答案一．选择题11.C2.D3.C4.C5.A6.C7.C8.C9.A10.A11.A2.C13.D14.A15.C二、填空题12345671891十字链表三元组.一对一一对多.2n-1.能否将关键字均匀影射到哈希空间上.前驱结点后继结点有无好的解决冲突的方法.n2+1.60解释：三元组存储行标，列表，非零元。一个需要六个字节，0*6=60.L->next=L.440.15,40,95,20,50,70三.判断题1234567891.F相当于树的先序遍历.T.F.F.F.F.F.T.F0.F四、简答题1.从顶点0到其余各节点的最短路径2.34.计算节点值为0的节点个数。.这里要区别克鲁斯卡尔跟普利姆算法的区别普利姆算法：每次选取从这个节点到其他未被选择节点的最短边加入。克鲁斯卡尔：给边排好序，每次选取最短的边，如果不构成回路就加入5.先序序列：ABDGCEHIF中序遍历：DGBAHEICF后序遍历：GDBHIEFCA6.（1）采用头插法，看清楚题目（2）比较4次（3（1*5+2*2+3+4）/9=1.78平均查找长度为1.78五、算法填空12.p->next!=NULLp=p->nextp->next=q->nextfree(q).j<ni>ja[i]=a[i+1]a[i+1]=tempflag==0六、编写算法1．设计在顺序有序表中实现折半查找的算法。（10分）2．设计AOV-网拓扑排序的算法（12分）数据结构》第七章有向无环图及其应用拓扑排序《2014参考答案一、选择题1.C2.A3.A4.B5.D7.C8.C9.C10.A11.A12.D13.B14.A15.A二、填空题123456.一对多多对多.插入和删除首结点时不必对头指针进行特殊处理.2n-1.将矩阵第i行全部置为零.队尾对头先进先出.能否将关键字均匀影射到哈希空间上有无好的解决冲突的方法三、判断题12345678.F.T.T.F.T.F.T.T91.F解释：0.T四、简答题1.2.关键路径：从源点到汇点的路径长度最长的路径叫关键路径。关键路径：a1a5a6a8a7a1034.在排好序的线性表中，删除值为X的所有元素。.算法填空12.sizeof(ElemType)!S.baseS.stacksizeetop+1.v<G.vexnumDeQueueEmpty(Q,u)!Visited[w]TRUEEnQueue(Q,w)六、编写算法.设计将两个有序链表合并为一个有序链表的算法.假设有序链表的元素按照非递减排列.(10分)12.给定带权有向图GV0,V0到其余顶点的最短路径.(15)2015参考答案一、选择题1.D2.C3.C4.B5.C6.A7.A8.B9.A10.C11.A12.C13.B14.A15.A二、填空题12345、从任意节点出发都能访问到整个链表、集合、520、O(n²)、2h-1图形结构67、m⌈m/2⌉、s->next=p->next;p->next=s;三、判断题1234567891.T.F.T.F.T.F.T.T.F0.T表头没有前驱，表尾没有后继不唯一四、简答题12.树的非递归中序遍历.3.快速排序：两边同时遍历，大于枢轴的交换到右边，小于的交换到左边此处不给该题的具体实现，解题过程参照下图：4(.1)((2)拓扑排序：V1v3v2v6v5v43)迪杰斯特拉算法问题：5.构造哈夫曼树如上图，编码a:11b:100c:001d:0001e:101f:01g:0000五、算法填空12、①！P②e③NULL④Q.rear->next⑤p、v<G.vexnum!visited[v]TRUEw>=0DFS(G,w)六、编写算法1.voidProcess(LinkList&L,intx,inty){//L线性表的元素递增有序排列LinkListp=L,q,s;if((p->next!=NULL)&&(x<=y)){while(p->next!=NULL&&p->next->data<=x)p=p->next;if(p->next==NULL||p->next->data>=y)returnERROR;q=p->next;while(q->next!=NULL&&q->data<y){s=q;q=q->next;free(s);}p->next=q;}}2.思路：利用图的广度优先遍历，那么最后一个遍历的节点一定离顶点最远。intMaxdist(AGragh*G,intv){ArcNode*p;intQu[MAXV];//循环队列