《(完整word版)《数据结构——C语言描述》习题及答案-耿国华.doc》由会员分享，可在线阅读，更多相关《(完整word版)《数据结构——C语言描述》习题及答案-耿国华.doc（80页珍藏版）》请在金锄头文库上搜索。
1、(完整word版)数据结构C语言描述习题及答案 耿国华第1章 绪 论习题一、问答题1. 什么是数据结构？2. 四类基本数据结构的名称与含义。3. 算法的定义与特性。4. 算法的时间复杂度.5. 数据类型的概念.6. 线性结构与非线性结构的差别.7. 面向对象程序设计语言的特点。8. 在面向对象程序设计中,类的作用是什么?9. 参数传递的主要方式及特点。10. 抽象数据类型的概念。二、判断题1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2. 算法就是程序。3. 在高级语言(如C、或 PASCAL）中,指针类型是原子类型。三、计算下列程序段中X=X+1的语句频度for(i=
2、1;i=n;i+） for(j=1；j=i;j+)for(k=1;k=j；k+） x=x+1;提示： i=1时： 1 = （1+1）1/2 = (1+12）/2 i=2时: 1+2 = （1+2)2/2 = （2+22）/2 i=3时： 1+2+3 = （1+3）3/2 = （3+32）/2 i=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区分语句频度和算法复杂
3、度：O（f(n)） = O(n3)四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn（x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1，n）, x和n，输出为Pn(x0）.通常算法的输入和输出可采用下列两种方式之一：（1） 通过参数表中的参数显式传递；（2） 通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。提示：float PolyValue(float a , float x， int n) 核心语句
4、：p=1; (x的零次幂)s=0;i从0到n循环s=s+ai*p； p=p*x； 或：p=x; (x的一次幂）s=a0；i从1到n循环s=s+aip； p=p*x; 实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案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)/61。4试编写算法，求pn（x)=a0+a1x+a2
5、x2+.+anxn的值pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小,规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1，n)、x和n,输出为Pn（x0)。 算法的输入和输出采用下列方法（1)通过参数表中的参数显式传递（2）通过全局变量隐式传递.讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递 优点：当没有调用函数时,不占用内存，调用结束后形参被释放,实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应,且返回值数量有限。（2）通过全局变量隐式传递 优点:减少实参与形参的个数
6、，从而减少内存空间以及传递数据时的时间消耗 缺点:函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue(） int i，n;float x，a，p; printf(“nn=”）; scanf（“%f”，&n）； printf（“nx=”)； scanf(“f”，&x);for（i=0;in；i+) scanf(“%f ”，ai)； /*执行次数：n次 */ p=a0； for（i=1；inext=S；（2）P-next= P-nextnext;(3）Pnext= Snext；（4）Snext= P-next；（5）Snext= L；（6）Snext= NULL;（7）Q
7、= P;（8）while(P-next！=Q) P=Pnext；（9）while（P-next!=NULL) P=P-next；（10）P= Q；（11）P= L;(12)L= S；(13）L= P；2.4 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上,以保持线性表L的有序性。提示：void insert(SeqList *L; ElemType x） 方法1 （1）找出应插入位置i,（2）移位,（3) 方法2 参P。 2292.5 写一算法，从顺序表中删除自第i个元素开始的k个元素。提示：注意检查i和k的合法性。 （集体搬迁，“新房、“旧房”） 方法1 以待移动元素下标m（“旧
8、房号”)为中心,计算应移入位置（“新房号）： for ( m= i1+k； m= Llast； m+) Lelem mk = Lelem m ； 同时以待移动元素下标m和应移入位置j为中心:data = mink) pre=p； p=pnext； (2)找到最后一个应删结点的后继s，边找边释放应删结点s=p;while (s！=NULL & sdata next; free(t）; （3）prenext = s;2.7 试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1， a2.， an)逆置为（an, an1,。, a1）.（1）以一维数组作存储结构，设线性表存
9、于a（1:arrsize)的前elenum个分量中。（2)以单链表作存储结构。方法1:在原头结点后重新头插一遍方法2：可设三个同步移动的指针p, q， r，将q的后继r改为p2。8 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C.提示:参P.28 例2-1 方法1 void merge（LinkList A； LinkList B； LinkList C） pa=Anext； pb=Bnext； *C=A； （*C）next=NULL；while （ pa！
10、=NULL & pb！=NULL ) if （ padata next; smallernext = （*C)next； /* 头插法 */ （*C)next = smaller;else smaller=pb; pb=pbnext; smallernext = (C）next; (*C）next = smaller； while ( pa!=NULL） smaller=pa； pa=panext; smallernext = （C）next; (C）next = smaller；while ( pb!=NULL) smaller=pb; pb=pbnext； smallernext = (*C）next; （C)next = smaller； 方法2 LinkList merge（LinkList A； LinkList B) LinkList C；pa=Anext； pb=Bnext; C=A; Cnext=NULL;
