数据结构历年真题总结

903数据结构历年真题总结

.2010:108

.选择

・数据结构定义

・数据D+关系/结构S=DS

・图的结点的度

•有向图：A->B,A的出度1（从A出去的弧的数目）入度0（进入A的弧的数目）B的出

度0入度1

・无向图：A-B-C,B的度是2（和某结点相连的边数）

•栈

・栈的序列，记住先入栈的后出栈即可

•广义表的长度

•广义表的长度是指广义表中原子/子表的数目，例如T=（a,（c,s）,b）长度3,包含2个原子

和1个子表

・散列表的平均检索长度

•散列表的平均查找长度ASL依赖于装填因子影响,不直接依赖表元素个数N,也不直接依

赖于表长M

・树的度和树的结点的度

•结点的度：结点孩子的数目

・树的度：树中结点最大的度数称为树的度

.树中的结点数=所有结点的度数之和+1,具体做题可以设度0结点有n0个，度1结点有1

个…，则可以根据题目得到两个式子，一个是树中结点数=0*n0+l*nl+...+m*nm+l,另

一个是树中结点数=n0+nl+n2+...nm,联立求解即可

・二维数组

・公式记不住就死算，注意从0开始还是1开始

•连通无向图

・n个结点的连通无向图，至少要有n-1个边。例如A-B-C-D，有4个点，至少3个边

.关键路径

・关键路径是指事件节点网络（AOE网）中，从源点到汇点的最长路径

・完全二叉树

•完全二叉树：结点编号连续的二叉树

・完全二叉树高K,则至少有2的k-1次方个结点（可以举例子硬算）

.填空

・栈和队列

・悔口队列都是操作受限的线性表,共同点是只运行在固定端点处进行插入删除

・树，森林与二叉树的转换

・森林转换二叉树

・森林中每棵树转换成二叉树，第二颗树接到第一颗树的右孩子处，以此类推（王道书

P172)

（0森林转化得到的二叉树

•树转换二叉树

・兄弟结点连线，每个结点只保留与其第一个孩子的连线其他连线都擦去，以树根为轴顺

时针转45°

(c)抹线(d)旋转

・DFS

・从某个点开始，一直遍历到无法遍历的点，再沿着之前遍历的轨迹退回，退回到能够遍历

未访问结点的结点停止，继续重复上述操作

・完全二叉树

・N个结点的完全二叉树,叶子结点的个数为向上取整(n/2),高度是向上取整log以2为底

(n+D

・广义表的操作

・tail:tail是取出来的永远是一个表(结果外面还要套一对括号)

・head:取广义表第一个元素(可以是原子也可以是表)

•例如LS=((a,b,c),(d,e,f)),head(LS)=(a,b,c),而tail(LS)=((d,e,f))

・最小生成树

・最小生成树是图的应用，从图生成一个树，该树包括尽可能少的边

・Prim:每次选与当前顶点集中距离最近的顶点纳入考量，适合边稠密的图

•kruskal:全局选边上权重最小的点，不构成回路则加入，构成则舍弃，适合边稀疏顶点多

的图

・快速排序

・选Pivot,high,low,先从high开始往前扫，确定枢轴值前面的元素

・树的遍历

•前序中任何T+中序，可以确定一个树

•根左右前序，左根右中序，左右根后序

•简答

.二分蛰找

・比较次数：向上取整Iog2（n+1）

•要求：原本的顺序表已经有序

•应用

・拓扑排序

・每次输出一个没有入度的点，可以用来判断是否有回路

•B-树插入

・先按照二叉排序树的比较，找到位置将结点插入

•插入后判断是否满足B-树的阶，比如3阶的B-树中，每个结点最多有2个元素（3个指针）

・如果满足ok,比如插入30,这是一个3阶的B-树

・如果不满足，先插入，然后将该结点中间元素上升到父结点，并从中间裂开。比如插入26,

发现会再30旁边，这个结点有3个元素了（4个指针）不满足3阶，所以中间元素30上

移动到24旁边，26和37裂开分居左右

•比如再插入85,原本应该再g结点上617085不满足，70上移，61和85裂开，得到这

个情况，然后发现e又不符合，70再上移动，53和90裂开，得到下图2

I312I26851

5061QO

•哈夫曼树

•哈夫曼树建立

•每次选择最小权重结点构建成

•带权路径长度

•WPL是每个结点*（根到该结点走了几个边）的求和

・例如上面的图WPL=（9+12+15）*2+6*3+（3+5）*4=122,即abf三点在第三层

要2个边，c再第四层要3个边，de在第五层要4个边，在求和即可

•排序

•直接插入排序

・每一趟将一个元素插入到最终排序好的位置，。（（1人2）

•快速排序

•假设从小到大排，选第一个元素作为pivot,后面设立low和high，先high往前扫描，

直到比pivot指的元素小，则换位，再low往后扫，直到比pivot值大则换位，重复两

个步骤

・堆排序

・初始化堆

•调整堆，如果要从小到大排序，则调整成大根堆，如果从大到小，则调整成小根堆

・假设从小到大排序，要求大根堆，将堆顶元素与末尾元素进行交换，使末尾元素最大。

然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、

重建、交换，最终遍历堆的结果即为从小到大，可参考图解堆排序

•o(nlogn)

・程序题

・试用c语言编写一介遍历二叉直找树的算法，要求遍历过程恰好按照结点的键

值从大到小排列

・二叉排序树，又叫二叉查找树BST,左子树<根<右子树，本题可以参考二叉树的遍历，按

照右根左的顺序遍历即可

voidsearch(BiTree*t)

(

//空BST则直接返回false

if(t==NULL){

returnfalse;

)

//按右根左顺序遍历BST

else(

search(t->rchild);

visit(t);

search(t->lchild);

}

}

・设L是一个带头结点的非递减有序单链表的表头指针，试设计一算法，将元素

e插入到链表L中合适位置，使该链表仍然非递减有序

•遍历该链表，上徽大小，当e比该元素大时则继续，小则停止，在该位置插入

//定义单链表的表头指针

structLinkList{

intdata;

LinkList*next;

)*L；

〃遍历链表以插入

voidinsert(LinkList*newNode){

LinkList*temp=L;

//遍历

while(temp->next!=NULL){

if(temp->next->data>newNode->data){

break;

}

temp=temp->next;

}

//把newnode插入到temp后面

newNode->next=temp->next;

temp->next=newNode;

)

.2011:105

.选择

・双循环链表的删除

•单链表插入：先连再改，待插入结点指向后继结点s->next=p->next,前驱结点指向待插

入结点p->next=s

•单链表删除：先连再改q指向被删除结点q=p->next,前驱结点指向后继结点p-

>next=q->next,释放q指针。

•双链表插入：先改后继，再改前驱。待插入结点指向后继s->next=p->next,后继结点指

向待插入结点p->next->prior=s,待插入结点指向前驱s->prior=p,前驱指向待插入结

点p->next=s

・双链表删除：先前驱指后继，再后继指前驱

•栈

・数据结构的概念辨析

•错误：因为队列只允许再一端插入且再另一端删除，因此一定是顺序表

・队列是线性表(线性结构)，不一定是顺序表(顺序存储)，可以是链队列

・错误：二维数组的每个元素都有两个前驱结点和两个后继结点

・数组是线性表的推广，一维数组是线性表，二维数组是元素是线性表的线性表

•线性表除了第一个元素外，有且仅一个前驱；除了最后一个元素之外，有且仅一个后继

•因此这里，二维数组的第一个元素，没有前驱结点；二维数组最后一个元素，没有后继

结点

•错误：链接存储是一种紧凑结构

•链式存储密度低，内存中可以不必连续，是不紧凑的

•正确：一维数组是一种顺序表

・一维数组就是线性表的顺序实现

.括号匹配的应用

•括号匹配是栈的应用之一

・树的遍历（不是二叉树的遍历）

•树的遍历是指按照某种方式访问每个结点，且仅访问一次。二叉树的前中后序遍历其实是

一样的，只不过树变成了二叉树，例如下面的树和对应的二叉树

•先根遍历：若非空，先访问根，再依次遍历根的每棵子树。与将树转化成二叉树后的先

序遍历一致。

・后根遍历：若非空，先依次遍历根的每棵子树，再访问根.与将树转化成二叉树后的中

序遍历一致。

・上图的先根遍历结果是ABEFCD,后根遍历结果是EFBCGDA。

•森林的遍历P173

•先序遍历：访问第一棵树的根，再先序遍历第一棵树中根的子树森林，再遍历除去第一

棵树之后的森林

・后续遍历：中序遍历第一颗子树的根节点的字数森林，再访问第一颗树的根，再遍历出

去第一棵树的根节点

.广义表

•广义表head获得的是第一个元素（可以是子表也可以是原子），tail获得的一定是子表

（用了tail先不管，外面套个括号先，再写里面的内容）

.十字链表

•十字链表是图的一种存储方法（表示方法）P218

・邻接矩阵：顶点数平方的空间复杂度

•邻接表：无向图（二倍边数+顶点数的空间复杂度），有向图（一倍边数+顶点数的空

间复杂度）

a）

首元结点

datafirstinfirstout

普通结点

tailvexheadvexhlinktlinkinfo

•邻接多重表：无向图

a）b）

首元结点

datafirstedge

普通结点

markivexilinkjvexjlinkinfo

・直接插入排序

•直接插入排序比较次数最少（当已经基本有序时），只需要比较n-1（每次都比较1次，

一共n-1个元素要比）

・数据结构概念辨析

•链表

•链表动态分配存储，空间灵活，插入删除很快，查找慢（不能随机访问）

.填空

・链表头结点的作用

•使得在链表头部的操作如插入删除等和在后面的操作一致

•使得非空和空链表操作一致

•数组

・算错了。。。

•树的表示法

•树的表示法即树的存储结构P170-171

・双亲表示法

・孩子表示法

•孩子兄弟表示法

・二叉树结点数计算

・二叉树只有度为0,1,2的结点

•二叉树有n0=n2+1即度0结点数目=度2结点数目+1

・二叉树深度计算

•N个结点的二叉树，最多N层（单支树），最少向上取整Iog2（n+1）层（完全二叉树）

・多叉树计算

・T具有n个结点的K叉树，每个结点都有K个指针域，则共有几个空指针？

•有n个结点，所以共有n*k个指针，每个结点（除了根）都会占用其父结点一个指针域,

所以有n-1个被占用，所以共有nk-n+1个空指针

•连通无向图

.简答

・队列，链队列，循环队列

・队列是只能在一端插入，另一端删除的操作受限的线性表

•链队列是使用链表存储的队列，循环队列是使用顺序存储的队列

•应用

・散列查找

•散列查找，计算H值，然后探测，一直到表空的地方就行，算ASL的时候可以直接把每个

元素计算和探测几次求和，再除以关键字数目

•深度优先生成树

・无向图用圆括号其中

G1=(V1,E1),Vl={a,b,c,d},El={(a,b),(a,c),(a,d)1(b,d),(c,d)}

・有向图用尖括号G2=(V2,E2),其中V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}

・先画图，再根据DFS遍历图，然后绘制成树即可(遍历顺序不唯一)

・各排序的比较

•空间复杂度：堆排序需要。(1),快速排序需要。(nlog2n)，归并排序需要。(n)

•稳定性：归并排序稳定，堆排序不稳定

・平均情况：快排平均最快

・最坏情况且内存节约：堆排序

・二叉树

・空树和只有根的树也是二叉树的类型

•程序

・有一个带头结点的单链表，设计一函数将其拆分成两

L={alfbl,a2,b2…,an,bn},

个带头结点的单链表A和B,正序链表A={al,a2，…,an},逆序链表

B={bn,bn-1bl},要求链表A使用链表L的头结点

typedefstruttList{

intdata;//或畴彳

structList*next;//指针域

}List)

voidsplit(List*&headL,List*&headA,List*&headB){

intcount=1;//count析汉苛作

List*p=headL;//p指向L

List*te«p;//保存偶数结点的岫时指针

headB->next=NULL；

while(p->next!=NULL){

//遍历

if(count%2==0){

//偶数结点移动至此eadB中,头插法

temp=p>next->next;

p->next->next=headB->next;

headB->next=p->next;

p->next=temp;

)

else{

//奇数的时候

p=p->next;

)

count++;

)

headA=headL;

)

.假设用单链表方式存储整数序列，如下形式，请编写一个递归算法，对该链表

进行操作，重复结点（值相同的结点），仅保留第一个，最后返回新链表的首

地址。

NODE*delsame_3(NODEahead)

{

NODE*p,*teflp4>ead;〃速以防head不断变化,但初始时tenp都指向新head

if(head->next=rJULL)returnhead;

head->next=delSane_3(head->next)//.'/闩到nead->next指向尾结点,此晰end指

向链表倒数第二个结点—

p=head->next;

while(pl=NULL)

{

if(head->data=p->data)

(

//如果当前head的数据和后面的数据一样，则飘除

temp->next=p->next;

free(p);

p=temp->next;

}else{

//继续

p=p->next;

temp=temp->next;

)

}

returnhead;

}

.2012:105

.选择

.绪论

•算法的空间复杂度是算法要耗费的存储空间

・算法的有穷性：一个算法必须在执行有穷步后结束，且每一步必须在有穷时间内完成

.线性表

•常插入删除可以用链表结构，在表尾插入删除顺序链表都可以，需要随机访问，插入指定

位置可以用顺序存储，需要访问前驱后继可以用双链表/循环链表等

.栈在表达式求值中的应用

•如果是中缀表达式，需要操作数榭口操作符栈，分别读数字和操作符。读数字压入数字栈，

读操作符压入操作符栈，如果读到操作符比目前栈顶操作符优先级高，则继续；如果读到

的操作符比操作符栈顶的操作符优先级低，则栈顶操作符出来，数字栈出两个元素进行操

作得到结果压回去，循环上述过程即可如s:〃guyon/article/details/89671260

・如果是后缀表达式，直接一个栈扫描表达式即可，扫到数字则进，扫到操作符则将栈顶两

个元素取出来，进行操作，然后压回去（看王道P92）

•数组

•死算即可

•二叉树

・若二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是？

・二叉排序树指左小于根小于右的树，建立的时候是依次读取元素，然后按照大小比较进

入对应的位置，例如给定[731015912],可以看到从任意结点到根不一定是有序

的

・哈夫曼树，选所有结点中最小的两个构成新结点，并将其加入结点列表，接下来每次在

结点列表中选择最小的两个构成新结点，直到没有结点，可以看到右侧也不一定是有序

的

•堆，有大根堆和小根堆（即一种特殊的完全二叉树），如果是大根堆，即根必须大于左

右两个孩子，如果从任意点往根走，必然是小到大的顺序。（小根堆同样）

・B+树：B-树的改进，叶子上面那层结点之间构成了链表

1235^9689111315

•完全二叉树

・某结点没有左孩子，该结点一定是叶子

・平衡二叉树

・平衡因子BF计算：左子树高度-右子树高度（平衡时BF只有0,1,-1）

•题目中说插入结点之后，A的左孩子BF=O,右孩子为1（即右孩子的左子树比右子树高

1）,所以可以推出插入点在A的右孩子的左子树上，造成A不平衡，因此是右左型，即

RL

・线索二叉树

•把二叉树中，没有用的空指针，当成线索，来指向先序/中序/后序遍历的前驱或后继。n个

结点的线索二叉树，包括n+1个线索。（n个结点，有2n个指针，然后其中n-1个指针

被用来当指向孩子的指针（即树有n个结点，应该有n-1个边，则有2n-n+l=n+l个线

索）（指向空的也是线索）

•二分蛰找

•排序算法比较

•I:啜次数与序列初态无关的是：简单选择排序(每次选择最小)

•直接插入排序(需要比较，序列初态影响比较次数)，冒泡排序同样，序列初态如果已经

基本有序，则比较次数很少，堆排序在建堆和调整堆时候需要比较，这和初始顺序也有关

.填空

・数据的存储结构

•数据的存储结构，又叫映像，也叫物理结构，包括数据元素的表示和关系的表示

・循环队列

•循环队列的元素个数：(rear+M-front)modM(M是表长)

•循环队列中，front指队头，rear指队尾后一个(具体题目具体看)，队满是rear+1mod

M==front,队空即rear==front

・广义表

•广义表深度是指广义表的括号嵌套有几层，例如(a,(a,b),d,e,((i,j),k)),深度是3。

•树的计算

•算错了。。。树的结点个数=树所有结点的度+1

•哈夫曼树

•画个哈夫曼树就好

•B-树

・m阶的B-树，每个结点最多有m-1个元素，有m个指针。

•单个结点2个数字则有3个指针，是3阶段【指针,A,指针B指针】

•冒泡排序和堆排序

・冒泡排序在最好的情况下，即基本有序的情况下，交换的次数是。次

•堆排序在最坏的情况下，需要比较向下取整nlog2n

.简答

・数据类型和抽象数据类型

・数据类型是一个值得集合和定义在该集合得一组操作的总称

•抽象数据类型指一个数学模型以及定义在该模型上的一组操作。仅取决于逻辑特性，和表

示实现无关，抽象在于数据类型的数学抽象特性，范围比数据类型更广阔，一般包括数据

对象，关系和操作三部分组成

•应用

•二叉排序树

・BST树建立规则，按顺序读取，然后大小比较，比该结点大的进入右侧，比结点小的进入

左侧

・邻接矩阵和最小生成树

•邻接矩阵

•图（不带权）的邻接矩阵：连着的是I,不连着算0（自己和自己是0）

•网（带权图）的邻接矩阵：连着的是权，不连着算8（严书算无穷，别写0）

・柘扑排序和二叉树转换森林

•二叉树转化成森林，先拆成一堆二叉树,然后对每个二叉树恢复成普通的树（右孩子变成

右兄弟，左孩子不动）

・快速排序和堆排序

•同10年

.程序

・在一个递增有序的线性表中，有数值相同的元素存在，若存储方式为单链表，

请设计算法去除重复部分，例如有线性表7-10-10-21-30-42-42-42-51-70,

去除之后是7-10-21-30-42-70

2012程序设计题

1.单链表去重

voidfind（node*head）{

//定文商个指计

node，p,q;

//一开始指向头结点

p=q=head;

//开始遍历单修表

while（p->nextlaNULLX

//q指向p的后一个

q=p->next;

//如果p的后一个所指和当前p所指数据域一样

while（q->data==p->data）//魏，,过所有与p一样的结点,直到屋1一；

//q往看再指向一个

q=q->next;

//p再指向q,即把中间一大堆一样的结点都给跳过了

p->next=q;

p=q;

）

}

・试设计算法再On时间复杂度内，队数组A[0,L...n-l]划分为左右两个部分,

使得左边的所有元素均为奇数，右边都为偶数，要求辅助空间。1

2.数组划分奇偶

#include<iostream>

usingnamespacestd;

#definen20

voidmain(){

intA[n];〃定义整型数组

inti=0;

intm;〃中间变量

intj=n;

cout<<”请输入n个数”;

for(i=0;i<n;i-»-+){

cin>>A[i];

)

//交换

for(i=0;i<(n/2);i++){

j=n-i；

if(A[i]%2==0){

//前偶后奇则交换

if(A[j]%2!=0){

m=A[j];

A[j]=A[i];

A[i]=m;

)

}

}

)

}

.2013:105

.选择

・基本概念

•逻辑上将数据结构分成：线性结构和非线性结构

・图的存储

・无向图可以用邻接矩阵，邻接表，邻接多重表，有向图可以用邻接矩阵，邻接表，十字链

表

•邻接多重表

a)

・例如里面V1后面接着［01］和［03］gpvl和v2有边，vl和v4有边，即边只存储

一次

・邻接多重表首元结点

datafirstedge

•临界多重表其他结点

markivexilinkjvexjlinkinfo

・mark:标志域，用于标记此节点是否被操作过，例如在遍历时，mark域为0表示

未被遍历；mark为1表示该节点已被遍历；

・ivex和jvex:数据域，分别存储图中各边两端的顶点所在数组中的位置下标;

•ilink:指针域，指向下一个存储与ivex有直接关联顶点的节点；

•jlink:指针域，指向下一个存储与jvex有直接关联顶点的节点；

•info:指针域，用于存储与该顶点的其他信息，比如无向网中各边的权；

•双向链表

・双链表插入结点，需要更改4个指针，前驱的next,后继的prior,以及插入结点的next

和prior指针

•图的回路

・用拓扑排序可以判断回路

・冒泡排序

•冒泡排序的规则：两两比较，小的/大的冒上去/下去

.线性表

・线性表的定义：n个具有相同特性的数据元素的有限序列。n可以为0,即空