1.1 简述下列概念：数据、数据元素、数据类型、、逻辑结构、结构、线性结构、非线性结构。
1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
1.3 常用的存储表示方法有哪几种?
1.4 设三个函数f，g，h分别为 f=100n3+n2+1000 ， g=25n3+5000n2 ， h=n1.5+5000nlgn 请判断下列关系是否成立：
f=O)
g=O)
h=O
h=O
1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少要多大?
1.6 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
i=1; k=0;
while
i=0; k=0;
do
while;
i=1; j=0;
while
x=n; // n1
while )
y++;
x=91; y=100;
while
if
else x++;
1.7 算法的时间复杂度仅与问题的规模相关吗?
1.8 按增长率由小至大的顺序排列下列各函数：
2100， n，n， nn ，n0.5 ， n! ，2n ，lgn ，nlgn， n
1.9 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1=1.39nlgn+100n+256=1.39nlgn+O， T2=2.0nlgn-2n=2.0lgn+O， 这两个式子表示，当n足够大时T1优于T2，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?
T1=5n2-3n+60lgn
T2=3n2+1000n+3lgn
T3=8n2+3lgn
T4=1.5n2+6000nlgn
|
