还剩26页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第一章数据结构概述基本概念与术语
1.数据数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称
2.数据元素数据元素是数据的基本单位,是数据这个集合中的个体,也称之为元素,结点,顶点记录(补充一个数据元素可由若干个数据项组成数据项是数据的不可分割的最小单位)
3.数据对象数据对象是具有相同性质的数据元素的集合,是数据的一个子集(有时候也叫做属性)
4.数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合
(1)数据的逻辑结构数据的逻辑结构是指数据元素之间存在的固有逻辑关系,常称为数据结构数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关,是独立于计算机的p-next=p-next-next;freeq;//这种题目靠一根指针是没有办法完成的,必须要借助第二根指针
9.在一个单链表中p所指结点之后插入一个s所指结点时,应执行:s-next=p-nextp-next=s操作
10.对于一个具有n个节点的单链表,在已知所指结点后插入一个新结点的时间复杂度是O1;在给定值为x的结点后插入一个新结点的时间复杂度是On.问答题11线性表可用顺序表或链表存储试问1两种存储表示各有哪些主要优缺点?顺序表的存储效率高,存取速度快但它的空间大小一经定义,在程序整个运行期间不会发生改变,因此,不易扩充同时,由于在插入或删除时,为保持原有次序,平均需要移动一半或近一半元素,修改效率不高链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空间,就不会产生存储溢出的问题同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高2若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时,应采用哪种存储表示?为什么?应采用顺序存储表示因为顺序存储表示的存取速度快,但修改效率低若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好第三章栈和队列
1.栈1栈的结构与定义定义限定仅在表尾进行插入或删除操作的线性表结构typedef struct list{int listsize;〃栈的容量struct list*head;〃栈顶指针struct list*base;〃栈底指针}2顺序栈操作算法入栈、出栈、判断栈空等这个是使用数组进行操作的,具体内容参照书本P46-47
(3)链栈的结构与定义
2.队列
(1)队列的定义定义只允许在表的一端进行插入,而在另一端删除元素补充内容
1、一个栈的入栈序列为“ABCDE,则以下不可能的出栈序列是(B)A.BCDAE B.EDACB C.BCADE D.AEDCB
2、栈的顺序表示中,用TOP表示栈顶元素,那么栈空的条件是(D)A.TOP=二STACKSIZE B.TOP=1c.TOP=0D.TOP==-
13、允许在一端插入,在另一端删除的线性表称为队列插入的一端为表头,删除的一端为表尾
4、栈的特点是先进后出,队列的特点是先进先出
5、对于栈和队列,无论他们采用顺序存储结构还是链式存储结构,进行插入和删除操作的时间复杂度都是0
(1)(即与已有元素N无关)
6、已知链栈Q,编写函数判断栈空,如果栈空则进行入栈操作,否则出栈并输出(要求判断栈空、出栈、入栈用函数实现)(详看考点2)
7.出队与取队头元素的区别出队就是删除对头的数据元素,取队头元素是获取对头的数据元素值,不需要删除
8.链栈与顺序栈相比,比较明显的优点是(D)A.插入操作比较容易B.删除操作比较容易C.不会出现栈空的情况D.不会出现栈满的情况考点1队列的编程结构:typedef struct QNode{int date;structQNode*next;}QNode,*QueuePtr;typedef struct{QueuePtr front;QueuePtr rear;JLinkQueue;创建:LinkQueue InitQueueLinkQueueQQ.front=Q.rear=QueuePtrmallocsizeofQNode;Q.front-nex t=NULL;return Q;入队LinkQueue EnQueueLinkQueueQ,int eQueuePtr p;p=QueuePtrmallocsizeofQNode;p-date=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return Q;出队LinkQueue DeQueueLinkQueueQint e;QueuePtrp;p=Q.front-next;e=p-date;Q.front=p-next;printfn%dn,e;ifQ.rear==pQ.rear=Q.front=NULL;freep;return Q;考点2栈的编程创建struct list*creatstruct list*p;p=struct list*mallocLEN;p-next=NULL;retump;入栈struct list*pushstruct list*head,int astruct list*p;p=structlist*mallocLEN;p-num=a;p-next=head;returnp;}出栈structlist*popstruct list*headstruct list*p;p=head-next;freehead;return p;判断栈空int listemptystructlist*headifhead-nextreturn0;else return1;第四章串(不是重点内容)
1.串是由零个或多个字符组成的有限序列
2.串的赋值:x=abc;或x[]=abc;第五章数组和广义表(不是重点内容)
1.多维数组中某数组元素的position求解一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数,然后要求你求出该数组中的某个元素所在的位置
2.明确按行存储和按列存储的区别和联系,并能够按照这两种不同的存储方式求解1中类型的题
3.将特殊矩阵中的元素按相应的换算方式存入数组中这些矩阵包括对称矩阵,三角矩阵,具有某种特点的稀疏矩阵等熟悉稀疏矩阵的三种不同存储方式三元组,带辅助行向量的二元组,十字链表存储掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法补充内容三元组结构typedef struct{int i,j;//元素行下标及列下标int e;〃元素值Triple;typedef struct{int mu,nu,tu;〃矩阵的行数、列数、非零元素个数Triple data[MAXSIZE+1];〃矩阵包含的三元组表,data[O]未用}TSMatrix;十字链表typedef struct OLNode{int i,j;//元素行下标及列下标int e;〃元素值structOLNode*right,*down;〃行的后继以及列的后继}OLNode,*OLink;typedef struct{int mu,nu,tu;〃矩阵的行数、列数、非零元素个数OLink*rhead,*chead;//行和列的表头指针组的首地址}CrossList;CrossList CreatCrossList M{%scanf d%d%d\m,n,t;M.mu二m;M.nu=n;M.tu=t;M.rhead=OLink*mallocm+1*sizeofOLink;〃开辟行表头指针组M.chead=OLink*mallocn+l*sizeofOLink;//开辟行列头指针组M.rhead[]=M.chead[]=NULL;〃初始化……〃接下来就是赋值和入链}第六章树和二叉树
1.树1树的概念及术语树n nNO个结点的有限集合当n=0时,称为空树;任意一棵非空树满足以下条件⑴有且仅有一个特定的称为根的结点;⑵当nl时,除根结点之外的其余结点被分成m m0个互不相交的有限集合T1,T2,…,Tm,其中每个集合又是一棵树,并称为这个根结点的子树依据数据元素之间的关系,可以把数据的逻辑结构分成以下几种
1.集合数据中的数据元素之间除了“同属于一个集合”的关系以外,没有其他关系
2.线性结构结构中的数据元素之间存在“一对一”的关系若结构为非空集合,则除了第一个元素之外,和最后一个元素之外,其他每个元素都只有一个直接前驱和一个直接后继
3.树形结构结构中的数据元素之间存在“一对多”的关系若数据为非空集,则除了第一个元素(根)之外,其它每个数据元素都只有一个直接前驱,以及多个或零个直接后继
4.图状结构结构中的数据元素存在“多对多”的关系若结构为非空集,折每个数据可有多个(或零个)直接后继
(2)数据的存储结构数据元素及其关系在计算机内的表示称为数据的存储结构想要计算机处理数据,就必须把数据的逻辑结构映射为数据的存储结构逻辑结构可以映射为以下两种存储结构
1.顺序存储结构把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中,借助元素在存储器中的相对位置来表示数据之间的逻辑关系
2.链式存储结构借助指针表达数据元素之间的逻辑关系不要求逻辑上相邻的数据元素物理位置上也相邻2结点的度结点所拥有的子树的个数树的度树中所有结点的度的最大值3叶子结点度为0的结点,也称为终端结点分支结点度不为的结点,也称为非终端结点4孩子、双亲树中某结点的子树的根结点称为这个结点的孩子结点,这个结点称为它孩子结点的双亲结点;兄弟具有同一个双亲的孩子结点互称为兄弟5路径如果树的结点序列nl,n2,…,nk有如下关系结点ni是ni+1的双亲l=ik,则把nl,n2,…,nk称为一条由nl至nk的路径;路径上经过的边的个数称为路径长度6祖先、子孙在树中,如果有一条路径从结点x到结点y,那么x就称为y的祖先,而y称为x的子孙7结点所在层数根结点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层树的深度树中所有结点的最大层数,也称高度8层序编号将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数9有序树、无序树如果一棵树中结点的各子树从左到右是有次序的,称这棵树为有序树;反之,称为无序树数据结构中讨论的一般都是有序树10树通常有前序根遍历、后序根遍历和层序次遍历三种方式树,不是二叉树,没中序遍历
2.二叉树1二叉树的定义二叉树是n n0个结点的有限集合,该集合或者为空集称为空二叉树,或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成满二叉树在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上满二叉树的特点叶子只能出现在最下一层;只有度为0和度为2的结点完全二叉树对一棵具有n个结点的二叉树按层序编号,如果编号为i IWiWn的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同完全二叉树的特点
1.在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一棵完全二叉树
2.叶子结点只能出现在最下两层,且最下层的叶子结点都集中在二叉树的左部;
3.完全二叉树中如果有度为1的结点,只可能有一个,且该结点只有左孩子
4.深度为k的完全二叉树在k-1层上一定是满二叉树3二叉树的性质性质1二叉树的第i层上最多有2i-l个结点i^lo性质2一棵深度为k的二叉树中,最多有2k-l个结点,最少有k个结点深度为k且具有2k-l个结点的二叉树一定是满二叉树性质3在一棵二叉树中,如果叶子结点数为nO,度为2的结点数为n2,则有:n0=n2+l一个结点的度就是指它放出的射线性质4具有n个结点的完全二叉树的深度为log2n+1性质5对一棵具有n个结点的完全二叉树中从1开始按层序编号,则对于任意的序号为i iWiWn的结点简称为结点i,有:1如果il,则结点i的双亲结点的序号为i/2;如果i=l,则结点i是根结点,无双杀结点2如果2iWn,则结点i的左孩子的序号为2i;如果2in,则结点i无左孩子3如果2i+lWn,则结点i的右孩子的序号为2i+l;如果2i+ln,则结点i无右孩子
3.二叉树的遍历递归调用与访问的顺序不同而产生不同的遍历方法1先序遍历void XianXuBiTreeT{ifT{printf%c,T-data;//先访问XianXuT-lchild;〃再继续遍历XianXuT-rchild;}2中序遍历3后序遍历
4.森林与二叉树的转换1同级以左为亲,即左一结点的右孩子是与它同级的右一结点2只认最左路线为亲子路线,即结点的左孩子是它下一级结点的最左的元素
5.哈夫曼树1哈夫曼树的基本概念哈夫曼树给定一组具有确定权值的叶子结点,带权路径长度最小的二叉树2哈夫曼树的特点
1.权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远禺根结点
2.只有度为0(叶子结点)和度为2(分支结点)的结点,不存在度为1的结点.
(3)哈夫曼树的构造算法思想及构造过程(森林与哈夫曼编码)就是求各权值和路径相乘之后叠加的最小值
1、已知一棵完全二叉树有47个结点,则该二叉树有(C)个叶子结点A.6B.12C.24D.48解法如下1+2+4+8+16=31计算从第一层到n-1层的结点个数47-31=16计算第n层的叶子结点个数16-16/2=8计算第n-1层的叶子结点个数所以,叶子结点数=16+8=24计算第n层和第n-1层的总叶子结点数
2、已知遍历一棵二叉树的前序序列ABCDEFG和中序序列CBEDAFG,那么是下面哪棵树(C)C图如下A
4、完全二叉树必须满足的条件为一棵具有n个结点的二叉树,它的结构与满二叉树的前n个结点的的结构相同
5、哈夫曼树不存在度为1的结点
6、有5个带权结点,其权值分别为2,5,3,7,11,根据哈夫曼算法构建该树,并计算该树的带权路径长度(构建哈夫曼树,很简单,从小开始,计算相加,然后把所有叶子结点乘以等级数字然后相加也即是带权路径长度二叶结点的权值*路径长度)
7.试找出分别满足下列条件的所有二叉树⑴前序序列和中序序列相同只有右子树⑵中序序列和后序序列相同只有左子树⑶前序序列和后序序列相同只有根,空二叉树第七章图
1.图的基本概念图的基本术语及推论图的结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关设图有n个顶点,则:有1/2nn-l条边的无向图称为完全图有n n-1条弧的有向图称为有向完全图元素被多少条弧的箭头所指,它的入度就为多少;反之,出度第一个顶点和最后一个顶点相同的路径叫做回路或环若图中任意两个顶点之间存在路径不一定是直接相连,则顶点不重复出现的路径叫简单路径称作连通图
2.邻接矩阵Wi,j Vi,Vj eVR邻接矩阵的定义A[i][j]={0即VR中不存在Vi,Vj时
3.图的遍历1深度优先遍历步骤
1.从任意顶点开始访问
2.访问后把该元素对应的访问标志赋值为1表示已访问该数据元素
3.寻找与其有关未被访问的所有邻接顶点,并从该顶点开始进行访问
4.重复
2、3步骤直到该连通图的所有顶点均已访问完毕2广度优先遍历步骤
1.从任意顶点开始访问
2.访问后把该元素对应的访问标志赋值为1表示已访问该数据元素
3.寻找与其有关未被访问的邻接顶点,并按顺序入列直到所有邻接顶点均已访问完毕
4.把最先入列的顶点出列,以它为顶点开始访问
5.重复
2、
3、4步骤直到该连通图的所有顶点均已访问完毕第八九十章查找表是由同一类型的数据元素或记录构成的集合对查找表的操作有1查询某个“特定的”数据元素是否在查找表中;2检索某个“特定的”数据元素的各种属性3在查找表中插入一个数据元素;4从查找表中删去某个特定元素静态查找表只进行前两种“查找”操作的查找表为静态查找表动态查找表若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则成为动态查找表排序其功能是将一个数据元素或记录的任意序列,重新排列成一个按关键字有序的序列
5.时间复杂度分析
1.常量阶算法的时间复杂度与问题规模n无关系Tn=Ol
2.线性阶算法的时间复杂度与问题规模n成线性关系Tn=On
3.平方阶和立方阶一般为循环的嵌套,循环体最后条件为i++时间复杂度的大小比较Ol Olog2n0nOn log2n On20n302n On!On n
6.算法与程序1算法的5个特性
1、输入有零个或多个输入
2、输出有一个或多个输出
3、有穷性要求序列中的指令是有限的;每条指令的执行包含有限的工作量;整个指令序列的执行在有限的时间内结束程序与算法的区别在于,程序不需要有有穷性
4、确定性算法中的每一个步骤都必须是确定的,而不应当含糊、模棱两可没有歧义
5、可行性算法中的每一个步骤都应当能被有效的执行,并得到确定的结果
2.算法设计的要求
1、正确性(达到预期效果,满足问题需求)
2、健壮性(能处理合法数据,也能对不合法的数据作出反应,不会产生不可预期的后果)
3、可读性(要求算法易于理解,便于分析)
4、可修改可扩展性
5、高效率(较好的时空性能)补充内容
1、名词解释数据结构、二元组数据结构就是相互之间存在一种或多种特定关系的数据元素的集合二元组就是一种用来表示某个数据对象以及各个元素之间关系的有限集合
2、根据数据元素之间关系的不同,数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构四种类型
3、常见的数据存储结构一般有两种类型,它们分别是顺序存储结构、链式存储结构
6.在一般情况下,一个算法的时间复杂度是问题规模的函数
7.常见时间复杂度有常数阶0
(1)、线性阶O(n)、对数阶O(log2n)、平方阶0(M2)、指数阶0(2册)通常认为,具有常数阶量级的算法是好算法,而具有指数阶量级的算法是差算法第二章线性表定义线性表是n个数据元素的有限序列一个数据元素可由若干个数据项组成
1.顺序表结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素,用这种存储形式存储的线性表称为顺序表
2.单链表1链表结点结构线性表中的数据元素可以用任意的一组存储单元来存储,用指针表示逻辑关系逻辑相邻的两元素的存储空间可以是不连续的2链表操作算法初始化、插入、输出、删除、遍历初始化p=struct student*mallocsizeofstruct student;插入p-next=head-next;head-next=p;输出printf4%d,,,p-data;册!1除q=p-next;p-next=q-next;freeq;结点遍历forp=head;p;p=p-next;补充内容:
1、线性表中,第一个元素没有直接前驱,最后一个元素没有直接后驱
2、在一个单链表中,若p所指结点是q所指结点的前驱结点,则删除结点q的操作语句为()P-next=q-next;free q;
3、在长度为N的顺序表中,插入一个新元素平均需要移动表中N/2个元素,删除一个元素平均需要移动(N-1)/2个元素
4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素,则采用顺序表存储结构最节省运算时间
5、已知顺序表中每个元素占用3个存储单元,第13个元素的存储地址为336,则顺序表的首地址为300o(第n个元素的地址即首地址+(n-l)*每个元素的存储空间,如a
[12](第13个元素)的地址=a
[0]+12*3)
6、设有一带头结点单链表L,请编写该单链表的初始化,插入、输出和删除函数(函数名自定义)结点定义typedef intdatatype;〃结点数据类型,假设为inttypedef struct node{〃结点结构datatype data;structnode*next;〃双向链表还应加上*previous}Lnode,*pointer;〃结点类型,结点指针类型typedef pointerIklist;//单链表类型,即头指针类型
1.初始化Iklist initlist{pointer head;head=new node;//这是C++做法//head=pointermallocsizeofLnode;这是C语言做法head-next=NULL;//循环链表则是head-next=head;〃双向链表应加上head-previos=NULL;return head;}
2.插入C语言中需要把head转化为全局变量才能实现此程序int insertlklisthead,datatype xjnti{pointer q,s;q=gethead,i-l;〃找第i-1个点if q二二NULL〃无第i-1点,即il或in+l时cout”非法插入位置!\n;〃这是C++做法,即C语言中的printf非法插入位置!W;return0;s=new node;//生成新结点即C语言中的s=pointermallocsizeofLnode;s-data=x;s-next=q-next;〃新点的后继是原第i个点q-next=s;〃原第i-1个点的后继是新点return1;〃插入成功}
3.删除C语言中需要把head转化为全局变量才能实现此程序int deletelklistheadjnt i{pointer p,q;q=gethead,i-l;〃找待删点的直接前趋ifq二二NULL||q-next==NULL〃即il或in时{cout«,,非法删除位置!\n”;return0;}p=q-next;〃保存待删点地址q-next=p-next;〃修改前趋的后继指针delete p;〃释放结点即C语言中的freep;return1;〃册U除成
1.不带头结点的单链表head为空的判定条件是AA.head=NULL B.head-next=NULL C.head-next=headD.head!=NULL
2.带头结点的单链表head为空的判定条件是B A.head=NULL B.head-next=NULL C.head-next=head D.head!=NULL
3.在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行BA.s-next=p;p-next=s;B.s-next=p-next;p-next=s;C.s-next=p-next;p=s;D.p-next=s;s-next=p;
4.在一个单链表中,若删除p所指结点的后续结点,则执行AA.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-nextD.p=p-next-next
5.从一个具有n个结点的有序单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较B个结点A.n B.n/2C.n-l/2D.0n log2n
6.给定有n个元素的向量,建立一个有序单链表的时间复杂度BA.Ol B.On C.On2D.On log2n
7.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是BA.Ol B.On C.On2D.On log2n
8.在一个单链表中删除q所指结点时,应执行如下操作q=p-next;。