习题1

1.1 选择题

（1）计算机识别、存储和加工处理的对象统称为_________。

A.数据 B.数据元素

C.数据结构 D.数据类型

（2）数据结构通常研究数据的_________及它们之间的联系。

A.存储和逻辑结构 B.存储和抽象

C.理想和抽象 D.理想与逻辑

（3）不是数据的逻辑结构的是__________。

A.散列结构 B.线性结构

C.树结构 D.图结构

（4）数据结构被形式地定义为<D,R>，其中D是_________的有限集，R是_________的有限集。

A.算法 B.数据元素

C.数据操作 D.逻辑结构

（5）组成数据的基本单位是__________。

A.数据项 B.数据类型

C.数据元素 D.数据变量

（6）设数据结构A=(D, R)，其中D={1, 2, 3, 4}，R={r}, r={<1, 2>, <2, 3>, <3, 4>, <4, 1>}，则数据结构A是__________。

A.线性结构 B.树形结构

C.图状结构 D.集合

（7）数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为_____。

A.存储结构 B.逻辑结构

C.顺序存储结构 D.链式存储结构

（8）在数据结构的讨论中，把数据结构从逻辑上分为_______。

A.内部结构与外部结构 B.静态结构与动态结构

C.线性结构与非线性结构 D.紧凑结构与非紧凑结构

（9）对一个算法的评价，不包括_________方面的内容。

A.健壮性和可读性 B.并行性

C.正确性 D.时空复杂度

（10）算法分析的两个方面是______。

A.空间复杂性和时间复杂性 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性

1.2 填空题

（1）数据结构是一门研究非数值计算的程序设计问题中计算机的_________及它们之间的_________和运算等的学科。

（2）数据结构包括数据的_________结构和_________结构。

（3）数据结构从逻辑上划分为三种基本类型：___________、__________和___________。

（4）数据的物理结构被分为_________、________、__________和___________四种。

（5）一种抽象数据类型包括_________和_________两部分。

（6）数据的逻辑结构是指_________，数据的存储结构是指_________。

（7）数据结构是指数据及其相互之间的____________。当结点之间存在M对N（M∶N）的联系时，称这种结构为________________。当结点之间存在1对N（1∶N）的联系时，称这种结构为_______________。

（8）对算法从时间和空间两方面进行度量，分别称为_________分析。

（9）算法的效率可分为_______________效率和_______________效率。

（10）for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复杂度为_________。

1.3 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。

（1）for(i＝1；i<＝n；i++)

　　　　　for(j＝1；j<＝n；j++)

　　　　　　　　s++；

（2）for(i＝1；i<＝n；i++)

　　　　　for(j＝i；j<＝n；j++)

　　　　　　　s++；

（3）for(i＝1；i<＝n；i++)

　　　　　for(j＝1；j<＝i；j++)

　　　　　　　s++；

（4）i＝1；k＝0；

　　　　　　while(i<＝n-1){

　　　　　　　k+＝10*i；

　　　　　　　　i++；

　　　　　　　　　}

（5）for (i＝1；i<＝n；i++)

　　　　　for (j＝1；j<＝i ；j++)

　　　　　　　　for (k＝1；k<＝j；k++)

　　　　　　　　　　　x=x+1；

1.5 试写一算法，自大至小依次输出顺序读入的三个整数X、Y和Z的值。

1.6 编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…+anxn的值Pn(x0)，要求算法的时间复杂度尽可能地小。