数据结构复习题及答案 2.doc

《数据结构复习题及答案 2.doc》由会员分享，可在线阅读，更多相关《数据结构复习题及答案 2.doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构复习题及答案 2.精品文档.数据结构模拟试题一一、单选题（每题 2 分，共20分）1. 对一个算法的评价，不包括如下（ ）方面的内容。A健壮性和可读性 B并行性 C正确性 D时空复杂度二、填空题（每题 6 分，共24分）1. 数据结构是指数据及其相互之间的_。当结点之间存在M对N（M：N）的联系时，称这种结构为_。三、运算题（每题6分，共24分）1. 已知一个65稀疏矩阵如下所示，试题一参考答案一、单选题（每题2分，共20分）1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C二、填空题（每空1分，共26分

2、）1. 联系 图（或图结构）2. 尾 首3. top=04. O（1） O（n）5. 128 44 1086. 3 3 7. 65515132-145-2515637 图7有序 n-18. 有序序列 后缀表达式（或逆波兰式）9. 2n n-1 n+110. 2i+1 2i+2 (i-1)/211. 开放定址法 链接法12. 快速 归并三、 运算题（每题6分，共24分）1. （1） (1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7) (3分)（2） 三元组线性表的顺序存储表示如图7示。2. 图8如图8所示。3. DFS： BFS： 4. 拓朴排序为： 4 3 6

3、5 7 2 1 四、阅读算法（每题7分，共14分）1. (1) 判断n是否是素数（或质数） （2）O（）2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。五、算法填空（8 分） (low+high)/2 high=mid-1 low=mid+1 六、 编写算法（8分）ElemType DeleFront(LNode * & HL)if (HL=NULL) cerr空表next;ElemType temp=p-data;delete p;return temp; 数据结构模拟试题二一、单选题1. 栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素B.都是先进后出 C.都

4、是先进先出D.没有共同点 二、 填空题1. 通常从四个方面评价算法的质量：_、_、_和_。三、运算题1. 1. 在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。 数据结构模拟试题二参考答案一、单选题（每题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)3. 9 3 34. -1 3 4 X * + 2 Y * 3 / -5. 2n n-1 n+16. e 2e7. 有向无回路8. n(n-1)/2 n(n-1)9. （12，40） （

5、 ） （74） （23,55，63）10. 增加111. O(log2n) O(nlog2n)12. 归并三、运算题（每题6分，共24分）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. 见图124444422255285283452843图12四、阅读算法（每题7分，共14分）1. 1. （1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,an,

6、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、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相

7、等）为 ( )。A n B n/2 C (n+1)/2 D (n-1)/2二、 填空题1、数据的逻辑结构被分为_、 _ 、_和_四种。三、 运算题1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。数据结构模拟试题三（答案）一、单选题题 号 1 2 3 4答 案 C D A B二、填空题1： 集合、线性、树、图；2： 数据描述、操作声名；3： （38，56，25，60，42，74）；4： HLnext =NULL； HL=HLnext；5： 前一个位置； n-1；6： S.stack S.top; HSdata;7： 5 318

8、： 边结点、邻接点域、权域、链域；9： 索引值域、开始位置域；10： 10、3、3、B、I和J；11： O（log2n）、O(nlog2n);12： m 、 m - 1三、 运算题1、划分次序划分结果第一次38 24 40 46 56 80 95 79第二次24 38 40 46 56 80 95 79第三次24 38 40 46 56 80 95 79第四次24 38 40 46 56 80 95 79第五次24 38 40 46 56 79 80 95第六次24 38 40 46 56 79 80 952、 0 1 2 3 4 5 6 7 8 9 10 11 127815035745203

9、1233612查找成功的平均查找长度：ASL SUCC=14/10= 1.43、此二叉树的后序遍历结果是：EDCBIHJGFA4、图深度优先序列广度优先序列邻接矩阵表示时0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9邻接表表示时0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，5四、阅读算法，回答问题（每小题8分，共16分）1、 1、 该算法的输入结果是：34 91 30 45 63 782、 2、 该算法的功能是：交换二叉树的左右子树的递归算法。五、算法填空，在画有横线的地方填写合适的内容（10分）1、1是：（low + high）/2;

10、 2是： Binsch(A,low,mid1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1；六、编写算法（10分）根据编程情况，酌情给分。Lnode *P=HL;HL=NULL;While (p!=null) Lnode*q=p; P=pnext; qnext=HL; HL=q;数据结构模拟试题四一、 项选择题1算法指的是（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列二、填空题16数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。 三、 解答题26画出下列广义表的共享结构图形表示 P=（z）,(x,y)）

11、,(x,y),x),(z)）数据结构模拟试题四参考答案一、 单项选择题（本大题共15小题，每小题2分，共30分） 1D，101112131415二、填空题（本大题共10小题，每小题2分，共20分）16存储（或存储结构）17.pnextnext18进栈和退栈191220a4,82138422abefcdg23快速排序、堆排序、希尔排序2425.多关键字三、解答题（本大题共4小题，每小题5分，共20分）26 图1 图22728该图的图形为： 深度优先遍历序列为：abdce广度优先遍历序列为：abedc29（）对关键字35、20、33和48进行查找的比较次数为、； （）平均查找长度四、算法阅读题（本

12、大题共4小题，每小题5分，共20分）30 S1=S1next s2=s2next s2(或s2!=NULL或s2&!s1) s1(或s1!=NULL或s1&!s2) return 031.（1）查询链表的尾结点 （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,an,a1）32. (i1)%2(或1i) Qreari (Qreari)%Maxsize33.(1)LeafheadFHGD （2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。五、算法设计题（本题共1

13、0分） 34（1）该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x的元素均落在ai1.h上。 （2）int f(int b,int n) 或 int f(int b,int n) int p,q； int p,q； p=arrange(b,0,n1,0)； p=arrange(b,0,n1,1)； q= arrange(b,p+1,n1,1)； q= arrange(b,0,p,0)； return qp； return pq； 数据结构模拟试题五一、选择题（20分）1组成数据的基本单位是（ ）。 (A) 数据项(B) 数据类型(C) 数据元素(D

14、) 数据变量二、填空题(30分)1. 设顺序循环队列Q0：m-1的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =_;。三、应用题（30分）1设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。数据结构模拟试题五参考答案一、选择题1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空题1. (F+1) % m2. O(n)，O(n)3. 2n，n+14. s-next=p-next; s-next=s5. n, 2e6. m

15、=2e7. CBA8. 4，169. i-j+1，010. n-1三、应用题1. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。2. 哈夫曼树略，WPL=783. (18,5,16,19,21,23)，(5，16，21，19，18，23)4. 线性探测：链地址法：5. 深度：125364，广度：123456，最小生成树T的边集为E=(1，4)，(1，3)，(3，5)，(5，6)，(5,6)四、算法设计题1. 设计判断单链表中结点是否关于中心对称算法。typedef struct int s100; int top; sqstack;int lklistsymmetry(lkl

16、ist *head) sqstack 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. 设计在链式存储结构上建立一棵二叉树的算法。typedef char datatype;typedef struct node datatype data;

17、struct node *lchild,*rchild; bitree;void createbitree(bitree *&bt) char ch; scanf(%c,&ch); if(ch=#) bt=0; return;bt=(bitree*)malloc(sizeof(bitree); bt-data=ch;createbitree(bt-lchild); createbitree(bt-rchild);3. 设计判断一棵二叉树是否是二叉排序树的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lc

18、hild,*rchild;bitree;void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key; inorder(bt-rchild);数据结构模拟试题六一、选择题(24分)1下面关于线性表的叙述错误的是（ ）。(A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现二、填空题(24分)1. 为了能有效地应用HA

19、SH查找技术，必须解决的两个问题是_和_。三、应用题(36分)1 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。数据结构模拟试题六参考答案一、选择题1.D2.B3.C4.A5.A6.C7.B8.C二、填空题1. 构造一个好的HASH函数，确定解决冲突的方法2. stack.top+，stack.sstack.top=x3. 有序4. O(n2)，O(nlog2n)5. N0-1，2N0+N16. d/27. (31，38，54，56，75，80，55，63)8. (1，3，4，2)，(1，3，2，4)三、应用题1.

20、(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

21、(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;数据结构模拟试题七一、选择题(30分)1设某数据结构的二元组形式表示为A=(D，R)，D=01，02，0

22、3，04，05，06，07，08，09，R=r，r=，则数据结构A是（ ）。(A) 线性结构(B) 树型结构(C) 物理结构(D) 图型结构二、填空殖(48分，其中最后两小题各6分)1. 数据的物理结构主要包括_和_两种情况。三、算法设计题(22分)1 设计在单链表中删除值相同的多余结点的算法。 数据结构模拟试题七参考答案一、选择题1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只

23、需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为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，hashtablej.key=k14. return(t)，t=t-rchild第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。三、算法设计题1. 设计在单链表中删除值

24、相同的多余结点的算法。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 struc

25、t 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); fo

26、r(i=f+1; ilchild-data=x | qi-rchild-data) break; if (flag=0) printf(not found xn); else if (idata); else printf(not parent);数据结构模拟试题八一、选择题(30分)1设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)二、填空题(42分)1 设有n个无序的记录关键字，则直接插入排序的时间复杂度为_，快速排序的平均时间复杂度为_。三、算法设计题(28分)1 设单链表中有仅三类字符

27、的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。数据结构模拟试题八参考答案一、选择题1C2D3D4B5C6A7B8A9C10A二、填空题1. O(n2)，O(nlog2n)2. pllink-rlink=p-rlink; p-rlink-llink=p-rlink3. 34. 2k-15. n/26. 50，517. m-1，(R-F+M)%M8. n+1-i，n-i9. (19，18，16，20，30，22)10. (16，18，19，20，32，22)11. Aij=112. 等于13. BDCA14. hashtabl

28、ei=0，hashtablek=s三、算法设计题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-ne

29、xt; 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

30、-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-l

31、child,key); else bstinsert(bt-rchild,key);void createbsttree(bitree *&bt) int i; for(i=1;i=n;i+) bstinsert(bt,random(100);数据结构模拟试题九一、选择题(30分) 1数据的最小单位是（ ）。(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量二、填空题(共30分)1. 设有一个顺序共享栈S0：n-1，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是_。三、应用题(24分)1. 设某棵二叉树的中序遍历序列为DBEAC，前

32、序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。数据结构模拟试题九参考答案一、选择题1A2B3A4A5D6B7B8B9C10C二、填空题1. top1+1=top22. 可以随机访问到任一个顶点的简单链表3. i(i+1)/2+j-14. FILO，FIFO5. ABDECF，DBEAFC，DEBFCA6. 8，647. 出度，入度8. ki=k2i & kik三、应用题1. DEBCA2. E=(1,5),(5,2),(5,3),(3,4),W=103. ASL=(1*1+2*2+3*4)/7=17/74. ASL1=7/6，ASL2=4/3四、算法设计题1. 设计判断两个二叉树是

33、否相同的算法。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. 设计两个有序单链表的合

34、并排序算法。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;数据结构模拟试题十一、选择题(30分)1 设一组权值集合W=2，3，4，5，6，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。(A) 20(B) 30(C) 40(D) 45二、判断题(20分)1调用一次深度优先遍历可以访问到图中的所有顶点。（ ）三、填空题(30分)1for(i=1，t=1，s=0；inext=p-next; p-next=s3. (1，3，2，4，5)4. n-15. 1296. F=R7. p-lchild=0&p-rchild=08. O(n2)9. O(nlog2n)， O(n)10. 开放定址法，链地址法四、算法设计题1. 设计在顺序有序表中实现二分查找的算法。s