数据结构试卷(一)参考答案3199

《数据结构试卷(一)参考答案3199》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构试卷(一)参考答案319917、读过一本好书，像交了一个益友——藏克家数据结构试卷（一）参考答案一、选择题（每题2分，共20分）　　1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、填空题（每空1分，共26分）1.正确性易读性强壮性高效率2.O(n)3.9334.-134X*+2Y*3/-5.2nn-1n+16.e2e7.有向无回路8.n(n-1)/2n(n-1)9.（12，40）（）（74）（23,55，63）10.增加111.O(log2n)O(nlog2n)12.归并三、计算题（每题6分，共24分）

2、1.线性表为：（78，50，40，60，34，90）2.邻接矩阵：邻接表如图11所示：图113.用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.见图12图12四、读算法（每题7分，共14分）1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,...,an,a1）2.递归地后序遍历链式存储的二叉树五、法填空（每空2分，共8分）trueBST->leftBST->right六、编写算法（8分）int

3、CountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX数据结构试卷（二）参考答案一、选择题1.D2.B3.C4.A5.A6.C7.B8.C二、填空题1.构造一个好的HASH函数，确定解决冲突的方法2.stack.top++，stack.s[stack.top]=x3.有序4.O(n2)，O(nlog2n)5.N0-

4、1，2N0+N16.d/27.(31，38，54，56，75，80，55，63)8.(1，3，4，5，2)，(1，3，2，4，5)三、应用题1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.2,ASL=91*1+2*2+3*4+4*2)=25/94.树的链式存储结构略，二叉树略5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6.略四、算法设计题1.设有一

5、组初始记录关键字序列（K1，K2，...，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki　　voidquickpass(intr[],ints,intt)　　{　　inti=s,j=t,x=r[s];　　while(ix)j=j-1;if(i

6、　}　　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;　　　　

7、　if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}}}数据结构试卷（三）参考答案一、选择题　　1.B2.B3.A4.A5.A　　6.B7.D8.C9.B10.D　　第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B　　第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂

8、度为O(log2n)二、填空题1.顺序存储结构、链式存储结构2.9，5013.54.出度，入度5.06.e=d7.中序8.79.O(1)10.i/2，2i+111.(5，16，71，23，72，94，73)12.(1，4，3，2)13.j+1，hashtable