数据结构考点(范围缩小版)

数据结构考点第一章绪论什么是数据结构？(选择)在应用程序中涉及到各种各样的数据，如何在计算机中组织、存储、传递数据，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，依此实现软件功能。综上，描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构。因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现。什么是算法？(选择)算法定义：为了解决某类问题而规定的一个有限长的操作序列。第二章线性表线性表的定义(选择)n(0)个数据元素的有限序列，记作q,.叫,a,a+i,...,a)其中卩是表中数据元素，n是表长度。 ' ”顺序表的定义(选择)将线性表中的元素相继存放在一个连续的存储空间中。用顺序表实现“交并减(算法)集合的“并”运算voidUnion(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);for(inti=0;i<m;i++){intx=GetData(B,i);〃在B中取一元素intk=Find(A,x); 〃在A中查找它if(k==-1) //若未找到插入它{Insert(A,x,n); n++;}}}集合的“交”运算voidIntersection(SeqList&A,SeqList&B){intn=Length(A);intm=Length(B);inti=0;while(i<n){intx=GetData(A,i);//在A中取一元素intk=Find(B,x); 〃在B中查找它if(k==-1){Delete(A,i);n--;}elsei++; 〃未找到在A中删除它}}链表的定义（选择）链表是线性表的链接存储表示。单链表是用一组地址任意的存储单元存放线性表中的数据元素。5.单链表的结构（选择）每个元素由结点（Node）构成,,它包括两个域:数据域Data和指针域Link。6.单链表的插入删除（应用）带头结点①插入第一种情况：在第一个结点前插入newnode->link=first;first=newnode;第二种情况：在链表中间插入newnode->link=p->link;p->link=newnode；第三种情况：在链表末尾插入newnode->link=p->link;？p->link=newnode；若将要插入的位置的节点命名为P，可简化为q->link=p->link;P->link=q;②删除在单链表中删除ai结点q=P->link;P->link=q->link;deleteq;算法：扫描两个多项式，若都未检测完：若当前被检测项指数相等，系数相加。若未变成0，则将结果加到结果多项式若当前被检测项指数不等，将指数小者加到结果多项式。若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。8.顺序表与链表的比较(选择)基于空间的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度＜1基于时间的比较存取方式顺序表可以随机存取，也可以顺序存取链表是顺序存取的插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针第三章栈和队列栈的定义与特点(选择)定义:是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)。特点：后进先出(LIFO)。顺序栈的定义(选择)栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。顺序栈压入与弹出(不考)①压入StatusPush(SqStack&S,SElemTypee){//将元素e插入栈成为新的栈顶元素,要考虑上溢情况if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e; //元素e插入栈顶，修改栈顶指针returnOK;}//Push②弹出StatusPop(SqStack&S,SElemType&e){〃若栈不空，则删除S的栈顶元素，用e返回其值并返回OK，否则返回ERRORif(S.top==S.base)returnERROR;//栈空，返回ERRORe=*--S.top;//删除栈顶元素，用e返回其值，并修改栈顶指针returnOK;}//Pop链栈的定义(选择)栈的链接表示，链式栈无栈满问题，空间可扩充，插入与删除仅在栈顶处执行，链式栈的栈顶在链头，适合于多栈操作链栈的压入与弹出(不考)①压入voidPush(LStack&S,ElemTypee){//在栈顶之上插入元素e为新的栈顶元素p=(LNode*)malloc(sizeof(LNode);//建新的结点if(!p)exit(1);//存储分配失败p->data=e;p->next=S.top;//链接到原来的栈顶S.top=p; //移动栈顶指针++S.length; //栈的长度增1}//Push②弹出boolPop(LStack&S,ElemType&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回TRUE；否则返回FALSEif(!S.top)returnFALSE;else{e=S.top->data;//返回栈顶元素q=S.top;S.top=S.top->next;//修改栈顶指针--S.length; //栈的长度减1deleteq; //释放被删除的结点空间returnTRUE;}}//Pop栈的应用(选择)要求能与队列的应用分开数制转换，行编辑程序，迷宫求解，表达式求值队列的定义与特点(选择)定义:只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾(rear),允许删除的一端称为对头(front)。特点：先进先出(FIFO)。链队列的定义队列的链式表示。链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。链队列的出队入队(不考)入队StatusEnQueue_L(LinkQueue&Q,QElemType){〃在链队列Q队尾，插入新的队尾结点p=(QueuePtr)malloc(sizeof(QNode));//为新元素e分配结点空间if(!p)exit(OVERFLOW); //存储分配失败p->date=e;p->next=NULL;Q.rear->next=p; //修改队尾指针，插入新队尾结点Q.rear=p;returnOK;}出队StatusDeQueue_L(LinkQueue&Q,QElemType&e){〃若队列不空，则删除Q的队头元素结点，用e返回其值，并返回OK；否则返回ERRORif(Q.front==Q.rear)returnERROR;//若队列空，返回ERRORp=Q.front->next; //p指向队头元素结点？e=p->data;Q.front->next=p->next;//修改链队列头结点指针if(Q.rear==p)Q.rear=Q.front;//对于链队列只有一个元素结点的情况,要同时修改队尾指针free（p）;returnOK;}循环队列的定义队满时再进队将溢出，解决办法：将顺序队列臆造为一个环状的空间，形成循环（环形）队列。循环队列的出队入队（应用）要求会操作队头、队尾指针加1，可用取模（余数）运算实现队头指针进1:front=（front+1）%maxsize;队尾指针进1:rear=（rear+1）%maxsize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：（rear+1）%maxsize==front;fromflnBDCrear空队列_股情况Vole队满（错误}rearfront7严frontfromflnBDCrear空队列_股情况Vole队满（错误}rearfront7严frontrear_front限满（正确）12.队列的应用杨辉三角第四章字符串字符串的定义（选择）字符串是n（0）个字符的有限序列，记作 S:“c_,c2c3...c"其中，S是串名字，“cy.c"123n 123n是串值，ci是串中字符，n是串的长度。例如,S=“TsinghuaUniversity”串模式匹配定义：在串中寻找子串（第一个字符）在串中的位置

词汇：在模式匹配中，子串称为模式，串称为目标。示例：目标T:"Beijing”，模式P:"jin”，匹配结果=3①穷举的模式匹配（应用）要求能把演示过程写出来第1趟Ti=L；ihhhl>a.穷举的模式P啼bii匹配过程第2趙Tabbabaestt式：血P^'ba第3趟Tab；kl>aPUha脚趟Tsibb';ihii1=3②匹配的改进算法不需要写过程了，要知道它的复杂度O（m+n）模戒匹配的改進算法：匹酉漲式血£肚第1趟Tahit1)cbc»€b岔bPi=.I i=7第2趟T汕b»I)€ilbC11£bAbPiib€i»第3趙T»hahcticiichab第五章数组与广义表数组的定义(选择)？？行优先存放地址计算(应用)二维三维给数组，求地址一维数组：LOC(i)=LOC(i-1)+l=a+i*l二维数组：LOC(i,j)=a+(i*m+j)*l设数组开始存放位置LOC(0,0)=a,每个元素占用l个存储单元三维数组：LOC(i1,i2,i3)=a+(i1*m2*m3+i2*m3+i3)*l各维元素个数为m『m2,m3N维数组：LOC(i,i,i)=a+(i*m*m*...*m+i*m*m*...*m++i*m+i)*l12n123n234n n-1nn各维元素个数为m1,m2,m3,…,mn用三元组表表示的稀疏矩阵及其转置与加法（应用）给矩阵，求转置非零元素个数远远少于矩阵元素个数用三元组表表示的稀疏矩阵及其转置til[21【3]行til[21【3]行(row)列(col)值(value)032206151111151723=635394091522811-w卩12p[4ls[^[7时间复杂度(选择)只要知道复杂度O(nu*tu) nu为矩阵列数，tu为非零元素个数第六章树和二叉树树的定义(选择)树是由n(n>0)个结点的有限集合。如果n=0,称为空树；如果n>0,则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1除根以外的其它结点划分为m(m>0)个互不相交的有限集T2，…，T其中每个集合本身又是一棵树，并1 2m且称为根的子树(SubTree)。基本术语结点：一个数据元素及指向其子树的分支。结点的度：结点拥有的子树个数。叶结点：度为零的结点。子女：结点子树的根。兄弟：同一结点子女。祖先：根到该结点路径上的所有结点。子孙：某结点为根的子树上的任意结点。结点层次：从根开始，根为第一层，根的子女为第二层，以此类推。树的深度(高度)：树中结点的最大层次数。有序树：树中结点的子树由左向右有序。森林：m(m>0)棵互不相交的树。二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。树的链表表示法(选择)

IChiWdata含两个指针域的结点结构LChikl含三个指针域的结点结构arentIChUdK：IChiWdata含两个指针域的结点结构LChikl含三个指针域的结点结构arentIChUdK：hildntIChUd性质：含有n个结点的二叉链表中有n+1个空链域IChUd二叉树的遍历会写出顺序就可以前序、中序、后续遍历二叉树的算法(不考)计算结点个数(递归算法)intCount(BinTreeNode*T){if(T==NULL)return0;elsereturn1+Count(T->leftChild)+Count(T->rightChild);}计算叶子结点个数intLeaf_Count(BitreeT){//求二叉树中叶子结点的数目if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeaf_Count(T-lchild)+Leaf_Count(T-rchild);//左子树的叶子数加上右子树的叶子数}计算二叉树的高度intHeight(BinTreeNode*T){if(T==NULL)return0;else{intm=Height(T->leftChild);intn=Height(T->rightChild));return(m>n)?m+1:n+1;}}非递归用栈实现？？（不考）线索二叉树的定义（选择）为什么用？利用的是什么？对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作.以二叉链表为存储结构时,结点的左右孩子可以直接找到,但不能直接找到结点的前驱和后继,而结点的前驱和后继只有在遍历二叉树的过程中才能得到.用二叉链表表示的二叉树中,n个结点的二叉树有n+1个空链域，可利用这些空链域存储结点的前驱或后继。9•线索二叉树的结点结构（选择）结点结构Child 如佃 EtlghHJhildT.efiThreadRighkhrendLeftThread=<kItftthild为左子攻指针T.etrnbiTj^I, LeftChild洵前驰线索Ri^htTliiriidHI,Ri^litChiI<1为右子女指针Ri盟htThread=1,Ri^liKhilJ^后继摘针10.树的左二子-右兄弟表示法（应用）与下一个一起考33(:10.树的左二子-右兄弟表示法（应用）与下一个一起考33(:/>11结点结构firstChildncitSiblin胃链域浒1个森林与二叉树的转换树的遍历（选择）知道哪个对应哪个将树化为二叉树，树的先根遍历对应二叉树的前序遍历，树的后根遍历对应二叉树的中序遍历前序中序遍历唯一确定一个二叉树（选择）知道这个原理就行霍夫曼算法（应用）能画出霍夫曼树，求WPL⑴由给定的n个权值｛w0,W],w2,...,wn-i｝，构造具有n棵扩充二叉树的森林F=｛T0,T2,...,T1｝，其中每棵扩充二叉树Ti只有一个带权值w.的根结点，其左、右子树均为空。n-i i i（2）重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。第七章图1.图的定义(选择)图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph=(V,E)其中V={x|xe某个数据对象}是顶点的有穷非空集合；E1={(x,y)|x,yeV}或E2={<x,y>|x,yeV&&Path(x,y)淇中，E1是顶点之间关系的有穷集合，也叫做边(edge)集合，此时的图称为无向图。E2表示从x到y的一条弧，且称x为弧尾，y为弧头，这样的图称为有向图。2.图的存储结构(选择)①邻接矩阵A.Edge[i][/]={0：若<i,j>eE或(i^j)eE否则②网络的邻接矩阵(有权)’W(i,j),若心j且<i,j>eE或(i,j)eEA.edge[i][j]=<g, 若i丰j且<i,j E或(i,j)电E0, 若i==j2.补一些术语，如顶点的度，出入度，强连通等(选择)3.邻接表是图的一种链式存储结构。■弧的结点结构adjyex；//该弧所指向的顶点的位置nextarc;//指向下一条弧指针info;"该弧相关信息的指针adjvexnextarcinfo■顶点的结点结构data;〃顶点信息datafirstarc19fii-starc；"指向第一条依附该顶点的弧19有向图有邻接表和逆邻接表。4.图的遍历(应用)给图求dfs或bfs生成树①深度优先前进——- 深度优先生成树|||[退 ②广度优先22ECj3/£)73V①H）69-广度优先搜索过程广度优先生成树5.图的连通性问题（选择）用深度和广度都可以最短路径的算法及三个子问题（应用&选择）应用要求掌握下列步骤，选择要知道Dijkstra解决的是哪个问题初始化：Se{v0};dist[j]eEdge[O][j],j=1,2,n-1;//n为图中顶点个数求出最短路径的长度：dist[k]emin{dist[i]},ieV-S;SeSU{k};修改：dist[i]emin{dist[i],dist[k]+Edge[k][i]},对于每一个ieV-S;④判断：若S=V,则算法结束，否则转②。7•利用Prim算法求最小生成树（应用）第九章查找1.有序表的查找折半查找的算法（算法）intSearch_Bin（SSTableST,KeyTypekval）{low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if(kval==ST.elem[mid].key)returnmid;//找到待查元素elseif(kval<ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}//Search_Bin时间复杂度O(log2n)2.顺序表和有序表的比较（选择）顺序表有序表表的特性无序有序存储结构顺序或链式顺序插删操作易于进行需移动兀素ASL的值大小第十章内部排序1.排序的定义（选择）在„„上排？（查找表）将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排序方法的稳定性（选择）知道那种排序方法是稳定的，不稳定的如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j],且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。内排序与外排序（选择）内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内