数据结构(C语言版)(第4版)习题讲述.docxVIP

习题 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.静态结构与动态结构 B．线性结构与非线性结构 D.紧凑结构与非紧凑结构 (9)对于一个算法的评价，不包括以下 方面的内容。 A.健壮性和可读性 B.并行性 C.正确性 D.时间空间复杂度 (10)算法分析的两个方面是 。 A．空间复杂性和时间复杂性 B.正确性和简明性 C．可读性和文档性 D.数据复杂性和程序复杂性 1.2 填空题 (1)数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。 (2)数据结构包括数据的 结构和 结构。 (3)数据结构从逻辑上划分为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.4分析下面语句段执行的时间复杂度。 (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试写一个算法，自大至小依次输出顺序读入的3个整数X、Y和Z。 1.6编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+???+anxn的值Pn(x0)，要求算法的时间复杂度尽可能小。 习题 2 2.1选择题 (1)线性表是具有n个 的有限序列(n≠0)。 A.表元素 B.字符 C.数据元素 D.数据项 (2)顺序表的存储结构是一种 的存储结构。 A.随机存取 B.顺序存取 C.索取存取 D. Hash存取 (3)在一个长度为n的顺序表中向第i个元素(1≤i≤n+1)之间插入一个新元素时需要向后移动 个元素