2010内蒙古自治区数据结构与算法(必备资料)

1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A) 单链表 B) 仅有头指针的单循环链表C) 双链表 D) 仅有尾指针的单循环链表2、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一C）不含回路 D）有n条边3、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一C）不含回路 D）有n条边4、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。

A）top不变 B）top=0 C）top-- D）top++5、以下属于顺序存储结构优点的是（ A ）。

A) 存储密度大B) 插入运算方便C）删除运算方便D）可方便地用于各种逻辑结构的存储表示6、广义表head(((a,b),(c,d)))的运算结果为（ A ）。

A）(a,b) B）(c,d)C）空表 D）（（a,b）,(c,d)）7、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)8、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A9、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。

B）线性表采用链接存储，便于插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用顺序存储，便于进行插入和删除操作。

10、设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。

A）p->next=p->next->next; B） p=p->next;C）p=p->next->next; D） p->next=p;11、n个顶点的强连通图至少有（ A ）条边。

内蒙古自治区考研计算机科学与技术二全科复习资料内蒙古自治区考研计算机科学与技术二全科复习资料是帮助考生全面准备和复习计算机科学与技术二专业知识的重要资料。

本文将介绍该资料的内容以及如何有效利用该资料进行复习。

一、资料简介内蒙古自治区考研计算机科学与技术二全科复习资料包含了该专业各学科的重点知识点、考点、常见题型以及解题思路等内容。

该资料主要分为以下几个部分：1. 专业基础知识：包括数据结构与算法、操作系统、数据库原理、计算机网络等专业基础知识的概念、原理和应用。

2. 专业选修课：根据内蒙古自治区考研计算机科学与技术二的要求，该资料还包括了专业选修课的相关知识点，如人工智能、图像处理等。

3. 历年真题解析：该资料还提供了近几年的考研真题及详细解析，帮助考生了解题目类型、难度以及解题思路，提高解题能力。

4. 模拟试题：为了帮助考生进行自我评估和提前适应考试环境，该资料还提供了大量的模拟试题，覆盖了各个知识点和题型。

二、资料使用方法为了最大限度地发挥该复习资料的作用，考生可以按照以下步骤进行复习：1. 制定复习计划：根据自己的时间和复习进度，合理安排每天的复习内容和时间，确保能够充分利用资料进行复习。

2. 阅读理解知识点：首先通读资料中的概念和原理部分，对各个知识点进行了解和理解，弄清楚核心概念和相关原理。

3. 刷题巩固知识点：在掌握了基础知识后，可以选择性地刷一些题目进行巩固。

根据资料中提供的题目和解析，有针对性地复习和提高自己的解题能力。

4. 针对性训练不足部分：在复习过程中，要注意发现自己的薄弱环节并加以针对性的复习和训练。

可以重点花时间解析和研究那些自己做错的题目或者不熟悉的知识点。

5. 考前模拟演练：在离考试时间较近时，可以进行一些模拟试题的演练，模拟真实考试环境，检验自己的复习情况。

三、复习技巧除了利用复习资料进行系统的复习外，考生还可以结合以下技巧提高复习效果：1. 制定合理的目标：根据考生自身情况和考试要求，制定合理的复习目标，把整个复习过程划分为若干个阶段和小目标，逐步完成，并及时进行总结和反馈。

1、将顶点放在两个集合V1和V2。

对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。

为此，用整数1和2表示两个集合。

再用一队列结构存放图中访问的顶点。

int BPGraph (AdjMatrix g)//判断以邻接矩阵表示的图g是否是二部图。

{int s[]; //顶点向量，元素值表示其属于那个集合（值1和2表示两个集合）int Q[];//Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。

int f=0,r,visited[]; //f和r分别是队列的头尾指针,visited[]是访问数组for (i=1;i<=n;i++) {visited[i]=0;s[i]=0;} //初始化，各顶点未确定属于那个集合Q[1]=1; r=1; s[1]=1;//顶点1放入集合S1while(f<r){v=Q[++f]; if (s[v]==1) jh=2; else jh=1;//准备v的邻接点的集合号if (!visited[v]){visited[v]=1; //确保对每一个顶点，都要检查与其邻接点不应在一个集合中for (j=1,j<=n;j++)if (g[v][j]==1){if (!s[j]) {s[j]=jh; Q[++r]=j;} //邻接点入队列else if (s[j]==s[v]) return(0);} //非二部图}//if (!visited[v])}//whilereturn(1); }//是二部图[算法讨论] 题目给的是连通无向图，若非连通，则算法要修改。

2、假设K1，…，Kn是n个关键词，试解答：试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，…，Kn 时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

3、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.4、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}写出G的拓扑排序的结果。

1、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。

N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct node{int data; struct node *lchild,*rchild;}node;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2)___ NR++; else (3)__ ;if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;}26.树的先序非递归算法。

void example(b)btree *b;{ btree *stack[20], *p；int top;if (b!=null){ top=1; stack[top]=b;while (top>0){ p=stack[top]; top--;printf(“%d”,p->data);if (p->rchild!=null){(1)___; (2)___;}if (p->lchild!=null)(3)___; (4)__;}}}}2、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.3、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。

设当n=m-1时结论成立，现证明当n=m时结论成立。

设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。

1、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。

所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。

void Translation（float *matrix，int n）//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。

{int i,j,k,l；float sum，min； //sum暂存各行元素之和float *p, *pi, *pk;for(i=0; i<n; i++){sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和.*(p+i)=sum; //将一行元素之和存入一维数组.}//for ifor(i=0; i<n-1; i++) //用选择法对数组p进行排序{min=*(p+i); k=i; //初始设第i行元素之和最小.for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号.if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和){pk=matrix+n*k; //pk指向第k行第1个元素.pi=matrix+n*i; //pi指向第i行第1个元素.for(j=0;j<n;j++) //交换两行中对应元素.{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.}//if}//for ifree(p); //释放p数组.}// Translation[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).2、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。

内蒙古自治区考研计算机科学与技术复习资料数据结构常考题目数据结构是计算机科学与技术考研的重要考点之一。

下面将为考生们提供一些内蒙古自治区计算机科学与技术考研的数据结构常考题目，供大家参考复习。

1. 顺序存储和链式存储的区别是什么？请举例说明。

顺序存储是在内存中按照线性顺序存储数据元素，通过数组实现。

链式存储是通过节点之间的指针链接来存储数据元素。

以实现线性表为例，顺序存储在内存中分配连续的存储空间，每个元素的存储位置可以通过索引计算得到。

而链式存储通过节点的next指针将各个节点链接在一起，每个节点存储数据元素以及指向下一个节点的指针。

2. 什么是栈和队列？它们的特点和应用场景分别是什么？栈是一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作。

栈的特点是只能访问栈顶元素，插入和删除操作都在栈顶进行，如函数调用栈、表达式求值等场景常使用栈来实现。

队列是一种先进先出（FIFO）的数据结构，允许在一端进行插入操作，在另一端进行删除操作。

队列的特点是只能访问队头和队尾元素，插入和删除操作分别在队尾和队头进行，如打印任务队列、消息队列等场景常使用队列来实现。

3. 请解释什么是二叉树和二叉搜索树，并给出它们的示例。

二叉树是每个节点最多有两个子节点的树结构。

每个节点最多有两个子节点，一个是左子节点，另一个是右子节点。

二叉搜索树是一种特殊的二叉树，它的左子树中的节点值小于根节点的值，右子树中的节点值大于根节点的值。

示例：5/ \3 7/ \2 44. 请解释什么是图和树的区别，并给出它们的应用场景。

树是一种特殊的图，它没有回路的图被称为树。

树具有层级结构，根节点位于最顶层，叶子节点位于最底层。

图是由节点和边组成的一种数据结构，节点之间的连接关系由边表示。

图是一种更为普遍的数据结构，可以是有向图或无向图，节点之间的关系可以是多对多的。

树的应用场景包括文件系统、家谱、网络拓扑结构等。

图的应用场景包括社交网络、地图导航、网络拓扑分析等。

内蒙古自治区考研计算机科学复习必备知识点1. 数据结构与算法数据结构与算法是计算机科学的基础，也是考研计算机科学专业的必备知识点。

在考研过程中，需要掌握以下几个重要的数据结构和算法：a) 数组与链表：数组是一种线性数据结构，能够在O(1)的时间复杂度内访问任意位置的元素。

链表是一种非线性数据结构，通过指针连接各个元素。

掌握数组与链表的特点、操作及其应用场景非常重要。

b) 栈与队列：栈是一种先进后出（FILO）的数据结构，队列是一种先进先出（FIFO）的数据结构。

掌握栈和队列的实现方式、基本操作以及应用场景。

c) 树与图：树是一种非线性数据结构，图是一种更加复杂的非线性数据结构。

掌握二叉树、二叉搜索树、堆、哈夫曼树等树的定义、遍历方式及其应用。

了解图的基本概念、表示方法以及最短路径算法、最小生成树算法等。

d) 排序与查找：了解常见的排序算法，如冒泡排序、选择排序、插入排序、快速排序、归并排序等，以及它们的时间复杂度和稳定性。

了解查找算法，如顺序查找、二分查找、哈希查找等。

2. 计算机网络计算机网络是计算机科学与技术的核心技术之一，在考研中也是重点考察的内容。

以下是值得关注的计算机网络知识点：a) 网络协议：了解TCP/IP协议族的基本架构、各层的功能和具体协议。

深入了解常用的应用层协议，如HTTP、FTP、SMTP等。

b) 网络通信：掌握数据在网络中的传输方式，如广播、单播、多播和任播。

了解常见的网络传输协议，如UDP和TCP。

熟悉IP地址、子网掩码、网关等网络地址的概念和使用。

c) 网络设备：了解路由器、交换机、网卡等网络设备的基本原理和功能。

了解子网的划分、VLAN的配置等网络设备的实际应用。

d) 网络安全：了解常见的网络攻击手段，如DDoS攻击、SQL注入攻击等，以及相应的防御措施。

掌握常见的加密算法和认证机制。

3. 数据库技术数据库是计算机科学中重要的应用技术之一，也是考研中的必备知识点。

内蒙古自治区考研计算机科学与技术四全科复习资料计算机科学与技术是一个快速发展的学科领域，它的知识体系非常庞大和复杂。

对于准备参加内蒙古自治区考研计算机科学与技术四全科考试的考生来说，有一个全面而准确的复习资料非常重要。

本文将为考生们提供一些复习资料的建议，以帮助他们在考试中取得好成绩。

第一科目：数据结构与算法分析数据结构与算法分析是计算机科学与技术学科的基础，也是考研考试中的重要内容。

考生们应重点复习以下几个方面的知识：1. 算法的时间与空间复杂度分析：考生们需要掌握常见算法的时间复杂度和空间复杂度，了解不同算法之间的优劣，并能够分析算法的效率。

2. 常见数据结构的实现与应用：考生们需要熟悉常见数据结构的特点、实现方法和应用场景，如数组、链表、栈、队列、树等。

3. 查找和排序算法：考生们需要了解查找和排序算法的原理和实现方法，包括顺序查找、二分查找、快速排序、归并排序等。

第二科目：操作系统与系统结构操作系统与系统结构是计算机科学与技术学科的重要组成部分，也是考研考试的重点内容。

考生们应重点复习以下几个方面的知识：1. 操作系统的基本概念和原理：考生们需要了解操作系统的基本概念、进程与线程管理、内存管理、文件系统管理等方面的知识。

2. 操作系统的实现和设计：考生们需要了解操作系统的实现和设计方法，包括中断处理、进程调度算法、内存管理算法等。

3. 计算机系统结构：考生们需要了解计算机系统的各个组成部分，如CPU、存储器、输入输出设备等，并了解它们之间的工作原理和相互关系。

第三科目：计算机网络计算机网络是一个涵盖面很广的学科，它对于计算机科学与技术学科的发展和应用起着重要的作用。

考生们应重点复习以下几个方面的知识：1. 计算机网络的基本概念和原理：考生们需要了解计算机网络的基本概念、拓扑结构、通信协议等方面的知识。

2. 网络通信技术和协议：考生们需要了解常见的网络通信技术和协议，如以太网、TCP/IP协议等，并能够分析网络通信的过程。

内蒙古自治区考研计算机科学复习资料数据结构重要题型归纳数据结构是计算机科学与技术领域中的基础课程之一，对于考研学生来说，熟练掌握数据结构的各种题型是必不可少的。

本文将从内蒙古自治区考研的角度出发，对数据结构中的重要题型进行归纳总结，供考生参考。

1. 数组和链表数组和链表是数据结构中最基本的两种数据类型，也是考研中经常出现的重要题型。

在解题过程中，考生需要理解数组和链表的基本概念和特点，并掌握它们的插入、删除、查找等操作。

2. 栈和队列栈和队列是常用的线性数据结构，同样也是考研中的热门考点。

考生需要了解栈和队列的特点，掌握它们的基本操作，如入栈、出栈、入队、出队等，并能够根据题目要求选择合适的数据结构进行解题。

3. 串串是由零个或多个字符组成的有限序列，字符串处理在计算机科学中有着广泛的应用。

考生需要了解串的基本操作，如串的比较、复制、连接等，并能够灵活运用相关算法解决与串相关的问题。

4. 树树是一种重要的非线性数据结构，常用于组织和存储具有层次关系的数据。

在考研中，二叉树及其派生结构是重点考点之一。

考生需要熟悉树的基本概念，掌握二叉树的各种遍历方式，如前序遍历、中序遍历、后序遍历等，并能够应用相关算法解决与树相关的问题。

5. 图图是由顶点和边组成的一种复杂数据结构，广泛应用于网络、社交等领域。

在考研中，图的基本概念和算法也是重要的考点。

考生需要了解图的表示方法，掌握图的遍历算法，如深度优先搜索（DFS）和广度优先搜索（BFS），并能够根据题目要求选择合适的算法解决与图相关的问题。

6. 排序和查找排序和查找是数据结构中非常重要的两个方面。

常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等，考生需要理解各种排序算法的原理和特点，并能够根据题目要求选择合适的排序算法解决问题。

查找算法包括线性查找、二分查找、哈希查找等，考生需要了解各种查找算法的原理和适用场景，并能够根据题目要求选择合适的查找算法解决问题。