数据结构考试大纲

第一章概述一、概念一、数据结构的要紧研究内容：一般是研究数据的存储结构(物理结构)和逻辑结构，以及它们之间的彼此联系；对每种结构概念相适应的各类运算，设计出相应的算法，分析算法的效率。二、从逻辑上能够把数据结构分为线性结构、非线性结构两大类。即：数据逻辑结构除集合之外，还包括线性结构、树形结构和图形结构。3、数据的逻辑结构与数据元素本身的内容和形式无关。4、数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。二、算法一、程序和算法原那么上是有区别的。二、算法分析的两个要紧方面是：时刻复杂度和空间复杂度第二章线性表一、顺序表一、顺序表中的地址计算公式：第一个元素的存储地址是LOC(a)，每一个元素占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，那么第i个元素的存储地址为：LOC(a)=LOC(a)+(i—l)*L(1WiWn)i1二、在顺序表中访问任意一结点的时刻复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。二、 单链表一、 在结点P后插入结构q的语句：q->next二p->next;p->next二q;二、 删除结点P后的结点q的语句：p->next二q->next;free(q);3、 链式存储的存储结构所占存储空间：分两部份，一部份寄存结点值，另一部份寄存表示结点间关系的指针4、 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并非必然紧邻。三、 双向链表一、在双向链表存储结构中，删除P所指的结点时可修改指针：p->next->prior=p->prior;p->prior->next=p->next;二、双向链表指针p的结点前插入一个指针q的结点操作是:q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;四、 各类存储结构综合一、 顺序表结构适宜于进行随机存取，而链表适宜于进行顺序存取。二、 单链表的每一个结点包括一个指针域，双向链表的每一个结点包括两个指针域。五、 例题和算法设计例1：顺序表中第一个元素的存储地址是50，每一个元素的长度为4，那么第10个元素的地址是：LOC(a)=LOC(a)+(10-1)*4=86101例2：在带头结点的单链表中删除一个最小值结点的算法。voiddelete(Linklist*L){Linklist*p,*q;p=L；q=L->next；while(q&&q->next){if(q->next->data<p->next->data)p=q；q=q->next；}if(p->next){q=p->next；p->next=q->next;free(q)；}}〃终止算法delete。例3：已知不带头结点的线性链表list,链表中结点构造为(data、link)，其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大从头链接。LinkedListLinkListSort(LinkedListlist)〃list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大从头链接。{p=list->link; 〃p是工作指针，指向待排序的当前元素。list->link=null;〃假定第一个元素有序，即链表中现只有一个结点。while(p!二null){r=p->link;〃匸是卩的后继。q=list;if(q->data>p->data、〃处置待排序结点p比第一个元素结点小的情形。{p->link=list;list二p;〃链表指针指向最小元素。}else〃查找元素值最小的结点。{while(q->link!=null&&q->link->data<p->datA、q=q->link;p->link=q->link;〃将当前排序结点链入有序链表中。q->link=p;}p二r;〃p指向下个待排序结点。}}例4：将一个带头结点、数据项递增有序的单向链表，从头排列链表，使数据项递减有序。voidinvert(Linklist*la){linklist*p,*q;p=la->next；la->next=NULL；while(p!=NULL){q=p->next；p->next=la->next；p=q；}}第3章栈和队列一、栈一、栈的特点：先进后出或称作后进先出二、入栈与出栈序列3、空栈：是不包括任何元素的栈4、栈的应用(1)在判别表达式中左，右括号是不是配对显现的算法中，采纳栈作为数据结构最正确。(2)在表达式求值、进制转换、函数或进程的挪用等算法中，都要用到栈。二、队列一、队列的特点：先进先出，在队列中，通常许诺删除的一端称为队头，许诺插入的一端称为队尾。二、队列的应用：解决运算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区，该缓冲区的逻辑结构确实是一个队列。3、循环队列中的元素个数计算公式。4、对顺序栈作操作运算时，进栈应先判别栈是不是满，出栈时应先判别栈是不是空。且顺序队列和循环队列关于队满和队空的判定条件是不一样的。五、设循环队列寄存在向量［M+1］中，设：队头指针为，队尾指针为，采用捐躯一个单元的方法来区分队满和队空。那么：出队操作时，队头指针转变可表示为：=(s.front+l)%(M+l)；队满的条件为：_(s.rear+l)%(M+l)==；三、 栈与队列的存储栈和队列都是操作受限的线性结构，都能够用顺序存储和链式存储。四、 例题分析例1：有六个元素6，5，4，3，2，1的顺序进栈，那么：(543612)不是合法的出栈序列。例2：设一个栈的输入序列是1，2，3，4，5,以下序列中，(D)是栈的合法输出序列。A.51234 B.45132C.43125 D.32154例3：数组Q[n]用来表示一个循环队列，front为当前队列头元素的前一名置，rear为队尾元素的位置，假定队列中元素的个数小于n,计算队列中元素个数的公式为：(n+rear-fron)%n例4：假设为循环队列分派的向量空间为Q[25](下标从0开始)，假设队列的长 度和队头指针值别离为15和20，那么当前队尾指针的值为：10。例5：循环队列存储在数组A[0..m]中，那么入队时的操作为(D)。A.rear=rear+1 B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modm D.rear=(rear+1)mod(m+1)第4、5章串和数组一、串一、 串的长度的概念：是指串中所含字符的个数二、 子串的概念，例如：“DTA”不是“DATAA”的子串。3、 串的存储结构中，堆分派存储是一种动态存储结构。4、 空串是任意串的字串。二、数组一、数组的地址计算公式：设二维数组是A[c1..d1,c2..d2]，那个地址c1,c2不必然是0。那么行优先存储时的地址公式为：LOC(a)=LOC(a)+[(i-c)*(d-c+1)+j-c]*Li,j c1,c2 1 2 2 2二维数组列优先存储的通式为：LOC(a)=LOC(a)+[(j-c)*(d-c+1)+i-c]*Lij c1,c2 2 1 1 1二、特殊矩阵的紧缩存储及其地址映射公式三、例题分析例1：设有数组A[i,j]，数组的每一个元素长度为4字节，i的值为1到7,j的值为1到10，数组从内存首地址Loc开始顺序寄存，当用以行为主寄存时，元素A[4,6]的存储首地址为(Loc+140 )；当用以列为主寄存时，元素A[4,6]的存储首地址为(Loc+152)。例2：设有一个9阶的对称矩阵，采纳紧缩存储方式，以行序为主存储，a1，1为第一元素，其存储地址为1,每一个元素占2个地址空间，那么a的7，5地址为(51)，则a的地址为(51)。5，7例3：设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的顺序寄存在一维数组B[1..n(n+1)/2]中，对上述任一元素a(1Wi,jWn，ij且iWj)在B中的位置为(B)。A.i(i-l)/2+j B.j(j-l)/2+iC.j(j-l)/2+i-1 D.i(i-l)/2+j-1例4：A[N，N]是对称矩阵，将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中，那么对任一上三角元素a[i][j]对应T[k]的下标k是(B)。A.i(i-1)/2+jB.j(j-1)/2+iC.i(j-i)/2+1D.j(i-1)/2+1例5：有一个二维数组A[0:8,1:5],每一个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的地址是100,假设按行主顺序存储，那么A[3,5]的地址是176和A[5,3]的地址是208。假设按列存储，那么A[7,1]的地址是128,A[2,4]的地址是216。第6章树一、 二叉树概念一、 由3个结点能够构造出5种不同的二叉树。二、 二叉树中，指针p所指结点为叶子结点的条件是：p->lchild==null&&p->rchlid==null3、在二叉树中，每一个结点的两棵子树是有序的。二、 二叉树的性质一、 性质2：二叉的高与结点之间的关系二、 性质5：完全二叉树中双亲、左小孩与右小孩之间的关系及其应用3、完全二叉树和满二叉树的关系：满二叉树必然是完全二叉树，完全二叉树不必然是满二叉树。4、在满二叉树中，只有度为0或度为2的结点，不存在度为1的结点。五、性质3：度为0、一、2三类结点间的关系三、二叉树的遍历一、由二叉树的先序序列和中序序列能够唯一确信一棵二叉树。由二叉树的后序序列和中序序列能够唯一确信一棵二叉树。但由二叉树的先序序列和后序序列不能唯一确信一棵二叉树。二、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的前后顺序完全相同。四、树的存储结构、树的遍历、树与二叉树之间的转换一、把一棵树转换为二叉树后，这棵二叉树的形态是唯一的，且没有右子树。即：由树转化为二叉树，其根结点的右子树老是空的。二、树转换成二叉树3、树的存储形式有：双亲表示法、小孩链表表示法、小孩兄弟表示法等，但没有顺序存储表示法。4、树的遍历五、丛林转换成二叉树：注意其左右子树上的结点个数。设丛林F对应的二叉树为B,它有m个结点，B的根为p,p的右子树结点个数为n,丛林F中第一棵树的结点个数是m-n。若是丛林F中有三棵树，第一，第二，第三棵树的结点个数别离为M1,M2和M3。那么与丛林F对应的二叉树根结点的右子树上的结点个数是M2+M3。五、 哈夫曼树一、 特点二、 组成和应用六、 例题分析一、二叉树性质应用例1：一个具有1000个结点的二叉树的高h介于10至1000之间，一个具有1000个结点的完全二叉树的高h等于10。

例2：具有256个结点的完全二叉树的深度为9（注意：不能是8）。例3：如某二叉树有30个叶子结点，有40个结点仅有一个小孩，那么该二叉树的总结点数为：99。例4：一棵完全二叉树上有1000个结点，其中叶子结点的个数是500个，若是有1000个结点，那么其叶子结点的个数是501个。二、已知中序序列和后序序列确信一棵树，已知中序序列和先序序列确信一棵树例1：已知一棵二叉树的先序序列是ABDEFCGH，中序序列是DBFEACGH，请画出这棵二叉树，并给出后序序列。答：该二叉树如右图后序序列：DFEBHGCA例2：已知一棵二叉树的中序序列是DBEFAGHC，后序序列是DFEBHGCA，请画3、树和二叉之间的转换例：请按小孩兄弟表示法将以下树结构转换为对应的二叉树，并给出该树的一树的一种先序遍历序列：ABEFGCDHI树的一种后序遍历序列：EFGBCHIDA

4、哈夫曼树生成及哈夫曼编码例：假设用于通信的电文仅由7个字母组成，字母在电文中显现的次数别离为这8个字母设计哈夫曼编码。答：哈夫曼树如下（形状不唯一）10：101 24：115,30,8,10,7,16,24。请依照各个字符的显现概率构造一棵哈夫曼树，并为这8个字母设计哈夫曼编码。答：哈夫曼树如下（形状不唯一）10：101 24：11哈夫曼编码（编码不唯一）30:00 5：0100 7：0101 16:011 8：100_、图的概念和存储结构一、 图能够没有边，但不能没有极点。二、 邻接表和邻接矩阵都可用于存储有向图和无向图。3、 在有向图中,＜v1,v2＞与＜v2,v1＞是两条不同的边。4、 在无向图G的邻接矩阵A中，假设A[i][j]等于1,那么A[j][i]等于1。五、完全图中，极点数和边数的关系二、 图的遍历一、 图的遍历方式：深度优先遍历、广度优先遍历二、 假设从无向图的任意一个极点动身进行一次深度优先搜索能够访问图中所有的极点，那么该图必然是连通图。3、 用邻接表表示图进行广度优先遍历时，通常借助队列来实现算法。4、 深度优先遍历算通常采纳递归或借助栈来实现。三、 最小生成树一、 带权图最小生成树不必然是唯一的，能够有一棵或多棵，但其最小生成树的代价是唯一的二、 最小生成树的两种生成算法四、 AOV网与AOE网一、拓扑排序方式能够判定出一个有向图是不是有环。

%■()1]1[01]100]0Q]1U100110011010110100001[01*1100010五、例题分析例1：具有9个极点的有向完全图有72条弧。具有9个极点的无向图，边的总数最多为36。例2：图的邻接矩阵如右图所示，那么从极点v0动身按深度优先遍历的结果是(0,3,6,1,5,4,2)例3：已知一个图的采纳二维数组表示的邻接矩阵如 下图所示，请回答以下问题：画出该邻接矩阵对应的图请画出自极点v1动身进行遍历所得的深度优先遍历生成树。v1v2v3v4v5v6V1011101v2101010v3110100答：该图为：101/001例4：已知一个图的采纳二维数组表示的邻接表如下图所示，请回答以下问题:画出该邻接表对应的图请画出自极点v1动身进行遍历所得的广度优先遍历生成树。

一、顺序查找和索引（分块）查找的算法思想一、索引查找中，数据的组织特点是：块内可无序，块间要有序。二、假设查找表的长度为n那么顺序查找法的平均查找长度为（n+1）/2。3、顺序查找算法能够适用于有序表、无序表，能够采纳顺序存储和链式存储。二、 折半查找一、 适用于折半查找的表的存储方式及元素排列要求：顺序方式存储，元素有序二、 折半查找中，元素的比较次数3、对有序表而言，采纳折半查找并非是总比采纳顺序查找法速度快。三、 二叉排序树一、概念：二叉排序树的左子树不为空，那么左子树上所有结点的值均小于它的根结点值，右子树不为空，则右子树上所有结点的值均大于它的根结点的值。二、关于一个二叉排序树，按二叉树层次进行遍历能够取得一个有序序列。3、关于两棵具有相同关键字但形状不同的二叉排序树，按中序遍历它们取得的序列的顺序是一样的。4、平稳二叉树中某一结点左子树的深度减去右子树的深度称为该结点的平稳因子。四、哈希查找一、散列法是一种将关键字转换为存储地址的存储方式。二、哈希函数的选择要视情形而定，不存在专门好与坏的哈希函数。3、哈希表的生成五、例题分析一、折半查找例一、在有序表A[1..25]中，按二分查找方式进行查找，查找长度为5的元素个数是10个例2：在有序表（3，5，8，15，25，34，55，78，90，100）中采纳折半查找方式，查找表中元素58，那么它将依次与表中（25，78，340，55）比较大小，查找结果是失败。二、二叉排序树构造例1：别离以以下序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（B）。A．（105，85，95，60， 125，110，140)B．（105，60，85， 95， 125，110，140)C．（105，125，110，140，85，60，95)D．（105，85，60，95， 125，140，110)例2：给定关键字序列21，88，20，10，13，12，24，31，若采纳二叉排序树查找，请回答以下问题：（1） 画出二叉排序树查找的二叉排序树。（2） 假定每一个元素的查找概率相等，那么查找成功时的平均查找长度是多少？答：(1)二叉排序树(关键字顺序已确信，该二叉排序树唯一)如以下图从上图能够取得二叉排序树查找的成功平均查找长度为：ASL=(1+2*2+3*2+4*2+5*1)/8=33、哈希表构造例1：设哈希表长为15，哈希函数是H(key)二key%ll,表中已有数据的关键字为26，38，72，84共四个，现要将关键字为49的元素加到表中，用线性探测再散列法解决冲突，那么放入的位置是：8；用二次探测法解决冲突，那么放入的位置是：9。例2：设哈希(Hash)表的地址范围为0〜17,哈希函数为：H(K)=KMOD16。K为关键字，用线性探测法再散列法处置冲突，输入关键字序列：(10，24，32，17，31，30，46，47，40，63，49)造出Hash表，试回答以下问题：按关键字的输入顺序构造哈希表，画出所构造哈希表的示用意。求所构造哈希表查找成功时的平均查找长度ASL。答：(1)最后取得的哈希表示用意如下表所示：012345678910111213141516173217634924401030314647(2) ASL=1/11(6+2+3X3)=17/11=1.5454545454例3、设关键字的输入序列为：(47，7，29，11，16，92，22，8，3)，哈希表的地址范围为0〜10，哈希函数为：H(K)=KMOD11，K为关键字值，采纳线性探测法处置冲突，请回答下面两个问题：(1)按关键字的输入顺序构造哈希表，画出所构造哈希表的示用意。（2）求所构造哈希表查找成功时的平均查找长度ASL。答：（1）最后取得的哈希表示用意如下表所示：地址编号012345678910关键字值112247921637298(2)ASL=(l+2+l+l+l+4+l+2+2)/9=5/3二第10章排序一、各类排序的算法思想一、内部排序的概念：内部排序确实是整个排序进程完全在内存中进行的排序。二、算法稳固性的概念。二、插入排序一、直接插入排序时，关键字的比较次数与记录的初始排列有关，初始序列顺序时比较次数最少，初始序列倒序时比较次数最多。二、直接插入排序的思想。3、 希尔排序的算法思想，能写出每一趟排序的结果序列。4、 希尔排序是不是是稳固的排序方式，并能说明缘故。三、选择排序一、概念：从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方式，称为选择排序二、堆排序：关于一个堆，按二叉树层次进行遍历不能取得一个有序序列。四、互换排序一、 对n个不同的关键字由小到大进行冒泡排序，在从大到小排列好（倒序）的情形下比较的次数最多，属于最坏的情形，其需要的时刻是O（n2）。在从小到大排列好（顺序）的情形下比较的次数最少。二、 快速排序算法思想及其应用，能写出每一趟排序的结果序列。3、快速排序是不是是稳固的排序方式，并能说明缘故。五、 归并排序一、对n个记录的集合进行归并排序，所需要的时刻是O（nlog2n）。六、 例题分析与算法描述一、插入排序例1：给定一组关键字序列｛15，25，10，40，25*，35，12，30，20，24，5｝,其中20和20*表示值相同的两个关键字，采纳希尔排序方式由小到大排序，dk依次取5,3,1。（1） 请写出排序进程（每趟排序的结果序列）。（2） 希尔排序是不是稳固的排序？什么缘故？答：（1）每趟排序的结果序列为：初态：15，25，10，40，25*，35，12，30，20，24，5第一趟（Dk=5）:5,12,10,20,25*,15,25,30,40,24,35第二趟（Dk=3）：5,12,10,20,25*,15,25,30,40,24,35第三趟（Dk=1）：5,10,12,20,15,25*,25,24,30,35,40最后取得的排序序列为：5,10,12,20,15,25*,25,24,30,35,40（2）希尔排序不是稳固的排序,因为值相同的两个关键字25和25*在排序前后位置发生了改变。例2：对序列｛16,10,7,8,22,1,5｝进行排序,进行一趟排序后,取得的排列为｛10,16,7,8,22,1,5｝，那么采纳的是（C）排序算法。A.简单选择 B.希尔 C.直接插入 D.归并二、堆排序例1：假设一组记录的排序码为（50,79,56,38,40,90）,那么利用堆排序的方式成立的初始堆为（90,79,50,38,40,46 ）。例2：以下关键字序列中,（D）是堆。A.16,72,31,23,94,53 B.94,23,31,72,16,53C.16,53,23,94,31,72 D.16,23,53,31,94,723、快速排序和冒泡排序例1：假设一组记录的排序码为（50,79,56,38,40,85）,那么利用快速排序的方式,以第一个记录为基准取得的一次划分结果为：40,38,50,56,79,85例2：设有一个整型数组中寄存了一个无序的序列k一.k二、…、kn。现要求将kn放在将元素排序后的正确位置上，要求比较关键字的次数不超过n。那么可用快速排序算法。例3：设有一个整型数组中寄存了一个序列k一.k二、…、kn。实现该序列的升序排列。要求：该算法在最好情形下(原始序列为升序时)一趟排序能够终止，时刻复杂度为O(n)。那么可用冒泡排序算法。例4：关键字序列为｛20，14，20*，33，87，22，2，10，72｝，其中，18和18*表示两个值相等的关键字，采纳快速排序算法由小到大进行排序，请回答下面两个问题：(1)写出排序进程(每趟排序后的关键字序列)。(2)快速排序是不是稳固的排序算法？什么缘故？答：(1)每趟排序结果初始序列：［20，14，20*，35，90，25，2，10，75］第一趟：［101420*2]20[25903575