数据结构答案及评分标准.doc_第1页
数据结构答案及评分标准.doc_第2页
数据结构答案及评分标准.doc_第3页
数据结构答案及评分标准.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

答案及评分标准一、 选择题（每项选择2分，共34分，错选不给分）1、D2、D3、B4、A5、A6、A7、D8、C9、AD10、BC11、C12、C13、D14、A15、D二、算法测试题（共31分）1、struct node *link;(2分)NULL ；或者 0 ；(2分)s-link=h-link;（2分）什么是表头结点？答：表头结点是有时为了操作方便而在链表的第一结点之前添加的一个结点，该结点结构与表中结点相同，但数据域不存放表中数据，或者闲置不用，或者存放特殊信息。表头结点的链域存放指向链表中第一个结点的指针。（2分，回答对点给1分；点0.5分；点0.5分。）如果该链表无表头结点该做怎样的修改？修改如下：void invert(LNode *h) LNode *s,*p; p=h；(1分)h=NULL;（1分） while(p!=NULL) s=p; p=p-link; s-link=h;（1分） h =s;（1分）2、m=q;(2分)q=q-link;（2分）p=p-link;（2分）不稳定（2分）n(n-1)/2（2分）当待排序序列为“正序”时，有最小移动次数0；（1分）当待排序序列为“逆序”时，有最大移动次数3(n-1)；（1分）算法的平均时间复杂度为O（n2）。（1分）3、p-rchild;（2分）q-LTag!=1;（2分） 1 （1分）；NULL；或者 0 ；三、应用题：1、（4分，画对根结点1分，左子树正确1.5分，右子树正确1.5分）后序序列为：DGJHEBKIFCA（2分）2、前序序列补充完整为：ABCDEFGH（1分）中序序列补充完整为：CBDEAGHF（1分）后序序列补充完整为：CEDBHGFA（1分）（3分，画对根结点1分，左子树正确1分，右子树正确1分） （4分）画对各结点线索指针得2分，标志位正确得1分，表头结点正确得1分）3、（4分，画对各树根结点2分，画对各子树子女结点2分）该森林的先序序列为：ABCMNSDEFGHKIJ（2分）4、（1）（2分,如果画的是无向图不給分）（2）（2分，上小题答错的学生，如果这里给出的答案符合他自己所画的图，给全分）0111000101000010010100000（3）a4 32b53c5d53e(2分，第1小题答错的学生，如果这里给出的答案符合他自己画的图，给全分)（4）可能的拓扑排序为：abdce 或 adbce
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论