2022年东南大学十套数据结构试题及答案,推荐文档 .pdf

《2022年东南大学十套数据结构试题及答案,推荐文档 .pdf》由会员分享，可在线阅读，更多相关《2022年东南大学十套数据结构试题及答案,推荐文档 .pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 数据结构试卷（一）三、计算题（每题6 分，共 24 分）1.在如下数组A 中链接存储了一个线性表，表头指针为A 0.next ，试写出该线性表。 A 0 1 2 3 4 5 6 7 data 60 50 78 90 34 40 next 3 5 7 2 0 4 1 2.请画出下图的邻接矩阵和邻接表。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; 用克鲁斯卡尔算法得到最小生

2、成树，试写出在最小生成树中依次得到的各条边。4.画出向小根堆中加入数据4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。四、阅读算法（每题7 分，共 14 分）1. LinkList mynote(LinkList L) /L 是不带头结点的单链表的头指针if(L&L-next) q=L；L=L next；p=L；S1：while(p next) p=p next；S2：pnext=q；qnext=NULL ；return L； 请回答下列问题：（1）说明语句S1 的功能；（2）说明语句组S2 的功能；（3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线

3、性表。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)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

4、- - - 名师精心整理 - - - - - - - 第 2 页，共 23 页 - - - - - - - - - 3 数据结构试卷（二）三、应用题 (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) ，查找方法用二分查找，要

5、求计算出查找关键字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)的时间复杂度内将线性表划分成两部分，其中左

6、半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。2 设有两个集合A和集合 B，要求设计生成集合C=A B的算法，其中集合A、B和 C用链式存储结构表示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 23 页 - - - - - - - - - 4 数据结构试卷（三）二填空题1.下列算法实现在顺序散列表中查找值为x 的关键字，请在下划线处填上正确的语句。struct recordint key; int others; int hashsqsearch(

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

8、 *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，假定选用的散列函数是H（K）= K mod 7 ，若发生冲突采用线性探查法处理，试：（1）计算出每一个元素的散列地址并在下图

9、中填写出散列表： 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。3已知序列（ 10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。四、算法设计题( 每题 15 分，共 30 分) 1 设计在单链表中删除值相同的多余结点的算法。2 设计一个求结点x 在二叉树中的双亲结点算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页 - - - - - - - - - 5 数据结构试卷（四）1 设一组初始记录

10、关键字序列为(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 ，解

11、决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表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=( )

12、, (e) , (a , (b , c , d )的头尾链表存储结构。2、下图所示的森林：(1) 求树（ a）的先根序列和后根序列；(2) 求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)3、设散列表的地址范围是 0.9 ，散列函数为H （key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素7、4、 5、3、6、2、8、9 依次插入散列表的存储结构。四、算法设计题( 每题 10 分，共 30 分) 1设单链表中有仅三类字符的数据元素( 大写字母、 数字和其它字符) ，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链

13、表只包含同类字符。2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3.在链式存储结构上建立一棵二叉排序树。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 23 页 - - - - - - - - - 6 数据结构试卷（五）1.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int rn) for(i=1;i=n-1; i+) for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;ex

14、change=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 ，前序

15、遍历序列为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 设计两个有序单链表的合并排序算法。名师资料总结 - - -精品资

16、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 23 页 - - - - - - - - - 7 数据结构试卷（六）四、算法设计题(20 分 ) 设计在顺序有序表中实现二分查找的算法。设计判断二叉树是否为二叉排序树的算法。在链式存储结构上设计直接插入排序算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 23 页 - - - - - - - - - 8 数据结构试卷（七）三、填空

17、题 (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

18、(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 设有向图中不存在有向边，则其对

19、应的邻接矩阵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、- - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - 10 数据结构试卷（九）五、算法设计题(20 分 ) 1 设计计算二叉树中所有结点值之和的算法。2 设计将所有奇数移到所有偶数之前的算法。3 设计判断单链表中元素是否是递增的算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 23 页 - - - - - - - - - 11 数据结构试卷（十）二、填空题 (48 分，其中最后两小题各

21、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.设一组初始关

22、键字序列为(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

23、=(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 设计

24、在二叉排序树上查找结点X的算法。3 设关键字序列(k1，k2， kn-1) 是堆，设计算法将关键字序列(k1，k2， kn-1，x) 调整为堆。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 23 页 - - - - - - - - - 12 数据结构试卷（一）参考答案三、计算题（每题6 分，共 24 分）1. 线性表为：（78，50，40， 60，34，90）2. 邻接矩阵：0111010101110111010101110邻接表如图11 所示：图 11 3. 用克鲁

25、斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 见图 12 图 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!=N

26、ULL) if (P-data=x) i+; p=p-next; /while, 出循环时 i 中的值即为x 结点个数return i; /CountX 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 23 页 - - - - - - - - - 13 数据结构试卷（二）参考答案三、应用题1.(22 ，40，45，48，80， 78)，(40 ，45， 48，80，22，78) 2.

27、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.设有一组初始记录关键字序列（K1，K2， Kn） ，要求设计一个算法能够在O(n) 的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。void quickpass(int r, int s, int t) int i=s, j=t, x=

28、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 页，共

29、23 页 - - - - - - - - - 14 数据结构试卷（三）参考答案二填空题13.j+1，hashtablej.key=k14.return(t)，t=t-rchild 三、计算题1AEBFGCDHFKJNULL2、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 6 63 36 1

30、5 22 40 （2）ASL=6 .15311213、(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(lklis

31、t *&head) lklist *p,*q,*s; for(p=head;p!=0;p=p-next) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 23 页 - - - - - - - - - 15 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

32、 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);

33、 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 23 页 - - - - - - - - - 16 数据结构试卷（四）参考答案二、填空题1.(19 ，18，16，20，30， 22) 2.(16 ，18，19，20，3

34、2， 22) 3.Aij=1 4.等于5.BDCA 6.hashtablei=0 ，hashtablek=s三、计算题11-11111111100000eabcdLS2(1) ABCDEF; BDEFCA ；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树；AGBCDEFHIJK3H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6 012345678945369827四、算法设计题1.设单链表中有仅三类字符的数据元素( 大写字母、数字和其它字符) ，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字

35、符。typedef char datatype; typedef struct node datatype data; struct node *next;lklist; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 23 页 - - - - - - - - - 17 void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) lklist *p; ha=0,hb=0,hc=0; for(p=head;p!

36、=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-

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

38、bt-keykey) bstinsert(bt-lchild,key); else bstinsert(bt-rchild,key); void createbsttree(bitree *&bt) int i; for(i=1;ik 三、应用题2.DEBCA 3.E=(1,5),(5,2),(5,3),(3,4),W=10 4.ASL=(1*1+2*2+3*4)/7=17/7 5.ASL1=7/6 ，ASL2=4/3 四、算法设计题1.设计判断两个二叉树是否相同的算法。typedef struct node datatype data; struct node *lchild,*rchild

39、; 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=

40、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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 23 页 - - - - - - - - - 19 数据结构

41、试卷（六）参考答案四、算法设计题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

42、 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)

43、 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 23 页 - - - - - - - - - 20 数据结构试卷（七）参考答案三填空题1.ij & ri.keynext=0) return; for(q=head; q!=0;q=q-

44、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+cou

45、nt-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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 23 页 - - - - - - - - - 21 数据结构试卷（八）参考答案三、填空题1.(49，13， 27，50，7

46、6，38，65，97) 2.t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k) 3.p-next=s 4.head-rlink ，p-llink 5.CABD 6.1，16 7.0 8.(13，27， 38，50，76，49，65，97) 9.n-1 10.50 四、算法设计题1.设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild

47、,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 )

48、 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

49、精心整理 - - - - - - - 第 21 页，共 23 页 - - - - - - - - - 22 数据结构试卷（九）参考答案四、算法设计题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

50、) ri=rj;i=i+1; while (ij & ri%2=1) i=i+1; if (inext=0) return(1);else for(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) return(0); return(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 23 页 - - - - - - - - - 23 数据结构试卷（十）参考答案二、填空题1.q-next 2.线性结构，树