课后题解答第一章.docVIP

什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构 = { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： 数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ② 数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； 施加于该数据结构上的操作。 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 数据元素是数据的最小单位。（是基本，数据项中的初等项才是） (2) 数据结构是数据对象与对象中数据元素之间关系的集合。 (3) 数据结构是具有结构的数据对象。 (4) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 (5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 【解答】 (1) ( (2) ( (3) ( (4) ( (5) ( 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。 (2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。（但是可以做的操作相同） (3) 数据的逻辑结构与数据元素本身的内容和形式无关。 (4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。P3 (5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 【解答】 (1) ( (2) ( (3) ( (4) ( (5) ( 有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时，对每个关系画出相应的结构图），并指出它们分别属于何种结构。 (1) A = (K, R)，其中 K = { a1, a2, a3, a4 }，R = { } (2) B = (K, R)，其中 K = { a, b, c, d, e, f, g, h }，R = { r }， r = {a,b, b,c, c,d, d,e, e,f, f,g, g,h } (3) C = (K, R)，其中 K = { a, b, c, d, e, f, g, h }，R = { r }， r = {d,b, d,g, b,a, b,c, g,e, g,h, e,f } (4) D = (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) } 【解答】 (1) (2) (3) (4) 指出下列各个算法的功能并计算其时间复杂度 (1) int Prime ( int n ) { int i = 2, x = (int) sqrt ( n ); while ( i = x ) { if ( n % i == 0 ) break; i++; } if ( i x ) return 1; else return 0; } (2) int sum1 ( int n ) { int p = 1, s = 0; for ( int i = 1; i = n; i++ ) { p *= i; s += p; } return s; } (3) int sum2 ( int n ) { int s = 0; for ( int i = 1; i = n; i++ ) { int p = 1; for ( int j = 1; j = i; j++ ) p *= j; s += p; } return s; } (4) int fun ( int n ) { int i = 1, s = 1; while ( s n ) s += ++i; return i; } (5) void UseFile ( ifstream inp, int c[ ] ) { //假定inp所对应的文件中保存有n个整数。 for ( int i = 0; i 10; i++ ) c[i] = 0; int x; while ( inp x ) { i = x%10; c[i]++; } } (6) void mtable ( int n