1、1. 数据结构试卷（一）参考答案 一、选择题 1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B 二、填空题 1. 1. (F+1) % m 2. 2. O(n)， O(n) 3. 3. 2n， n+1 4. 4. s-next=p-next; s-next=s 5. 5. n, 2e 6. 6. m=2e 7. 7. CBA 8. 8. 4， 16 9. 9. i-j+1， 0 10. 10. n-1 三、应用题 1. 1. 链式存储结构略，前序 ABDEC，中序 DBEAC，后序 DEBCA。 2. 2. 哈夫曼树略， WPL=78 3. 3. (18,5,1
2、6,19,21,23)， (5， 16， 21， 19， 18， 23) 4. 4. 线性探测： 6827322510876543210 链地址法： 276832251086543210hhhhhhh5. 5. 深度： 125364，广度： 123456，最小生成树 T 的边集为 E=(1， 4)， (1， 3)， (3， 5)， (5， 6)，(5,6) 四、算法设计题 1. 1. 设计判断单链表中结点是否关于 中心对称算法。 typedef struct int s100; int top; sqstack; int lklistsymmetry(lklist *head) sqstack
3、 stack; stack.top= -1; lklist *p; for(p=head;p!=0;p=p-next) stack.top+; stack.sstack.top=p-data; for(p=head;p!=0;p=p-next) if (p-data=stack.sstack.top) stack.top=stack.top-1; else return(0); return(1); 2. 2. 设计在链式存储结构上建立一棵二叉树的算法。 typedef char datatype; typedef struct node datatype data; struct node
4、*lchild,*rchild; bitree; void createbitree(bitree * scanf(“%c“, if(ch=#) bt=0; return; bt=(bitree*)malloc(sizeof(bitree); bt-data=ch; createbitree(bt-lchild); createbitree(bt-rchild); 3. 3. 设计判断一棵二叉树是否是二叉排序树的算法。 int minnum=-32768,flag=1; typedef struct nodeint key; struct node *lchild,*rchild;bitree
5、; void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key; inorder(bt-rchild); 数据结构试卷（二）参考答案 一、选择题 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空题 1. 1. 构造一个好的 HASH 函数，确定解决冲突的方法 2. 2. stack.top+， stack.sstack.top=x 3. 3. 有序 4. 4. O(n2)， O(nlog2n) 5. 5. N0-1， 2N0+N1 6. 6.
6、d/2 7. 7. (31， 38， 54， 56， 75， 80， 55， 63) 8. 8. (1， 3， 4， 2)， (1， 3， 2， 4) 三、应用题 1. 1. (22， 40， 45， 48， 80， 78)， (40， 45， 48， 80， 22， 78) 2. 2. q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q; 3. 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 4. 树的链式存储结构略，二叉树略 5. 5. E=(1， 3)， (1， 2)， (3， 5)， (5， 6)， (6，
7、 4) 6. 6. 略 四、算法设计题 1. 1. 设有一组初始记录关键字序列（ K1， K2， ， Kn），要求设计一个算法能够在 O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于 Ki，右半部分的每个关键字均大于等于 Ki。 void quickpass(int r, int s, int t) int i=s, j=t, x=rs; while(ix) j=j-1; if (inext) for(q=hb;q!=0;q=q-next) if (q-data=p-data) break; if(q!=0) t=(lklist *)malloc(sizeof(lkl
8、ist); t-data=p-data;t-next=hc; hc=t; 数据结构试卷（三）参考答案 一、选择题 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第 3 小题分析：首先用指针变量 q 指向结点 A 的后继结点 B，然后将结点 B 的值复制到结点 A 中，最后删除结点 B。 第 9 小题分析： 9 快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的 10 个数，而堆 排序只需要在初始堆的基础上再进行 10 次筛选即可，每次筛选的时间复杂度为 O(log2n)。 二、填空题 1. 1. 顺序存储结构、链式存储结构 2. 2. 9，
9、501 3. 3. 5 4. 4. 出度，入度 5. 5. 0 6. 6. e=d 7. 7. 中序 8. 8. 7 9. 9. O(1) 10. 10. i/2， 2i+1 11. 11. (5， 16， 71， 23， 72， 94， 73) 12. 12. (1， 4， 3， 2) 13. 13. j+1， hashtablej.key=k 14. 14. return(t)， t=t-rchild 第 8 小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度 1+log2n。 三、算法设计题 1. 1. 设计在
10、单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node datatype data; struct node *next;lklist; void delredundant(lklist * 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; else s=q,q=q-next; 2. 2. 设计一个求结点 x在二叉树中的双亲结点算法。 typedef struct node
11、datatype data; struct node *lchild,*rchild; bitree; bitree *q20; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) if (bt!=0 return; else r=(r+1)% 20; qr=bt; preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x) int i; preorder(bt,x); for(i=f+1; ilchild-data=x | qi-rchild-
12、data) break; if (flag=0) printf(“not found xn“); else if (idata); else printf(“not parent“); 数据结构试卷（四）参考答案 一、选择题 1 C 2 D 3 D 4 B 5 C 6 A 7 B 8 A 9 C 10 A 二、填空题 1. 1. O(n2)， O(nlog2n) 2. 2. pllink-rlink=p-rlink; p-rlink-llink=p-rlink 3. 3. 3 4. 4. 2k-1 5. 5. n/2 6. 6. 50， 51 7. 7. m-1， (R-F+M)%M 8. 8
13、. n+1-i， n-i 9. 9. (19， 18， 16， 20， 30， 22) 10. 10. (16， 18， 19， 20， 32， 22) 11. 11. Aij=1 12. 12. 等于 13. 13. BDCA 14. 14. hashtablei=0， hashtablek=s 三、算法设计题 1. 1. 设单链表中有仅三类字符的数据元素 (大写字母、数字和其它字符 )，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表 只包含同类字符。 typedef char datatype; typedef struct node datatype data; stru
14、ct node *next;lklist; void split(lklist *head,lklist * ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) head=p-next; p-next=0; if (p-data=A ha=p; else if (p-data=0 hb=p; else p-next=hc; hc=p; 2. 2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedef struct node int data; struct node *lchild,*rchild; bitree; void swapbitree
15、(bitree *bt) bitree *p; if(bt=0) return; swapbitree(bt-lchild); swapbitree(bt-rchild); p=bt-lchild; bt-lchild=bt-rchild; bt-rchild=p; 3. 3. 在链式存储结构上建立一棵二叉排序树。 #define n 10 typedef struct nodeint key; struct node *lchild,*rchild;bitree; void bstinsert(bitree * bt-key=key;bt-lchild=bt-rchild=0; else i
16、f (bt-keykey) bstinsert(bt-lchild,key); else bstinsert(bt-rchild,key); void createbsttree(bitree * for(i=1;ik 三、应用题 1. 1. DEBCA 2. 2. E=(1,5),(5,2),(5,3),(3,4),W=10 3. 3. ASL=(1*1+2*2+3*4)/7=17/7 4. 4. ASL1=7/6， ASL2=4/3 四、算法设计题 1. 1. 设计判断两个二叉树是否相同的算法。 typedef struct node datatype data; struct node
17、*lchild,*rchild; bitree; int judgebitree(bitree *bt1,bitree *bt2) if (bt1=0 else if (bt1=0 | bt2=0 |bt1-data!=bt2-data) return(0); else return(judgebitree(bt1-lchild,bt2-lchild)*judgebitree(bt1-rchild,bt2-rchild); 2. 2. 设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist * while(ha!=0 el
18、se s-next=ha; s=ha;ha=ha-next; else if(s=0) hc=s=hb; else s-next=hb; s=hb;hb=hb-next; if(ha=0) s-next=hb; else s-next=ha; 数据结构试卷（六）参考答案 一、选择题 1 D 2 A 3 A 4 A 5 D 6 D 7 B 8 A 9 C 10 B 11 C 12 A 13 B 14 D 15 B 二、判断题 1错 2对 3对 4对 5错 6错 7对 8错 9对 10对 三、填空题 1. 1. O(n) 2. 2. s-next=p-next; p-next=s 3. 3. (1
19、， 3， 2， 4， 5) 4. 4. n-1 5. 5. 129 6. 6. F=R 7. 7. p-lchild=0 int others; int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(lowk) high=mid-1; else low=mid+1; return(0); 2. 2. 设计判断二叉树是否为二叉排序树的算法。 int minnum=-32768,flag=1; typedef struct nodeint key; struct node *lchild,*rchild;bitree
20、; void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key;inorder(bt-rchild); 3. 3. 在链式存储结构上设计直接插入排序算法 void straightinsertsort(lklist * int t; if (head=0 | head-next=0) return; else for(q=head,p=head-next;p!=0;p=q-next) for(s=head;s!=q-next;s=s-next) if (s-datap
21、-data) break; if(s=q-next)q=p; elseq-next=p-next; p-next=s-next; s-next=p; t=p-data;p-data=s-data;s-data=t; 数据结构试卷（七） 一、选择题 1 B 2 B 3 C 4 B 5 B 6 A 7 C 8 C 9 B 10 D 二、判断题 1对 2对 3对 4对 5对 6对 7对 8错 9错 10错 三、填空题 1. 1. s-left=p， p-right 2. 2. n(n-1)， n(n-1)/2 3. 3. n/2 4. 4. 开放定址法，链地址法 5. 5. 14 6. 6. 2h-
22、1， 2h-1 7. 7. (12， 24， 35， 27， 18， 26) 8. 8. (12， 18， 24， 27， 35， 26) 9. 9. 5 10. 10. inext=0) return; for(q=head; q!=0;q=q-next) min=q-data; s=q; for(p=q-next; p!=0;p=p-next) if(minp-data)min=p-data; s=p; if(s!=q)t=s-data; s-data=q-data; q-data=t; 2. 2. 设计在顺序存储结构上实现求子串算法。 void substring(char s , lo
23、ng start, long count, char t ) long i,j,length=strlen(s); if (startlength) printf(“The copy position is wrong“); else if (start+count-1length) printf(“Too characters to be copied“); else for(i=start-1,j=0; ikey=x) return; else if (bt-keyx) level(bt-lchild,x); else level(bt-rchild,x); 数据结构试卷（八）参考答案 一
24、、选择题 1 C 2 C 3 C 4 B 5 B 6 C 7 B 8 C 9 A 10 A 二、判断题 1对 2错 3对 4错 5错 6对 7对 8对 9对 10对 三、填空题 1. 1. (49， 13， 27， 50， 76， 38， 65， 97) 2. 2. t=(bitree *)malloc(sizeof(bitree)， bstinsert(t-rchild,k) 3. 3. p-next=s 4. 4. head-rlink， p-llink 5. 5. CABD 6. 6. 1， 16 7. 7. 0 8. 8. (13， 27， 38， 50， 76， 49， 65， 97
25、) 9. 9. n-1 10. 10. 50 四、算法设计题 1. 1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。 void countnode(bitree *bt,int countnode(bt-lchild,count); countnode(bt-rchild,count); 2. 2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 typedef struct int vertexm; int edgemm;gadjmatrix; typedef struct node1int info;int adjvertex; struct node1 *nextarc;
26、glinklistnode; typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 ) int i,j; glinklistnode *p; for(i=0;iadjvertex=j; p-nextarc=gi.firstarc; gi.firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode);p-adjvertex=i; p-nextarc=gj.firstarc; gj.firstarc=p;
