命题计算机系答案824数据结构

西安科技大2008年入学考试参考答案科目编号 科目名称：数据结构与算法设一、选择题（每题1分，共10分 9. 二、填空题（每空1分，共20分9．12．插入 选13．开放定址法 链地址14．n(n- n(n-15．n-1；三、解答题（6题，每题10分60分n1n由于表长n已给定，此时证明理想的块长度应 ，n nns=┏n/b┑=┏10000/10┑=100平均检索长度为2外排序是在排序的过参与排序的数据太多，在内存中容纳不下，因此在排序过需要不断进行内外存的信息传送的排序。决定外排序时间性3n=1n<m-1n=ma1，a2，…，am，b1，b2，…，bm因为前序序列由前序遍历而得a1即为根结点的元素序序列由可以得到{b1,…,bj-1}为左的中序序列，{bj+1,…,bm}为右的中序若j=1，即b1为根，此时二叉树的左为空，{a2,…,am}为右的前序序列，{b2，…,bm}为右的中序序列右的结点数为m-1由此，这两个序列唯一确定了右，也唯一确定了二叉树。若j=m，即bm为根，此时二叉树的右为空，同上，子序列{a2,…,am}{b1,…,bm-1}唯一确定左序列{aj+1,…,am}{bj+1,…,bm}唯一确定了右。由此证明了唯一的根及其左右只能构成一棵确定的二叉树。4（9先序：（A）B（D）F（K）I H（J）G J（C（后序：（D）K（I）F J（E）G（C）A513H(key)=keyMOD13。用线性探测再散列法解决，各关键字在表中的位置如下所示 76FFGMHILJKF：FGILJKHF：FGHMILJK 8AABCEFGD四、算法设计题（任选3题，每题20共60分（2，1，3p1，qpq域向后移动直到终端结点来删除所有与*pdatanextvoidpurge(slink{slink*p=sq->next,*q,*r;if(p==NULL)return;while(q-if(q->next->data==p->data){}elseq=q->next;}}若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j中的最大值则称此元素为该矩阵中的一个马鞍点假设以二维数组矩阵，voidGet_Saddle(intA[m][n])//A{{if(A[i][j]<min)min=A[i][j];if(A[i][j]==min){if(min<A[k][j])flag=0; }采用邻接表结构，编写一个判别无向图中任意给定的两个顶点之间是kintintexist_path_len(AdjListG,inti,intj,int{if(i==j&&k==0)return1;elseif(k>0){{if(exist_path_len(G,l,j,k-1))returnreturn0;}T[n]中，T[n]T[0]该二叉树的二叉链表表示。typedefstructnode{intdata;stuctnodetypedefBintreeNode*voidConstrucTree(intT[],intn,intI,BintreeNode*&intmain(void){Binarytreet;intn;Cout<<”pleaseenterthenumberofInt*A=newFor(int cin>>A[i]For(intI=0;I<n;I++)cout<<A[i]; Areturn1}voidConstrucTree(intT[],intn,intI,BintreeNode*&{if(I>=n)ptr=NULL ptr=newBintreeNode;