有哪些信誉好的足球投注网站- 1、本文档共7页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
丹青不知老将至，贫贱于我如浮云。——杜甫
《数据结构》试题答案A卷
姓名班级
题号一二三总分
题分403030100
得分
得分一、回答下列问题(每题5分，共40分)
1．给定序列（67，45，87，19，55，32，70，60，90，23），写出它的初始堆序
列。
答：调整后的初始堆序列(小根堆)为：19，23，32，45，55，87，70，60，90，67
或者是大根堆：90,67,87,60,55,32,70,45,19,23
19
2332
45558770
609067
2．设一个序列奇数项和偶数项分别由小到大有序，用什么方法可以最快得到一
个有序序列，分析它的时间复杂度。
答：把奇数项和偶数项分为2个有序序列，然后进行合并，时间复杂度为O(n)。实际上就
是把2个有序表合并为一个有序表。见教科书算法2.7。
3．二叉排序树中的最大值在二叉排序树的何处？
答：最大值应该位于二叉排序树中根的右子树的最右叶子上。
1
丹青不知老将至，贫贱于我如浮云。——杜甫
4．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序是否比用锦
标赛排序更快？为什么？
答：此题用锦标赛排序比堆排序要快。理由是；
①在首次求最小值时，锦标赛排序对2048个结点建树得到最小码只需比较n-1(即2047)次，
而此时堆排序建初始堆得到最小码却可能需要比较4072次(因为每个结点的调整都要与左
右两边的孩子相比。从第1024个结点往前调整，有512个结点可能调整1次，但要与左右
孩子都比较，有256个结点可能调整2次，每次都要与左右孩子比较，有128个结点可能调
整3次，……有32个结点调整5次，……根结点可能要调整10次，每次都会与左右孩子比
较，所以可能会比较2036×2=4072次)。
而两种算法对求后面4个次小码的平均效率相同，都是logn，所以，此题用锦标赛排序会
2
比堆排序快。
5．n个顶点、m条边的全连通图，至少去掉几条边才能构成一棵树？
答：因为树的结构是一对多，即n个结点的树只有n-1条边与双亲结点相连。只要再多添一
条边就会成为图结构。所以，m条边的图要去掉m-(n-1)=m-n+1条边才能构成一棵树。这棵
树也就是最小生成树。
6．设模式串为：liuwenliuyuliuyingliyu,求该模式串的next函数。
答：Next[j]=0111111234112341
7．一个二叉树按层次遍历的顺序存储结构如下，请画出该二叉树(φ为空)。
123456789101112131415
ABD
文档评论（0）