2023年数据结构复习资料.docx

2023年数据结构复习资料 第一篇：数据结构复习资料 数据结构复习资料 模块一：计算题 一.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 解：在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。 二叉树自画！ 二试列出如下列图中全部可能的拓扑排序序列。 123456 解：全部可能的拓扑排序序列为：152364、152634、156234、561234、516234、512634、512364 三已知哈希表地址空间为0.8，哈希函数为H(key)=key%7，接受线性探测再散列处理冲突，将数据序列100,20,21,35,3,78,99,45依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度以及查找因子。 解：哈希表及查找各关键字要比较的次数如下所示： ASL=1(4×1+1×2+1×4+2×5)=2.5 8a=8/9 四已知关键字序列23，13，5，28，14，25，试构造二叉排序树。 解： 五设有序列：w=23,24,27,80,28，试给出哈夫曼树； 哈夫曼树如下列图所示： 六：已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 解：先由先序序列的第一个结点确定二叉树的根结点，再由根结点在中序序列中左侧部分为左子树结点，在右侧部分为右子树结点，再由先序序列的第一个结点确定根结点的左右孩子结点，由类似的方法可确定其他结点，如下列图所示。 七此题8分 对于如下列图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的转变状况。 解：用Kruskal算法构造最小生成树的过程如下列图所示： 八给出一组关键字29、18、25、47、58、12、51、10，写出归并排序方法进行排序时的转变过程。 解： (l8,29)(25,47)(12,58)(l0,51)(l8,25,29,47)(10,12,51,58)(l0,12,18,25,29,47,51,58) 九 三、此题8分 请画出如下列图所示的邻接表。 解：邻接表如下列图所示： *454545 十推断以下序列是否是小根堆? 假如不是，将它调整为小根堆。1 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 2 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 解：1不是小根堆。调整为：12,24,33,65,33,56,48,92,86,70 2是小根堆。 十一 设有如下列图所示的AOE网其中vii=l，2，6表示事务，弧上表示活动的天数。 v26v14v48217v311v693v5 找出全部的关键路径。 解：全部的关键路径有：v1v2v3v5v6，以及v1v4v6。十二.对给定的有7个顶点的有向图的邻接矩阵如下：l画出该有向图； 2若将图看成是AOE-网，画出关键路径。 é¥ê¥êê¥êê¥ê¥êê¥ê¥ë252¥2¥¥¥1¥¥¥¥¥¥¥¥¥¥¥¥¥¥¥ù¥8¥úú35¥úú 5¥¥ú¥39úú¥¥5ú¥¥¥úû 解：1由邻接矩阵所画的有向图如下列图所示： 2212523*5关键路径如下列图所示： 22213715945 42 其次篇：数据结构期末复习资料 数据结构课程复习资料 第一章：数据结构概述 1、驾驭数据结构的定义，即数据结构三要素：数据的规律结构、存储结构、操作； 2、数据结构包括：规律结构和存储结构； 3、数据之间的关系：表一对一之间的关系、树一对多之间的关系、图多对多之间的关系； 4、算法的定义：算法衡量的标准：时间困难度和空间困难度； 5、算法时间困难度的求法：给定一段程序，求其时间困难度；时间困难度的比较； 6、为什么学习“数据结构？“数据结构课程主要学了哪些学问？ 其次章：线性表 1、线性表依据存储结构不同分为依次表、链式表；依次表的特点：规律上相邻的两个元素在物理上也相邻；链式表的特点：规律上相邻的两个元素在物理上未必相邻；“未必的含义是可相邻也可以不相邻 2、比较线性表依次存储和链式存储的优缺点。 第三章：栈和队列 1、栈和队列的特点：栈：后进先出，队列：先进先出 2、熟识栈和队列的基本操作：初始化栈、入栈操作、出栈操作、推断栈是否为空、取栈顶元素等。 3、根据实例，能够简洁的推断出是栈的应用还是队列的应用？ 4、重点驾驭栈的应用：进制转换算法的思想或程序。 第四章：数组 1、牢记对称矩阵、三角矩阵、对角矩阵的特点，驾驭矩阵中的元素Aij与一维数组SA的对应关系。 2、驾驭稀疏矩阵的三元组表示法。 第五章：串 1、驾驭上课介绍的9种函数名称及其实现结果； 第六章：树 1、二叉树的5特性质； 2、二叉树前序、中序和后序遍历，根据2种遍历结果求第3种遍历结果。 3、完全二叉树、满二叉树、哈弗曼树的定义； 4、给定一组叶子权值，求带权路径长度最小的多少？ 第七章：图 1、驾驭图的术语：无向完全图、有向完全图、顶点的度等； 2、图的深度优先遍历和广度优先遍历； 3、图的邻接矩阵存储，给定一个图，求出邻接矩阵；或者给定一个邻接矩阵，构造图； 4、图的最小生成树； 第八章：查找 1、查找的定义：静态查找和动态查找 2、折半查找算法的思想； 第九章：排序 1、驾驭排序的分类：插入排序、交换排序、选择排序； 2、重点驾驭希尔排序、快速排序、简洁选择排序； 第三篇：数据结构 试验：线性表的基本操作 学习驾驭线性表的依次存储结构、链式存储结构的设计与操作。对依次表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。 1.依次表的实践 1)建立4个元素的依次表s=sqlist=1，2，3，4，5，实现依次表建立的基本操作。 2)在sqlist =1，2，3，4，5的元素4和5之间插入一个元素9，实现依次表插入的基本操作。 3)在sqlist =1，2，3，4，9，5中删除指定位置i=5上的元素9，实现依次表的删除的基本操作。2.单链表的实践 3.1)建立一个包括头结点和4个结点的5，4，2，1的单链表，实现单链表建立的基本操作。 2)将该单链表的全部元素显示出来。 3)在已建好的单链表中的指定位置i=3插入一个结点3，实现单链表插入的基本操作。 4)在一个包括头结点和5个结点的5，4，3，2，1的单链表的指定位置如i=2删除一个结点，实现单链表删除的基本操作。5)实现单链表的求表长操作。 1.打开VC+。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 线性是我们学习数据结构中，遇到的第一个数据结构。学习线性表的重点驾驭依次表和单链表的各种算法和时间性能分析。线性表右两种存储方式即依次存储结构和链式存储结构。通过学习我知道了对线性表进行建立、插入、删除，同时单链表也是进行建立、插入、删除。而对于依次表的插入删除运算，其平均时间困难度均为0n.通过这次的学习，驾驭的太娴熟，主要是课本上的学问点没有彻底的理解，回去我会多看书，理解重要的概念。总之，这次试验我找到了自己的缺乏之处，以后会努力的。 试验二：栈的表示与实现及栈的应用 1驾驭栈的依次存储结构及其基本操作的实现。2驾驭栈后进先出的特点，并利用其特性在解决实际问题中的应用。3驾驭用递归算法来解决一些问题。 1.编写程序，对于输入的随便一个非负十进制整数，输出与其等值的八进制数。 2.编写递归程序，实现N！的求解。3.编写递归程序，实现以下函数的求解。 n,n=0,1ìFib(n)=í îFib(n-1)+Fib(n-2),n>1 4.编写程序，实现Hanoi塔问题。 1.打开VC+。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 通过这次的学习我驾驭了栈这种抽象数据类型的特点，并能在相应的应用任务中正确选用它；总的来说，栈是操作受限的线性表，是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶top，相应地，表头端称为栈底botton；栈又称为后进先出Last In First Out的线性表,简称LIFO结构，因为它的修改是按后进先出的原则进行的。 加上这个试验，我已经学了线性表依次表，单链表和栈，知道它们都是线性表，而且对以后的学习有很大的作用，可以说这是学习以后学问的总要基础。 试验三：二叉树的建立及遍历 1驾驭利用先序序列建立二叉树的二叉链表的过程。2驾驭二叉树的先序、中序和后序遍历算法。 1.编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。如：输入先序序列abc#de#，则建立如下列图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 1.打开VC+。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 这次试验是关于二叉树的常见操作，主要是二叉树的建立和遍历，在这次试验中我按先序方式建立二叉树的，而遍历方式则相对要多一些，有递归的先序、中序、后序遍历，和非递归的先序、中序、后序遍历，此外还有层次遍历.二叉树高度和叶子个数的计算和遍历相差不大，只是加些推断条件，总体来说，本次试验不太好做，期间出现了很多规律错误，变量初始化的问题等，不过经过细致排查最终都一一解决了。 试验四：查找与排序 1驾驭折半查找算法的实现。2驾驭冒泡排序算法的实现。 1.编写折半查找程序，对以下数据查找37所在的位置。5，13，19，21，37，56，64，75，80，88，92 2.编写冒泡排序程序，对以下数据进行排序。49，38，65，97，76，13，27，49 1.打开VC+。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 1查找算法的代码如下所示： #include “stdio.h #include “malloc.h #define OVERFLOW-1 #define OK 1 #define MAXNUM 100 #define N 10 typedef int Elemtype;typedef int Status;typedef struct Elemtype *elem; int length;SSTable;Status InitList(SSTable &ST) int i,n; ST.elem = (Elemtype*) malloc(Elemtype); if(!ST.elem)return(OVERFLOW); printf(“输入元素个数和各元素的值:); scanf(“%dn,&n); for(i=1;iST.elem) t=ST.elem;= (Elemtype*) malloc (MAXNUM*sizeof ST.elem=ST.elem;ST.elem=t;void display(SSTable ST) int i; for(i=1;inext=HL;HL=p;C.P->next=HL;p=HL;D.P->next=HL->next;HL->next=p;4.两个字符串相等的条件是 A.串的长度相等 B.含有相同的字符集 C.都是非空串 D.串的长度相等且对应的字符相同 5若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是 A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为A.0 B.1 C.48 D.49 7.已知用某种排序方法对关键字序列51，35，93，24，13，68，56，42，77进行排序时，前两趟排序的结果为 35，51，24，13，68，56，42，77，93 35，24，13，51，56，42，68，77，93所接受的排序方法是 A.插入排序 B.冒泡排序 C.快速排序 D.归并排序 8.已知散列表的存储空间为T，散列函数Hkey=key%17,并用二次探测法处理冲突。散列表中已插入以下关键字：T=39，T=57和T=7，则下一个关键字23插入的位置是 A.T B.T C.T D.T 9.假如将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=(a11,a21,an1),(a12,a22,an2),，a1n,a2n,ann),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是A.head(tail(head(L)B.head(head(head(L)C.tail(head(tail(L)D.head(head(tail(L)10.在一个具有n个顶点的有向图中，全部顶点的出度之和为Dout，则全部顶点的入度之和为 A.Dout B.Dout-1 C.Dout+1 D.n 11从规律关系来看，数据元素的干脆前驱为0个或1个的数据结构只能是A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 12栈的插入和删除操作在()进行。 A栈顶 B.栈底 C.随便位置 D指定位置 13由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为A.24 B.71 C.48 D.53 14一个栈的输入序列为1 2 3，则以下序列中不行能是栈的输出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15关于栈和队列的说法中正确的选项是 A栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 16关于存储相同数据元素的说法中正确的选项是A依次存储比链式存储少占空间 B.依次存储比链式存储多占空间 C.依次存储和链式存储都要求占用整块存储空间 D.链式存储比依次存储难于扩充空间 17已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行A.qnext=s；pnext=s； B.qnext=s；snext=p； C.qnext=s；qnext=p； D.qnext=s；snext=q； 18设一组记录的关键字key值为62，50，14，27，19，35，47，56，83，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是A.1 B.2 C.3 D.4 19执行下面程序段时，S语句被执行的次数为：for(int i=1;ikey=Key) printf(“已找到n); return; p=(Key key)? p->lchild:p->rchild; printf(“没有找到n); void InsertBST(BSTree *T,KeyType Key) BSTNode *f,*p; p=(*T); while(p) if(p->key=Key) printf(“树中已有Key不需插入n); return; f=p; p=(Key key)?p->lchild:p->rchild; p=(BSTNode*)malloc(sizeof(BSTNode); p->key=Key; p->lchild=p->rchild=NULL; if(*T)=NULL)(*T)=p; else if(Keykey)f->lchild=p; else f->rchild=p; /*InsertBST*/ void DelBSTNode(BSTree *T,KeyType Key) BSTNode *parent=NULL, *p, *q,*child; p=*T; while(p) if(p->key=Key)break; parent=p; p=(Key key)?p->lchild:p->rchild; if(!p)printf(“没有找到要删除的结点n);return; q=p; if(q->lchild && q->rchild) for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild; if(!parent)*T=child; else if(p=parent->lchild) parent->lchild=child; else parent->rchild=child; if(p!=q) q->key=p->key; free(p); void InorderBST(BSTree T) if(T!=NULL) InorderBST(T->lchild);printf(“%5d,T->key);InorderBST(T->rchild);