计算机软件基础习题及参考答案.pdfVIP

习题一 1. 什么是数据结构， 数据的逻辑结构， 数据的存储结构？数据结构对算法有什么影响？请举 例说明。 2. 数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？ 3. 设 n 为正整数 , 分析下列各程序段中加下划线的语句的执行次数。 (1) for (int i = 1; i = n; i++) for (int j = 1; j = n; j++) { c[i][j] = 0.0; for (int k = 1; k = n; k++) c[i][j] = c[i][j] + a[i][k] * b[k][j]; } (2) x = 0; y = 0; for (int i = 1; i = n; i++) for (int j = 1; j = i; j++) for (int k = 1; k = j; k++) x = x + y; (3) int i = 1, j = 1; while (i=n j=n) { i = i + 1; j = j + i; } * (4) int i =1; do{ for (int j = 1; j = n; j++) i = i + j; }while(i100 + n); 4. 试编写一个函数计算 n!*2 n 的值，结果存放于数组 A[arraySize] 的第 n 个数组元素中， 0 n arraySize 。若设计算机中允许的整数的最大值为 maxInt ，则当 narraySize 或者对于 k 某一个 k (0 k n) ，使得 k!*2 maxInt 时，应按出错处理。可有如下三种不同的出 错处理方式： (1) 用 printf 显示错误信息 及 exit (1) 语句来终止执行并报告错误； (2) 用返回整数函数值 0, 1 来实现算法，以区别是正常返回还是错误返回； (3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。 5. 设有一个线性表 (a 0, a 1 , …, a n-2 , a n-1 ) 存放在一个一维数组 A[arraySize] 中的前 n 个 数组元素位置。 请编写一个函数将这个线性表原地逆置， 即将数组的前 n 个原址内容置换为 (a n-1 , a n-2 , …, a 1, a 0) 。最后分析此算法的时间复杂度及空间复杂度。 6. 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下 , 对有 127 个元素的顺序表进行插入 , 平均需要移动多少个元素 ? 删除一个元素 , 又平均需要移动多 1 / 36 少个元素 ? 7. 利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，