数据结构复习(1-7,10)最新完结版

《数据结构复习(1-7,10)最新完结版》由会员分享，可在线阅读，更多相关《数据结构复习(1-7,10)最新完结版（8页珍藏版）》请在装配图网上搜索。

1、第一章1.1概念数据（data）：是对客观事务的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机处理的符号总称数据元素（data element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象（dataobject）：是性质相同的数据元素集合，是数据的一个子集。数据结构（data structure）：是相互之间存在一种或多种特定关系的数据元素的集合存储结构：在计算机中表示数据元素和关系的数据结构（又称映象）。顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。链接存储，结点间的逻辑关系由附加指针字段表示。索引存储，存储结点信息的同时，建立附加索引表，

2、有稠密索引和稀疏索引。散列存储，按结点的关键字直接计算出存储地址。数据类型:是一个值的集合和定义在这个值集上的一组操作的总称。分为：原子类型和结构类型抽象数据类型：ADT,是指一个数学模型以及定义在该模型上的一组操作。1.16试写一算法，从大到小依次输出顺序读入的三个整数，X,Y,Z. Void descsort() Scanf(x,y,z); If(xy) temp =x;x=y;y=temp;If(y=temp) y= temp; Else y=x;x=temp;Printf(x,y,z);/descsort第二章：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点

3、。则： a.在P结点后插入s的语句序列是：4,1 b.在p前插入s的语句序列是：7,11,8,4,1 c.在表首插入s的语句序列是：5,12 d.在表尾插入s的语句序列是：6,11,9,11.p-next=s;2.p-next=p-next-next;3.p-next= s-next;4.s-next=p-next;5.s-next=L;6.s-next=NULL;7.Q=P;8.while(p-next != Q) P=P-next;9.while(p-next != NULL) P=P-next;10.P=Q; 11.P=L;12.L=S;13L=P;2.7 已知L是带表头的非空单链表，且

4、P结点既不是首元结点，也不是尾元结点，则：a.删除p结点的直接后继结点的语句序列：11,3,4b.删除p结点的直接前驱结点的语句序列：10,12,8,11,4,14c.删除p结点的语句序列:10,12,7,3,14d.删除首元结点的语句序列是：12,11,4,14e.删除尾元结点的语句是：9,11,3,141.p=p-next;2.p-=p;3.p-next=p-next-next;4.p=p-next-next;5.while(p!=NULL) p=p-next;6.while(Q-next != NULL) p=Q;Q=Q-next;7.while(p-next != Q) p=-next

5、;8.while(p-next-next != Q) p=p-next;9.while(p-next-next!= NULL) p=p-next;10.Q=P;11.Q=P-next;12.P=L;13.L=L-next;14.free(Q);2.4一元多项式的表示及相加：一个一元多项式可按升幂写成： 在计算机里表示一个线性表p来表示：P=()抽象数据类型一元多项式定义：ADT Polynomial数据对象: D=TermSet中的每一个元素包含一个表示系数的实数和表示指数的整数 数据关系：R1=|D 且中的指数值Pi =S3 则出栈先后顺序：po = S3,S2,S1,H3,H2,H1Pi

6、=S2 即调度后车厢顺序：S3,S2,S1,H3,H2,H1Pi =S1Pi =H3Pi =H2栈底-Pi =H1假设6节车厢以 H1,S1,H2,S2,H3,S3排队进站调度，使得出站最后形成软席车厢排在硬席车厢前，则操作如下：Pi=H1Pi=S1Po=S1Pi =H2Pi=S2Po=S2Pi =H3Pi=S3Po =S3Po=H3Po=H2Po=H1即：调度完成后车厢顺序：S1,S2,S3,H3,H2,H1第四章 串4.3 设s=I AM A STUDENT t=GOOD, q=WORKER.求：StrLength(s),StrLength(t),SubString(s,8,7), Sub

7、String(t,2,1),Index (s,A), Index(s,t),Replace(s,STUDENT,q),Concat(SubString(s,6,2),Concat(t,SubString(s,7,8).StrLength(s) = 14, StrLength(t)=4, SubString(s,8,7)=STUDENT, SubString(t,2,1)=OIndex (s,A)=3, Index(s,t)=0, Replace(s,STUDENT,q)=I AM A WORKERConcat(SubString(s,6,2) =A ,Concat(t,SubString(s,

8、7,8)= STUDENT)= A GOOD STUDENT;4.4已知下列字符串a= THIS,f= A SAMPLE,c= GOOD,d= NE,b= ,s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2),t=Replace(f,SubStgring(f,3,6),c),u=Concat(SubString(c,3,1),d), g= IS,v=Contcat(s,Concat(b,Concat(t,Concat(b,u),试问：s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？S

9、=THIS SAMPLE IST=GOOD,V=THIS SAMPLE IS GOOD ONE,StrLength(s)=14Index(v,g) =3,Index(u,g)=04.5试问执行以下函数会产生怎么样的结果？ Void demonstrate() StrAssign(s,THIS IS A BOOK); Replace(s,SubString(s,3,7),ESE,ARE); StrAssign(t,Concat(s,S);StrAssign(u,XYXYXYXYXYXY); StrAssign(v,SubString(u,6,3); StrAssign(w,W); Printf(

10、t=,t,v=,v,u=,Replace(u,v,w);/demonstrate答：t=THESE ARE BOOKS,v=YXY,u=XWXWXW第五章：数组与广义表5.1假设有两维数组A68，每个元素用相邻的6个字节存储。存储器按字节编址。已知A的起始存储位置是1000，计算1， 数组A的体积。6x6x8=288Amn数组，每个元素占L个字节，计算体积公式MxNxL2， 数组A的最后一个元素a57的第一个字节的地址。公式数组中某个元素的地址=数组基地址+（列数x行标+列标）x每个元素的字节答案是 1000+(8x5+7)x6=12823， 按行存储，元素a14的首字节地址。1000+(8x

11、1+4)x6=10724， 按列存储时，元素a47的首字节地址。按列存储时，计算公式里下标做逆向变化数组中某个元素的地址=数组基地址+（行数x列标+行标）x每个元素的字节1000+(6x7+4)x6=1276四维数组首字节地址计算（了解即可）A9358，每个元素占4字节A1111=1000+(3x5x8x1+5x8x1+8x1+1)x4=776A8247=1000+(3x5x8x8+5x8x2+8x4+7)x4=44165.10求广义表操作结果记住2个概念1，非空广义表，第一个元素为head 表头，其余元素为Tail 表尾。2，任意一个非空列表，表头可能为原子或列表，表尾一定是列表。GetHe

12、ad(p,h,w)=pGetTail(b,k,p,h)=(k,p,h)GetHead(a,b),(c,d)=(a,b)GetTail(a,b),(c,d)=(c,d)GetHeadGetTail(a,b),(c,d)=(c,d)GetTailGetHead(a,b),(c,d)=(b)GetHeadGetTailGetHead(a,b),(c,d)=bGetTailGetHeadGetTail(a,b),(c,d)=(d)第六章：树与二叉树比较重要的2个考点，就是树转换成二叉树和（树或者二叉树转换成森林）；(1) 树转换成二叉树 口诀：1.链接兄弟节点，2.删除兄弟节点与根节点连线，3.以根结

13、点为支撑点，左支臂结点不动，右支臂结点顺时针转45图手工画下(2) 二叉树转换成森林 ，类似上面，个人总结：1.链接兄弟节点，2.删除二叉树的右支臂连接线 ，3,单独排列树，成为森林图手工画下第七章：图 概念：图中的数据元素通常称做顶点(Vertex) V是顶点的有穷非空集合;VR是两个顶点之间的关系集合。若VR 则表示v到w的一条弧(Arc)，且称V为弧尾(tail)或初始点称为W为弧头（head）或终端点。此时图称为有向图。反之为无向图。有向图略： G1 G1=() V1 V2 = V3 V4 有向顺序：=7.1已知道如图所示的有向图，请给出该图的 1.每个顶点的入/出度 2.邻接矩阵 5

14、.强连通分量 3.邻接表 4.逆邻接表 第八章 动态存储管理不整理了，没时间，放弃此章节。第九章 查找第十章 排序选择排序算法：Void SelectSort(SqList &L) for(i=1;iL.length;+i) j=SelectMinKey(L,i); /在L.riL.length中选择key最小的记录 if(i!=j) L.ri L.rj/SelectSort算法实现：#include stdio.hvoid selectSort(int arr10);int main() int a10, i;for (i = 0; i 10; i+)scanf(%d, &ai);for (i = 0; i 10; i+)printf(%3d, ai);printf(n);selectSort(a);for (i = 0; i 10; i+)printf(%3d, ai);void selectSort(int arr10) int i, t, j;for (i = 0; i 9; i+) for (j = i + 1; j 10; j+) if (arrj arri) t = arri;arri = arrj;arrj = t;