2022年数据结构复习提纲收集 .pdf

《2022年数据结构复习提纲收集 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构复习提纲收集 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习提纲第一章 数据结构概述基本概念与术语（ P3）1 数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2 数据 是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合2数据元素是数据的基本单位3数据对象相同性质的数据元素的集合4数据结构包括三方面内容 :数据的逻辑结构 .数据的存储结构 .数据的操作 . （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入 ,删除等 . 5.时间复杂度分析- 1

2、、名词解释：数据结构、二元组2、根据数据元素之间关系的不同，数据的逻辑结构可以分为集合、线性结构、树形结构和图状结构 四种类型。3、常见的数据存储结构一般有四种类型，它们分别是_顺序存储结构 _、_链式存储结构 _、_索引存储结构 _和_散列存储结构 _。4、以下程序段的时间复杂度为_O(N2)_。int i,j,x; for(i=0;in:i+) n+1 for(j=0;j=0)个具有相同性质的数据元素a1,a2,a3 ,an 组成的有穷序列/顺序表结构#define MAXSIZE 100 typedef int DataType; Typedef struct DataType item

3、sMAXSIZE; Int length; Sqlist,*LinkList; /初始化链表void InitList(LinkList *L) (*L)=(LinkList)malloc(sizeof(LNode); if(!L) coutnext=NULL; /插入数据void InsertList(LinkList L,int pos,DataType x) LinkList p=L,q; int i=0; while(p&inext; i+; if(!p|ipos-1) coutnext=p-next; p-next=q; q-data=x; /销毁链表名师资料总结 - - -精品资料

4、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - void DestoryList(LinkList L) LinkList t; while(L) t=L; L=L-next; free(t); /遍历链表void TraverseList(LinkList L) LinkList t=L; while(L) t=t-next; coutdata” ”; coutendl; /删除元素void DeleteList(LinkList L,int pos) L

5、inkList p=L,q; int i=0; while(p&inext; i+; if(!p|ipos-1) coutnext; p-next=q-next; free(q): 第三章 栈和队列1. 栈（1） 栈的结构与定义（2） 顺序栈操作算法：入栈、出栈、判断栈空等（3） 链栈的结构与定义名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 2. 队列（1） 队列的定义- 1、一个栈的入栈序列为 “ABCDE ” ，则以下不

6、可能的出栈序列是（）A. BCDAE B. EDACB C. BCADE D. AEDCB 2、栈的顺序表示仲，用TOP 表示栈顶元素，那么栈空的条件是（）A. TOP=STACKSIZE B. TOP=1 C. TOP=0 D. TOP=-1 3、允许在一端插入，在另一端删除的线性表称为_队列 _。插入的一端为_队尾_，删除的一端为 _队头_。4、栈的特点是 _先进后出 _，队列的特点是 _先进先出 _。5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是_O(1)_。6、已知链栈 Q，编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。 （要

7、求判断栈空、出栈、入栈用函数实现）/判断栈空 (完成题目要求 ) void EmptyStack(LinkStack Q) LinkStack t; char x=a; /假设链栈存储字符型数据if(Q-next)t=Pop(Q,x);coutdata; else Push(Q,x); /初始化栈void InitStack(LinkStack *Q) *Q=(LinkStack)malloc(sizeof(SNode); if(!Q) coutnext=NULL; /入栈void Push(LinkStack Q,datatype x) LinkStack t; InitStack(&t);

8、 t-data=x; t-next=Q-next; Q-next=t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - /出栈void Pop(LinkStack Q,datatype &x) LinkStack t=Q-next; if(!t) coutnext=t-next; x=t-data; free(t); 基本概念数据结构的研究对象是什么？数据，数据元素 （数据结构中讨论的 基本单位 、数据整体中相对独立的单位、数

9、据元素的特点：相对性） ，数据结构 ，数据类型和抽象数据类型，数据对象数据结构是什么？定义：数据元素以及它们之间存在一种或多种特定的关系。特点 ：数据元素集合相同， 而其上的关系不同， 则构成的数据结构不同。逻辑结构是什么？主要有哪几类？逻辑结构 ：对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。存储结构是什么？存储结构：是数据逻辑结构在计算机中的表示和实现，故又称数据物理结构。什么是算法？定义：是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。五大特性： 有穷性、确定性、可行性、输入、输出线性表线性表的定义 ?

10、线性表是由 n(n0) 个属性相同数据元素a1,a2an组成的一个有限序列，线性表或是空表，或可以表示为A=(a1，a2，ai，an) 其中 ai(i=1，2，n)是线性表中的一个元素。如何在顺序存储结构表示的线性表中实现插入元素操作？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - int insertElement(List_Array *list_ptr, char *element) /把新字符串插入到线性表的最后位置i

11、f(list_ptr-count = LISTMAX)return (-1); / 到达最大大小else strcpy(list_ptr-listlist_ptr-count,element);list_ptr-count+; /下一个元素return (1); / 成功返回 如何在顺序存储结构表示的线性表中实现元素删除操作？int deleteElement(List_Array *list_ptr, int pos) int k;/检查下标 pos位置上是否存在数据if (pos list_ptr-count-1)return (-1); / 出错else / 将 pos位置后所有元素向前

12、移动for (k = pos; k count - 1;k+)strcpy(list_ptr-listk,list_ptr-listk+1);list_ptr-count-;return (1); / 删除成功如何在顺序存储结构表示的线性表中找到元素后继？物理地址上紧接着该元素后一个级即该元素的后继用数组的下标加1 即可找到 .如何在顺序存储结构表示的线性表中找到元素前驱？物理地址上紧接着该元素前一个即该元素的前驱用数组下标减 1 即可找到链表什么是链接存储结构？通过指针管理的一组存储单元，（这组存储单元的内存地址可以是连续的，也可以是不连续的） 。链接存储结构中的每个存储单元称为“ 结点”

13、，结点包含一个数据域和一个指针域；链接存储结构中的结点通过指针域指示后继结点的内存地址；访问链接存储结构通常由第一个结点开始，逐一访所有结点。如何将新结点添加到单链表中？表头位置Node *t=new Node; t-Data=d; t-next=head; head=t;表尾位置Node *t =new Node; t-data=d; last-next=t; last=t;两个结点中间名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - -

14、 - - 查找单链表中指定结点？设置一个跟踪链表结点的指针p，初始时 p 指向链表中的第一个结点， 然后顺着 next 域依次指向每个结点，每指向一个结点就判断其是否等于指定结点，若是则返回该结点地址。 否则继续往后搜索， 直到 p 为 NULL ，表示链表中无此元素，返回NULL 。算法的时间复杂度为O(n)。如何删除单链表中的结点？要删除链表中第i 个结点，首先在单链表中找到删除位置i1 前一个结点，并用指针p 指向它，指针 t 指向要删除的结点。将指针 p 所指结点的指针域修改为所t 指结点的后继结点的地址。从链表中删除链接关系后的结点需动态的释放（delete )。Node *t,*p

15、; t=p -next; p-next=t-next ; delete t; 如何用单链表表示线性表？如何实现链接存储结构表示的线性表的操作？插入、删除、查找栈和队列什么是栈？栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。栈中允许插入和删除运算的一端称作栈顶 (top) 不允许插入和删除的另一端称作栈底(bottom) 如何实现栈的入栈和出栈操作？栈顶表示（两种存储结构）入栈、出栈什么是队列？队列(queue)是限定只能在表的一端进行插入，在表的另一端进行删除的线性表、队尾 (rear) 允许插入的一端 、队头(front)允许删除的一端如何实现队列的入队和出队操作？队头、队

16、尾（两种存储结构）循环队列已满标志队列已满标志bFull=true; （表示队列为满）bFull=false; （表示队列为空）设空单元(rear+1)%Max=front （表示队列为满）front=rear(表示队列为空）栈的应用算术表达式三种形式前缀表达式 =运算符操作数1操作数 2中缀表达式 =操作数 1运算符操作数2后缀表达式 =操作数 1操作数 2运算符中缀表达式、后缀表达式中缀表达式转换成后缀表达式排序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页

17、 - - - - - - - - - 什么是直接插入排序法？排序过程、代码如何实现依次将待排序数据元素按其关键字的大小插入到有序区的适当位置上.什么是简单选择排序法？排序过程、代码如何实现将乱序的序列分成两组,一组有序 (刚开始元素个数为0),一组无序 .每次都选取无序区域中关键字最小的数据元素插入到有序区最后面.什么是快速排序法？排序过程、如何实现选取一个元素为中轴,然后将无序序列中大于中轴的元素一道中轴元素右边 ,小于中轴的元素移到中轴的左边.移动完后 ,将中轴元素的左边的无序序列和右边的无序序列分别重复以上过程(递归 ).直到全部有序为止.什么是二路归并排序法？如何归并两个有序表排序过程

18、、如何实现先将相邻的两个有序子序列合并,并存放于一个临时数组中,合并完成后再复制回原序列 .合并时 ,依次比较两个子序列相对应的数据元素的关键字值 ,将关键字值较小的数据元素复制到临时数组中,然后再比较下一个关键字 .反复如此 ,直至一个子序列复制完成,再将另一个非空的子序列剩余部分复制到临时数组中.内部查找什么是二分查找（折半查找）？前提条件查找的表为有序表查找过程如何实现？首先确定待查找区间的中间位置,然后把待查找关键字key 与中间位置上数据元素的关键字mkey 做比较 ;若 key=mkey,则查找成功 ;若 keymkey,则在待查找区间的后半自取件继续这样额查找;直到找到或查找区间

19、的上界小于下届(没找到 )为止. 什么是散列查找？冲突、同义词冲突: 在构造哈希表时 ,不同的关键字可能得到同一个哈希地址,这种现象称为冲突 .在构造哈希表时 ,冲突在所难免 . 同义词 : 把具有不同关键字而有相同哈希地址的数据元素称作同义词.开放地址法解决冲突开放定址法是使用某种探查技术在哈希表中形成一个探查序列,当冲突发生时 ,沿此序列举个单元地查找,直到找到空闲单元地址的方法.方法主要有 : 线性探查法平方探查法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10

20、 页 - - - - - - - - - 双哈希函数探查法链接法解决冲突做法是 : 把所有关键字为同义词的数据元素存在同一个单链表中. 树与二叉树什么是树？根、树的度、结点树是由 n(n=0)个元素构成的有限集合 .其中,n=0 称为空树 ;n0 称为非空树 .对于任意一棵非空树 ,都满足一下条件 : 1. 有且仅有一个称为根的节点,它比较特殊 ,没有前驱结点 ; 2. 其余结点被分成 m(m=0)个互不相交的有限集T1,T2, .Tm,其中每一个集合 Ti(i0）结点的完全二叉树的深度为log2n +1二叉树的遍历方法（先序、中序、后序）先序遍历 :头结点左子树右子树中序遍历 :左子树头结点

21、右子树后续遍历 :左子树右子树头结点附:层序遍历 :按照每个元素的下标依次遍历什么是二叉搜索树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 如何生成二叉搜索树二叉搜索树或者是空树 ,或者是具有以下性质的二叉树: 1.若左子树非空 ,则左子树上所有结点的关键字值均小于它的根节点的关键值. 2.若右子树非空 ,则右子树上所有结点的关键字值均大于它的根节点的关键值. 3.左右子树本身又是一颗二叉排序树. 如何在二叉搜索树实现数据查

22、找类似于折半查找 ,过程为 : 设待查找数据元素为a ,要比较的二叉排序树根节点的关键字值为b 若 a=b,则查找成功 . 若 ab,则继续查找右子树 . 图什么是图？ (重点要看看书 )有向图、无向图、路径由没有方向的边构成的图称为无向图. 由有有方向的边构成的图称为有向图. 由顶点 vi 经过一系列的边或弧能够到达顶点vj,则称这一系列的边或弧为顶点 vi 到顶点 vj 的路径 . 有向边、无向边有方向的边称为有向边,一般称为弧 .有向边的始点称为弧尾,有向边的终点称为弧头没有方向的边称为无向边,简称边 .图的存储结构重点:邻接矩阵、邻接表邻接矩阵式表示顶点之间相邻关系的矩阵.它以矩阵的行和列表示顶点,以矩阵中的元素表示边或弧.邻接矩阵式图的顺序存储结构.(P216) 邻接表是图的链式存储结构.邻接表由边表和顶点表组成.(P221) 图的遍历方法？深度优先遍历 (P226)广度优先遍历 (P228)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -