数据结构试题

1数据结构试卷（一）阅读算法（每题7分，共14分）1.LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L-next){q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）2.voidABC(BTNode*BT){ifBT{ABC(BT-left);ABC(BT-right);coutBT-data'';}}该算法的功能是：递归地后序遍历链式存储的二叉树。算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST-data){item=BST-data;//查找成功return__true_________;}elseif(itemBST-data)returnFind(__BST-left___,item);elsereturnFind(__BST-right___,item);}//if}编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。2intCountX(LNode*HL,ElemTypex)intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P-data==x)i++;p=p-next;}//while,出循环时i中的值即为x结点个数returni;}//CountX1．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。算法设计题1.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(ij){while(ij&&r[j]x)j=j-1;if(ij){r[i]=r[j];i=i+1;}while(ij&&r[i]x)i=i+1;if(ij){r[j]=r[i];j=j-1;}}r[i]=x;}2.设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next){for(q=hb;q!=0;q=q-next)if(q-data==p-data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-next=hc;hc=t;}}}计算题(每题10分，共30分)1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。3AEBFGCDHFKJNULL2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图中填写出散列表：`0123456（2）求出在查找每一个元素概率相等情况下的平均查找长度。H(36)=36mod7=1;H１(22)=(1+1)mod7=2;….冲突H(15)=15mod7=1;….冲突H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;….冲突（1）01234566336152240（2）ASL=6.15311213．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18算法设计题(每题15分，共30分)1．设计在单链表中删除值相同的多余结点的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p-next){for(q=p-next,s=q;q!=0;)if(q-data==p-data){s-next=q-next;free(q);q=s-next;}4else{s=q,q=q-next;}}}2.设计一个求结点x在二叉树中的双亲结点算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt-data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt-lchild,x);preorder(bt-rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i=r;i++)if(q[i]-lchild-data==x||q[i]-rchild-data)break;if(flag==0)printf(notfoundx\n);elseif(i=r)printf(%c,bt-data);elseprintf(notparent);}1.设计在顺序有序表中实现二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].keyk)high=mid-1;elselow=mid+1;}return(0);}2.设计判断二叉树是否为二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt-lchild);if(minnumbt-key)flag=0;minnum=bt-key;inorder(bt-rchild);}}3.在链式存储结构上设计直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head-next==0)return;5elsefor(q=head,p=head-next;p!=0;p=q-next){for(s=head;s!=q-next;s=s-next)if(s-datap-data)break;if(s==q-next)q=p;else{q-next=p-next;p-next=s-next;s-next=p;t=p-data;p-data=s-data;s-data=t;}}}1.设计一个在链式存储结构上统计二叉树中结点个数的算法。voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt-lchild,count);countnode(bt-rchild,count);}}2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i=n-1;i++)g2[i].firstarc=0;for(i=0;i=n-1;i++)for(j=0;j=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p-adjvertex=j;p-nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p-adjvertex=i;p-nextarc=g[j].firstarc;g[j].firstarc=p;}}6数据结构试卷（四）计算题(每题10分，共30分)1、画出广义表LS=((),(e),(a,(b,c,d)))的头尾链表存储结构。2、下图所示的森林：(1)求树（a）的先根序列和后根序列；(2)求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)3、设散列表的地址范围是[0..9]，散列函数为H（key）=（key2+2）MOD9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。四、算法设计题(每题10分，共30分)1．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3.在链式存储结构上建立一棵二叉排序树。7数据结构试卷（五）三、应用题(32分)1.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。2.设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。3.设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。4.设散列表的长度为8，散列函数H(k)=kmod7，初始记录关键字序列为(25，31，8，27，