必威体育精装版数据结构习题(有答案).docxVIP

第1章绪 1.1有下列几种二兀组表示的数据结构，试画出它们分别对应的图形表示， 并指出它们分别属于何种结构。 ⑴ A= （ D ，R ），其中，D = { a i，a2，a 3，a4 }， R={ } ⑵ B= （ D，R ），其中，D = { a，b，c, d，e}, R={ （a，b），（b，c）, （c, d），（d，e）} ⑶ C= （ D，R ），其中，D = { a，b，c，d，e，f，g}， R={ （d，b），（d， g），（b，a），（b，c），（g，e），（e，f）} ⑷ K= （ D，R ），其中，D = { 1，2，3，4，5，6}， R={ ＜1，2＞，＜2， 3＞，＜2，4＞，＜3，4＞，＜3，5＞，＜3，6＞，＜4，5＞，＜4，6＞} （1） 集合 （2） 线性表 （3） 树 （4）图 1.2设n为正整数，求下列各程序段中的下划线语句的执行次数。 (1) i=1; k=0 while(i=n-1) { k+=10*i ; i++; } (2) for (in t i=1; i=n; i++) for (int j=1; j=n; j++) { c[i][j]=0; for (i nt k=1; k=n; k++) c[i][j]=c[i][j]+a[i][k]*b[k][j] } 解： n-1 n n n 3 1 n i 1 j 1 k 1 (3) x=0; y=0; for (int i=1; i=n; i++) for (int j=1; j=i; j++) for (int k=1; k=j; k++) x=x+y; n i j 1 n i j n i(i 1) 1 n i2 1 n i 1 ?n(n 1)(2n 1) 1 ?n(n 1) 1 j / — i i ? ? (3) i 1 j 1 k 1 i 1 j 1 i 1 2 2 i 1 2 i 1 2 6 2 2 n(n 1)(n 2) 6  1.3指出下列个算法的功能，并求其时间复杂度。(1) int sum1(i nt n){ 1.3指出下列个算法的功能，并求其时间复杂度。 (1) int sum1(i nt n) { int p=1,s=0; for (int i=1;i=n; i++) { p*= i； s+=p;} return s; } ⑵ 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; } 解： n ⑴ i! , T(n)=O(n) i 1 n ⑵ i! , T(n)=O(n 2) i 1 } 1.4算法设计 1枚是假的，伪币与真币重量略有不同。如何借用一架有3 1枚是假的，伪币与真币重量略有不同。如何借用一架 上机练习题 要求：给出问题分析、算法描述、源程序及运行截图，在线提交。 1.设a, b, c为3个整数，求其中位于中间值的整数。 第2章线性表 1.设计算法：在顺序表中删除值为 e的兀素，删除成功，返回1 ; int SqlistT::DeleteElem( T e ) 否则，返回0。 { for (i=1; i=le ngth; i++) // 按值顺序查找 * i 可从0开始 if (elem[i-1]= =e) // 找到，进行删除操作 { for ( j=i; jlength; j++) // ai 至 an 依次前移 Elem[j-1] = elem[j]; len gth - - ; // 表长减一 return 1 ; //删除成功，返回 } return 0 ; //未找到，删除不成功，返回 } 1 0 int SqListT::Locate ( T 解：设表长为n,等概率下，每个兀素被定位的概率为： p=1/n 2.分析顺序表中兀素疋位算法 e )的时间复杂度。 疋位成功第i个兀素，需比较i次 一、n 1 C. 1 V 1 °n(n 1) n 1 f(n) ?i i ? i 1 n n i 1 n 2 2 3.对于有头结点的单链表，分别写出定位成功时， 实现下列定位 语句序列。 (1)定位到第i个结点ai； p=head; j=0; while ( p ji ) { p=p-n ext; j++;} (2)定位到第i个结点的前驱ai-i ; p=head; j=0; while ( p ji-1 ) { p=p- next; j++;} (3)定位到尾结点; p=head; while ( p -next ) p=p-n ext; (4)定位到尾结点的前驱。 p=head; 4. 4.描述一下三个概念的区别：头指针，头结点，首元