资源描述
word34 / 34数据结构试卷一三、计算题每题 6 分，共24分1. 在如下数组A中存储了一个线性表，表头指针为A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. 请画出如下图的邻接矩阵和邻接表。3. 一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7; E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4. 画出向小根堆中参加数据4, 2, 5, 8, 3时，每参加一个数据后堆的变化。四、阅读算法每题7分，共14分1. LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答如下问题： 1说明语句S1的功能； 2说明语句组S2的功能； 3设链表表示的线性表为a1,a2, ,an,写出算法执行后的返回值所表示的线性表。2. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;/查找成功 return _; else if(itemdata) return Find(_,item); else return Find(_,item); /if六、编写算法共8分统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)数据结构试卷二三、应用题(36分)1 设一组初始记录关键字序列为(45，80，48，40，22，78)，如此分别给出第4趟简单项选择择排序和第4趟直接插入排序后的结果。2 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列设双向链表中结点的两个指针域分别为llink和rlink。3 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比拟次数并计算出查找成功时的平均查找长度。4 设一棵树T中边的集合为(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)，要求用孩子兄弟表示法二叉链表表示出该树的存储结构并将该树转化成对应的二叉树。5 设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。6 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分) 1 设有一组初始记录关键字序列K1，K2，Kn，要求设计一个算法能够在O(n)的时间复杂度将线性表划分成两局部，其中左半局部的每个关键字均小于Ki，右半局部的每个关键字均大于等于Ki。2 设有两个集合A和集合B，要求设计生成集合C=AB的算法，其中集合A、B和C用链式存储结构表示。数据结构试卷三二填空题1. 如下算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i,j; j=i=k % p;while (hashtablej.key!=k&hashtablej.flag!=0)j=(_) %m; if (i=j) return(-1); if (_ ) return(j); else return(-1);2. 如下算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (t!=0)if (t-key=k)_; else if (t-keyk) t=t-lchild; else_;三、计算题(每题10分，共30分)1.二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。2待散列的线性表为36，15，40，63，22，散列用的一维地址空间为0.6，假定选用的散列函数是HK= K mod 7，假如发生冲突采用线性探查法处理，试：1计算出每一个元素的散列地址并在如下图中填写出散列表： 0 1 2 3 4 5 62求出在查找每一个元素概率相等情况下的平均查找长度。3序列10，18，4，3，6，12，1，9，18，8请用快速排序写出每一趟排序的结果。四、算法设计题(每题15分，共30分)1 设计在单链表中删除值一样的多余结点的算法。2 设计一个求结点x在二叉树中的双亲结点算法。数据结构试卷四1 设一组初始记录关键字序列为(20，18，22，16，30，19)，如此以20为中轴的一趟快速排序结果为_。2 设一组初始记录关键字序列为(20，18，22，16，30，19)，如此根据这些初始关键字序列建成的初始堆为_。3 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，如此顶点i和顶点j互为邻接点的条件是_。4 设无向图对应的邻接矩阵为A，如此A中第i上非0元素的个数_第i列上非0元素的个数填等于，大于或小于。5 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，如此后序遍历该二叉树的序列为_。6 设散列函数H(k)=k mod p，解决冲突的方法为链地址法。要求在如下算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。typedef struct node int key; struct node *next; lklist; void createlkhash(lklist *hashtable )int i,k; lklist *s;for(i=0;im;i+)_;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_;三、计算题(每题10分，共30分)1、画出广义表LS=( ) , (e) , (a , (b , c , d )的头尾链表存储结构。2、如下图所示的森林：(1) 求树a的先根序列和后根序列； (2) 求森林先序序列和中序序列；3将此森林转换为相应的二叉树；3、设散列表的地址围是 0.9 ，散列函数为Hkey= key 2 +2MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。四、算法设计题(每题10分，共30分)1 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3. 在链式存储结构上建立一棵二叉排序树。数据结构试卷五1. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return；2. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。struct recordint key; int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(low=high) _; if(rmid.key=k) return(mid+1); else if(_) high=mid-1;else low=mid+1; return(0);三、应用题(32分)1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。2. 设无向图G如右图所示，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。4. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。四、算法设计题(28分)1 设计判断两个二叉树是否一样的算法。2 设计两个有序单链表的合并排序算法。数据结构试卷六四、算法设计题(20分) 设计在顺序有序表中实现二分查找的算法。 设计判断二叉树是否为二叉排序树的算法。 在链式存储结构上设计直接插入排序算法数据结构试卷七三、填空题(30分)1. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(ij) while (ix.key) j=j-1; if (ij) ri=rj;i=i+1; while (_) i=i+1; if (idata=k;t-lchild=t-rchild=0;else if (t-datak) bstinsert(t-lchild,k);else_;3 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，如此在结点A的后面插入结点X需要执行的语句序列：s-next=p-next; _;。4 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，如此指针变量p和指针变量head之间的关系是p=_和head=_设结点中的两个指针域分别为llink和rlink。5 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，如此其前序遍历序列为_。6 完全二叉树中第5层上最少有_个结点，最多有_个结点。7 设有向图中不存在有向边，如此其对应的邻接矩阵A中的数组元素Aij的值等于_。8 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，如此第4趟直接选择排序完毕后的结果为_。9 设连通图G中有n个顶点e条边，如此对应的最小生成树上有_条边。10 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，如此将它们调整成初始堆只需把16与_相互交换即可。四、算法设计题(20分)1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。数据结构试卷九五、算法设计题(20分)1 设计计算二叉树中所有结点值之和的算法。2 设计将所有奇数移到所有偶数之前的算法。3 设计判断单链表中元素是否是递增的算法。数据结构试卷十二、填空题(48分，其中最后两小题各6分)1. 设指针变量p指向单链表中结点A，如此删除结点A的语句序列为：q=p-next；p-data=q-data；p-next=_；feee(q)；2. 数据结构从逻辑上划分为三种根本类型：_、_和_。3. 设无向图G中有n个顶点e条边，如此用邻接矩阵作为图的存储结构进展深度优先或广度优先遍历时的时间复杂度为_；用邻接表作为图的存储结构进展深度优先或广度优先遍历的时间复杂度为_。4. 设散列表的长度为8，散列函数H(k)=k % 7，用线性探测法解决冲突，如此根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是_。5. 设一组初始关键字序列为(38，65，97，76，13，27，10)，如此第3趟冒泡排序完毕后的结果为_。6. 设一组初始关键字序列为(38，65，97，76，13，27，10)，如此第3趟简单项选择择排序后的结果为_。7. 设有向图G中的有向边的集合E=，如此该图的一个拓扑序列为_。8. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的容。typedef struct nodeint data;struct node *lchild;_;bitree;void createbitree(bitree *&bt)scanf(“%c,&ch);if(ch=#) _;else bt=(bitree*)malloc(sizeof(bitree); bt-data=ch; _;createbitree(bt-rchild);9. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的容。typedef struct node int data; struct node *next; lklist; void lklistcreate(_ *&head ) for (i=1;idata);p-next=0;if(i=1)head=q=p;else q-next=p;_; 三、算法设计题(22分)1 设计在链式存储结构上合并排序的算法。2 设计在二叉排序树上查找结点X的算法。3 设关键字序列(k1，k2，kn-1)是堆，设计算法将关键字序列(k1，k2，kn-1，x)调整为堆。 数据结构试卷一参考答案三、计算题每题6分，共24分1. 线性表为：78，50，40，60，34，902. 邻接矩阵： 邻接表如图11所示：图113. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 见图124444422255285283452843图12四、 读算法每题7分，共14分1. 1查询链表的尾结点2将第一个结点到链表的尾部，作为新的尾结点 3返回的线性表为a2,a3,an,a1 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. (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. 设有一组初始记录关键字序列K1，K2，Kn，要求设计一个算法能够在O(n)的时间复杂度将线性表划分成两局部，其中左半局部的每个关键字均小于Ki，右半局部的每个关键字均大于等于Ki。void quickpass(int r, int s, int t) int i=s, j=t, x=rs; while(ij)while (ix) j=j-1; if (ij) ri=rj;i=i+1; while (ij & rix) i=i+1; if (inext) 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; 数据结构试卷三参考答案二填空题13.j+1，hashtablej.key=k14.return(t)，t=t-rchild三、计算题1 2、H(36)=36 mod 7=1; H(22)=(1+1) mod 7=2; .冲突H(15)=15 mod 7=1;.冲突 H2(22)=(2+1) mod 7=3; H(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 0 1 2 3 4 5 663361522402ASL=3、(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) 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 *q20; 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; 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-data) break; if (flag=0) printf(not found xn); else if (idata); else printf(not parent);数据结构试卷四参考答案二、填空题1. (19，18，16，20，30，22)2. (16，18，19，20，32，22)3. Aij=14. 等于5. BDCA6. hashtablei=0，hashtablek=s三、计算题12 (1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树；3H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法设计题1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;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-datanext=ha; ha=p; else if (p-data=0 & p-datanext=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 10typedef 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-keykey) bstinsert(bt-lchild,key); else bstinsert(bt-rchild,key);void createbsttree(bitree *&bt) int i; for(i=1;ik三、应用题2. DEBCA3. E=(1,5),(5,2),(5,3),(3,4),W=104. ASL=(1*1+2*2+3*4)/7=17/75. 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-datadata)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. 设计在顺序有序表中实现二分查找的算法。struct record int key; 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. 设计判断二叉树是否为二叉排序树的算法。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(minnumbt-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) for(s=head;s!=q-next;s=s-next) if (s-datap-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. ij & ri.keynext=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. 设计在顺序存储结构上实现求子串算法。void substring(char s , long 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); 数据结构试卷八参考答案三、填空题1. (49，13，27，50，76，38，65，97)2. t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k)3. p-next=s4. head-rlink，p-llink5. CABD6. 1，167. 08. (13，27，38，50，76，49，65，97)9. n-110. 50四、算法设计题1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count);2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm; int edgemm;gadjmatrix;typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode;typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 )int i,j; glinklistnode *p;for(i=0;i=n-1;i+) g2i.firstarc=0;for(i=0;i=n-1;i+) for(j=0;jadjvertex=j;p-nextarc=gi.firstarc; gi.firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode);p-adjvertex=i;p-nextarc=gj.firstarc; gj.firstarc=p;数据结构试卷九参考答案四、算法设计题1 设计计算二叉树中所有结点值之和的算法。void sum(bitree *bt,int &s) if(bt!=0) s=s+bt-data; sum(bt-lchild,s); sum(bt-rchild,s);2 设计将所有奇数移到所有偶数之前的算法。void quickpass(int r, int s, int t) int i=s,j=t,x=rs; while(ij) while (ij & rj%2=0) j=j-1; if (ij) ri=rj;i=i+1; while (ij & ri%2=1) i=i+1; if (inext=0) return(1);elsefor(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) return(0);return(1);数据结构试卷十参考答案二、填空题1. q-next2. 线性结构，树型结构，图型结构3. O(n2)， O(n+e)4. 8/35. (38，13，27，10，65，76，97)6. (10，13，27，76，65，97，38)7. 1246538. struct node *rchild，bt=0，createbitree(bt-lchild)9. lklist，q=p三、算法设计题1. 设计在链式存储结构上合并排序的算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0; while(ha!=0 & hb!=0) if(ha-datadata)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;2. 设计在二叉排序树上查找结点X的算法。bitree *bstsearch1(bitree *t, int key) bitree *p=t; while(p!=0) if (p-key=key) return(p);else if (p-keykey)p=p-lchild; else p=p-rchild; return(0);3. 设关键字序列(k1，k2，kn-1)是堆，设计算法将关键字序列(k1，k2，kn-1，x)调整为堆。void adjustheap(int r ,int n) int j=n,i=j/2,temp=rj-1; while (i=1) if (temp=ri-1)break; elserj-1=ri-1; j=i; i=i/2; rj-1=temp;
展开阅读全文