人武学院《数据结构》课后习题答案及期末综合练习

第十章内部排序一、基本知识题答案1. 排序：将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。 内部排序：数据存储在内存中，并在内存中加以处理的排序方法叫内部排序。 堆：堆是一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点，此结点数据必须大于或等于其儿子结点数据。稳定排序：一种排序方法，若排序后具有相同关键字的记录仍维持原来的相对次序，则称之为稳定的，否则称为不稳定的。2. 回答下面问题 (1) 5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最好？为什么？ (2) 大多数排序算法都有哪两个基本操作？ 答：(1)采用堆排序最好。 因为以上几种算法中，快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。 (2)两个基本操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身。3. 3. 已知序列17，25，55，43，3，32，78，67，91，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。 答：采用冒泡排序法排序时的各趟结果如下：初始：17，25，55，43，3，32，78，67，91第1趟：17，25，43，3，32，55，67，78，91第2趟：17，25，3，32，43，55，67，78，91第3趟：17，3，25，32，43，55，67，78，91第4趟：3，17，25，32，43，55，67，78，91第5趟：3，17，25，32，43，55，67，78，91第5趟无元素交换，排序结束。 4. 已知序列491，77，572，16，996，101，863，258，689，325，请分别给出采用快速排序、堆排序和基数排序法对该序列作递增排序时每一趟的结果。答：采用快速排序法排序时的各趟结果如下：初始：491，77，572，16，996，101，863，258，689，325第1趟：325，77，258，16，101 491 863，996，689，572第2趟：101，77，258，16 325，491 863，996，689，572第3趟：16，77 101 258 325，491 863，996，689，572第4趟：16 77 101 258 325，491 863，996，689，572第5趟：16，77，101 258 325，491 863，996，689，572第6趟：16，77，101，258，325，491 863，996，689，572第7趟：16，77，101，258，325，491 572，689 863 996第8趟：16，77，101，258，325，491，572 689 863 996第9趟：16，77，101，258，325，491，572，689，863 996第10趟：16，77，101，258，325，491，572，689，863，996采用堆排序法排序时各趟的结果如下图所示：(a) 初始堆 (b) 建堆 (c) 交换996和77，输出996 (d) 筛选调整采用基数排序法排序时各趟的结果如下：初始：491，77，572，16，996，101，863，258，689，325第1趟（按个位排序）：491，101，572，863，352，16，996，77，258，689第2趟（按十位排序）：101，16，352，258，863，572，77，689，491，996第3趟（按百位排序）：16，77，101，258，352，491，572，689，863，9965. 已知序列86，94，138，62，41，54，18，32，请给出采用插入排序法对该序列作递增排序时，每一趟的结果。答：采用插入排序法排序时各趟的结果如下：初始：(86)，94，138，62，41，54，18，32第1趟：(86，94)，138，62，41，54，18，32第2趟：(86，94，138)，62，41，54，18，32第3趟：(62，86，94，138)，41，54，18，32第4趟：(41，62，86，94，138)，54，18，32第5趟：(41，54，62，86，94，138)，18，32第6趟：(18，41，54，62，86，94，138)，32第7趟：(18，32，41，54，62，86，94，138) 6. 已知序列27，35，11，9，18，30，3，23，35，20，请给出采用归并排序法对该序列作递增排序时的每一趟的结果。答：采用归并排序法排序时各趟的结果如下：初始：27，35，11，9，18，30，3，23，35，20第1趟：27，35 9，11 18，30 3，23 20，35第2趟：9，11，27，35 3，18，23，30 20，35第3趟：9，11，27，35 3，18，20，23，30，35第4趟：3，9，11，18，20，23，27，30，35，35 二、算法设计题答案1. 二、算法设计题1. 一个线性表中的元素为全部为正或者负整数，试设计一算法，在尽可能少的时间内重排该表，将正、负整数分开，使线性表中所有负整数在正整数前面。解：本题的算法思想是：设置两个变量分别指向表的首尾，它们分别向中间移动，指向表首的如果遇到正整数，指向表尾的如果遇到负整数则互相交换，然后继续移动直至两者相遇。实现本题功能的算法如下： void part(int array,int n) int i,j; i=1; j=n;while(i<j) while(i<j && arrayi<0) i+; while(i<j && arrayj>=0) j-; if(i<j) array0=arrayi; arrayi=arrayj; arrayj=array0; 2. 设计一个用单链表作存储结构的直接插入排序算法。解： 实现本题功能的算法如下： void insertsort(node *head) node *p,*q,*pre; pre=head; p=head->next; /*p指向待插入的元素*/ while(p!=NULL) q=head; if(p->key<q->key) /*插到表首*/ pre->next =p->next; p->next =head; head=p; else while(q->next!=p && q->next ->key<p->key) q=q->next;if(q->next =p) pre=p;p=p->next; else pre->next =p->next; p->next =q->next; q->next =p; p=pre->next; 3. 试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。）解：实现本题功能的算法如下： void dbubblesort(sqlist r,int n) int i,j,flag; flag=1; i=1; while(flag!=0) flag=0; for(j=i;j<n-i;j+) if(rj>rj+1)flag=1;r0=rj;rj=rj+1;rj+1=r0; for(j=n-i;j>i;j-) if(rj<rj-1) flag=1;r0=rj;rj=rj-1;rj-1=r0; i+; 4.设一个一维数组An中存储了n个互不相同的整数，且这些整数的值都在0到n-1之间，即A中存储了从0到n-1这n个整数。试编写一算法将A排序，结果存放在数组Bn中，要求算法的时间复杂性为O(n)。 解：实现本题功能的算法如下：void sort(int An,int Bn) int i; for(i=0;i<n;i+) BAi=Ai; 第九章一、基础知识题1.(1)查找：查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。 (2)树型查找：将原始数据表示成二叉排序树，树的每个结点对应一个记录，利用此二叉排序树进行类似于二分查找思想的数据查找，这种查找方法称为树型查找。 (3)平衡因子：二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子。 (4)散列函数：根据关键字求存储地址的函数称为散列函数。 (5)两个不同的关键字，其散列函数值相同，因而被映射到同一个表位置上的现象称为冲突。2. 设有序表为a,b,c,d,e,f,g，请分别画出对给定值f,g和h进行拆半查找的过程。答：查找f的过程如下：查找成功，找到k=f值查找g的过程如下：查找成功，找到k=g值 查找h的过程如下：3. 试述顺序查找法、二分查找法和分块查找法对被查找表中元素的要求，每种查找法对长度为n的表的等概率查找长度是多少答：顺序查找法：表中元素可以任意存放。查找成功的平均查找长度为(n+1)/2。 二分查找法：表中元素必须以关键字的值递增或递减地存放且只能以顺序表存放。查找成功的平均查找长度为log2(n+1)-1。 分块查找法：表中每块内的元素可以任意存放，但块与块之间必须按关键字的大小递增或递减地存放，即前一块内所有元素的关键字不能大（或小）于后一块内任意一个元素的关键字。若用顺序查找确定所在块，平均查找长度为1/2(n/s+s)+1；若用二分查找确定所在块，平均查找长度为log2(n/s+1)+s/2。4. 设散列表长m=14，哈希函数为H(k)=k mod 11，表中一共有8个元素15,27,50,73,49,61,37,60 ，试画出采用二次探测法处理冲突的散列表。答：采用二次探测法处理冲突的散列表如下：5. 线性表的关键字集合为113,12,180,138,92,67,94,134,252,6,70,323,60，共有13个元素，已知散列函数为：H（k）=k mod 13，采用链接表处理冲突，试设计这种链表结构。答：由题意，可得： H(113) = 113 % 13 =9 H(12) = 12 % 13 =12 H(180) = 180 % 13 =11 H(138) =138 % 13 =8 H(92) = 92 % 13 =1 H(67) = 67 % 13 =2H(94) = 94% 13 =3 H(134) = 134% 13 =4 H(252) = 252 % 13 =5 H(6) = 6% 13 =6 H(70) = 70 % 13 =5 H(323) = 323% 13 =11 H(60) = 60 % 13 =8链接表法的散列表如下图所示：6. 设关键字集合为27,49,79,5,37,1,56,65,83，散列函数为：H（k）=k mod 7，散列表长度m=10，起始地址为0，分别用线性探测和链接表法来解决冲突。试画出对应的散列表。 答：线性探测法的散列表如下图所示： 链接表法的散列表如下图所示：二、算法设计题1.从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找。解：实现本题功能的算法如下，如果查找成功，则返回指向关键字为x的结点的指针，否则返回NULL。 node *sqsearch(node *head,int x) node *p=head; while(p!=NULL) if(x>p->key) p=p->link; else if(x=p->key) return p; else p=NULL; return p; 虽然链表中的结点是按递增顺序排列的，但是其存储结构为单链表，查找结点时只能从头指针开始逐步进行搜索，所以不能用折半查找。2.如果线性表中各结点查找概率不等，则可以使用下面的策略提高顺序表的查找效率：如果找到指定的结点，则将该结点和其前趋（若存在）结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法（注意查找时必须从表头开始向后扫描）。 解：采用顺序存储结构的算法如下，设记录存储在线性表的1n单元中。如果查找成功，返回关键字为k的记录在线性表中的位置，如果失败则返回0。 int seqsearch(sqlist r,int n,int k) int i,j; i=1; while(ri.key!=k) && (i<=n) i+; if(i<=n) r0=ri; ri=ri-1; ri-1=ri; i-; return(i);else return(0); 采用链式存储结构的算法如下。如果查找成功，则返回指向关键字为k的结点的指针，否则返回NULL。 node *seqsearch(node *head,int k) if(head->key=k) return(head); else node *p,*q; int x;p=head; q=head->link; while(q!=NULL && q->key!=k) p=q; q=q->link; if(q!=NULL) x=p->key; p->key=q->key; q->key=x; q=p; return(q); 3. 试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。解：本题的算法思想是：首先计算要删除的关键字为k的记录所在的位置，将其置为空（即删除），然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录，如果有则将记录移到原来k所在的位置，直至表中没有与k冲突的记录为止。实现本题功能的算法如下： void delete(sqlist r,int n,int k) int h,h0,h1; h=k%n; while(rh.key!=k) h=(h+1)%n; rh=NULL;h0=h;h1=(h+1)%n;while(h1!=h) while(rh1.key%n!=h) h1=(h1+1)%n; rh0=rh1; rh1=NULL; h0=h1; h1=(h1+1)%n; 4. 设给定的散列表存储空间为H1m，每个单元可存放一个记录，Hi(1im)的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突方法为线性探测法，编写一个函数将某记录R填入到散列表H中。解：本题的算法思想：先计算地址H(R.key)，如果没有冲突，则直接填入；否则利用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实现本题功能的函数如下： void insert(record H,int m,record R) int i; i=H(R.key); if(Hi=NULL) Hi=R; else while(Hi!=NULL) i=(i+1)%(m+1); Hi=R; 第七章一、基本知识题1. 图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？ 答：图是比树更为复杂的一种非线性数据结构，在图结构中，每个结点都可以和其它任何结点相连接。 无向图：对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。 有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。 子图：设有两个图G =(V,E)和G=(V,E)，若V(G)是V(G)的子集，且E(G)是E(G)的子集，则称G是G的子图(Subgraph)。网络：有些图，对应每条边有一相应的数值，这个数值叫做该边的权。边上带权的图称为带权图，也称为网络。2. 什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图的连通分量？答：顶点的度：图中与每个顶点相连的边数，叫该顶点的度。 在一个图中，若从某顶点Vp出发，沿一些边经过顶点V1,V2,Vm到达，Vq，则称顶点序列(Vp, V1,V2,Vm, Vq)为从Vp到Vq的路径。 在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。 非连通图的连通分量：非连通图的每一个连通的部分叫连通分量。3. 给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。答：图G所对应的邻接矩阵如下： 图G所对应的邻接表如下：图254. 假设图的顶点是A、B请根据下面的邻接矩阵画出相应的无向图或有向图。 答：(a)所对应的无向图如下图(a)所示，(b)所对应的有向图如下图(b)所示： 5.5. 分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。图26 答：深度优先搜索得到的顶点访问序列：0、1、3、7、8、4、9、5、6、2； 广度优先搜索得到的顶点访问序列：0、1、2、3、4、5、6、7、8、9。6. 应用prim算法求图6.27所示带权连通图的最小生成树。答：该图的最小生成树如下：图277. 写出图6.28所示有向图的拓朴排序序列答：该有向图的拓朴排序序列为：3、1、4、5、2、6。二、算法设计题图28二、算法设计题答案1. 如图6.29所示图G，试给出其对应的邻接表，并写出深度优先算法。解：该图对应的邻接表如下：深度优先算法：void dfsgraph(adjlist adj, int n) /*深度优先遍历整个图*/ int i; for(i=1;i<=n;i+) visitedi=0; for(i=1;i<=n;i+) if(!visitedi) dfs(adj,i);void dfs(adjlist adj,int v) /*以v为出发点，对图进行dfs遍历*/ struct edgenode *p; visitedv=1; printf("%d",v); p=adjvlink; while(p!=NULL) if(visitedpadjvex=0) dfs(adjlist,padjvex); p=pnext; 2. 如图6.29所示图G，试给出其对应的邻接矩阵，并写出广度优先算法。解：该图对应的邻接矩阵如下：广度优先算法：void bfsgraph(int adjarraynn,int n) /*广度优先遍历整个图*/ int i; for(i=0;i<n;i+) visitedi=0; for(i=0;i<n;i+)图29 if(!visitedi)bfs(adjarray,i); void bfs(int adjarray,int v) /*以v为出发点，对图进行bfs遍历*/ int i,j; queue q; printf("%d",v); visitedv=1; enqueue(&q,v); while(!queueemty(&q) i=dequeue(&q);for(j=0;j<n;j+) if(adjarrayij=1 && !visitedj) printf("%d",j); visitedj=1; enqueue(&q,j); 3. 编写一个函数通过与用户交互建立一个有向图的邻接表。解：实现本题功能的算法如下： void creategraph(adjlist g) int e,i,s,d,n; struct edgenode *p ; printf("请输入结点数(n)和边数(e):n"); scanf("%d,%d",&n,&e); for(i=1;i<=n;i+) printf("n请输入第%d个顶点信息：",i); scanf("%c",&gi.data);gi.link=NULL; for(i=1;i<=e;i+) printf("n请输入第%d条边起点序号，终点序号：",i); scanf("%d,%d",&s,&d); p=(struct edgenode *)malloc(sizeof(edgenode); padjvex=d; pnext=gs.link; gs.link=p;4. 编写一个无向图的邻接矩阵转换成邻接表的算法。解：本题的算法思想是：逐个扫描邻接矩阵的各个元素，如第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。实现本题功能的算法如下： void transform(int adjarraynn,adjlist adj) int i,j; edgenode *p; for(i=0;i<n;i+) adji.data=i;adji.link=NULL; for(i=0;i<n;i+) for(j=0;j<n;j+) if(adjarrayij=1) p=(edgenode *)malloc(sizeof(edgenode); padjvex=j; pnext=adji.link; adji.link=p; 5.已知一个有n个顶点的有向图的邻接表，设计算法分别实现1) 求出图中每个顶点的出度。2) 求出图中每个顶点的入度。3) 求出图中出度最大的一个顶点，输出其顶点序号。4) 计算图中出度为0的顶点个数。解：(1) 本题的算法思想是：计算出邻接表中第i个单链表的结点数，即为i顶点的出度。求顶点的出度数的算法如下： int outdegree(adjlist adj,int v) int degree=0; edgenode *p; p=adjv.link; while(p!=NULL) degree+; p=p->next; return degree; void printout(adjlist adj,int n) int i,degree; printf("The outdegrees are:n"); for(i=0;i<n;i+) degree=outdegree(adj,i); printf("(%d,%d)",i,degree); (2)本题的算法思想是：计算出整个邻接表中所具有的结点为i的结点数，这就是i顶点的入度。求顶点的入度数的算法：int indegree(adjlist adj,int n,int v) int i,j,degree; edgenode *p; for(i=0;i<n;i+) p=adji.link; while(p!=NULL) if(p->adjvex=v)degree+; p=p->next; return degree; void printin(adjlist adj,int n) int i,degree; printf("The indegrees are:n"); for(i=0;i<n;i+) degree=indegree(adj,n,i); printf("(%d,%d)",i,degree); (3)求最大出度的算法：void maxoutdegree(adjlist adj,int n)int maxdegree=0,maxv=0, degree, i;for(i=0;i<n;i+) degree=outdegree(adj,i);if(degree>maxdegree) maxdegree=degree; maxv=i; printf("maxoutdegree = %d, maxvertex = %d",maxdegree,maxv);(4)求出度数为0的顶点数的算法： int outzero(adjlist adj,int n)int num=0,i;for(i=0;i<n;i+) if(outdegree(adj,i)=0) num+;return num;第六章一、基础知识题1. 就如图5.21所示的树回答下面问题： 1）哪个是根结点？ 2）哪些是叶子结点？ 3）哪个是E的父结点？ 4）哪些是E的子孙结点？ 5）哪些是E的兄弟结点？哪些是C的兄弟结点？ 6）结点B和结点I的层数分别是多少？ 7）树的深度是多少？ 8）以结点G为根的子树的深度是多少？ 9）树的度是多少？答：1）A是根结点2）D、H、I、J、F、G是叶子结点3）B是E的父结点4）H、I、J是E的子孙结点5）D是E的兄弟结点，B是C的兄弟结点6）B的层数是2，I的层数是47）树的深度是48）以结点G为根的子树的深度是19）树的度是3 2.分别画出含3个结点的树与二叉树的所有不同形态。答：3个结点的树：3个结点的二叉树：3. 高度为h的完全二叉树至少有多少个结点？最多有多少个结点？答：高度为h的完全二叉树至少有个结点，最多有个结点。4. 采用顺序存储方法和链式存储方法分别画出图5.22所示二叉树的存储结构。答：该二叉树的顺序存储：该二叉树的链式存储：5. 分别写出图5.22所示二叉树的前序、中序和后序遍历序列。图22答：先序遍历序列：1、2、4、7、3、5、8、6、9中序遍历序列：7、4、2、1、8、5、3、6、9后序遍历序列：7、4、2、8、5、9、6、3、1 6.若二叉树中各结点值均不相同。 1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA，请画出此二叉树。 2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG，请画出此二叉树。答：7. 一个二叉树如图5.23所示,分别写出其前序、中序、后序的遍历序列。答：先序遍历序列：A、B、D、E、F、C、G中序遍历序列：D、F、E、B、A、G、C后序遍历序列：F、E、D、B、G、C、A 8.输入一个正整数序列55,34,18,88,119,11,76,9,97,99,46，试构造一个二叉排序树。9. 有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为5、2、1、6、4。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。第8题各字符对应的哈夫曼编码如下： a: 10, b: 001, c: 000, d: 11, e: 01二、算法设计题答案 1.一个二叉树以链式结构存储，分别给出求二叉树结点总数和叶子结点总数的算法。解：求二叉树结点总数的算法如下： int CountNode(btree *t,int num) /*num初值为0*/ if(t!=NULL) num+; num=CountNode(t->left,num); num=CountNode(t->right,num); return num;求二叉树叶子结点总数的算法如下：int CountLeaf(btree *t,int num) /*num初值为0*/ if(t!=NULL) if(t->left=NULL && t->right=NULL) num+; num=CountLeaf(t->left,num); num=CountLeaf(t->right,num); return num;2. 2. 一个二叉树以链式结构存储，写出在二叉树中查找值为x的结点的算法。解：本题可以用先序、中序和后序遍历中的任意一种遍历，只要将遍历算法中的访问根结点改为判断其值是否等于x。下面是用中序遍历求解的算法，函数返回值为x的结点的地址，若没有找到则返回空。 btree *search(btree *t,int x,btree p) /*p的初值为NULL*/ if(t!=NULL) p=search(t->left,x,p); if(t->data=x)p=t; /*找到x的地址放在p中*/ p=search(t->right,x,p); return p;3. 设计一个算法将一个以链式存储结构的二叉树，按顺序方式存储到一维数组中。解：这是一个递归算法，如下： void create(btree *t,int tree,int i) if(t!=NULL) treei=t->data; create(t->left,tree,2*i); create(t->right,tree,2*i+1); 4. 假设二叉排序树t的各元素值均不相同，设计一个算法按递增次序打印各元素值。解：按中序序列遍历二叉排序树即按递增次序遍历，所以递增打印二叉排序树各元素值的函数如下： void inorder(btree *t) if(t!=NULL) inorder(t->left); printf("%d",t->data); inorder(t->right); 5. 已知一个中序线索二叉树，试编写中序遍历的非递归算法。解：在中序线索二叉树中进行非递归中序遍历，只要从头结点出发，反复找到结点的后继，直至结束即可。在中序线索二叉树中求结点后继的算法如下： tbtree *succ(tbtree *p) btree *q; if(p->rtag=1) return (p->right);else q=p->right; while(q->ltag=0) q=q->left; return(q);由此得到中序遍历线索二叉树的非递归算法如下： void thinorder(tbtree *p) if(p!=NULL) while(p->ltag=0) p=p->left; do printf("%d",p->data); p=succ(p); while(p!=NULL);第五章A1020采用列为主序存储,每个元素占1个单元,A00的地址为200,则A612的地址是多少? 3262. 稀疏矩阵m×n采用三元组顺序表存储结构,非零元个数tu满足什么条件时,该存储结构才有意义?tu<m*n/33. 二维数组A10.205.10采用行为主序存储,每个元素占4个单元,A105的地址为1000,则A189的地址是多少?(1208)4. 稀疏矩阵的三元组顺序表存储结构是随机存储结构吗?为什么?(不是)5. 广义表(a,b,c,d)的表头和表尾分别是什么?（(a,b,c,d);空表）6. 广义表(a),(b),c),(d)的长度和深度分别是多少? （3，4）第一章数据物理结构 算法 二、简答 一、名词解释数据：就是一切能够由计算机接受和处理的对象。数据项：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理，也称为元素、顶点或记录。它可以由若干个数据项组成。数据结构：指的是数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。数据逻辑结构：是指数据元素之间的逻辑关系，是从逻辑上描述数据，与数据的存储无关，独立于计算机。数据物理结构：是指数据元素及其关系在计算机存储器内的表示，是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。算法：是对特定问题求解步骤的一种描述。它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。算法的时间复杂性：是该算法的时间耗费，它是该算法所求解问题规模n的函数。当n趋向无穷大时，我们把时间复杂性T(n)的数量级称为算法的渐进时间复杂性。二、简答题1. 算法分析的目的是什么？ 答：对算法进行分析的目的有两个：第一个目的是可以从解决同一问题的不同算法中区分相对优劣，选出较为适用的一种；第二个目的是有助于设计人员考虑对现有算法进行改进或设计出新的算法。2. 什么是算法的最坏和平均时间复杂性？ 答：算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间；平均时间复杂性是研究同样的n值时各种可能的输入，取它们运算时间的平均值。三、答案1三、分析下列算法的时间复杂性: 1sum=0; for (i=1;i<=n;i+) sum=sum+i; 答：该程序段的时间复杂性为T(n)=O(n)。22i=1; while(i<=n) i=i*10; 1*10 for(j=0;j<n;j+) 答：该程序段的时间复杂性T(n)=O(log10n)。33sum=0; for(i=0;i<n;i+) sum=sum+Arrayij; 答：该程序段的时间复杂性(n)=O(n2)。第二章一、基础知识题一、基本知识题答案1 1. 试比较顺序表与链表的优缺点。的操作。 答：顺序表用结点物理位置的相邻性来反映结点间的逻辑关系，其优点是：节省存储、随机存取，当表长变化较小，主要操作是进行查找时，宜采用顺序表。链表用附加的指针来反映结点间的逻辑关系，插入和删除操作相对比较方便，当表长变化较大，主要操作是进行插入和删除时，宜采用链表。2. 2. 试分析单链表与双链表的优缺点。 答：双链表比单链表多增加了一个指针域以指向结点的直接前趋，它是一种对称结构，因此在已知某个结点之前或之后插入一个新结点、删除该结点或其直接后继都同样方便,操作的时间复杂度为O(1)；而单链表是单向结构，对于找一个结点的直接前趋的操作要从开始结点找起，其时间复杂度为O(n)。3. 3. 为什么在单循环链表中设置尾指针比设置头指针更好？ 答：由于对表的操作常常在表的两端进行，所以对单循环链表，当知道尾指针rear后，其另一端的头指针是rear->next->next（表中带头结点）。这会使操作变的更加容易。 4. 4. 写出在循环双链表中的p所指结点之后插入一个s所指结点答： s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 5.5. 写出在单链表中的p所指结点之前插入一个s所指结点的操作。 答： s->next=p->next; p->next=s; temp=p->data; p->data=s->data; s->data=temp; 6. 6. 请利用链表来表示下面一元多项式 A(x)=4*x11+9*x8+11*x3+8*x+7答：多项式A(x)用链表表示如下：head_A->4,11->9,8-.11,3->8,1->7,0二、算法设计题答案1. 1. 有一个有n个结点的单链表，设计一个函数将第i-1个结点与第i个结点互换，但指针不变。解：本题的算法思想是：要使结点互换而指针不变，只要将两个结点的数据进行交换即可。实现本题功能的函数如下： void exchange(node *head,int i,n) node *p,*q; int data; if(i>n) printf("error!n"); else p=head; for(int j=1;j<i;j+) p=p->next; q=p->next; data=q->data; q->data=p->data; p->data=data; 2. 2. 设计一个函数，查找单链表中数值为x的结点。 解：实现本题功能的函数如下： void search(node *head,int x) node *p; p=head; while(p->data!=x && p!=NULL) p=p->next; if(p!=NULL) printf("结点找到了！n"); else printf("结点未找到！n"); 3. . 已知一个单链表，编写一个删除其值为x的结点的前趋结点的算法。解：本题的算法思想是：先找到值为x的结点*p和它的前趋结点*q，要删除*q，只需把*p的值x放到*q的值域中，再删除结点*p即可。实现本题功能的函数如下： void delete(node *head,int x) node *p,*q; q=head; p=head->next; while(p!=NULL) && (p->data!=x) q=p; p=p->next; if(p=NULL) printf("未找到x！n"); else if(q=head) printf("x为第一个结点，无前趋！n"); else q->data=x; q->next=p->