《数据结构C语言描述习题及答案耿国华》由会员分享，可在线阅读，更多相关《数据结构C语言描述习题及答案耿国华（79页珍藏版）》请在金锄头文库上搜索。
1、.第1章绪论习题一、问答题1. 什么是数据构造？2. 四类根本数据构造的名称与含义。3. 算法的定义与特性。4. 算法的时间复杂度。5. 数据类型的概念。6. 线性构造与非线性构造的差异。7. 面向对象程序设计语言的特点。8. 在面向对象程序设计中，类的作用是什么？9. 参数传递的主要方式及特点。10. 抽象数据类型的概念。二、判断题1. 线性构造只能用顺序构造来存放，非线性构造只能用非顺序构造来存放。2. 算法就是程序。3. 在高级语言如C、或 PASCAL中，指针类型是原子类型。三、计算以下程序段中*=*+1的语句频度for(i=1;i=n;i+) for(j=1;j=i;j+)for(k
2、=1;k=j;k+) *=*+1;提示：i=1时： 1 = (1+1)1/2 = (1+12)/2i=2时： 1+2 = (1+2)2/2 = (2+22)/2i=3时： 1+2+3 = (1+3)3/2 = (3+32)/2i=n时： 1+2+3+n = (1+n)n/2 = (n+n2)/2f(n) = (1+2+3+n) + (12 + 22 + 32 + + n2 ) / 2 = (1+n)n/2 + n(n+1)(2n+1)/6 / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n) = O(n3)四、试编写算法求一元多项式Pn(*)
3、=a0+a1*+a2*2+a3*3+an*n的值Pn(*0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：此题中的输入ai(i=0,1,n), *和n，输出为Pn(*0).通常算法的输入和输出可采用以下两种方式之一：（1） 通过参数表中的参数显式传递；（2） 通过全局变量隐式传递。试讨论这两种方法的优缺点，并在此题算法中以你认为较好的一种方式实现输入和输出。提示：float PolyValue(float a , float *, int n) 核心语句：p=1; (*的零次幂)s=0;i从0到n循环s=s+ai*p; p
4、=p*; 或：p=*; (*的一次幂)s=a0;i从1到n循环s=s+ai*p; p=p*; 实习题设计实现抽象数据类型有理数。根本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案1.3计算以下程序中*=*+1的语句频度 for(i=1;i=n;i+)for(j=1;j=i;j+) for(k=1;k=j;k+) *=*+1;【解答】*=*+1的语句频度为：T(n)=1+(1+2)+1+2+3+1+2+n=n(n+1)(n+2)/61.4试编写算法，求pn(*)=a0+a1*+a2*2+.+an*n的值pn(*0),并确定算法中每一语句的执行次数和整个算法的时间复杂
5、度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：此题中的输入为ai(i=0,1,n)、*和n,输出为Pn(*0)。算法的输入和输出采用以下方法1通过参数表中的参数显式传递2通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】1通过参数表中的参数显式传递优点：当没有调用函数时，不占用存，调用完毕后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。2通过全局变量隐式传递优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数Poly
6、Value() int i,n;float *,a,p;printf(nn=); scanf(%f,&n); printf(n*=); scanf(%f,&*);for(i=0;in;i+) scanf(%f ,&ai); /*执行次数：n次 */ p=a0; for(i=1;i=n;i+) p=p+ai*; /*执行次数：n次*/ *=*;printf(%f,p); 算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a , float *, int n) float p,s;int i;p=*; s=a0;for(i=1;ine*t=S
7、;2P-ne*t= P-ne*t-ne*t;3P-ne*t= S-ne*t;4S-ne*t= P-ne*t;5S-ne*t= L;6S-ne*t= NULL;7Q= P;8while(P-ne*t!=Q) P=P-ne*t;9while(P-ne*t!=NULL) P=P-ne*t;10P= Q;11P= L;12L= S;13L= P;2.4 线性表L递增有序。试写一算法，将*插入到L的适当位置上，以保持线性表L的有序性。提示：void insert(SeqList *L; ElemType *) 1找出应插入位置i，2移位，3 参P. 2292.5 写一算法，从顺序表中删除自第i个元素开场
8、的k个元素。提示：注意检查i和k的合法性。集体搬迁，新房、旧房 以待移动元素下标m旧房号为中心，计算应移入位置新房号： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ; 同时以待移动元素下标m和应移入位置j为中心： 以应移入位置j为中心，计算待移动元素下标：2.6线性表中的元素整数以值递增有序排列，并以单链表作存储构造。试写一高效算法，删除表中所有大于mink且小于ma*k的元素假设表中存在这样的元素，分析你的算法的时间复杂度注意：mink和ma*k是给定的两个参变量，它们的值为任意的整数。提示：注意检查mink和ma*k的合法性：mink ne*t
9、;while (p!=NULL & pdata ne*t; 2找到最后一个应删结点的后继s，边找边释放应删结点s=p;while (s!=NULL & sdatane*t; free(t); 3prene*t = s;2.7试分别以不同的存储构造实现线性表的就地逆置算法，即在原表的存储空间将线性表a1, a2., an逆置为an, an-1,., a1。1以一维数组作存储构造，设线性表存于a(1:arrsize)的前elenum个分量中。2以单链表作存储构造。方法1：在原头结点后重新头插一遍方法2：可设三个同步移动的指针p, q, r，将q的后继r改为p2.8 假设两个按元素值递增有序排列的线
10、性表A和B，均以单链表作为存储构造，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表即A表和B表的结点空间存放表C.提示：参P.28 例2-1void merge(LinkList A; LinkList B; LinkList *C) pa=Ane*t; pb=Bne*t; *C=A; (*C)ne*t=NULL;while ( pa!=NULL &pb!=NULL ) if ( padata data ) smaller=pa; pa=pane*t; smallerne*t = (*C)ne*t; /* 头插法 */(*C)ne*t = smaller;e
11、lse smaller=pb; pb=pbne*t; smallerne*t = (*C)ne*t; (*C)ne*t = smaller; while ( pa!=NULL) smaller=pa; pa=pane*t; smallerne*t = (*C)ne*t;(*C)ne*t = smaller;while ( pb!=NULL) smaller=pb; pb=pbne*t; smallerne*t = (*C)ne*t;(*C)ne*t = smaller;LinkList merge(LinkList A; LinkList B) LinkList C；pa=Ane*t; pb=Bne*t; C=A; Cne*t=NULL; return C;2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。s为指向链表*个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。提示：设指针p指向s结点的前趋的前趋，则p与s有何关系？2.10 有单链表表示的线性表中含有三类字符的数据元素如字
