数据结构习题答案

数据结构习题答案Tag内容描述：<p>1、单元练习1一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）（3）数据元素是数据的最小单位。（）（4）数据的逻辑结构和数据的存储结构是相同的。（）（5）程序和算法原则上没有区别，所以在讨论数据结构时可。</p><p>2、第1章 绪论1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状。</p><p>3、I Single Choice(10 points)1. ( a )For the following program fragment the running time(Big-Oh) is .i = 0;s = 0;while(s ( 5*n*n + 2) i+;s = s + i;a. O(n) b. O(n2) c. O(n1/2) d. O(n3)2. ( c )Which is non-linear data structure_____.a. queue b.stack c. tree d. sequence list3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is .a. O(1) b. O(n) c。</p><p>4、数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 、数据信息在计算机中的 以及一组相关的运算等的课程。 A操作对象计算方法逻辑结构数据映象 A存储结构 关系 运算 算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是 的有限集合，R是D上的 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系3. 在数据结构中，从逻辑上可以把数据结构分成 。A动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构4. 算法分析的目的。</p><p>5、第1章 绪1.1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。(1) A= ( D，R )，其中，D = a1，a2，a 3，a4 ， R= (2) B= ( D，R )，其中，D = a，b，c，d，e， R= (a，b)，(b，c)，(c，d)，(d，e)(3) C= ( D，R )，其中，D = a，b，c，d，e，f，g， R= (d，b)，(d，g)，(b，a)，(b，c)，(g，e)，(e，f)(4) K= ( D，R )，其中，D = 1，2，3，4，5，6， R= ，(1) 集合(2) 线性表 (3) 树 (4) 图 1.2 设n为正整数，求下列各程序段中的下划线语句的执行次数。(1) i=1; k=0while(i=n-1。</p><p>6、习题三3.1 3.10 3.133.5 3.6 3.15 3.17 3.19 3.24 3.29 3.31 3.5(1) 给定操作序列P1P2P3PiPn（Pk为S或X，k=1,2,n ）是合法的，当且仅当满足下列条件：a. 序列中包含的S的个数和X的个数相等；b. 对于任意的j（1jn）；有P1P2P3Pj子序列中所包含的S的个数大于等于X的个数；(2)证明：设P1P2P3PiPn ，Q1Q2Q3QiQn是两个不同的合法序列； 两者不同， k=mini| PiQi , 1in 且k1， PkQk （因P1 ，Q1肯定是S，否则不合法！） 即，P1P2P3Pk-1 和Q1Q2Q3Qk-1是相等的，但PkQk由此可知：两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同，由于Pk。</p><p>7、数据结构课后习题参考答案1.1.20（1）T(n) = n-1；渐近时间复杂度为O(n)。（2）T(n) = log2n；渐近时间复杂度为O(log2n)。（3）T(n) = n(n+1)(n+2)/6；渐近时间复杂度为O(n3)（4）T(n) =；渐近时间复杂度为O()2.2.3template bool SeqList:Insert2(int i, T x)if (i n-1)cout Out of bounds endl;return false;if (n = maxLength)T *elem = new T2 * maxLength;maxLength = maxLength * 2;for (int j = 0; j = i; j+)elemj。</p><p>8、第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+（1+2+n）=n(n+1)(n+2)/6 1. 4试编。</p><p>9、单元练习1一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（）（1）数据的逻辑结构与数据元素本身的内容和形式无关。（）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（）（3）数据元素是数据的最小单位。（）（4）数据的逻辑结构和数据的存储结构是相同的。（）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。</p><p>10、第一章 绪论 1 第18页 第 5 题 确定下列各程序段的程序步 确定划线语句的执行次数 计算它们的渐近时间复杂度 1 i 1 k 0 do k k 10 i i while i n 1 划线语句的执行次数为 n 1 2 i 1 x 0 do x i 2 i while in 划线语句的执行次数为 log2n 3 for int i 1 i n i for int j 1 j i j for in。</p><p>11、第二部分 习 题 黑龙江科技学院 习题一 绪 论 1、数据的逻辑结构、数据的物理存储结构、数据的操作（或运算）及其实现。 2、非线性结构 3、数据元素、 关系 4、 A 5、 (1) n2 (2) n(n+1)/2 (3) n*m 6、（1）O()（3）O(log3n) 习题二 线性表 1、第一个（或首元）、最后一个（或尾元）、位置（或序号）、直接前驱、直接后继 2、n-i+1、n-i 3、A 4。</p>