下载文档原格式
山西省考研计算机科学与技术复习资料数据结构常见算法解析算法是计算机科学与技术领域的重要核心内容之一，而数据结构是算法实现的基础。
在山西省考研计算机科学与技术的复习中，掌握常见的数据结构和算法解析是至关重要的。
本文将针对山西省考研计算机科学与技术专业的考试要求，为考生提供一份数据结构常见算法的解析资料。
一、线性表1.1 顺序表1.1.1 插入操作在顺序表中插入一个元素，需要将插入位置后的元素依次后移一个位置，然后将新元素插入到空出的位置。
1.1.2 删除操作在顺序表中删除一个元素，需要将删除位置后的元素依次前移一个位置。
1.2 链表1.2.1 单链表单链表由节点组成，每个节点包含数据域和指针域。
插入和删除操作只需要改变指针域即可。
1.2.2 双链表双链表在单链表的基础上，每个节点多了一个指向前驱节点的指针域。
1.3 栈和队列1.3.1 栈栈是一种具有特定操作限制的线性表，只允许在表尾进行插入和删除操作，符合先进后出的原则。
1.3.2 队列队列也是一种具有特定操作限制的线性表，只允许在表尾进行插入操作，在表头进行删除操作，符合先进先出的原则。
二、树2.1 二叉树2.1.1 先序遍历先序遍历是指按照根节点-左子树-右子树的顺序遍历二叉树。
2.1.2 中序遍历中序遍历是指按照左子树-根节点-右子树的顺序遍历二叉树。
2.1.3 后序遍历后序遍历是指按照左子树-右子树-根节点的顺序遍历二叉树。
2.2 平衡二叉树平衡二叉树要求左子树和右子树的高度差不超过1，在插入和删除操作时，需要对树进行旋转操作以保持平衡。
2.3 B树B树是一种自平衡的搜索树，适用于大数据量的存储和快速查找。
三、图3.1 图的存储结构3.1.1 邻接矩阵邻接矩阵是通过一个二维数组来表示图的连接关系。
3.1.2 邻接表邻接表是通过一个链表数组来表示图的连接关系。
3.2 图的遍历算法3.2.1 深度优先搜索（DFS）深度优先搜索是从图的某个顶点开始，递归遍历其邻接点，直到没有未访问的邻接点为止。
《数据结构B》实验指导书计算机科学与技术学院计算机科学与技术系2011年09月目录实验一线性表 (1)实验二树 (5)实验三图 (7)实验四查找 (11)实验五内排序 (13)实验一线性表【目的与要求】本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上的实现，提高分析和解决问题的能力。
要求仔细阅读并理解下列例题，上机调试并编译执行通过，并观察其结果，然后独立完成后面的实验内容，写出完整的实验报告。
编写程序过程中注意养成良好的编程风格与习惯，要求程序结构清晰，程序缩进，适当注释。
【参考例题】[问题描述]用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。
[输入]初始字符串，插入位置，插入字符，删除字符。
[输出]已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。
[存储结构]采用链式存储结构[算法的基本思想]建立链表：当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各个结点的数据域。
[参考源程序]#define NULL 0typedef struct node{char a;struct node *link;}node,*nodelink;void readlink(nodelink head){nodelink p,q;char c;p=head;printf("Input a linktable(a string):");scanf("%c",&c);if (c=='\n') printf("This string is empty。
山西省 2015年专升本选拔考试C 程序设计数据结构（C语言版）说明：1.本试卷分C程序设计和数据结构（C语言版）两部分，各占100分，满分200 分，考试时间150分钟。
2.答卷前先填写密封线内的项目和座位号，答案直接写在试卷上。
第一部分C程序设计一、单项选择题【本大题共10小题，每小题1分，共计10分。
在每小题的四个备选答案中，只有一个答案是正确的，请将代表正确答案的字母填入下列表格内）1.下列标识符中,不合法的标识符是（B ）A.CHARB.-abC.SumD.a_b2.下列不是合法字符常量的是（B ）A.‘+’B. "m"C.‘?’D.‘6’3.假设定义 int x,y;且执行scanf("%d%3d"，&x，&y）；语句时，从第一列开始输入数据1234 56789<回车>，则x和y的值分别是（A ）A.1234 567B.1234 56789C.1 234D.1234 894.执行下面程序时，将M，N分别赋给c，d，正确的输入是（B ）main({char c,d;scanf(“c:%c;d:%c”,&c,&d);}A.M NB. c:M;d:NC.M;ND.c:M d:N5. 在下列运算符中，优先级最低的运算符是（C ）A.!=B.!C. &&D.++6. 若a=1，b=2，c=3，d=4，则条件表达式 a<b?a:c<d?c:d 的结果是（A）A.1B.2C.3D.47. 以下程序输出结果是（D ）main{int i=8,j=8;printf("%d,%d\n",++i, j--);A.8,7B.8,8C. 9,7D.9,88.在C语言的语句中，用作判断的表达式是（D ）A.关系表达式B.逻辑表达式C.算术表达式D.任意表达式9.在C语言中，while 和 do…while循环的主要区别是（A ）A.do……while 的循环体至少无条件执行一次B.while 循环的控制条件比do…while的循环控制条件严格C.do…while允许从外部转到循环体内D.do…while的环体不能是复合语句10.下列定义语句不正确的是（C ）A.double x[5]={2.0,4.0,6.0,8.0,10.0};B.char c1[]={‘1’，‘2’，‘3’，’4’, ‘5’，‘1’}；C. int yf[5]=(0,1,3,5,7,9);D.char c2[]={‘\10’,’\xa’,’\x8’};二、填空题（本大题共5小题，每空2分，共计12分。
2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)的全部内容。
2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C .A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便.6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A .（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2) 。
数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究（ D ）。
A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。
A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。
A. 图B. 树C. 广义表D. 栈6、算法是（ D ）。
A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。
A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)11、抽象数据类型的三个组成部分分别为（ A ）。
A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型二、填空题三、综合题1、将数量级O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增长率由小到大排序。
答案： O(1) O(log2N) O(N) O(Nlog2N) O(N2) O(N3) O(2N)一、填空题1. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。
2. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
3. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。
8．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引、散列。
9. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
二、单项选择题（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储三、简答题1.数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。
华北国土资源丨论文I n7qHuabei land and Resources | u ^u对山西省统一年产值更新工作中农用地附加收益数据的分析李宇(山西省国土资源调查规划院，山西太原034000)摘要：农用地附加收益是年产值标准测算过程中的一项基础调查内容，文章通过对农用地附加收益这一项数据的汇总与分析，为今后的统一年产值更新工作提供一定的数据基础与指导意见。
关键词：统一年产值更新工作；农用地附加收益；数据分析中图分类号：F301 文献标识码：A文章编号：1672-7487 (2018) 01-75-31引言开展征地统一年产值标准更新工作，是依法做好征地 补偿标准工作、维护被征地农民的切身利益、促进土地资 源的合理利用和优化配置的重要举措，更是解决当前征地 补偿中存在的区域划分不合理、行政区域之间补偿标准悬 殊过大、个别地区补偿标准与经济发展不适应等问题的客 观需要。
2013年山西省政府公布的统一年产值标准《山西省人 民政府关于调整全省征地统一年产值标准的通知》（晋政 发[2013]22号）已执行了4年。
4年间，随着山西省经济社会 的发展，不管是主要农作物产量、价格和附加收益，还是 人均GDP、农民人均收入、养老保险标准等各方面因素都 有了不同的增长变化，继续采用原先的标准必然会带来各 种各样的社会问题，为了更好地保护农民利益，保障经济 建设的髓服2017年，山西省开雛行了新，的统一 年靖示准酿工作。
农用地的附加收益调查，是年产值标准测算过程中的 一项基本调查内容，对各县统一年产值标准的最终确定具 有一定的指导和借鉴作用。
2概念与内涵农用地的附加收益调查，是与主要农作物年产量调查同步进行的。
农用地的附加收益包括其他副产品收益和其 他多种经营收益（其他种植等多种经营）以及相关的农业 补贴调查。
其他副产品主要是指农作物的秸秆等农副产 品，可根据实际情况进行折算；其他多种经营主要是指其 他种植等多种经营等。
1、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。
（1）．请各举一个结点个数为5的二部图和非二部图的例子。
（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。
设G用二维数组A来表示，大小为n*n（n为结点个数）。
请在程序中加必要的注释。
若有必要可直接利用堆栈或队列操作。
【
2、冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。
（注：双向起泡排序即相邻两趟排序向相反方向起泡）
3、本题应使用深度优先遍历，从主调函数进入dfs(v)时，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。
将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。
题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。
建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。
int num=0， visited[]=0 //num记访问顶点个数,访问数组visited初始化。
const n=用户定义的顶点数;
AdjList g ; //用邻接表作存储结构的有向图g。
void dfs(v)
{visited [v]=1; num++; //访问的顶点数＋1
if (num==n) {printf(“%d是有向图的根。
\n”,v); num=0;}//if
p=g[v].firstarc;
while (p)
{if (visied[p->adjvex]==0) dfs (p->adjvex);
p=p->next;} //while
visited[v]=0; num--; //恢复顶点v
}//dfs
void JudgeRoot()
//判断有向图是否有根，有根则输出之。
{static int i ;
for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。
{num=0; visited[1..n]=0; dfs(i); }
}// JudgeRoot
算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。
4、编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。
5、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。
所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。
请给出用“破圈法”
求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算
法。
注：圈就是回路。
6、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列
可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15
分）
（1）A和D是合法序列，B和C 是非法序列。
（2）设被判定的操作序列已存入一维数组A中。
int Judge(char A[])
//判断字符数组A中的输入输出序列是否是合法序列。
如是，返回true，否则返回false。
{i=0; //i为下标。
j=k=0; //j和k分别为I和字母O的的个数。
while(A[i]!=‘\0’) //当未到字符数组尾就作。
{switch(A[i])
{case‘I’: j++; break; //入栈次数增1。
case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}
}
i++; //不论A[i]是‘I’或‘O’，指针i均后移。
}
if(j!=k) {printf(“序列非法\n”)；return(false);}
else {printf(“序列合法\n”)；return(true);}
}//算法结束。
7、(1)p->rchild (2)p->lchild (3)p->lchild (4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild)
25. (1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)
26. .(1)top++ (2) stack[top]=p->rchild (3)top++ (4)stack[top]=p->lchild
27. (1)*ppos // 根结点（2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1
8、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入
的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况
（入栈满等）给出相应的信息。
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。
问能
否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。
设布尔函数Knap(S，
n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。
请在下
列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)
若S=0
则Knap←true
否则若（S<0）或(S>0且n<1)
则Knap←false
否则若Knap(1) , _=true
则print(W[n])；Knap ←true
否则 Knap←Knap(2) _ , _
设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。
例如：
设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。
将n(n>1)个整数存放到一维数组R中。
设计一个尽可能高效（时间、空间）的算
法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0, x1, x2,…, xn-1），变换为(xp， xp＋1, … , xn-1 ,x0 , x1,…, xp-1)。
9、4、void LinkList_reverse(Linklist &L)
//链表的就地逆置;为简化算法,假设表长大于2
{
p=L->next;q=p->next;s=q->next;p->next=NULL;
while(s->next)
{
q->next=p;p=q;
q=s;s=s->next; //把L的元素逐个插入新表表头
}
q->next=p;s->next=q;L->next=s;
}//LinkList_reverse
10、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。
编写一个算法完成下列功能：
（1）．建立有向图G的邻接表存储结构；
（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。
