云南开放大学数据结构（C#语言）第一次离线作业

第1章
习题
一、填空题
1、数据的____________是数据的逻辑结构在计算机存储器内的表示。
2、数据的逻辑结构可以分类为           结构和            结构两大类。
3、          和            合称为非线性结构。
4、在树形结构中，除了树根结点以外，其余每个结点只有            个前驱结点。
5、在图型结构中，每个结点的前驱结点数和后继结点数可以是            。
6、数据的存储结构又叫            。
7、顺序存储结构是把逻辑上相邻的结点存储在物理上             的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
8、链式存储结构是把逻辑上相邻的结点存储在物理上               的存储单元里，结点之间的逻辑关系由附加的指针域来体现。
9、            是指用于解决特定问题的方法，是对问题求解过程的一种描述。
10、算法分析的两个主要方面是              复杂度和             复杂度。
二、选择题
1、（  ）是数据的最小单元，（  ）是数据的基本单元。
A．数据项 B．数据元素 C．信息项 D．表元素
2、数据结构是指（  ）以及它们之间的（  ）。
A．运算 B．结构 C．数据元素 D．计算方法
3、数据的运算（  ）。
A．效率与采用何种存储结构有关         B．是根据存储结构来定义的
C．有算数运算和关系运算两大类         D．必须用程序设计语言来描述
4、下列关于算法的说法错误的是（  ）。
A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的
C．算法的可行性是指指令不能有二义性
D．以上几个都是错误的
5、算法分析的主要目的是（  ）。
A．分析数据结构的合理性
B．分析数据结构的复杂性
C．分析算法的时空效率以求改进
D．分析算法的有穷性和确定性
6、一个算法具有（  ）等特点。
A．健壮性 B．可行性 C．确定性 D．至少有一个输入量
三、应用题
1、下列是某种数据结构的二元组表示，试画出其图形表示，并指出属于何种数据结构类型。
（1）B=（K，R），其中：
K={a，b，c，d，e，f，g，h}
R={r}
r={〈d，b〉，〈d，g〉，〈d，a〉，〈b，c〉，〈g，e〉，〈g，h〉，〈a，f〉}
（2）B（K，R），其中：
K={1，2，3，4，5，6}
R={r}
r={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}
2、计算下列程序段的渐近时间复杂度，用数量级O( )表示，问题的输入规模都为n。
（1）  void f1(int n)
{ int i=1,k=0;
while(i<n)
{  k+=10*i;
i++;
}
}
（2）  void f2(int n)
{ int i=91,j=100;
while(i>0)
if(i>100)
{x﹣=10;
y﹣﹣;
}
else
i++;
}
（3）  void f3(int n)
{int i=1;
while(i<n)
i*=3;
}