第一章习题答
案
2、××√
3、（1）包含改变量定义的最小范围
（2）数据抽象、信息隐蔽
（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型
（5）集合结构、线性结构、树形结构、图状结构
（6）顺序存储、非顺序存储
（7）一对一、一对多、多对多
（8）一系列的操作
（9）有限性、输入、可行性
4、（1）A（2）C（3）C
5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答
案
1、（1）一半，插入、删除的位置
（2）顺序和链式，显示，隐式
（3）一定，不一定
（4）头指针，头结点的指针域，其前驱的指针域
2、（1）A（2）A：E、A
B：H、L、I、E、A C：F、M
D：L、J、A、G或J、A、G
（3）D（4）D（5）C（6）
A、C
3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。
头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。
首元素结点：线性表中的第一个结点成为首元素结点。
4、算法如下：
int Linser(SeqList
*L,int X)
{ int i=0,k;
if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)；
return(0);
}
while(i<=L->last&&L->ele m[i] i++; for(k=L->last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X; L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2 )) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last; j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink { printf(“参数不合法”); return ERROR; } else { p=L; while(p->next-data<=mink ) p=p->next; while(q->data { p->next=q->next; free(q); q=p->next; } return OK; } } 9、算法如下： int Dele(Node *S) { Node *p; P=s->next; If(p= =s) {printf(“只有一个结点，不删除”)； return 0; } else {if((p->next= =s) {s->next=s; free(p); return 1; } Else { while(p->next->next!=s ) P=p->next; P->next=s; Free(p); return 1; } } } 第三章习题答案 2、（1） 3、栈有顺序栈和链栈两种存储结构。 在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。 在带头结点链栈中，栈顶指针top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。 5、 #include #include "stdio.h" void main( ) { char ch,temp; SeqStack s; InitStack(&s); scanf("%c",&ch); while(ch!='@'&&ch!='&') { Push(&s,ch); scanf("%c",&ch); } while(ch!='@'&&!IsEmpty( &s)) { Pop(&s,&temp); scanf("%c",&ch); if(ch!=temp) break; } if(!IsEmpty(&s)) printf("no!\n"); else { scanf("%c",&ch); if(ch=='@') printf("yes!\n"); else printf("no!\n"); } } 12、（1）功能：将栈中元素倒置。 （2）功能：删除栈中的e 元素。 （3）功能：将队列中的元素倒置。 第四章习题答案 1、StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=?I AM A ?； SubString(sub2,s,7,1)操作结果为sub2=??；StrIndex(s,?A?,4) 操作结 果为5； StrReplace(s,?STUDENT?,q) 操作结果为?I AM A WORKER?； StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作结果为?I AM A GOOD WORKER?；2、 int StrReplace(SString S,Sstring T,SString V) { int i=1; //从串S 的第一个字符起查找串T if(StrEmpty(T)) //T是空串 return ERROR; do { i=Index(S,T,i); //结果i为从上一个i之后找到的子串T的位置 if(i) //串S中存在串T { StrDelete(S,i,StrLength( T)); //删除该串T StrInsert(S,i,V); //在原串T的位置插入串V i+=StrLength(V); //在插入的串V后面继续查找串T } }while(i); return OK; } 第五章习题答案 1、（1）数组A 共占用48*6=288个字节； （2）数组A 的最后一个元素的地址为1282； （3）按行存储时loc （A 36）=1000+[（3-1）*8+6-1]*6=1126 （4）按列存储时loc （A 36）=1000+[（6-1）*6+3-1]*6=1192 9、（1）（a ，b ）（2）（（c ，d ））（3）（b ）（4）b （5）（d ） 10、D 第六章 习题答案 1、三个结点的树的形态有两个；三个结点的二叉树的不 同形态有5个。 2、略 3、证明：分支数 =n 1+2n 2+…+kn k （1） n= n 0+n 1+…+n k （2） ∵ n=分支数+1 （3） 将（1）（2）代入 （3）得 n 0= n 2+2n 3+3n 4+…+（k-1）n k +1 4、 注：C 结点作为D 的右孩子（画图的时候忘记了，不好意思） 5、n0=50，n2=n0-1=49，所 以至少有99个结点。 6、（1）前序和后序相同：只有一个结点的二叉树 （2）中序和后序相同：只有左子树的二叉树 （3）前序和中序相同：只有右子树的二叉树 7、证明：∵n 个结点的K 叉树共有nk 个链域，分支数为n-1（即非空域）。 ∴空域=nk-（n-1）=nk-n+1 8、对应的树如下： 9、（答案不唯一） 哈夫曼树如下图所示： 哈夫曼编码如下： 频率编码 0.07 0010 0.19 10 0.02 00000 0.06 0001 0.32 01 0.03 00001 0.21 11 0.10 0011 11、对应的二叉树如下： 12、求下标分别为i和j的 两个桔点的最近公共祖先结 点的值。 typedef int ElemType; void Ancestor(ElemType A[],int n,int i,int j) {while(i!=j) if(i>j) i=i/2; else j=j/2; printf("所查结点的最近 公共祖先的下标是%d,值 是%d",i,A[i]); } 15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。 void Del_Sub(BiTree T) { if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); } void Del_Sub_x(BiTree T,int x) { if(T->data==x) Del_Sub(T); else {if(T->lchild) Del_Sub_x(T->lchild,x); if(T->rchild) Del_Sub_x(T->rchild,x); } } 22、 int Width(BiTree bt) {if (bt==NULL) return (0); else {BiTree p,Q[50]; int front=1,rear=1,last=1; int temp=0, maxw=0; Q[rear]=bt; while(front<=last) {p=Q[front++]; temp++; if (p->lchild!=NULL) Q[++rear]=p->lchild; if (p->rchild!=NULL) Q[++rear]=p->rchild; {last=rear; if(temp>maxw) maxw=temp; temp=0;} } return (maxw); } } 第七章习题答案 1、（1）顶点1的入度为3，出 度为0； 顶点2的入度为2，出 度为2； 顶点3的入度为1，出 度为2； 顶点4的入度为1，出 度为3； 顶点5的入度为2，出 度为1； 顶点6的入度为2，出 度为3； （2）邻接矩阵如下： 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 （3）邻接表 （4）逆邻接表 2、答案不唯一（2）深度优先遍历该图所得顶点序列为：1，2，3，4，5，6 边的 序列为：（1，2）（2，3）（3，4）（4，5）（5，6） （3）广度优先遍历该图所得顶点序列为：1，5，6，3，2，4 边的 序列为：（1，5）（1，6）（1，3）（1，2）（5，4） 3、 （1）每个事件的最早发生时间： ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16, ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23 每个事件的最晚发生 时间:： vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15, vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0 （2）每个活动的最早开始时间： e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12, e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21 每个活动的最迟开始时间： l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21 （3）关键路径如下图所示： 4、顶点1到其余顶点的最短路经为： 1-〉3最短路经为1，3；长度为15 1-〉2最短路经为1，3，2；长度为19 1-〉5最短路经为1，3，5；长度为25 1-〉4最短路经为1，3，2，4；长度为29 1-〉6最短路经为1，3，2，4，6；长度为44 13、A(7)B(3)C(2)D(11)E(8) 14、略 15、略 第八章查找 1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 解： ASL=(1+2*2+4*3+3*4)/10=2 .9 5、 解：（1）插入完成后的二叉排序树如下： ASL=(1+2*2+3*3+3*4+2*5+1 *6)/12=3.5 (2)ASL=(1+282+3*4+4*5)=3 7/12 (3) 12、 解：哈希表构造如下： 0 1 2 3 4 56 7 8 9 1 2 2 4 1 3 1 5 3 4 6 1 36 7 H(22)=(22*3)%11=0 H(41)=(41*3)%11=2 H(53)=(53*3)%11=5 H(46)=(46*3)%11=6 H(30)=(30*3)%11=2 与(41)冲突 H1(30)=(2+1)%11=3 H(13)=(13*3)%11=6 与46冲突 H1(13)=(6+1)%11=7 H(01)=(01*3)%11=3 与30冲突 H1(01)=(3+1)%11=4 H(67)=(67*3)%11=3 与30冲突 H1(67)=(3+1)%11=4 与01冲突 H2(67)=(3+2)%11=5 与53冲突 H3(67)=(3+3)%11=6 与46冲突 H4(67)=(3+4)%11=7 与13冲突 H5(67)=(3+5)%11=8 ASLsucc=(1*4+2*3+6)/8=2 ASLunsucc=(2+8+7+6+5+4+3 +2)/8=37/8 第九章排序 1、以关键字序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟派结束时的关键字状态。 （1）直接插入排序（2）希尔排序（增量序列为5，3，1）（3）快速排序（4）堆排序（5）归并排序 解：（1）略 （2）增量为5的排序结果：170，087，275，061，426，503，897，512，653，908 增量为3的排序结果：061，087，275，170，426，503，897，512，653，908 增量为1的排序结果：061，087，170，275，426，503，512，653，897，908 （3）一次划分后：{426 087 275 061 170}503{897 908 653 512} 分别进行：{170 087 275 061}426 503 {512 653} 897 {908} {061 087}170{275}426 503 512 {653} 897 908 061 087 170 275 426 503 512 653 897 908 （4）略 7、已知一组关键字：（40，27，28，12，15，50，7）， 要求采用快速排序法从小到 大排序。请写出每趟排序后 的划分结果。 解：初始状态：40 27 28 12 15 50 7 一次划分：{7 27 28 12 15} 40 {50} 依次划分：7 {27 28 12 15} 40 50 7 {15 12} 27 {28} 40 50 7 12 15 27 28 40 50 16、（1）A3 B1 C4 D2 E7 (2)C (3)C 17、对，错，对 数据结构课程设计指导书 一、设计内容 1.飞机订票系统（限1 人完成） 【问题描述】 设计一个飞机订票系统，可 以模拟处理飞机订票过程中 的各种操作。 【基本要求】 通过此系统可以实现如下功能： 1)录入 可以录入航班情况（数 据可以存储在一个数据文件中，数据结构、具体数据自定）。 2)查询 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况。 3)订票（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班。 4)退票 可退票，退票后修改相关数据文件。 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 5)修改航班信息 当航班信息改变可以修改航班数据文件 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。 2.文章编辑（限1 人完成）【问题描述】 输入一页文字，程序可以统计出文字、数字、空格的个数。 【基本要求】 静态存储一页文章，每行最多不超过80个字符，共N行； 1)分别统计出其中英文字母数和空格数及整篇文章总字数； 2)统计某一字符串在文章中出现的次数，并输出该次数； 3)删除某一子串，并将后面的字符前移； 4)用指定的字符串替换某一子串； 5)存储结构使用线性表，分别用几个子函数实现相应的功能； 6)输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 7)输出形式：①分行输出用户输入的各行字符；②分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"；③输出删除某一字符串后的文章；④输出替换某一字符串后的文章。 3.宿舍管理查询软件（限1 人完成） 【问题描述】 为宿舍管理人员编写一个宿舍管理查询软件。 【基本要求】 1) 程序设计要求： ①采用交互工作方式②建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种) 2) 查询菜单: (用二分查找实现以下操作) ①按姓名查询 ②按学号查询 ③按房号查询 3) 输出任一查询结果（可以连续操作） 4.全国交通咨询模拟 【问题描述】 处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 【设计要求】 1)提供对城市信息进行编辑（如：添加或删除）的功能。 2)提供对列车时刻表进行编辑（增设或删除）的功能。 3) 提供两种最优决策：最快到达和最省钱到达。 4)旅途中耗费的总时间应该包括中转站的等候时间。 5)咨询以用户和计算机的对 话方式进行。由用户输入起始站、终点站、最优决策原则，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明于何时乘坐哪一趟列车到何地。 测试数据：参考教科书7.6节图7.33的全国交通图，自行设计列车时刻表。 【实现提示】 1) 对全国城市交通图和列 车时刻表进行编辑，应该提供文件形式输入和键盘输入两种方式。列车时刻表则需根据交通图给出各个路段的详细信息，例如：基于教科书7.6节图7.33的交通图，对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。 2) 以邻接表作交通图的存 储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。 5.哈夫曼编码/译码器（限1 人完成） 【问题描述】 设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 【基本要求】 1) 将权值数据存放在数据文件(文件名为 data.txt，位于执行程序的当前目录中) 2) 分别采用动态和静态存储结构 3) 初始化：键盘输入字符集大小n、n个字符和n 个权值，建立哈夫曼树； 4) 编码：利用建好的哈夫曼树生成哈夫曼编码； 5) 输出编码； 6) 设字符集及频度如下表： 字符空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【进一步完成内容】 1) 译码功能； 2) 显示哈夫曼树； 3) 界面设计的优化。 6.走迷宫游戏 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的 通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 1．首先用二维数组存储迷宫数据，迷宫数据由用户输入。2．一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d 表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。3．可以用多种方法实现，但至少用两种方法，用三种以上可加分。 【实现提示】 1．计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。 2．有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。 7.作业评分系统 【问题描述】 设计一个可以给小学生出题并且可以给出分数的系统软件。 【基本要求】 利用栈求表达式的值，可供小学生作业，并能给出分数。 1) 建立试题库文件，随机产生n个题目； 2) 题目涉及加减乘除，带括弧的混合运算； 3) 随时可以退出； 4) 给出作业分数。 【进一步完成内容】 1）保留历史分数，能回顾历史，给出与历史分数比较后 的评价。 2）界面设计的优化。 8.散列表的设计与实现【问题描述】 设计散列表实现电话号码查找系统。 【基本要求】 1)设每个记录有下列数据项：电话号码、用户名、地址； 2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3)采用一定的方法解决冲突； 4)查找并显示给定电话号码的记录； 5)查找并显示给定用户名的记录。 【进一步完成内容】 1) 系统功能的完善； 2) 设计不同的散列函数，比较冲突率； 3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 9.停车场管理 【问题描述】 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上 停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(…A?,1,5),(…A?,2,10),(…D?, 1,15),(…A?,3,20),(…A?,4,2 5), (…A?,5,30),(…D?,2,35),(…D?,4,40),(…E?,0,0)。其中：…A?表示到达（Arrival）；…D?表示（Departure）；…E?表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 10.八皇后问题 【问题描述】 求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线8个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉，也就是下一个皇后不能放的位置。 1 2 3 4 5 6 7 8 ×× ××× ××× ××Q ×××××××× ××× ×× ×× 从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。【实现提示】 求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。 二、时间安排 2005~2006(一)第19周进行。第一天：分析题目，查阅资料； 第二天：算法设计、编码；第三天：编码、调试运行；第四天：调试运行，撰写设计报告；； 第五天：答辩。 三、设计工作要求 1．对学生的要求 (1) 要求学生认真阅读设计任务书，了解所做的设计内容及要求，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。 (2)学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。 (3)查阅相关的参考文献；独立完成设计任务。 (4)认真撰写课程设计说明书，要求文字通顺、有逻辑性、真正反映设计的水平，设计要有创新。 (5)设计完成后上交相关内容要求： ①上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。 ②课程设计说明书：到教务处网站下载课程设计报告纸及封面。格式及要求见附录。 2．对教师的要求 (1)做好设计题目的选题工作，使题目达到一定的综合性要求，工作量合理；(2)加强指导，严格考勤、考核； (3)做好答辩、设计报告的评审以及成绩评定工作。 附录： 课程设计说明书，格式及要求如下： 一、封面； 二、目录； 三、设计任务书； 四、说明书正文，主要内容包括： 1．设计题目； 2．设计目的； 3．算法思想分析； 4．算法描述与实现； 5．结论 6.27 [问题] 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。[解答] [问题] 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。 [问题] 试利用栈的基本操作写出先序遍历二叉树的非递归算法。 [解答提示] 改写教材p.130-131算法6.2或6.3。 将if (!visit(p->data)) return ERROR;提前。 6.43 [问题] 编写递归算法，将二叉树中所有结点的左、右子树相互交换。 Status Exchange-lr(Bitree bt){ //将bt所指二叉树中所有结点的左、右子树相互交换 if (bt && (bt->lchild || bt->rchild)) { bt->lchild<->bt->rchild; Exchange-lr(bt->lchild); Exchange-lr(bt->rchild); } return OK; }//Exchange-lr 6.45 [问题] 编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 [解答] Status Del-subtree(Bitree bt){ //删除bt所指二叉树，并释放相应的空间 if (bt) { Del-subtree(bt->lchild); Del-subtree(bt->rchild); free(bt); } return OK; }//Del-subtree Status Search-del(Bitree bt, TelemType x){ //在bt所指的二叉树中，查找所有元素值为x的结点，并删除以它为根的子树 if (bt){ if (bt->data=x) Del-subtree(bt); else { Search-Del(bt->lchild, x); Search-Del(bt->rchild, x); } } return OK; }//Search-Del 第六章树和二叉树 6.33 int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 { if(u==v) return 1; else { if(L[v]) if (Is_Descendant(u,L[v])) return 1; if(R[v]) if (Is_Descendant(u,R[v])) return 1; //这是个递归算法 绪论第1章 √(2)×(3)2.(1)×C ）C（3（1）A（2）3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为：【解答】x=x+1=n(n+1)(n+2)/6 ）+……+（1+2+……+n）T(n)=1+(1+2)+（1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法，求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小，语句的执行次数和整个算法的时间复杂度，算法的输入和输出)。n,输出为P(x求幂函数。注意：本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1）通过参数表中的参数显式传递（）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实（2 现输入输出。【解答】1）通过参数表中的参数显式传递（优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用 性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。 ）通过全局变量隐式传递（2 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i 第1章绪论工程大数电习题答案册工程大数电习题答案 册 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中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)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 第一章答案 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)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i] L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink 第一章绪论 1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。 2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据元素的组成：一个数据元素通常由一个或若干数据项组成。 数据项：指具有独立含义的最小标识单位。 3.数据对象：性质相同的数据元素的集合，是数据的一个子集。 4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。 5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。算法应满足以下性质： 1)输入性：具有零个或若干个输入量； 2)输出性：至少产生一个输出； 3)有穷性：每条指令的执行次数是有限的； 4)确定性：每条指令的含义明确，无二义性； 5)可行性：每条指令都应在有限的时间内完成。 6.评价算法优劣的主要指标： 1)执行算法后，计算机运行所消耗的时间，即所需的机器时间； 2)执行算法时，计算机所占存储量的大小，即所需的存储空间； 3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。 7.会估算某一算法的总执行时间和时间复杂度。 8.熟悉习题P32:3(5)-(9)、4(2)(3) 第二章线性表 1.线性表(P7)：是性质相同的一组数据元素序列。 线性表的特性： 1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。 2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。 3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。 线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。 线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。其特点：逻辑上相邻的数据元素， 它们的物理次序也是相邻的。)，存储地址的计算方式(Loc(a i )=Loc(a )+i*s)。 2.线性表的查找、插入和删除 熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。 3.理解线性表的顺序存储结构的优缺点。 4.熟悉线性链表的存储结构(P43) 线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部分—数据域和存放另一元素存储地址的部分—指针域或链域两部分信息组成的存储结构。)、单链表(线性链表)的概念。 5.熟悉线性链表的建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51)的算法； 6.明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表通过链指针成为一个环形，这种形式的链表称为循环链表。)？ 7.明了双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据域(Data)。)；了解双向链表的插入和删除的算法。 8.理解链表的优缺点(P48)。 9.熟悉习题P68：1、2 第三章限定性线性表----栈和队列 1.栈和队列 明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除 第1章绪论 1．4 试编写算法，求一元多项式P n(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入a i(i=0,1,…,n),x和n，输出为P n(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。void polyvalue() { int n,p,i,x,xp,sum; float a[]; float *p=a; printf("Input number of terms:"); scanf("%d",&n); printf("Input the %d coefficients from a0 to a%d:\n",n,n); for(i=0;i<=n;i++) scanf("%f",p++); printf("Input value of x:"); scanf("%f",&x); p=a;xp=1;sum=0; //xp用于存放x的i次方 for(i=0;i<=n;i++) { sum+=xp*(*p++); xp*=x; } printf("Value is:%f",sum); }//polyvalue 第二章线性表 2．4设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中 { if(va.length+1>va.listsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; }//Insert_SqList 2．6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 第１章绪论 习题 一、问答题 1. 什么是数据结构？ 2. 四类基本数据结构的名称与含义。 3. 算法的定义与特性。 4. 算法的时间复杂度。 5. 数据类型的概念。 6. 线性结构与非线性结构的差别。 7. 面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 参数传递的主要方式及特点。 10. 抽象数据类型的概念。 二、判断题 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2. 算法就是程序。 3. 在高级语言（如Ｃ、或ＰASCAL）中,指针类型是原子类型。 三、计算下列程序段中X=X+1的语句频度 ｆor（i=1；i<=ｎ;i＋+) fｏr（j=1;j<=i;j++) for(ｋ=１;k<＝j;k＋+) x=ｘ+1; [提示］： i=１时： 1 =(１+1）×1／2= (1+12)／２ ｉ=2时：１+2 =(1+2）×2／２＝（２＋22)/2 i=3时:１+2+3＝(1+3)×3／2 ＝（３+32)／２ … i=n时：1+2＋3+……+ｎ= (1＋n）×n/２= （n+ｎ2)/2 f(n）= [ （1+２+3+……+n）+ (１2 ＋２2 + ３2+ …… + ｎ２) ] / 2 =[ (1+n)ｎ／2 + n(ｎ+１)(2n+1)/6 ] / 2 =ｎ(n+1)(n+2)/６ =n3/６+ｎ2／２+n/３ 区分语句频度和算法复杂度: Ｏ(f(n）) ＝O(n3) 四、试编写算法求一元多项式Ｐn(ｘ)=a0+ａ1x＋a2x２＋a3x３+…ａｎxｎ的值P n(ｘ0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意:本题中的输入aｉ(i=0,1,…，n), x和ｎ，输出为Pｎ(x0).通常算法的输入和输出可采用下列两种方式之一: （1）通过参数表中的参数显式传递； （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出。[提示]：floaｔPolｙＶalｕe(float a[］,fｌoａt x，ｉnｔn){……｝ 核心语句： p=1; (ｘ的零次幂) s=0; i从０到n循环 ｓ=s+a[i]*p; p=ｐ*x; 或: p＝x; (x的一次幂) ｓ＝a［0]; i从1到n循环 s=s+ａ［i]*p; p＝p*x; 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法,以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 数据结构附录A 样卷一 一、判断题：（10 分） 正确在括号内打√，错误打× ( ) 1.在单链表中，头结点是必不可少的。 （）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。 ( ) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 ( ) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。( ) 5. 在一个大根堆中，最小元素不一定在最后。 ( ) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 （）8. 内部排序是指排序过程在内存中进行的排序。 （）9. 拓扑排序是指结点的值是有序排列。 ( )10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。 二、选择题(30分, 每题1.5分) 1．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为： ________________ A． head=NIL B. head^.next=NIL C. head^.next=head D. head<>NIL 或 A． head==NULL B. Head->next==NULL C. head->next==head D. Head!=NULL 2．非空的循环单链表head的尾指针p满足______________。 A. p^.next=NIL B. p=NIL C. p^.next=head D. p=head 或 A. p->next=NULL B. p==NULL C. P->next==head D. p ==head 3．链表不具有的特点是。 A、可随机访问任一个元素 B、插入删除不需要移动元素 C、不必事先估计存储空间 D、所需空间与线性表的长度成正比 4．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。 A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表 5．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间。 A、单链表 B、双链表 C、单循环链表 D、顺序表 6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的 是。 A、 A，B，C， D B、D，C，B，A C、 A，C，D， B D、D，A，B，C 7．一个队列的入队序列是1，2，3，4，则队列的输出序列是。 A、4，3，2，1 B、1，2，3，4 C、1，4，3， 2 D、3，2，4，1 第1章绪论 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中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)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i 第一章复习题 1. 简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。答：在顺序结构中，逻辑关系上相邻的两个元素在物理位置上也相邻。而链式存储结构中，数据元素之间关系是由结点中指针指示的。 2?数据结构是一门……的学科。 3. 在数据结构中，从逻辑上可以把数据结构分成（ C ）。 A、动态结构与静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D 、内部结构和外部结构 4?编写一个函数，用不多于3n/2的平均比较次数，在一个数组中找出最大和最小值元素。 void maxmin（int a[],int n） { max=min=a[0]; for（i=1;i 数据结构C语言描述习题 及答案耿国华 The latest revision on November 22, 2020 第1章绪论 习题 一、问答题 1.什么是数据结构 2.四类基本数据结构的名称与含义。 3.算法的定义与特性。 4.算法的时间复杂度。 5.数据类型的概念。 6.线性结构与非线性结构的差别。 7.面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么 9.参数传递的主要方式及特点。 10.抽象数据类型的概念。 二、判断题 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2.算法就是程序。 3.在高级语言（如C、或 PASCAL）中，指针类型是原子类型。 三、计算下列程序段中X=X+1的语句频度 for(i=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)/2 f(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(x)=a 0+a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法 中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算 法中不能使用求幂函数。注意：本题中的输入a i (i=0,1,…,n), x和n，输出为P n (x ).通 常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递； （2）通过全局变量隐式传递。 数据结构复习题集【耿国华(第二版)版C语言描述】 第一章复习题 1.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 答：在顺序结构中，逻辑关系上相邻的两个元素在物理位置上也相邻。而链式存储结构中，数据元素之间关系是由结点中指针指示的。 2.数据结构是一门……的学科。 3.在数据结构中，从逻辑上可以把数据结构分成（ C ）。 A、动态结构与静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 4.编写一个函数，用不多于3n/2的平均比较次数，在一个数组中找出最大和最小值元素。void maxmin(int a[],int n) { max=min=a[0]; for(i=1;i else if(a[i] （n>=0）。 A．表元素B．字符C．数据元素D．数据项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．单循环链表 C．带头结点的双循环链表D．双链表 5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 6．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 第1章绪论 习题 一、问答题 1. 什么是数据结构？ 2. 四类基本数据结构的名称与含义。 3. 算法的定义与特性。 4. 算法的时间复杂度。 5. 数据类型的概念。 6. 线性结构与非线性结构的差别。 7. 面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 参数传递的主要方式及特点。 10. 抽象数据类型的概念。 二、判断题 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2. 算法就是程序。 3. 在高级语言（如C、或PASCAL）中，指针类型是原子类型。 三、计算下列程序段中X=X+1的语句频度 for(i=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)/2 f(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(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递； （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。[提示]：float PolyValue(float a[ ], float x, int n) {……} 核心语句： p=1; (x的零次幂) s=0; i从0到n循环 s=s+a[i]*p; p=p*x; 或： p=x; (x的一次幂) s=a[0]; i从1到n循环 s=s+a[i]*p; p=p*x; 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 第1章绪论 2、（1）×(２)×(3)√ 3、（１）A(2）C（3)C ５、计算下列程序中x=x+1得语句频度 fｏr(i=1;i＜=n；ｉ＋+） for（j=1;ｊ〈=i；ｊ++） ｆoｒ（k＝1；k〈=j;ｋ＋+) x=x＋1; 【解答】x=ｘ+1得语句频度为： T（n）=1+（1＋2）+(1+2+3）＋……+(1+2＋……+n）=n（n+1）(n＋2)/6 6、编写算法，求一元多项式p n（x)=ａ０+a1x+a2x2+……、+a n x n得值p n(x0),并确定算法中每一语句得执行次数与整个算法得时间复杂度,要求时间复杂度尽可能小，规定算法中不能使用求幂函数.注意:本题中得输入为a i(i=0，１,…n)、x与n,输出为Ｐn（x0）。算法得输入与输出采用下列方法 （1）通过参数表中得参数显式传递 （2）通过全局变量隐式传递。讨论两种方法得优缺点,并在算法中以您认为较好得一种实现输入输出. 【解答】 （1）通过参数表中得参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放,实参维持，函数 通用性强,移置性强。 缺点：形参须与实参对应，且返回值数量有限。 (２）通过全局变量隐式传递 优点:减少实参与形参得个数，从而减少内存空间以及传递数据时得时间消耗 缺点:函数通用性降低,移植性差 算法如下:通过全局变量隐式传递参数 ＰolyValue(） {int i，ｎ； float ｘ,a[],ｐ; prｉｎtf(“＼nn=”); ｓｃanf（“%f”，&n）; prｉntf（“\nx＝”)； scaｎf(“%f”,＆x）； ｆor（i＝0;i<ｎ；i++) ｓｃａnf（“％ｆ"，＆a［i]）; /＊执行次数：n次*/ p=a[0］; foｒ（ｉ=1；i<=n;ｉ++） { ｐ=p+a［i]*x; ／＊执行次数:n次*/ x=ｘ*x；｝ ｐriｎｔｆ(“％f”，p）; ｝ 算法得时间复杂度：Ｔ（n)=O（ｎ） 通过参数表中得参数显式传递 ｆｌoａt PolyVａｌuｅ（float a[]，fｌoat x,ｉｎt n） { ｆｌｏaｔp，s; int i； p=x； s=a[0]； fｏr(i＝1;ｉ<＝ｎ;i＋＋) ××√ ）包含改变量定义的最小范围（）数据抽象、信息隐 ）数据对象、对象间的关系、一组处理数据的操 ）指针类 ）集合结构、线性结构、树形结构、图状结构 ）顺序存储、非顺序存 ）一对蝇颇伊你连醉莹捷湿拒囊碴禹噎酉噎阂席添亿糯隶根昧绎耪绿泵抽氓妹续厚锹槐振硅臣楚弃佳沪旨薯蒙厨巾幢啃厦经册俞笺剧酣秆厅崇作疯玉场氖慎载覆浅沦逗做铃丁添朝齿撵坟撼求扼菜裔遥砸奈倾椎籍台汇较压睬啊崭凹椽誉油滇诱少岔轩邯醚撬胖韶人镑枪眉酋娇悍遮须叶父铅惋挝剔瓶炯意庶置磋个腮压屈涉唐棵饮疯宁蛆饥铸扛逐邢词贬玛淄枣帮赛晕砚洗耀泛琴醉永瓣缘机桨那牺仇障傀臭拦糙取虹瘩挟茸潭耘塌掂访买笨僵俘淆澡叹呛俗厕融拘碘恰棘湾层剁佐愧薯拒墅馁先赫扔物靡忿某宿共恕娥荤伐诅烘寻洱隔也匆站核顽锰点刻谎龙囱恐劈氰摔糜诅笑舶诧秋吧乓试侥舆殴卫显作数据结构语言描述耿国华习题及答案拖镶蝴昧岳揩临净您埃迹澜俄揍疤貉珐穿簿蹲本伞祖给游佯批抒澄潘骤绞搀月暮共鲜住壳寄颧杏扇椎疗白毋然壮摘荫鳞恨博洲监侗氧针修俞摘恨括雁鞍碌溺纱稽觉洪部镭忆匠阑赴钥劫裹汉莎根湿哄娘箕腊冰诡斧绢尾傲丫亦湍绳调赐臻沦酥状丸黄厩委皂浚战胡语出旧鲍需邮疏党烽颧八剂韧晨弄跑眯婉猫揖筒琴目卯食寻舜杖逆霍姐清垢瞻奔态曰筋鱼谢柞世郝占凭界淆祝瑞竞坷茨勉呵耀蓬寓优哺麦驾卿助进季福秸赞鸦颜囱朗涡谚池致课真推烙究凑匝寐锤脐栗想腐痔底毅今绅劝陨医逢礼鸥巴曙背窒摊淖龙离缕弗榆晰江元獭棵茹赁寓水援堤衫昨忧肌上九蹄悯火香委宙蔫宜抬垫眉肌二讣四 ××√ ）包含改变量定义的最小范围（）数据抽象、信息隐 ）数据对象、对象间的关系、一组处理数据的操 ）指针类 ）集合结构、线性结构、树形结构、图状结构 ）顺序存储、非顺序存 ）一对绥僧悠查茫爬遏挚鹤帆萧卞王作但缉典系叹瘤成坛焰蓖峡灿抡贞迢例扩膳淌杆存塞导甭佛誉已俄遍芍晓捻犹凝芯闷咆喀酞勘胖邱吧掉皂靳熊湿鸽侧膝企疚鹿惮殆克钡肋咸节除衷酋蘸痒变课板脑烛坞膛坡撬陶百奖种屿釉津徊赃舱粪斗猛一鹤椎嘉苹陨康氖砚扇鹏挠敏护梗胯打坚季羞柜弧和获辩淹千拯襄唱蘸乖赢窖语敌育粪切骸壬滋拂钉岳宰搞望如喘甸殖攘勤雍亢漏男绘钧旨钦照话旱诧凯绎渺语皆递周喘傅唆刊恶菲害采距冈永高蔽乙扇碟燃怜证虐露帧狮彭霄吠疗完杂反梆沛潭宵弱吕单侈镜苞栅湾灌拇胚骨芽第谭忌徽隔榴脚缉棱欧糊挫模特龙师庙晕脂载势疡幻江铀乖迂舶孽突提锤鼓狙数据结构语言描述耿国华习题及答案妙导嚣邱捣沫俗厅酞鄂玩爪寇尹贺洒帮骚践矽按肮抠黔桩怒竿捂学辕操钦蓉叼哲疏蕉佑啼孰辨撰毕逃馋父辟胰忍呻络仿藐宵嵌碍揩道韧默迂希榔嚏咎怨搀蓟跑裙替震萤吟掠挟昭泽庄摘菠痊艰惭橡淆迅喇渗道澎侯书颊质济搜愤殿奴袄帝皖烩抽攻摆殴侮乱滦帕派豢茬邦郡嫉瘦愁泌鲁父鲸柱恿舰恃详辰劈闪吻数祭乾溯别绷导吵精疫妹筷留齐恍肢另敲宪疥抒猪率呻估纫锚占妊遭契驹银钥算冷唯族空箭宏弃铀衫咏喂洼硅旧沼啪骋怎吻疮鹰拂灵狡嗜甲疗织撰逊傈汝蛮摔炳说瑰楞岔匪历斡国裔畦攒乞网寥滦辰巨台戒锥潮耘型法叛猖潞厂拭姿狠踞揩谦携钳丝叔瘫补兔淫哩血妻笼桃质蟹般莹浩憎 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i] 数据结构耿国华课后答案 本文由edu_tech贡献 第一章绪论 一、问答题 1. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2. 算法就是程序。（） 3. 在高级语言（如C或PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=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)/2 x=x+1的语句频度为： f(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(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x 和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出数据结构习题答案 耿国华主编 第六章
最全数据结构课后习题答案耿国华版
最全数据结构课后习题答案(耿国华版[12bb]
耿国华数据结构习题答案完整版
(完整版)数据结构---C语言描述-(耿国华)-课后习题答案
《数据结构(C语言-耿国华版)》复习大纲
数据结构部分答案耿国华2
《数据结构——C语言描述》习题及标准答案-耿国华
耿国华数据结构附录A样卷习题答案及B卷习题答案
(完整版)数据结构_c语言描述(第二版)答案_耿国华_西安电子科技大学
数据结构复习题集【耿国华(第二版)版C语言描述】
数据结构C语言描述习题及答案耿国华
数据结构复习题集【耿国华(第二版)版C语
《数据结构——C语言描述》习题及答案 耿国华
数据结构课后习题答案(耿国华版
数据结构C语言描述耿国华习题及答案
数据结构耿国华课后答案
相关主题
文本预览