2019-2020学年安徽大学数据结构B卷算法与排序分析

本资源是一份2019-2020学年安徽大学《数据结构》考试试卷B卷，主要考察算法分析与理解能力。共计四道题目，涉及时间复杂度分析、函数功能理解、排序算法分析以及具体应用实例。 第一题是关于时间复杂度的计算，函数`voidFun(int n)`使用了两个嵌套循环，外层循环`i`从1到`n`，内层循环`j`从`2*i`到`n`，每次循环增加计数器`m`。由于内层循环的范围会随着外层循环的进行逐渐减小，所以可以认为这个算法的时间复杂度是O(n^2)，其中`n`为输入的整数。 第二题涉及到一个字符处理函数`Fun(int d)`，它通过取余数和位操作将一个十进制数`d`转换成十六进制字符串并存储在静态字符数组`b`中。(1)题要求说明该函数的功能，答案是将十进制数转换为十六进制表示；(2)题当`d=100`时，执行后数组`b`的值将是十六进制形式的"64"。 第三题是冒泡排序的实现，`voidFun(int a[], int n)`用于对整数数组`a`进行排序。(1)题指出该算法的功能是进行一趟冒泡排序，即将数组中的最大元素逐步“冒”到数组末尾；(2)题给定数组`a[]={5,1,3,6,2,7,4,8}`，由于每趟冒泡排序都会使未排序部分的最大元素向右移动一位，所以当n=8时，共需执行3趟排序。排序结果分别是：第一趟后变为`[1,5,3,6,2,7,4,8]`，第二趟后变为`[1,3,5,2,6,4,7,8]`，第三趟后数组已完全排序。 第四题的题目内容缺失，但可以根据类似的模式推断，可能是另一段需要分析算法逻辑、运行结果或者性能优化的问题。 这些题目旨在检验学生对基本数据结构和常见算法的理解，如循环复杂度的分析、字符串处理、排序算法原理及其实现等。解答这类题目需要扎实的数据结构基础和编程经验，以及对算法性能的敏感洞察力。