版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1 .数据结构试卷(1)参考回答一、选择问题1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填补问题1. 1. (F 1) % m2. 2. O(n ),O(n )。3. 3. 2n、n 14. 4. s-next=p-next; s-next=s5. 5. n,2e6. 6. m=2e7. 7. CBA8.8.4和169.9.I-j 1,010. 10. n-1三、应用问题1. 1 .链接的记忆结构被省略,序言ABDEC、序言DBEAC、后文DEBCA。2. 2 .哈夫曼树,WPL=783.3.(18,5,16,19,21,23 )、(5,16,21,19,18,23 )4
2、. 4 .线性检测:链寻址法:5. 5 .深度:宽度:最小生成树t的边集合为e= 1,4 )、(1,3 )、(3,5 )、(5,6 )、(5,6 ) 四、算法设计问题1. 1 .设计确定单链表节点是否适用于中心对称算法。类型结构 int s 100 ; int top; sqstack;int lklistsymmetry(lklist *head )举止sqstack stack stack.top=-1; lklist *p;for (p=头部; p!=0; p=p-next ) 堆栈. top; stack.sstack.top=p-data; 以下for (p=头部; p!=0; p=
3、p-next ) if (p-data=stack.s stack.top ) stack.top=stack.top-1; else return(0)返回(1)以下2. 2 .在连锁记忆结构中设计制作二叉树的算法。typedef char datatype;类型结构节点数据类型数据; 结构节点*rchild、*rchild; PS树;void createbitree(bitree *bt )举止char ch; 扫描( % c ,ch );PS (ch=# Bt=0; 返回; 以下Bt=(bi tree * ) malloc (sizeof (bi tree ) ); bt-data=c
4、h;createbitree (Bt-lchild ) createbitree (Bt-rchild )以下3. 3 .设计确定二叉树是否是二叉树的算法。int minnum=-32768,标志=1;类型结构节点 int key; 结构节点*rchild、*rchild; PS树;订单上的语音(bi tree * Bt )举止PR!=0)inorder(bt-lchild ); 最小密钥(if )标志=0; minnum=bt-key; inorder(bt-rchild )以下以下数据结构试卷(2)参考回答一、选择问题1.D2.B3.C4.A5.A6.C7.B8.C二、填补问题1. 1 .
5、建立好的HASH函数,确定解决冲突的方法2. 2. stack.top,stack.sstack.top=x3. 3 .秩序4. 4. O(n2),O(nlog2n )。5.5.n0- 1,2 n0n 1六.六. d/27.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*3*4*
6、2)=25/94. 4 .省略树的连锁记忆结构,省略二叉树5.5.e= (1,3 ),(1,2 ),(3,5 ),(5,6 ),(6,4 ) 6. 6 .略四、算法设计问题1. 1 .需要设置一组初始记录关键字序列(K1,K2,Kn )来设计一种算法,该算法可在O(n )的时间复杂度中将线性表分成两个部分。 左半部分的各关键字比Ki小,右半部分的各关键字在Ki以上。快速通过(int r ,int s,int t )举止int i=s,j=t,x=rs;while(ix) j=j-1; PS (PS ) for(q=hb; q!=0; q=q-next ) if (q-data=p-data )
7、中断;PS!=0) t=(lk list * ) malloc (sizeof (lk list ) ); t-data=p-data; t-next=hc; hc=t; 以下以下以下数据结构试卷(3)参考回答一、选择问题1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第三小问题分析:首先用指针变量q指定节点a的后续节点b,接着将节点b的值复制到节点a中,最后删除节点b。第9小问题分析: 9快速排序、合并排序、插入排序在整个排序结束前不能求出最小的10个,但堆栈排序在最初的堆栈之外再进行10次过滤即可,每次过滤的时间的复杂度为O(log2n )二、填补问题1. 1 .顺序存储结构
8、、链存储结构2.2.9,5013. 3. 54. 4 .出度、入度5. 5. 06. 6. e=d7. 7 .序言8. 8. 79. 9. O(1)10.10.I/2和2i111.11.(5,16,71,23,72,94,73 )12.12.(1,4,3,2 )13. 13. j 1,散列 j .key=k14.14 .返回(t ),t=t-rchild第8小问题分析:二分搜索的过程可以用一棵二分树来描述,这个二分树被称为二叉判定树。 用规则表进行二分搜索时的搜索长度,不超过二叉判定树的高度1 log2n。三、算法设计问题1. 1 .设计一种在单链表中删除值相同的多馀节点的算法。typedef
9、 int datatype;类型结构节点数据类型数据; 结构节点*下一步; lklist;void delredundant(lklist *head )举止lklist *p、*q、*s;for (p=头部; p!=0; p=p-next )举止for(q=p-next,s=q; q!=0; (请参见。)if (q-data=p-data ) s-next=q-next; 自由(q ) q=s-next; 以下else s=q,q=q-next; 以下以下以下2. 2 .设计求节点x的二叉树的父母节点算法。类型结构节点数据类型数据; 结构节点*rchild、*rchild; PS树;bitr
10、ee *q20; int r=0,f=0,标志=0;void preorder(bitree *bt,char x )举止PR!=0 flag=0)PS (PS数据=x ) 标志=1; 返回; 以下else r=(r 1)% 20; qr=bt; preorder(bt-lchild,x) preorder(bt-rchild,x )以下以下void parent(bitree *bt,char x )举止PS;preorder(bt,x )for(i=f 1; i=r; I ) if (q I -液晶数据=x| q I -液晶数据)中断;if (标志=0)打印( not found xn )
11、;else if (I=r )打印机( % c ,bt-data ); else printf(not parent );以下数据结构试卷(4)参考回答一、选择问题1.C2.D3.D4.B5.C6.A7.B8.A9.C10.A二、填补问题1. 1. O(n2),O(nlog2n )。2. 2. pllink-rlink=p-rlink; p-rlink-llink=p-rlink3. 3. 34. 4. 2k-15. 5. n/26.6.50和517. 7. m-1、(R-F M)%M8. 8. n 1-i和n-i9.9.(19,18,16,20,30,22 )10.10.(16,18,19,
12、20,32,22 )11. 11. Aij=112. 12 .相等13. 13. BDCA14. 14. hashtablei=0,hashtablek=s三、算法设计问题假定链接列表中只有三种字符的数据元素(大写、数字和其它字符),使用原始链接列表的节点空间来设计三种链接列表的算法,使得每个链接列表仅包含相同的字符。typedef char datatype;类型结构节点数据类型数据; 结构节点* next; lklist;void split(lklist *head,lklist *ha,lklist *hb,lklist *hc )举止lklist *p; ha=0,hb=0,hc=0
13、;for (p=头部; p!=0; p=头部)举止头=p-next; p-next=0;if (p-data=A p-data=Z) p-next=ha; ha=p; 以下else if (p-data=0p-data=9) p-next=HB; hb=p; else p-next=hc; hc=p; 以下以下以下2. 2 .设计一种用连锁存储结构交换二叉树中所有节点的算法。类型结构节点 int data; 结构节点*rchild、*rchild; PS树;void swapbitree(bitree *bt )举止bi树* p;PD=0)返回swapbitree (Bt-lchild ) s
14、wapbitree (Bt-rchild )p=bt-lchild; bt-lchild=bt-rchild; bt-rchild=p;以下3. 3 .在链型存储结构上创建二叉树。#define n 10类型结构节点 int key; 结构节点*rchild、*rchild; PS树;void bstinsert(bitree *bt,int key )举止if (Bt=0) Bt=(bi tree * ) malloc (sizeof (bi tree ) ); bt-key=key; bt-lchild=bt-rchild=0; 以下else if (Bt-keykey ) BST insert (Bt-lchild,key) else bstinsert(bt-rchild,key )以下void createbsttree(bitree *bt )举止PS;for(i=1; i=n; i ) bstinsert(bt,random(100 ) );以下数据结构试卷(5)参考了答案一、选择问题1.A2.B3.A4.A5.D6.B7.B8.B9.C10.C二、填
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年全球场景微电网产业发展蓝皮书-星星充电x高工咨询
- 水仙花和兰花区别
- 由非洲基因型基孔肯雅病毒导致的在印度的基孔肯雅大流行
- 眩晕症的护理查房
- 2027年春季开学考试高二化学易错题卷及答案
- 2027年春季开学考试二年级数学培优卷及答案
- 2027年四川省高考三模语文仿真卷及答案
- 关于下季度销售数据汇报的确认函7篇
- 年度保险续费通知催办函8篇
- 关于办公用品采购程序修订函(4篇)
- 2026年中学生生命科学知识竞赛题库及参考答案
- 河北石家庄市2026-2027学年高三上学期11月期中地理+答案
- 2027年备考军队文职人员招聘之军队文职法学通关试题库(有答案)
- 2026年案件警示教育考试题题库(含参考答案)
- 2026年道教全真考试题库(含答案)
- 第16课《金字塔》课件(内嵌视频)2026-2027学年语文五年级上册统编版
- 2026年校招:广东能源集团笔试题及答案
- 支气管扩张症诊疗指南(2026年)
- T/CMEAS 079-2026院内快速反应体系建设规范
- 血透病人消化道出血的护理查房
- 2026年全国版图知识竞赛(小学组)练习题及答案
评论
0/150
提交评论