安全检测:瑞星:安全 诺顿:安全 卡巴:安全
第一章习题(概述)
1.1选择一个单位的工资表,指出其中的元素、元素的字段以及元素之间的关系,并给出一些最基本的运算。
1.2描述数据结构、逻辑结构、存储结构和运算的有关概念及其相互之间的关系。
1.3已知一个群体中有n个人,这些人之间可能存在同学关系,请用一个数据模型来描述这一关系,并给出可能基本运算。
1.4描述算法所具备的基本特征,并指出算法与程序之间的差异。
1.5计算下列各程序段的时间复杂度。
(1)for (I=0; I<n; I++)
for (j=I; j<n;j++) x++; n^2
(2)I=n;
While (I>1) I= I/2; n
(3)For (I=1; I<=n; I++)
For (j=1; j<=n; j++) n^3
For (k=1; k<=n; k++)
x++;
(4)For (I=1; I<n; I++)
For (j=1; j<n; j++) x++; n^2
For (k=1; k<n;k++) x++;
第二章习题(线性表)
2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last,在实现各基本运算时需要做那些修改?
2.2试用顺序表表示较多位数的大整数,以便于这类数据的存储。请选择合适的存放次序,并分别写出这类大数的比较、加、减、乘、除等运算,并分析算法的时间性能。
2.3试用顺序表表示集合,并确定合适的约定,在此基础上编写算法以实现集合的交、并、差等运算,并分析各算法的时间性能。
2.4假设顺序表L中的元素递增有序,设计算法在顺序表中插入元素x,要求插入后仍保持其递增有序特性,并要求时间尽可能少。
2.5假设顺序表L中的元素递增有序,设计算法在顺序表中插入元素x,并要求在插入后也没有相同的元素,即若表中存在相同的元素,则不执行插入操作。
2.6设计算法以删除顺序表中重复的元素,并分析算法的时间性能。
2.7假设顺序表L中的元素按从小到大的次序排列,设计算法以删除表中重复的元素, 并要求时间尽可能少。要求:
(1)对顺序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法,并统计移动元素的次数。
(2)分析算法的时间性能。