数据结构练习题(有答案).doc

第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，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 (int i=1; i=n; i++) for (int j=1; j=n; j++) { c[i][j]=0; for (int k=1; k=n; k++) c[i][j]=c[i][j]+a[i][k]*b[k][j] } 解： (1) n-1 (2) (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; (3) 1.3 指出下列个算法的功能，并求其时间复杂度。 (1) int sum1(int n) { int p=1,s=0; for (int i=1;i=n; i++) { p*= i; s+=p;} return s; } (2) 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; } 解： (1) , T(n)=O(n) (2) , T(n)=O(n2) 1.4 算法设计 有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。 上机练习题 要求：给出问题分析、算法描述、源程序及运行截图，在线提交。 1. 设 a, b, c为3个整数，求其中位于中间值的整数。 第2章 线性表 1. 设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。 int SqlistT::DeleteElem( T e ) { for (i=1; i=length; i++) // 按值顺序查找 * i可从0开始 if (elem[i-1]= =e) // 找到，进行删除操作 { for ( j=i; jlength; j++) // ai至an依次前移 Elem[j-1] = elem[j]; length - - ; // 表长减一 return 1 ; //删除成功，返回 1 } return 0 ; // 未找到，删除不成功，返回 0 } 2. 分析顺序表中元素定位算法 int SqListT::Locate ( T e ) 的时间复杂度。 解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n 定位成功第i个元素，需比较i次 3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。 (1) 定位到第i个结点ai； p=head; j=0; while ( p ji ) { p=p-next; j++;} (2) 定位到第i个结点的前驱ai-1； p=head; j=0; while ( p ji-1 ) { p=p-next; j++;} (3) 定位到尾结点； p=head; while ( p -next ) p=p-next; (4) 定位到尾结点的前驱。 p=head; while ( p-next-next ) p=p-next; 4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。 头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。 首元结点：指链表中的第一个元素结点。 5. 对于无头结点单链表，给出删除第i个结点