数据结构第1章 习题
- 格式：doc
- 大小：46.50 KB
- 文档页数：4
一、选择题（在六个备选答案中，有一个或多个正确选择，将所选答案的字母，填写在题干后面的括号中。）
01. 下面正确的叙述有（ ）。
A）若干数据元素构成了数据 B）数据项是数据的最小单位
C）数据元素是数据的基本单位 D）若干数据项构成一个数据元素
E）若干数据元素构成数据对象 F）数据项具有独立意义且不可分割
02. 数据结构包括数据和结构，因此数据结构的简单定义包括（ ）。
A）若干数据元素的集合 B）数据元素的基本操作
C）数据元素之间的关系 D）数据元素的存储结构
E）数据元素的内存映像 F）数据元素的物理结构
03. 计算机所处理的数据通常存在某种内在联系，这种内在联系是指（ ）。
A）数据与数据之间存在的关系 B）数据元素内部存在的某种关系
C）数据项与数据项之间的关系 D）在数据项内部存在的某种关系
E）数据元素之间存在某种关系 F）逻辑结构与存储结构之间的关系
04. 数据的逻辑关系是指（ ）。
A）存储地址之间的相邻关系 B）数据元素构成的集合
C）数据元素之间的相邻关系 D）数据项之间的相邻关系
E）结点与结点之间的关系 F）数据对象之间的相邻关系
05. 从逻辑结构上可将数据结构划分为（ ）。
A）动态结构和静态结构 B）树形结构和图状结构
C）紧凑结构和松散结构 D）存储结构和物理结构
E）内部结构和外部结构 F）线性结构和非线性结构
06. 与数据元素本身的形式、内容、相邻位置、个数无关的选项有（ ）。
A）存储结构 B）运算操作
C）逻辑结构 D）图形表示
E）物理结构 F）机内表示
07. 数据的存储结构有（ ）。
A）顺序存储结构 B）索引存储结构
C）链式存储结构 D）散列存储结构
E）线性存储结构 F）网状存储结构
08. 在同一个数据对象中，关于数据元素的叙述，下面正确的选择有（ ）。
A）所有数据元素的性质相同 B）数据元素作为一个整体处理
C）若干数据元素构成数据对象 D）数据元素可以表示不同事物
E）数据元素由若干数据项组成 F）数据元素之间存在某种关系
09. 在数据结构中，与所使用计算机无关的选择有（ ）。
A）数据的逻辑结构 B）数据的物理结构
C）数据的存储结构 D）数据的内存映像
E）数据的运算操作 F）数据的计算方法
10. 在计算机中存储数据时，需要存储（ ）。
A）数据元素的取值 B）数据元素的运算操作
C）数据元素的类型 D）数据元素的相邻关系
E）数据的处理方法 F）数据元素的逻辑关系
11. 算法的基本特性包括（ ）。
A）可行性 B）零个或多个输入
C）确定性 D）一个或多个输出
E）有穷性 F）与问题规模有关
12. 算法的评价标准有（ ）。
A）有穷性 B）正确性
C）健壮性 D）通用性
E）可读性 F）高效性
13. 关于算法的概念，下列正确的说法有（ ）。
A）算法是指令的有限序列 B）算法等同于程序
C）算法最终必须编程实现 D）算法等同于运算
E）算法是操作的有限序列 F）至少有一个输出
14. 关于算法的叙述，下列正确的说法有（ ）。
A）算法可以用来交流阅读 B）算法只有一个入口
C）算法可用流程图来描述 D）算法只有一个出口
E）算法可用自然语言描述 F）算法可以没有输入
15. 算法分析的目的是分析（ ）。
A）算法是否具有较好的可读性 B）算法最终输出结果
C）算法功能是否符合设计要求 D）算法效率是否高效
E）在算法中是否存在语法错误 F）算法输入是否合法
16. 算法的高效性包括（ ）。
A）算法要正确 B）问题规模要小
C）算法要健壮 D）存储空间要小
E）算法要可行 F）执行时间要短
17. 算法的时间复杂度与（ ）有关。
A）问题规模 B）程序设计语言
C）编译质量 D）基本操作频度
E）硬件性能 F）输出数据大小
18. 算法的时间复杂度为O(n2)，这表明（ ）。
A）问题规模为n2 B）执行时间与n2成正比
C）问题规模为n D）执行时间与n成正比
E）执行时间为n2 F）问题规模与n2成正比
19. 在下列函数中，时间复杂度较小的两个函数是（ ）。
A）n2+100 B）n lg n
C）n+100 D）n!
E）2n F）lg n
20. 在下列函数中，时间复杂度相同的函数是（ ）。
A）n2+100 B）n3+n+10
C）nn D）n!
E）2n F）n3+lg n
二、填空题（在括号内填入适当文字）
01. （ ）是数据的基本单位，（ ）是数据的最小单位。
02. 数据结构包括（ ）的集合以及它们之间的（ ）。
03. 数据的逻辑结构在计算机中的表示称为数据的（ ）或（ ），又称机内映像。
04. 在数据的存储结构中，一个结点存储一个（ ）。
05. 逻辑相邻的数据元素，物理地址也相邻，这样的存储结构称为（ ）存储结构。
06. 逻辑相邻的数据元素，物理地址可以不相邻，这样的存储结构称为（ ）存储结构。
07. 算法具有5个特性：输入、输出、有穷性、（ ）和（ ）。
08. 算法的评价标志包括：正确性、通用性、可读性、（ ）、（ ）。
09. 算法的执行时间是（ ）的函数，最终归结为执行基本操作的次数。
10. 算法的高效性要求：（ ）、（ ）。
三、判断题（在题干后面的括号中，用“√”或“×”标记叙述是否正确）
01. 一些表面上很不相同的数据，可以具有相同的逻辑结构。 （ ）
02. 从不同角度观察，同一数据可以抽象为不同的逻辑结构。 （ ）
03. 数据元素之间的逻辑关系主要指数据元素之间的相邻关系。 （ ）
04. 数据对象是数据的一个子集，由一组数据元素构成。 （ ）
05. 数据关系是一个集合，数据元素之间可能有多种关系。 （ ）
06. 在顺序存储结构中，所有结点占用一片连续的存储区域。 （ ）
07. 在顺序存储结构中，任意两个结点的存储地址相邻。 （ ）
08. 在链式存储结构中，一个结点占用一片连续的存储区域。 （ ）
09. 在链式存储结构中，所有结点占用一片连续的存储区域。 （ ）
10. 在链式存储结构中，每个结点都包含数据域和指针域。 （ ）
11. 逻辑结构相同的数据，可以采用不同的存储结构。 （ ）
12. 逻辑结构不相同的数据，必须采用不同的存储结构。 （ ）
13. 数据的逻辑结构与数据元素的机内表示无关。 （ ）
14. 逻辑结构相同的数据，存储结构的结点必然相同。 （ ）
15. 一个数据元素可以表示一个职工、一件商品、一个车站等。 （ ）
16. 算法的优劣与计算机和描述语言均无关系。 （ ）
17. 可以使用不同的程序语言描述算法。 （ ）
18. 可以使用不同的自然语言描述算法。 （ ）
19. 算法就是程序，程序就是算法，二者等同。 （ ）
20. 设计算法的最终目的是：必须用程序设计语言实现算法。 （ ）
四、根据二元组关系，画出数据元素之间逻辑关系的图形表示。
（1）A=(D, R)
其中，D={a,b,c,d,e}
R={}
（2）B=(D,R)
其中，D={a,b,c,d,e,f}
R={,,,,}
（3）F=(D,R)
其中，D={50,25,64,57,82,36,75,55}
R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>}
（4）C=(D,R)
其中，D={1,2,3,4,5,6}
R={<1,2>,<2,3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}
五、分析算法的时间复杂度
（1）计算基本操作执行次数，然后给出时间复杂度。
fun(int n)
{ x=x+1;
for(i=1; i<=n; i++) x=x+1;
for(j=1; j<=n; j++)
for(k=1; k<=n; k++)
{ x=x+1; x=x*2; }
}
（2）计算基本操作执行次数，然后给出时间复杂度。
Sum1( int n )
{ int p=1, sum=0, m ;
for (m=1; m<=n; m++)
{ p*=m; sum+=p; }
return (sum);
}
（3）估算量级，不要求计算基本操作的确切执行次数。
Sum2( int n )
{ int sum=0, m, t ;
for (m=1; m<=n; m++)
{ p=1 ;
for (t=1; t<=m; t++) p*=t ;
sum+=p;
}
return (sum) ;
}
（4）递归函数——阶乘，估算量级，不计算确切执行次数。提示：虽然算法没有循环，但需要多次调用函数自身。
fact( int n )
{ if (n<=1) return(1) ;
else return( n*fact(n-1)) ;
}
（5）估算量级，不要求计算基本操作的确切执行次数。
#define N 100
void scheme()
{ int i, j, k, count, money;
for (i = 0; i<=N; i++ )
for (j = 0; j<=N; j++ )
for (k=0; k<=N; k++)
{ count=i+j+k; money=3*i+2*j+0.5*k;
if ( count==N && money==N)
printf (“%d, %d, %d \n%”, i, j, k) ;
