数据结构考研必背算法5星
文档说明：本文档是针对考研专业课《数据结构》所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助；
线性表
1.逆转顺序表中的所有元素
void Reverse(int A[ ],int n){
int i,t;
for(i=0;i t = A[i]; A[i] = A[n-i-1]; a[n-i-1] = t; } } 自我总结： 2. 删除线性表中数据域为X的所有结点； void Del_X(Linklist &L,Elemtype X){ Linklist p,q = L; p = L->next; while (P!=NULL){ if(p->data == X){ q->next = p->next; free(p); p=q->next; }else{ q = p; p = p->next; } } if(L->data == X){ q = L; L = L->next; free(q); } } 自我总结： 3.删除不带头结点单链表L中所有值为X的结点（递归） void Del_X(Linklist &L,Elemtype X){ LNode *p; if(L==NULL) return ; if(L->data == X){ P = L; L = L->next; free(p); Del_X(L,X); }else{ Del_X(L->next,X); } } 自我总结： 4.删除带头结点单链表L中所有值为X 的结点 void Del_X(Linklist &L,Elemtype X){ LNode *p = L->next,*pre = L, *q; while(P!=NULL){ if(P->data == X){ q = p; p=p->next; pre->next = p; free(q); }else{ pre = p; p=p->next; } } } 注：本算法是在无序单链表中删除满足某种条件的所有结点；如：若是要删除介于max 和min之间的所有结点，只需将if语句改为if(p->data>min&&p->data 自我总结： 5.逆转线性表（不带头） void reverse(Linklist &L){ Linklist p, q, r; p = L; q = NULL; while(p!=NULL){ r = q; q = p; p = p->next; q->next = r; } L = q; } 带头结点： Linklist reverse(Linklist L){ LNode *pre,*p=L->next,*r=p->next; p->next = NULL; while(r!=NULL){ pre = p; p = r; r = r->next; p->next = pre; } L->next = p; return L; } 自我总结： 6. 复制线性链表(递归) Linklist copy(Linklist list1){ Linklist list2; if(list1==NULL) return NULL; else{ list2 = (Linklist)malloc(sizeof(LNode)); list2 ->data = list1->data; list2 -> next = copy(list1->next); return list2; } } 自我总结： 7. 将两个按值有序排列的非空线性表合并为一个按值有序的线性表 Linklist Mergelist(Linklist L1,Linklist L2){ Linklist L3,p = L1,q = L2,r; if(L1->data <= L2->data){ L3 = L1; r = L1; p = L1->next; }else{ L3 = L2; r = L2; q = L2->next; } while(P!=NULL&&q!=NULL){ if(p->data <= q->data){ r->next = p; r = p; p = p->next; }else{ r->next = q; r = q; q = q->next; } } r->next=p!=NULL?p:q; return L3; } 自我总结： 8. 将两个按值递增线性表合并为一个按值递减的线性表 void MergeList(LinkList &L1,LinkList &L2){ LNode *r,*p1=L1->next;*p2=L2->next; L1->next = NULL; while(p1&&p2){ if(p1->data <= p2->data){ r = p1->next; p1->next = L1->next; L1->next=p1; p1 = r; }else{ r = p2->next; p2->next = L1->next; L1->next = p2; p2 = r; } if(p1){ p2 = p1; } while(p2){ r = p2->next; p2->next = L1->next; L1->next = p2; p2 = r; } free(L2); } } 自我总结： 树 1.先序遍历（递归）void PreOrder(BiTree T){ if(T!=NULL){ visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } 先序遍历（非递归） void PreOrder(BiTree T){ InitStack(S); BiTree p =T; while(p!=NULL||!IsEmpty(S)){ while(p!=NULL){ visit(p); Push(S,p); p = p->rchild; } Pop(S,p); p = p->rchild; } } 自我总结： 2.中序遍历（递归）void InOrder(BiTree T){ if(T!=NULL){ InOrder(T->lchild); Visit(T); InOrder(T->rchild); } } 中序遍历（非递归）void InOrder(BiTree T){ InitStack(S); BiTree p = T; while(p||！IsEmpty(S)){ if(p){ Push(S,p); p = p->lchild; } else{ Pop(S,p); Visit(p); p=p->rchild; } } } 自我总结： 3.后序遍历（递归）void PostOrder(BiTree T){ if(T!=NULL){ PostOrder(T->lchild); PostOrder(T->rchild); Visit(T); } } 后序遍历（非递归） void PostOrder(BiTree T){ InitStack(S); BiTree p = T; r = NULL; while(p||!IsEmpty(S)){ if(p){ Push(S,p); p = p->lchild; }else{ GetTop(S,p); if(p->rchild&&p->rchild!=r){ p = p->rchild; Push(S,p); p = p->lchild; }else{ Pop(S,p); Visit(p); r = p; p = NULL; } } } } 自我总结： 4.层序遍历（自上而下，自左至右） void LevelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q,T); while(!IsEmpty(Q)){ DeQueue(Q,p); Visit(p); if(p->lchild!=NULL) EnQueue(Q,p->lchild); if(p->rchild!=NULL) EnQueue(Q,p->rchild); } } 自我总结： 5.层序遍历（自下而上，自右至左）void InvertLevel(BiTree bt){ Stack S;Queue Q; if(bt!=NULL){ InitStack(S); InitQueue(Q); EnQueue(Q,bt); while(IsEmpty(Q)==false){ DeQueue(Q,p); Push(S,p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } while(IsEmpty(S)==false){ Pop(S,p); visit(p->data); } } } 自我总结： 6.求二叉树深度（高度）（递归） int Btdepth(BiTree T){ if(T==NULL) return 0; Ldep = Btdepth(T->lchild); rdep = Btdepth(T->rchild); if(ldep>rdep) return ldep+1； else return rdep+1; } 注：求某一层结点个数，每一层结点个数，树的最大宽度等，都采用此思想 自我总结： 求二叉树深度（非递归） int Btdepth(BiTree T){ if(!T) return 0; int front = -1,rear = -1; int last = 0,level = 0; BiTree Q[MaxSize]; Q[++rear]=T； BiTree p; while(front p=Q[++front]; if(p->lchild) Q[++rear]=p->lchild; if(p->rchild) Q[++rear]=p->rchild; if(front==last){ level++; last=rear; } } return level; } 自我总结： 7.交换二叉树中所有结点的左右子树 位置（递归） void swap(BiTree b){ if(b){ swap(b->lchild); swap(b->rchild); temp=b->lchild; b->lchild=b->rchild; b->rchild=temp; } } 非递归 #define MAX_QUEUE 50 void swap(BiTree T){ BiTree QUEUE[MAX_QUEUE]，temp,p=T; int front,rear; if(T!=NULL){ QUEUE[0]=T; front=-1; rear=0; while(front p=QUEUE[++front]; temp=p->lchild; p->lchild=p->rchild; p->rchild=temp; if(p->lchild!=NULL) QUEUE[++rear]=p->lchild; if(p->rchild!=NULL) QUEUE[++rear]=p->rchild; } } } 自我总结： 8.删除二叉树中以某个结点为根结点 的子树 void DeleteXTree(BiTree bt){ if(bt){ DeleteXTree(bt->lchild); DeleteXTree(bt->rchild); free(bt); } } void Search(BiTree bt,ElemType X){ if(bt){ if(bt->data==X){ DeleteXTree(bt); exit(0); } initQueue(Q); EnQueue(Q,bt); while(!IsEmpty(Q)){ DeQueue(Q,p); if(p->lchild) if(p->lchild->data==X){ DeleteXTree(p->lchild); p->lchild=NULL; }else EnQueue(Q,p->lchild); if(p->rchild) if(p->rchild->data==X){ DeleteXTree(p->rchild); p->rchild=NULL; }else EnQueue(Q,p->rchild); } } } 自我总结： 9.建立二叉树（从键盘输入数据，先 序遍历递归算法） BiTree Create(){ char ch; BiTree T; scanf("%c",&ch); if(ch==' ') return NULL; else{ T=(BiTree)malloc(sizeof(BTNode)); T->data=ch; T->lchild=Create(); T->rchild=Create(); return T; } } 自我总结： 10.建立二叉树（从数组获取数据）Bitree CreateBT(int A[],int i,int n){ BiTree p; if(i>n) return NULL; else{ p=(BiTree)malloc(sizeof(BTNode)); p->data=A[i]; p->lchild=CreateBT(A,2*i,n); p->rchild=CreateBT(A,2*i+1,n); return p; } } 法二： BiTree CreateBT(int A[],int n){ int i; BiTree *PT; for(i=1;i<=n;i++){ if(A[i]!=0){ PT[i]=(BiTree)malloc(sezeof(BTNode)); PT[i]->data=A[i]; }else{ PT[i]=NULL; } } for(i=1;i<=n;i++){ if(PT[i]!=NULL){ PT[i]->lchild=PT[2*i]; PT[i]->rchild=PT[2*i+1]; } } } 自我总结： 11.求结点所在的层次： #define MAX_STACK 50 int LayerNode(BiTree T,int item){ BiTree STACK1[MAX_STACK],P=T; int STACK2[MAX_STACK],flag,top=-1; while(p!=NULL||top!=-1){ while(p!=NULL){ STACK1[++top]=p; STACK2[top]=0; p=p->lchild; } p=STACK1[top]; flag=STACK2[top--]; if(flag==0){ STACK1[++top]=p; STACK2[top]=1; p=p->rchild; }else{ if(p->data==item) return top+2; p=NULL; } } } 自我总结： 查找 1.顺序查找： typedef struct{ ElemType *elem; int TableLen; }SSTable; int Search_Seq(SSTable ST,ElemType key){ ST.elem[0]=key; for(i=ST.TableLen;ST.elem[i]!=key;--i) ; return i; } 递归： int SeqSearch(int A[],int n,int key,int i){ if(i>=n) return -1; if(A[i]==key) return i; else return SeqSearch(A,n,key,i+1); } 调用:Pos=SeqSearch(A,n,key,0); 总结： 2.折半查找： int Binary_Search(SeqList L,ElemType key){ int low = 0;high=L.TableLen-1,mid; while(low<=high){ mid=(low+high)/2; if(L.elem[mid]==key) return mid; else if(L.elem[mid]>key) high=mid-1; else low = mid+1; } return -1; } 递归： typedef struct{ ElemType *elem; int length; }SSTable; int BinSearchRec(SSTable ST,ElemType key,int low,int high){ if(low>high) return 0; mid=(low+high)/2; if(key>ST.elem[mid]) BinSearchRec(ST,key,mid+1,high); else if(key BinSearchRec(ST,key,low,mid-1); else return mid; } 自我总结： 3.在按值递归排序且长度为n的线性表中 折半查找并插入一个元素 void BinInsert(int A[],int n,int key){ int j,low=0,high=n-1,mid; while(low<=high){ mid=(low+high)/2; if(key>A[mid]) low=mid+1; else high=mid-1; } for(j=n;j>low;j--) A[j]=A[j-1]; A[low]=key; n++; } 自我总结： 4.在按值递增排列且长度为n的线性表中 折半查找值不小于key的最小元素void BinSearch(int A[],int n,int key){ int low=0,high=n-1,mid; while(low<=high){ mid=(low+high)/2; if(key==A[mid]) return mid; if(key>A[mid]) return mid+1; else high=mid-1; } if(low<=n-1) return low; else return -1; } 自我总结： 《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系： （1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 （2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 （3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算） 第二章线性表 1、线性表的特点： （1）存在唯一的第一个元素；（这一点决定了图不是线性表） （2）存在唯一的最后一个元素； （3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表） （4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法： （1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节） （2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序： 设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解 目 录 第一部分 历年考研真题汇编 .......................................................................................................................... 2000年华南师范大学计算机学院925数据结构考研真题 ................................................................. 1999年华南师范大学计算机学院925数据结构考研真题 ................................................................. 第二部分 兄弟院校真题汇编 .......................................................................................................................... 2011年厦门大学845数据结构考研真题 ............................................................................................... 2009年厦门大学845数据结构考研真题 ............................................................................................... 2008年厦门大学845数据结构考研真题 ............................................................................................... 2006年厦门大学496数据结构考研真题 ............................................................................................... 华南师范大学计算机学院 925数据结构历年考研真题汇编 最新资料，WORD 格式，可编辑修改！ 2018考研计算机：数据结构重难点及 复习建议 新东方在线推荐： 一、重难点解析和复习建议 数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。 当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。 下面我们来解析一下知识点： 线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。 栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。 树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景： 假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/ 2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢? 1.2 分析问题（建立模型）： 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。 图 G5无向连通图的生成树为(a)、(b)和(c)图所示： G5 G5的三棵生成树： 可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。 1.3最小生成树的定义： 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。 最小生成树的性质： 假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中， 则必存在一棵包含边（u,v）的最小生成树。 1.4 解决方案： 两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质 1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2) 一.选择题篇 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1）它必须具备（2）这三个特性。【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 数据结构考研大纲 【硕士研究生考试】 Ⅰ考查目标 计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 Ⅱ考试形式和试卷结构 一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟 二、答题方式答题方式为闭卷、笔试 三、试卷内容结构 数据结构45分计算机组成原理45分 操作系统35分计算机网络25分 四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分 数据结构 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 （三）图的遍历 1. 深度优先搜索 2. 广度优先搜索 （四）图的基本应用及其复杂度分析 1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找（六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1. 直接插入排序 2. 折半插入排序 （三）气泡排序（bubble sort）（四）简单选择排序 （五）希尔排序（shell sort）（六）快速排序 （七）堆排序 （八）二路归并排序（merge sort）（九）基数排序 （十）各种内部排序算法的比较（十一）内部排序算法的应用 目前刚整理了2009-2015的试题过几天2016的也会上传上去 希望对你有帮助。。。。。。。 2009 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的 父结点，则在原来的森林中，u和v可能具有的关系是I．父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 8.下列叙述中，不符合m阶B树定义要求的是 A．根节点最多有m棵子树 B.所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接 9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是 A．3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D.3，12，5，8，28，20，15，22，19 10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序 41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： 数据结构考研必背算法5星 文档说明：本文档是针对考研专业课《数据结构》所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助； 线性表 1.逆转顺序表中的所有元素 void Reverse(int A[ ],int n){ int i,t; for(i=0;i 《数据结构》复习重点知识点归纳 一．数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为： ·概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 ·线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题，如果有，也是与其它章节内容相结合。 ·栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 ·串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 ·多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 ·树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 ·图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 ·查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 ·排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 数据结构精选考研试题 [注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分] 1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？ 3、什么是结构化程序设计？ 4、哈希方法的基本思想 5、给出一不稳定排序方法名称与实例二、构造结果：[24分] 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．假设用于通讯的电文仅8个字母组成，字母在电文中出现的频率 分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为，H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分] 四、编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分] 五、编写程序，完成下列功能：[15分] 1．读入整数序列，以整数0作为序列的结束标志，建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0 六、 湖北工业大学计算机学院数据结构历年考研真题汇 编 Final approval draft on November 22, 2020 目 录 说明：数据结构科目代码更换频繁，2016年科目代码是836，本书以此为准。 湖北工业大学计算机学院 836数据结构历年考研真题汇编 最新资料，WORD 格式，可编辑修改！ 2008年湖北工业大学计算机学院917数据结构历年考研真题汇编考研真题 试卷代号 917 试卷名称 数据结构 ①试题内容不得超过画线范围，试题必须打印，图表清晰，标注准确 ②考生请注意：答案一律做在答题纸上，做在试卷上一律无效。 二○○八年招收硕士学位研究生试卷 一．单项选择题（在每小题列出四个供选择的答案A ．B ．C ．D 中，选一个正确的答案,将其代号填在答卷纸相应题号后的下横线上，每小题2分，共20分） 1．以下术语与数据的存储结构无关的是（ ）。 A ．栈 B. 哈希表 C. 双向链表 D. 线索二叉树 2．在一个以 h 为头指针的双向循环链表中，指针p 所指的元素是尾元素的条件是（ ）。 A. p==h B. h->rlink==p C. p->llink==h D. p- >rlink==h 3．设栈S 和队列Q 的初始状态为空，元素a,b,c,d,e,f 依次通过栈S ，一个元素 出栈后即进队列Q ，若6个元素出队的序列是a,c,f,e,d,b ，则栈S 的容量至 少应该是( )。 A ． 6 B. 5 C. 4 D. 3 4．用循环链表表示队列，设队列的长度为n ，若只设尾指针，则出队和入队的时 间复杂度分别为( )。 A ．O(1)，O(1) B. O(1)，O(n) C. O(n)，O(1) D. O(n)，O(n) 5．设串s1=“ABCDEFG”， s2=“12345”，则strconcat (strsub (s1, 2, strlen(s2)), strsub (s1, strlen(s2), 7))的结果串是( )。 A ．BCDEF B ．BCDEFG C ．EFG D ．BCDEEFG 6．某二叉树T 有n 个结点，设按某种顺序对T 中的每个结点进行编号，编号为 1，2，… ，n ，且有如下性质：T 中任一结点V ，其编号等于V 左子树上的最 小编号减1，而V 的右子树的结点中，其最小编号等于V 左子树上结点的最大 编号加1。这时是按( )编号的。 A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次遍历序列 7．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 ( ) 。 A ．（15，13，14，6，17，16，18） B.（15，17，16，18，13，6，14） C.（15，6，13，14，17，16，18） D. (15，13，6，14，17，18，16) 8．已知由7个顶点组成的无向图的邻接矩阵为： A B C D E F G 考研数据结构图的必背算 法及知识点 Prepared on 22 November 2020 1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树 问题背景： 假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢 分析问题（建立模型）： 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。 图G5无向连通图的生成树为(a)、(b)和(c)图所示： G5 G5的三棵生成树： 可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。 最小生成树的定义： 如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。 最小生成树的性质： 假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中， 则必存在一棵包含边（u,v）的最小生成树。 解决方案： 两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质 1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2) 假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。设置两个新的集合U和T，其中 集合U（顶点集）用于存放G的最小生成树中的顶点， 集合T（边集合）存放G的最小生成树中的边。 T，U的初始状态：令集合U的初值为U＝{u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T＝{}。 一、选择题 1.算法的计算量的大小称为计算的（B）。【北京邮电大学2000二、3（20/8分）】 A．效率B.复杂性C.现实性D.难度 2.算法的时间复杂度取决于（C）【中科院计算所1998 二、1（2分）】 A．问题的规模B.待处理数据的初态和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法 (2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（4分）】 4．一个算法应该是（B）。【中山大学1998二、1（2分）】 A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C. 5.下面关于算法说法错误的是（D）【南京理工大学2000一、1（分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 6.下面说法错误的是（C）【南京理工大学2000一、2（分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执 行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1)B.(1),(2)C.(1),(4)D.(3) 7．从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技大学1996一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（D）。【北方交通大学2000二、1（2分）】 A．循环队列B.链表C.哈希表D.栈 9．以下数据结构中，哪一个是线性结构（D）【北方交通大学2001一、1（2分）】 A．广义表B.二叉树C.稀疏矩阵D.串 10．以下那一个术语与数据的存储结构无关（A）【北方交通大学2001一、2（2分）】 数据结构考研真题及知识点解析 考察目标 1. 理解数据结构的基本概念、基本原理和基本方法。 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。 3. 能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C、C++或Java语言设计与实现算法的能力。 第2章线性表 一、考研知识点 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储 2.链式存储 3.线性表的应用 二、考研真题 （一）选择题 近两年第2章没有考选择题，因为此章主要是线性表的操作，而且又是这门课的一个基础，考综合题的可能性比较大，而且可以和第3章、第9章和第10章的内容结合来出题。 1．（11年）设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。 x=2; while(x 数据结构考研真题及其 答案 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN 一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 2 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈 9．以下数据结构中，哪一个是线性结构（ D ） 【北方交通大学 2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关（ A ）【北方交通大学 2001 一、2（2分）】 3 《数据结构》考研真题及解答 目录 2009 年试题 (1) 填空题 (1) 解答题 (2) 2010 年试题 (2) 填空题 (2) 解答题 (4) 2011 年试题 (4) 填空题 (4) 解答题 (5) 2012 年试题 (6) 填空题 (6) 解答题 (7) 2013 年试题 (8) 填空题 (8) 解答题 (9) 2014 年试题 (10) 填空题 (10) 解答题 (11) 2015 年试题 (12) 填空题 (12) 解答题 (14) 2009 年试题 填空题 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要 输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图 2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。若每个元素出栈后立即 进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是 A．1 B.2 C.3 D.4 3.给定二叉树图所示。设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。 若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是 A．LRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数 最多是 A．39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原 来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系 A.只有II B.I 和II C.I 和III D.I、II 和III 7.下列关于无向连通图特性的叙述中，正确的是 I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1 其他 1.线性表的顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。 2.栈：是限制在表的一端进行插入和删除操作的线性表。特点：先进后出 3.串（字符串）：是零个或多个字符组成的有限序列。记作：S=”a1a2a3……” 4.树：是n(n>=0)个结点的有限集合T ，若n=0时称为空树，否则： （1）有且只有一个特殊的称为树的根结点；（2）若n>1时，其余的结点被分为m(m>0)个互不相交的了T1,T2,T3……T m，其中每个子集本身又是一棵树，称其为根的子树。 5.二叉树：是n(n>=0)个结点的有限集合。若n=0时称为空树，否则： （1）有且只有一个特殊的称为树的根结点；（2）若n>1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。 6.二叉树的性质： 性质1：在非空二叉树中，第i层上至多有2i-1个结点(i>=1)。 性质2：深度为k的二叉树至多有2k-1个结点(k>=1) 。 性质3：对任何一棵二叉，若其叶子结点数为n0，深度为2的结点数为n2，则n0=n2+1。 性质4、性质5 7．二叉树存储结构：顺序存储、列表存储 8.图的存储结构（方式）：邻接矩阵（广度优先） 9.哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址。 10.冲突处理：当出现冲突时，为冲突元素找到另一个存储位置。 11.快速排序在（c ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 12.设有n个结点的无向图，该图至少应有( n-1)条边才能确保是一个连通图. 最多的是N（N-1）/2 13.邻接矩阵是对称矩阵的图是无向图 14. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 15.双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ D ） A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink; B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink; C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p; D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 16.设树T的度为3，其中度为1，2，3的结点个数分别为2，1，1 则T中的叶子数为 4 。 17.设哈夫曼树的结点总数为2n-1个，则叶子数是n。 18.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树满足只有一个叶子结点。 19.不存在特别好与坏的哈希函数，要视情况而定。 20.若选用H（K）=K %9作为散列函数，则20的散列地址为 2 。 21.对一个有序表，用二分（对半）法查找某元素的速度比用顺序法查找一定快？ 二分查找法的查找速度一定比顺序查找法快。（×）（不能确定） 22.在双链表中，在指针P所指结点前面插入一个结点S时的语句序列是： S->next=P;S->prior=P->prior;P->prior=S;____ S->prior->next=S ___； 23. 在双向链表指针p的结点前插入一个指针q的结点操作是（C ）。 C. q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;考研数据结构必须掌握的知识点与算法-打印版
华南师范大学计算机学院925数据结构历年考研真题汇编34p
2018考研计算机：数据结构重难点及复习建议
计算机数据结构考研真题及其答案
考研数据结构图的必背算法及知识点
计算机考研数据结构真题汇总
最新数据结构考研大纲资料
计算机考研数据结构统考历年真题
数据结构考研必背算法5星
考研《数据结构》复习知识点归纳
数据结构精选考研试题
湖北工业大学计算机学院数据结构历年考研真题汇编
考研数据结构图的必背算法及知识点
数据结构考研真题及其答案
数据结构考研知识点总结
数据结构考研真题及其答案
历年《数据结构》考研真题及解答
数据结构(考研复习整理)
相关主题
文本预览