还剩23页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
习题
2.1 什么是数据结构?它对算法有什么影响? 答数据结构是指同一数据对象中各数据元素间存在的关系 数据结构对算法的影响算法的实现必须借助程序设计语言中提供的数据类型及其运算一个算法的效率往往与数据的表达形式有关,因此数据结构的选择对数据处理的效率起着至关重要的作用它是算法和程序设计的基本部分,它对程序的质量影响很大 习题
2.2 何谓算法?它与程序有何区别? 答广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”计算机算法是通过计算机能执行的算法语言来表达的 和程序的区别一个程序包括两个方面的内容
(1)对数据的描述,即数据结构
(2)对操作的描述,即算法 所以算法是程序的一个要素 习题
2.3 何谓频度,时间复杂度,空间复杂度?说明其含义 答频度在某个算法中某个语句被重复执行的次数就是此语句的频度 时间复杂度是用来估算一个算法的执行时间的量,以算法中频度最大的语句来度量 空间复杂度指在算法中所需的辅助空间的单元,而不包括问题的原始数据占用的空间习题
2.4算法 A=a0 a1 ……an mul = 1 // sum=a0 for i=1 to n mul = mul * x sum = A[i]*mul + sum //求和 endi 程序代码#includestdio.h#includestdlib.h#defineN10doublepolynomailinta[]intidoublexintn;intmain{doublex;intni;inta[N];printf输入变量的值x:;cinx;cout输入多项式的阶次n:;cinn;ifnN-1exit0;cout输入多项式的系数a
[0]--a[n]:;fori=0;i=n;i++cina[i];coutThepolynomailvalueispolynomailanxnendl;return0;}doublepolynomailinta[]intidoublexintn{ifi0returna[n-i]+polynomailai-1xn*x;elsereturna[n];}本算法的时间复杂度为On习题
2.9boolIsSubSequenceStringa[]intnStringb[]intm{inti=0;intj=0;whilein{ifa[i]==b[j]/**相等时,下标同时向后移动一个位置.*/{i++;j++;}else{j++;/**不等时只将b[]数组下标向后移动一个位置.*/ifj==m/**当b[]数组找完时,指向了第m+1个不存在的元素,则不符合*/returnfalse;//a[]不是b[]的子序列}}returntrue;//a[]是b[]的子序列}上机需要定义main函数别偷懒哦`习题
2.10voidmgslintninta[]intmintb[]intc[]{intk=0i=0j=0;whileinjm{ifa[i]=b[j]//复制有序表a中的元素{c[k]=a[i];i=i+1;}else{c[k]=b[j];j=j+1;}k=k+1;}ifi==n//复制有序表b中剩余元素fori=j;im;i++{c[k]=b[i];k=k+1;}else//复制有序表a中剩余元素forj=i;jn;j++{c[k]=a[j];k=k+1;}return;}习题
2.11voidinvslintninta[]{intk;intt;fork=1;k=n/2;k++{t=a[k-1];a[k-1]=a[n-k];a[n-k]=t;}return;}intmain{inta
[10]={12….};invsl10a;forinti=0;i10;i++printf“%d”a[i];return0;}习题
2.12intListLength_LLinkListL{inti=0;LinkListp=L;ifpp=p-next;whilep{p=p-next;i++;}returni;}习题
2.13intDeleteElem_LLinkListLintxintk{inti=1;LinkListp=L;whilepi!=k-1{p=p-next;i++;}p=p-next-next;}习题
2.14设待插入的结点值为x,则至少需要考虑下面三种情况
1.prev-val≤x≤current-val: 插入到prev和current之间
2.x是链表中最小或者最大的值 插入x到链表头部的前面
3.回到起始点 插入到起始点前面第1和2种情况还比较容易考虑到,但是第3种情况往往会被忽略,先给出代码,再根据代码来分析这些情况为什么都需要考虑到
1.void insertNode * aNode int x {
2. //链表为空,创建节点返回
3. if !aNode {
4. aNode = new Nodex;
5. aNode-next = aNode;
6. return;
7. }
8.
9. Node *p = aNode;
10. Node *prev = NULL;
11. do {
12. prev = p;
13. p = p-next;
14. if x = p-data x = prev-data break; // 情况1,找到正常位置返回,如例子中插入4到链表中
15. if prev-data p-data x p-data || x prev-data break; // 情况2,x最小或者最大,插入到链表最前面
16. } while p != aNode; // 情况3,回到起始结点,停止.
17.
18. Node *newNode = newNodex;
19. newNode-next = p;
20. prev-next = newNode;
21.} 1)链表只有一个结点 如果x等于该结点值,则直接在情况1处理否则情况3处理2)链表包含重复值 如果链表为1-*1-1,起始结点为第二个1,则在其中插入2时,由情况3处理,即最终插入到初始结点前面会变成1-2-1-
1.循环链表从第二个1开始,照样是有序的习题
2.15//将合并后的结果放在C表中,并删除B表StatusListMerge_LLinkListALinkListBLinkListC{LinkListpapbqaqb;pa=A-next;pb=B-next;C=A;whilepapb{qa=pa;qb=pb;pa=pa-next;pb=pb-next;qb-next=qa-next;qa-next=qb;}if!paqb-next=pb;pb=B;freepb;returnOK;}习题
2.18//在单循环链表S中删除S的前驱结点StatusListDelete_CLLinkListS{LinkListpq;ifS==S-nextreturnERROR;q=S;p=S-next;whilep-next!=S{q=p;p=p-next;}q-next=p-next;freep;returnOK;}习题
2.19//带头结点的单链表的逆置StatusListOppose_LLinkListL{LinkListpq;p=L;p=p-next;L-next=NULL;whilep{q=p;p=p-next;q-next=L-next;L-next=q;}returnOK;}习题
2.21 有一铁路交换站如题图(栈),火车从右边开进交换站,然后再开到左边,每节车厢均有编号如1,2,3,…,n请问
(1)当n=3和n=4时有哪几种排序方式?哪几种排序方式不可能发生?
(2)当n=6时,325641这样的排列是否能发生?154623的排列是否能发生?解 N=3时可能的出栈序列 123 1S1X2S2X3S3X 132 1S1X2S3S3X2X 213 1S2S2X1X3S3X 231 1S2S2X3S3X1X 312 CAB 321 1S2S3S3X2X1X N=4,不可能的排列 4312 4213 4231 4123 41323124 3142 3412 1423 2413 N=6时,325641可能 154623不可能习题
2.24双向栈(a[]mtop1top2x){top1=m;top2=1;iftop1==top2then{printf“上溢”returnERROR}whiletop1!=top2{ifx%2==0{a[top2]=x;top2++;}else{a[top1]=x;top1--;}}}习题
2.26用三元组和带行辅助向量形式表示下列稀疏矩阵
(1)
(2)
(1)三元组带行辅助向量行列值1115142216-15221123334-6519163282:三元组带行辅助向量i123456POS146778NUM321011行列值11815-131926211524628532-334436344248453-1262274481791129429669930i123456789POS147101213141516NUM333211114习题
2.27试说明树与二叉树有何不同?为何要将一般树转换为二叉树?解树与二叉树区别树是由n个(n=0)结点组成的有限集合T,其中有且仅有一个结点称为根结点,在此类元素结点之间存在明显的分支和层次关系二叉树是一种特殊的树结构,每一个结点最多只有两个孩子,即最多只有两个分支为何要转换一般树,树中结点次序没有要求,分支庞杂而二叉树,元素之间存在严谨的前后代关系,在对数据元素进行删除、查找、插入等运算时更加有效率习题
2.28习题
2.29解在一般的二叉树中,叶子结点总是比度为2的结点多1个而在完全二叉树中,度为1的结点最多有1个综合以上两点,如果完全二叉树的结点数为奇数,设为2n+1则没有度为1的结点,在所有结点中有n个是度为2的结点,n+1个是叶子结点;如果完全二叉树的结点数为偶数,设为2n则其中有1个是度为1的结点,剩下的结点中有n-1个是度为2的结点,n个是叶子结点本题中,如果完全二叉树公有1000个结点,则有500个叶子结点,499个度为2的结点,有1个度为1的结点习题
2.30设一棵二叉树其中序和后序遍历为中序BDCEAFHG后序DECBHGFA画出这棵二叉树的逻辑结构,并写出先序遍历结果先序遍历ABCDEFGH其逻辑结构如下习题
2.311//复制一棵二叉树StatusCopyBiTreeBiTreeTBiTreeT1{BiTreep;ifT{p=newBiTNode;if!preturnERROR;p-data=T-data;T1=p;CopyBiTreeT-lchildT1-lchild;CopyBiTreeT-rchildT1-rchild;}else{T1=T;}returnOK;}2//判断两棵二叉树是否相等/*T1T2分别指向两个二叉树的根结点.若T1与T2相等则返回1;否则返回0*/intBiTreeEqualBiTreeT1BiTreeT2{ ifT1==NULLT2==NULLreturn1; ifT1!=NULLT2!=NULLT1-data==T2-dataBiTreeEqualT1-leftChildT2-leftChildBiTreeEqualT1-rightChildT2-rightChildreturn1; return0;}3//计算二叉树的树叶StatusPOLeafNodeNumintiBiTreeT{ifT{if!T-lchild!T-rchildi++;POLeafNodeNumiT-lchild;POLeafNodeNumiT-rchild;}returnOK;}4//求二叉树的深度intBiTDepthBiTreeT{intldeprdep;if!Treturn0;else{ldep=BiTDepthT-lchild+1;rdep=BiTDepthT-rchild+1;returnldeprdepldep:rdep;}}补充//按先序交换二叉树的左右子树StatusExchangeBiTreeBiTreeT{BiTreep;ifT{p=T-lchild;T-lchild=T-rchild;T-rchild=p;ExchangeBiTreeT-lchild;ExchangeBiTreeT-rchild;}returnOK;}习题
2.32DEFIJKGLABCABFCDEGH177777407777217777837777947777157777277777547777367777307777287777。