还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
、数据结构的章节结构及重点构成数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表,树和二叉树,图,查找,内排,外排,文件,动态存储分配对于绝大多数的学校而言,外排,文件,动态存储分配〃三章基本上是不考的,在大多数高校的计算机本科教学过程中,这三章也是基本上不作讲授的数据结构的章节比重大致为概论概念,时间复杂度
1.2,线性表:基础章节,必考内容之一概念,算法设计题栈和队列:基本概念
3.串基本概念
4.,多维数组及广义表基本概念
56.树和二叉树•重点难点章节,各校必考章节概念,问答,算法设计题
7.图:重点难点章节,各校必考章节概念,问答,算法设计题8,查找重点难点章节,概念,问答9,排序重点难点章节,问答各种排序算法的排序过程
二、各章节的主要内容:第一章概述主要内容本章主要起到总领作用,为读者进行数据结构的学习进行了一些先期铺垫大家主要注意以下几点()数据结构的基本概念(数据;数据元素;数据项;数据结构;数据的逻辑结构线性和非线性,具体1分为集合、线性结构、树形结构和图状结构;数据的存储结构顺序存储和链式存储;运算)()算法的度量时间效率和空间效率,分别用时间复杂度和空间复杂度度量,掌握时间复杂度的度量方法2量方法(大0表示法)参考题目填空题、数据结构是相互之间存在一种或者多种特定关系的数据元素的集合,它包括三方面的内容,分别是数据1的逻辑结构、()和()O、数据结构按逻辑结构可分为两大类,它们分别是()和()2数据的物理结构主要包括()和()两种情况
3.线性表,栈,队列和二叉树四种数据结构中()是非线性结构,()是线性结构
4.、线性结构中元素之间存在()关系,树形结构中元素之间存在()关系,图形结构中元素之间5存在()关系
6、程序段的时间复杂度是o()for i=l;i=n;i++{k++;()for j=l;j=n;j++查找和排序现实生活中,几乎无处不在,特殊是现在的网络时代,万事离不开小到文档内文search search,字的搜索,大到上的搜索,占领了我们上网的大部份时间INTERNET search在的教材中,普通将分为三类在顺序表上的查找;在树表上的查找;在哈希表上的查找本DS search:123次复习这一章的知识时,要掌握以下内容关键字、主关键字、次关键字的含义;静态查找与动态查找的含义及区别;1线性表上的查找顺序查找和二分查找及其比较次数23基本哈希表的查找算法参考题目、顺序查找法适合于存储结构为____的线性表1散列存储顺序存储或者链接存储A.B.压缩存储索引存储C.D.、在查找过程中,若同时还要做增、删工作,这种查找则称为2静态查找动态查找内查找外查找A.B.C.D.、对线性表进行二分查找时,要求线性表必须3以顺序方式存储以顺序方式存储且元素有序A.B,以链接方式存储以链接方式存储且元素有序C.D.、在有序表中二分查找关键字时所需进行的关键字比较次数为412,24,36,48,60,72,
8472、折半查找有序表若查找表中元素它将挨次与表中元素54612,20,28,38,50,70,88,100,20,_______________________比较大小简答题、已知散列函数为关键值序列为1H k=k mod13,19,01,23,14,55,20,84,27,68,11,10,处理冲突的方法为线性探测法,散列表长度为7713构造哈希表画不意图;1计算装填因子;2计算查找成功情况下的平均查找长度;3采用哈希函数并用线性探测开放地址法处理冲突,在数列地址空间[]中对关
2.Hk=3*k mod
130..12键字序列22,15,40,46,17,13,14,28,38构造哈希表画示意图;1装填因子;2等概率下成功的平均查找长度3答哈希地址0123456789101112关键字比较次数装填因子二23ASL=SUCC.已知散列函数为关键值序列为{表长为采用链表处理冲突3H k=k mod7,19,01,23,14,55,68,11,82,36,7构造哈希表画示意图;1()计算查找成功情况下的平均查找长度2己知一个有序表为当二分查找法为和的元素时,分别需要多少次
4.{12,18,20,25,29,32,40,62,83,90,95,98},2990比较才干查找成功若采用顺序查找时,分别需要多少次比较才干查找成功?第八章内部排序主要内容内排是课程中最后一个重要的章节,考查你对书本上的各种排序算法及其思想以及其优缺点和性能DS指标(时间复杂度)能否了如指掌从排序算法的种类来分,本章主要阐述了以下几种排序方法:插入、选择、交换、归并、计数等五种排序方法本次复习这一章的知识时,要掌握以下排序算法的思想()简单选择排序1()快速排序(用中间数将待排数据组一分为二)2()冒泡排序3()了解插入排序,堆排序和归并排序排序(是通过控制每次参预排序的数的总范围“由小到大”的增量4来实现排序效率提高的的)H给出关键字序列,能够写出每趟排序过程参考题目、关键字序列为()采用快速排序以第一个记录为基准得到的第一次划分结果是(17,6,8,4,3,5,)o()A.5,3,6,4,7,8B.3,5,6,4,7,8C.6,4,3,5,7,8D.(5,6,3,4,7,8)初始记录关键字序列为
2.45,80,55,A.45,55,40,42,80,85B.42,40,45,80,85,88C.40,80,55,45,42,85D.42,40,45,85,55,80)则以选择排序法得到的第一趟排序的结果是()40,42,85,A.1B.2C.n-1D.n稳定的排序方法是
4.o直接插入排序和冒泡排序直接插入排序和快速排序B,A,.堆排序和归并排序排序是简单选择排序和直接插入排序DC.稳定的在快速排序、堆排序、归并排序中,简
6.答用冒泡排序的方法对个数据进行排序,第一趟共比较()对元素
3.n写出对关键字序列()分别使用冒泡排序和选择排序算法的每一趟排序结
1.40,24,80,39,43,18,20果、有一组关键码序列()分别采用选择排序和快速排序方法由小到大进行排序,请写出每238,19,65,13,97,49,趟排序的结果x=x+k;,下列算法的时间复杂度是7ofori=0;im;i++;forj=0;jn;j++a[i][j]=i下列算法的时间复杂度是
8.二i=s0;二whilesn{i++;s+i;}判断题:、在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻()
1、顺序存储方式优点是存储密度大,且插入和删除运算效率高()
2、线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同()3第二章线性表主要内容作为线性结构的开篇章节,线性表一章在线性结构的学习乃至整个数据结构学科的学习中,其作用都是不可低估的在这一章,第一次系统性地引入链式存储的概念,链式存储概念将是整个数据结构学科的重中之重,无论哪一章都涉及到了这个概念线性表一章注意以下几个方面().线性表的相关基本概念,如:前驱、后继、表长、空表、首元结点,头结点,头指针等概念1()线性表的结构特点,主要是指:除第一及最后一个元素外,每一个结点都惟独一个前趋和惟独一个后继2()线性表的顺序存储方式及基本运算(插入、删除操作、平均挪移次数、时间复杂度)3()线性表的链式存储方式及基本运算(单链表插入、删除,求长度操作、平均挪移次数、时间复杂度)4()顺序存储和链式存储的特点,不同之处5()线性表的简单算法题6参考题目
一、选择题、线性表是()1一个有限序列,可以为空一个有限序列,不能为空A.B.一个无限序列,可以为空一个无限序列,不能为空C.D.、在表长为的顺序表上做插入运算,平均要挪移的结点数为()2nA.n B.n/2C.n/3D.n/
4、链表不具有的特点是()3随机访问不必事先估计存储空间A.B.插入删除时不需挪移元素所需的空间与线性表成正比C.D.、带头结点的单链表为空的判定条件是()4head;;;;A.head=NULL B.head-next=NULL C.head-next=head D.head!=NULL、在一个单链表中,若所指结点不是最后结点,在之后插入所指结点,则执行()5P PS;A.S-next=P-next;P-next=S B.P-next=S-next;S-next=P;;C.P-next=P;P-next=S D.P-next=S;S-next=P、在已知头指针的单链表中,要在其尾部插入一新结点,其算法所需的时间复杂度为6A.01B.0log nC.0n D.0nz
2、在一个单链表中,已知所指结点是所指结点的直接前趋,若在之间插入结点,则执行的操作是7q pp,q sA.s-next=p-next;p-next=s;B.q-next=s;s-next=p;C.p-next=s-next;s-next=p;D.p-next=s;s-next=q;、设顺序线性表中有个数据元素,则第个位置上插入一个数据元素需要挪移表中个数据元素,8n i删除第个元素时,需向前挪移的元素的个数是在顺序表中插入一个元素,需要平i lWWn均挪移元素,删除一个元素,需要平均挪移元素,具体挪移的元素个数与有关,插入删除操作的时间复杂度均为o、设单链表的结点结构为为指针域,已知指针指向单链表中为的结点,指针指向9data,next,next pxdata xpy为的新结点,若将结点插入结点之后,则需要执行以下语句data yy xo设指针变量指向单链表中结点的前驱结点,若删除单链表中结点则执行操作
10.p A A,
三、算法设计设计算法,计算顺序表中数据元素为的元素个数L x顺序表结构如下typedef struct{int data
[100];int length;}sqlist;函数首部为int countsqlistL,int x设计算法,在顺序线性表中,删除顺序表中第个元素,顺序表结构同上题函数首部为
2.i intdel sqlist*L,inti.设计算法,在顺序线性表中,删除值为的元素3x函数首部为void delxsqlist*L,int x对给定的单链表元素各不相同,编写一个删除中值为的结点的算法链式结构如下
4.L Lxtypedef struct LinkList{int data;structLinkList*next;}Node,*LinkList;int delxLinkList*head,int x编写算法求带头结点的单链表的表长,结构同上题
5.int countLinkList*head第三章栈与队列主要内容:栈与队列,是不少学习的同学遇到第一只拦路虎,不少人从这一章开始坐晕车,向来晕到现在DS栈和队列一章注意以下几个方面()栈的定义及其相关数据结构的概念合法的出栈序列、出栈序列个数、顺序栈,链栈1()队列的定义及其相关数据结构的概念,包括:循环队列2()栈和队列的特点栈一后进先出;队列一先进先出3()递归算法概念栈与递归的关系,所有的递归算法都可以借助栈将递归转向于非递归算法4()操作顺序栈的进栈、出栈操作循环队列的队空、队满条件,出队、入队、求队列元素个数5操作参考题目循环队列是空队列的条件是()
1.()A.Q.rear==Q.front B.Q.rear+1%maxsize==Q.front C.Q.rear==0D.Q.front==0链栈与顺序栈相比,比较明显的优点是()
2.通常不会浮现栈满的情况通常不会浮现栈空的情况A.B.插入操作更加方便删除操作更加方便C.D.若一个栈的输入序列是输出序列的第一个元素是,则第个输出元素是()
3.123,……,n,n i不确定A.n-i B.n-i+1C.i D.•对于一个栈,给定输入序列为则下列不可能为输出序列的是()41,2,3,A.1,2,3B.3,2,1C.3,1,2D.2,1,3栈是限定在()处进行插入或者删除操作的线性表
5.端点栈底栈顶中间A.B.C.D.当循环队列是满队列时,存放队列元素的数组有个元素,则中存放()个数据元素
6.q datan dataA.n B.n-1C.n-2D.O循环队列用数组丁存放其元素值,已知其头尾指针分别是和则当前队列中的元素个数是
7.elem[0,1]front rear,O栈的特点是,队列的特点是
8.Io设栈和队列的初始状态为空,元素挨次通过栈,一个元素出栈后即将进入队列若
9.S Qel,e2,e3,e4,e5,e6Q,个元素出队的顺序是则栈的容量至少应该是6e2,e4,e3,e6,e5,el,S若用一个大小为的一维数组来实现循环队列,当前和的值分别是和从队列中删除一个元素,
10.6rear front03,再加入两个元素后,当前队列中共个元素,的值为的值为rear,front第四章串主要内容最容易自学的章节之一本章注意()串的基本概念串(串是其元素均为字符型数据的特殊线性表),子串、空串与空格串的区别,串相等1的条件、模式匹配()串的定长顺序存储2()串的基本操作功能,如求串长,串联接,串替换等,给出一个字符串能够写出操作的结果3参考题目:串是一种特殊的线性表,其特殊性体现在
1.o,则在中的位置是
2.Sl=ABCD”S2=CD”S2SI假设,的结果是
3.S=abcaabcaaabca”,T=bca IndexS,T,36设有函数返回和串的连接串,返回串的从序号的字符开
4.SUABCDEFG,S2=ZPQRST,conx,y xy subsS,i,j Si始的个字符组成的子串,返回串的长度,则的结果是j lenss consubsSl,2,lenS2,subsSl,lenS2,2在串中,,的结果是
5.SubStringstudent5,2假设〃〃,〃〃,〃,结果是_
4.S=abcaabcaaabca T=bca V=x ReplaceS,T,V两个串相等的充分必要条件是且
7.o子串的定位操作通常称为
8.o第五章数组与广义表主要内容多维数组中某数组元素的存储位置求解普通是给出数组元素的首元素地址和每一个元素占用的地址1空间并组给出多维数组的维数,然后要求你求出该数组中的某个元素所在的位置明确按行存储和按列存储的区别和联系,并能够按照这两种不同的存储方式求解中类型的题21稀疏矩阵的压缩存储概念,三元组表和十字链表存储3广义表的概念,理解广义表的递归特性,特殊应该明确表头与表尾的定义4广义表的存储特性一难以用顺序存储结构存储能画出头尾表示法5广义表的操作和给出一个广义表能够写出取表头和取表尾操作的结果6GetHead GetTail,参考题目常对数组进行的两种基本操作是
1.建立与删除索引和修改A.B.对数据元素的存取和修改查找与索引C.D.二维数组中,每一个元素的长度为个字节,行下标从到列下标从到从首地址开始连续存
2.AA3i7,j09,SA放在存储器内,该数组按行存放时,数组元素⑺⑷的起始地址为AoA.SA+141B.SA+144C.SA+222D.SA+225对稀疏矩阵进行压缩存储目的是
3.o已知广义表则运算的结果为
4.A=a,b,B=A,A,C=a,b,A,B,tailheadtailC求下列广义表操作的结果
5.1GetTail[GetHead[a,b,c d]]=,2GetTail[GetHead[GetTail[a,b,c,d]]]=第六章树与二叉树主要内容从对线性结构的研究过度到对树形结构的研究,是数据结构课程学习的一次跃变,此次跃变完成的好坏,将直接关系到你到实际的考试中是否可以拿到高分,而这所有的一切,将最终影响你的专业课总分所以,树这一章的重要性,已经不说自明了总体来说,树一章的知识点包括()二叉树的概念、性质性质非常重要1()二叉树的存储结构顺序存储和二叉链表存储2()二叉树遍历的三种算法(
①给二叉树能写出遍历序列,根据遍历序列可以构造二叉树;
②遍历递归算法3(二叉树的其他算法不少都是在遍历的基础上得到的)、在三种基本遍历算法的基础上实现二叉树的其它算法(如求叶子结点、总结点、高度等,子细揣摩求解思路)()线索二叉树的概念(利用二叉链表存储时的空链域指向前驱和后继,空链域个数;给出一棵二叉树能4画出对应的线索二叉树,如—图)P
1496.16()树、森林的概念,树与森林的遍历算法(给出树或者森林,能写出其要求的遍历序列),树和森林的5遍历算法与二叉树遍历算法的联系()树与森林和二叉树的相互转换6()最优二叉树的概念,哈夫曼树的概念,特点(惟独和2的结点),能够按指定权值建立哈夫曼树,给7出哈夫曼编码,计算WPL树一章,处处是重点,道道是考题,大家务必个个过关参考题目、在具有个结点的彻底二叉树中,结点()的父结点是()1n iil不存在」A.2i B.C.2i+l D.[i/
2、下列陈述中正确的()2二叉树是度为的有序树A.2二叉树中结点惟独一个孩子时无摆布之分B.二叉树中必有度为的结点C.2二叉树中最多惟独两棵子树,并且有摆布之分D.、以二叉链表作为二叉树的存储结构,在具有个结点的二叉链表中()空链域的个数为()3n n0,A.2n-1B.n-1C.n+1D.2n+
1、将一棵有个结点的彻底二叉树从上到下,从左到右挨次对结点进行编号,根结点的编号为则编号为41001,的结点的左孩子编号为()49A.99B.98C.50D.
48、在一棵具有五层的满二叉树中,结点总数为()5A.31B.32C.33D.16A.2k-i-l B.2k-i C.2k-i+l D.2k-
1、三个结点可以构成()种不同形状的二叉树7A.D.51B.2C.
3、树中所有结点的度之和等于所有结点数加()O8D.2A.0B.1C.-1则度为的结点数为(),度为的结点数为()
21、含有个结点的二叉树中,度为的结点数为9104,D.6A.3B.4C.5)、有个叶结点的哈夫曼树所具有的结点数为(10m深度为的彻底二叉树中至少有()个结点
6.k填空A.m B.m+1C.2m D.2m-1若某二叉树有个叶子节点,有个节点仅有一个孩子,则该二叉树的总的节点数是
1.2030o设二叉树中度数为的结点数为度数为的结点数为则该二叉树中总共有一个结点
2.050,130,.若前序遍历二叉树的结果为序列、、则有棵不同的二叉树可以得到这一结果3A BC,线索二叉树的左线索指向其,右线索指向其
4.o、已知彻底二叉树的第层惟独个结点,则该树共有个叶子结点5T57简答.已知一棵二叉树的先序遍历序列中序遍历序列为构造该二叉树,写出后序序列1EFHIGJK,HFIEJGK,.已知一棵二叉树的前序序列为中序序列为请画出该二叉树,写出后序序列2ABCDEFGH,CBEDFAGH,,已知一棵二叉树的后序序列,中序序列,请画出该二叉树,写出先序序列3“cdbgfea“cbdaegf”.根据后序序列〃和中序序列〃构建二叉树,并给出其先序序列4“cedbhjigfa“cbedahgijf.假设用于通信的电文字符集为各字母浮现次数分别为现需求这些字母的最优编码,计5{A BC DE},{29576},算树的带权路径长度huffman.假设用于通信的电文由个字母组成,其频率分别为试构造相应的哈夫曼68a,b,c,d,e,f,g W={5,2,9,11,8,3,7},树,给出每一个字母的编码,并计算它的带权路径长度haffman
三、算法设计.编写算法求二叉树中叶子结点的数目1数据结构定义为typedef struct Node{int data;struct Node*Lchild;structNode*Rchild;}BiTNode,*BiTree;函数首部为()int leafBiTree*root利用二叉树遍历算法求二叉树的高度,假设根结点的高度为
2.
1.()int DepthBiTree*root以二叉链表为存储结构写出求二叉树结点总数的算法
3.第六章图主要内容如果说,从线性结构向树形结构研究的转变,是数据结构学科对数据组织形式研究的一次升华,那末从树形结构的研究转到图形结构的研究,则进一步让我们看到了数据结构对于解决实际问题的重大推动作用图这一章的特点是:概念繁多,与离散数学中图的概念联系密切,算法复杂,考研时极易被考到,且容易出大题,如果不考查树与图两章的知识,几乎是不可想像的主要知识点如下
(1)图的基本概念图的定义和特点,无向图,有向图,入度,出度,彻底图,生成子图,路径长度,回路,(强)连通图,(强)连通分量、生成树等概念与这些概念相联系的相关计算题也应该掌握(如有向(无向)彻底图边的条数、生成树的边的条数等)()图的存储形式只看邻接矩阵和(逆)邻接表2()图的两种遍历算法:深度遍历和广度遍历,能够画出任意一幅图的深度优先搜索生成树和广度优先搜索生3成树()生成树、最小生成树的概念以及最小生成树的构造算法和算法4RIM KRUSKAL考查时,普通不要求写出算法源码,而是要求根据Prim算法、Kruskal算法构造该图的最小生成树,画出其构造过程及最平生成的最小生成树以下内容考研很重要()拓扑排序问题5拓扑排序有两种方法,一是无前趋的顶点优先算法,二是无后继的顶点优先算法换句话说,一种是“从前向后”的排序,一种是“从后向前”排固然,后一种排序出来的结果是“逆拓扑有序”的要求按指定图,写出拓扑排序序列()关键路径问题6这个问题是图一章的难点问题理解关键路径的关键有三个方面:一是何谓关键路径,二是最早时间是什么意思、如何求,三是最晚时间是什么意思、如何求关键路径问题是工程进度控制的重要方法,具有很强的实用性要求对指定图,写出关键路径最短路径问题与关键路径问题并称为图一章的两只拦路虎概念理解是比较容易的,关键是算法的理解7最短路径问题分为两种:一是求从某一点出发到其余各点的最短路径;二是求图中每一对顶点之间的最短路径这个问题也具有非常实用的背景特色,一个典型的应该就是旅游景点及旅游路线的选择问题解决第一个问题用DIJSKTRA算法,解决第二个问题用FLOYD算法注意区分参考题目、在一个具有个结点的无向图中,要连通全部结点至少需要1n・条边条边条边条边A nB.n+1C.n-1D.n/
2、最小生成树指的是2由连通图所得到的边数至少的生成树A.由连通图所得到的顶点相对较少的生成树B.连通图的所有生成树中权值之和最小的生成树C.连通图的极小连通子图D.、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的3倍倍倍倍A.1/2B.1C.2D.
4、有个结点的无向图的边数最多为4nA.n+1B.n n-1/2C.n n+1D,2n n+
1、若个顶点的无向图采用邻接矩阵存储方法,该邻接矩阵是一个5n普通矩阵对称矩阵对角矩阵稀疏矩阵A.B.C.D.下列算法中,算法用来求图中每对顶点之间的最短路径
6.A.Dijkstra B.Floyed C.Prim D.Kruskal、最小生成树的构造可使用7Ao算法冒泡算法迪杰斯特拉算法哈夫曼算法A.prim B.C.D.、有个结点的有向彻底图有条边88CA.14B.28C.56D.
112、已知有向图其中9G=V,E,V={V1,V2,V3,V4,V5,V6,V7},E={V1,V2,V1,V3,的拓扑序歹是V1,V4,vV2,V5,vV3,V5,vV3,V6,vV4,V6,vV5,V7,vV6,V7},G UA.V1,V3,V4,V6,V2,V5,V7B.V V V V,V,V V1532564557C・VVV,V,V,V,V D.153545267设无向图中的边的集合则从顶点出发进行深度优先遍历
10.G E={a,b,a,e,a,c,b,e,e,d,d,f,f,c},a可以得到的一种顶点序列为o有个顶点组成的无向连通图,最多可以有条边
11.N简答题给出下图中从出发的深度优先遍历序列和广度优先遍历序列
1.a0求下图的最小生成树,要求分别用算法和算法,算法从定点出发画出最小生成树的生
2.prim kruskalprim1成过程求下图的最小生成树,要求分别用算法和算法,树的算法从定点出发画出最小生成
3.prim kruskalprim a生成过程.已知图如下所示,列出图的邻接表,写出拓扑排序序列(写出一种即可),求出关键路径4G G已知图如下所示,列出图的邻接表,写出拓扑排序序列(写出一种即可),求出关键路径
5.G G第七章查找主要内容在不少数据结构的教材中,是把查找与排序放入高级数据结构中的应该说,查找和排序两章是前面我们所学的知识的综合运用,用到了树、也用到了链表等知识,对这些数据结构某一方面的运用就构成为T。