七、(本题15分)设关键字序列为:49,38,66 ， 80 ， 70,15 ， 22 ， 欲对该序列进行从小到大排序 。
( 。

8、1）用直接插入排序法进行排序 ， 写出每趟的结果 。
(2）采用待排序列的第一个关键字作为枢轴 ， 写出快速排序法的一趟和二趟排序之后的状态 。
（3）画出待排序列的初始化堆 。
答案： 直接插入排序法原始关键字序列为：（49) 38 66 80 70 15 22(38 49） 66 80 70 15 22（38 49 66) 80 70 15 22（38 49 66 80) 70 15 22（38 49 66 70 80) 15 22（38 49 66 70 80) 15 22（15 38 49 66 70 80） 22（15 22 38 49 66 70 80） 快速排序法原始关键字序列为：49 ， 38 ， 66 。

9、 ， 80 ， 70,15 ， 22第一趟排序后 22 38 15 （49） 70 80 66第二趟排序后 15 (22) 38 66 (70) 80 该堆是最大堆,具体如下：80706638491522八、（本题10分）假设一棵树的存储结构采用双亲表示法 ， 双亲数组为int parentMaxSize ， 其中MaxSize为最大结点个数 。
树中各结点按先根遍历的次序存放 ， 根结点存于parent0 。
试编写一个函数 ， 计算下标p所指结点和下标q所指结点的最近公共祖先结点.参考答案：int CommonAncestry(int parent ，int MaxSize, int p ，int q）int i,j;
for 。

10、 (i=p； i！=-1；i=parenti)for (j=q； j！=-1； j=parentj)if （i=j) return I;
九、（本题10分）1 ， 2 ， n这n个数,无序地保存在数组c1 。
n中.请编写一个时间复杂度为O（n)的排序算法 ， 将数组c1 。
n按小到大排序.参考答案:void C_sort（int c, int n)int i, x;
for （i=1;
i=n；i+)while （ci！=i）x=ci；ci=cx；cx=x;
交换O(n)次 。
结尾处,小编送给大家一段话 。
米南德曾说过,“学会学习的人 ， 是非常幸福的人” 。
在每个精彩的人生中 ， 学习都是永恒的主题 。
作为一名专业文员教职,我更加 。

11、懂得不断学习的重要性 ， “人生在勤 ， 不索何获” ， 只有不断学习才能成就更好的自己 。
各行各业从业人员只有不断的学习 ， 掌握最新的相关知识 ， 才能跟上企业发展的步伐,才能开拓创新适应市场的需求.本文档也是由我工作室专业人员编辑,文档中可能会有错误 ， 如有错误请您纠正,不胜感激!At the end ，Xiao Bian gives you a passage 。
Minand once said, people who learn to learn are very happy people.” 。
In every wonderful life ，learning is an eternal theme. A 。

12、s a professional clerical and teaching position ，I understand the importance of continuous learning, ”life is diligent, nothing can be gained”, only continuous learning can achieve better self 。
Only by constantly learning and mastering the latest relevant knowledge, can employees from all walks of l 。

13、ife keep up with the pace of enterprise development and innovate to meet the needs of the market 。
This document is also edited by my studio professionals ，there may be errors in the document, if there are errors, please correct ，thank you!此处将被文件名替换编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心 ， 本文档内容是由我和我的同事精心编辑整理后发布的 ， 发布之前我们对文中内容进行仔细校对 ， 但是难免会有疏漏的地方 ， 但是任然希望（此处将被文件名替换）的内容能够给您的工作和学习带来便利 。
同时也真诚的希望收到您的建议和反馈 ， 这将是我们进步的源泉 ， 前进的动力 。
本文可编辑可修改 ， 如果觉得对您有帮助请收藏以便随时查阅 ， 最后祝您生活愉快 业绩进步 ， 以下为此处将被文件名替换的全部内容 。

来源：(未知)

【学习资料】网址：/a/2021/0321/0021739336.html

标题：数据结构|2011《数据结构》期末试卷_A卷( 二 )