四读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树五法填空 ( 每空 2 分, 共 8 分 ) true B

Size: px

Start display at page:

Download "四读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树五法填空 ( 每空 2 分, 共 8 分 ) true B"

晓贲
6 years ago
Views:

1 数据结构试卷 ( 一 ) 参考答案一选择题 ( 每题 2 分, 共 20 分 ) 1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二填空题 ( 每空 1 分, 共 26 分 ) 1. 正确性易读性强壮性高效率 2. O(n) X * + 2 Y * 3 / n n-1 n+1 6. e 2e 7. 有向无回路 8. n(n-1)/2 n(n-1) 9. (12,40) ( ) (74) (23,55,63) 10. 增加 1 11.O(log 2n) O(nlog 2n) 12. 归并三计算题 ( 每题 6 分, 共 24 分 ) 1. 线性表为 :(78,50,40,60,34,90) 邻接矩阵 : 邻接表如图 11 所示 : 图用克鲁斯卡尔算法得到的最小生成树为 : (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 见图图

2 四读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树五法填空 ( 每空 2 分, 共 8 分 ) true BST->left BST->right 六编写算法 (8 分 ) int CountX(LNode* HL,ElemType x) int i=0; LNode* p=hl;//i 为计数器 while(p!=null) if (P->data==x) i++; p=p->next; //while, 出循环时 i 中的值即为 x 结点个数 return i; //CountX 数据结构试卷 ( 二 ) 参考答案一选择题 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二填空题 1. 构造一个好的 HASH 函数, 确定解决冲突的方法 2. stack.top++,stack.s[stack.top]=x 3. 有序 4. O(n 2 ),O(nlog 2n) 5. N 0-1,2N 0+N 1 6. d/2 7. (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/9 4. 树的链式存储结构略, 二叉树略 5. E=(1,3),(1,2),(3,5),(5,6),(6,4) 6. 略四算法设计题 1. 设有一组初始记录关键字序列 (K 1,K 2,,K n), 要求设计一个算法能够在 O(n) 的时间复杂度内将线性表划分成两部分, 其中左半部分的每个关键字均小于 K i, 右半部分的每个关键字均大于等于 K i

3 void quickpass(int r[], int s, int t) int i=s, j=t, x=r[s]; while(i<j) while (i<j && r[j]>x) j=j-1; if (i<j) r[i]=r[j];i=i+1; while (i<j && r[i]<x) i=i+1; if (i<j) r[j]=r[i];j=j-1; r[i]=x; 2. 设有两个集合 A 和集合 B, 要求设计生成集合 C=A B 的算法, 其中集合 A B 和 C 用链式存储结构表示 typedef struct node int data; struct node *next;lklist; void intersection(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; 数据结构试卷 ( 三 ) 参考答案一选择题 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(log 2n) 二填空题 1. 顺序存储结构链式存储结构 2. 9, 出度, 入度 e=d 7. 中序

4 O(1) 10. i/2,2i (5,16,71,23,72,94,73) 12. (1,4,3,2) 13. j+1,hashtable[j].key==k 14. return(t),t=t->rchild 第 8 小题分析 : 二分查找的过程可以用一棵二叉树来描述, 该二叉树称为二叉判定树在有序表上进行二分查找时的查找长度不超过二叉判定树的高度 1+log 2n 三计算题 1. A E B NULL F G C H F D K J 2 H(36)=36 mod 7=1; H 1(22)=(1+1) mod 7=2;. 冲突 H(15)=15 mod 7=1;. 冲突 H 2 (22)=(2+1) mod 7=3; H 1(15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1;. 冲突 (1) (2)ASL= (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,18 1,3, 4,6,8,9,10,12,18,18 四算法设计题 1. 设计在单链表中删除值相同的多余结点的算法 typedef int datatype; typedef struct node datatype data; struct node *next;lklist; void delredundant(lklist *&head)

5 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; else s=q,q=q->next; 2. 设计一个求结点 x 在二叉树中的双亲结点算法 typedef struct node datatype data; struct node *lchild,*rchild; bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) 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); void parent(bitree *bt,char x) int i; 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("not found x\n"); else if (i<=r) printf("%c",bt->data); 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. O(n 2 ),O(nlog 2n) 2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink k-1 5. n/ ,51 7. m-1,(r-f+m)%m

6 8. n+1-i,n-i 9. (19,18,16,20,30,22) 10. (16,18,19,20,32,22) 11. A[i][j]=1 12. 等于 13. BDCA 14. hashtable[i]=0,hashtable[k]=s 三计算题 1. LS > > > 1 0 e 0 a > > 1 0 b 0 c 0 d 2. (1) ABCDEF; BDEFCA;(2) ABCDEFGHIJK; BDEFCAIJKHG 林转换为相应的二叉树 ; A B G C H D I E J F K 3.H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)= 四算法设计题 1. 设单链表中有仅三类字符的数据元素 ( 大写字母数字和其它字符 ), 要求利用原单链表中结点空间设计出三个单链表的算法, 使每个单链表只包含同类字符 typedef char datatype; typedef struct node datatype data; struct node *next;lklist;

7 void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) head=p->next; p->next=0; if (p->data>='a' && p->data<='z') p->next=ha; ha=p; else if (p->data>='0' && p->data<='9') p->next=hb; hb=p; else p->next=hc; hc=p; 2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法 typedef struct node int data; struct node *lchild,*rchild; bitree; void swapbitree(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. 在链式存储结构上建立一棵二叉排序树 #define n 10 typedef struct nodeint key; struct node *lchild,*rchild;bitree; void bstinsert(bitree *&bt,int key) if (bt==0)bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0; else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); void createbsttree(bitree *&bt) int i; for(i=1;i<=n;i++) bstinsert(bt,random(100)); 数据结构试卷 ( 五 ) 参考答案一选择题 1.A 2.B 3.A 4.A 5.D 6.B 7.B 8.B 9.C 10.C 二填空题 1. top1+1=top2

8 2. 可以随机访问到任一个顶点的简单链表 3. i(i+1)/2+j-1 4. FILO,FIFO 5. ABDECF,DBEAFC,DEBFCA 6. 8,64 7. 出度, 入度 8. k i <=k 2i && k i <=k 2i+1 9. n-i,r[j+1]=r[j] 10. mid=(low+high)/2,r[mid].key>k 三应用题 1. DEBCA 2. E=(1,5),(5,2),(5,3),(3,4),W=10 3. ASL=(1*1+2*2+3*4)/7=17/7 4. ASL1=7/6,ASL2=4/3 四算法设计题 1. 设计判断两个二叉树是否相同的算法 typedef struct node datatype data; struct node *lchild,*rchild; bitree; int judgebitree(bitree *bt1,bitree *bt2) if (bt1==0 && bt2==0) return(1); 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. 设计两个有序单链表的合并排序算法 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data<hb->data)if(s==0) hc=s=ha; else 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

9 二判断题 1. 错 2. 对 3. 对 4. 对 5. 错 6. 错 7. 对 8. 错 9. 对 10. 对三填空题 1. O(n) 2. s->next=p->next; p->next=s 3. (1,3,2,4,5) 4. n F==R 7. p->lchild==0&&p->rchild==0 8. O(n 2 ) 9. O(nlog 2 n), O(n) 10. 开放定址法, 链地址法四算法设计题 1. 设计在顺序有序表中实现二分查找的算法 struct record int key; int others;; int bisearch(struct record r[ ], int k) int low=0,mid,high=n-1; while(low<=high) mid=(low+high)/2; if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; return(0); 2. 设计判断二叉树是否为二叉排序树的算法 int minnum=-32768,flag=1; typedef struct nodeint key; struct node *lchild,*rchild;bitree; void inorder(bitree *bt) if (bt!=0) inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild); 3. 在链式存储结构上设计直接插入排序算法 void straightinsertsort(lklist *&head) lklist *s,*p,*q; int t; if (head==0 head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next)

10 for(s=head;s!=q->next;s=s->next) if (s->data>p->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;

试卷代号 : 座位号 I II 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构试题 2011 年 7 月! 题号 I - I 二三四! 五! 六总分分数 I I I 1 1- I ---1 I 得分评卷人一单项选择

试卷代号 : 座位号 I II 中央广播电视大学学年度第二学期开放本科期末考试数据结构试题 2011 年 7 月! 题号 I - I 二三四! 五! 六总分分数 I I I 1 1- I ---1 I 得分评卷人一单项选择试卷代号 : 1 0 1 0 座位号 I II 中央广播电视大学 2 0 1 0-2 0 1 1 学年度第二学期 " 开放本科 " 期末考试数据结构试题 2011 年 7 月! 题号 I - I 二三四! 五! 六总分分数 I I I 1 1- I ---1 I 得分评卷人一单项选择题 ( 在括号内填写所选择的标号每小题 2 分, 共 1 8 分 ) 1. 一种抽象数据类型包括数据和

四 读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树 五 法填空 ( 每空 2 分, 共 8 分 ) true B

四读算法 ( 每题 7 分, 共 14 分 ) 1. (1) 查询链表的尾结点 (2) 将第一个结点链接到链表的尾部, 作为新的尾结点 (3) 返回的线性表为 (a 2,a 3,,a n,a 1 ) 2. 递归地后序遍历链式存储的二叉树五法填空 ( 每空 2 分, 共 8 分 ) true B