第一篇：2014考研数据结构变化
一、数据结构考查目标
1、掌握数据结构的基本概念、基本原理和基本方法。
2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基
本的时间复杂度与空间复杂度的分析。
3、能够数据结构基本原理和方法进行问题的分析与求解，具备采用C或
C++语言设计与实现算法的能力。
二、数据结构变化解析
1.变化一
【考察目标】
3.能够数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力，删去了“Java”。
2.变化二
四.图
(二)图的存储及基本操作
1.邻接矩阵法
2.邻接表法
3.邻接多重表、十字链表(新增考点)
3.变化三
五、查找
(一)查找的基本概念
(二)顺序查找法
(三)分块查找法(新增考点)
(四)折半查找法
(五)B树及其基本操作、B+树的基本概念
(六)散列(Hash)表
(七)字符串模式匹配(新增考点)
(八)查找算法的分析与应用
三、复习与备考指导
1、扎实基础，注意综合应用，特别是有关于线性表算法的综合设计，一定要牢牢掌握。
2、加强对C语言基础的学习，2014年新东方在线应广大考生的需求将开设C语言专项精讲课程，保障大家考研（微博）成功。
3、大家在复习时，先要了解数据结构科目的考试范围、内容，系统梳理教材中的考查知识点，建立层次分明的知识体系。
4、数据结构科目的特点是思路灵活，概念联系紧密。从线性表，树，图，以及后面的查找，排序，是一环扣一环的。如二叉树遍历的递归和非递归算法、图的深度优先遍历等都要用道栈，树的层次遍历、图的广度优先遍历则要用到队列。查找和排序则要综合运用线性表、栈、树等知识。所以建议大家在复习时，先弄懂基本概念，然后多做习题来加深对基本概念、基础知识的理解，掌握解题思路和技巧。
5、对于数据结构的学习，难在其中的算法及实现。因此很多同学在复习数据结构时，有这样的疑问：数据结构中的算法是否需要背诵?数据结构是非常灵活的科目，所以不建议大家死记硬背算法，大家应该在理解的基础上适当的记忆一些经典算法。
6、大家在复习时，如果时间充足，可以在计算机上编写程序，自己实现教材上的算法，加深对算法的理解。不过对于时间仓促的同学来说，可以使用实例来验证自己算法的正确性
第二篇：2009考研数据结构试题点评
2009年考研计算机专业综合考试数据结构试题点评
2009年考研计算机专业综合考试是统一命题后的首次考试。本次考试统考科目包括四门计算机专业课：数据结构、计算机组成原理、操作系统和计算机网络，这四门课程合在一起称为计算机科学专业基础综合，共150分。其中数据结构占45分。总体上来看，2009年的考研数据结构试题注重对基础知识的考察。重点考察的是对基本知识点、基本概念的理解。在基础题中又有拔高，重点考察了对基础知识的应用能力、应变能力和实际动手能力。题目总的来说不难，没有出现超出考试大纲的题目。
下面我们对2009的考研数据结构试题进行简要的点评。
一、单项选择题，每小题2分，共80分。
单选题覆盖了大纲列出的各章的知识点，主要考察对各种数据结构、基本查找和排序算法的基本概念和特点的理解以及灵活运用。1-10题是数据结构部分的试题。
1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是
A.栈 B.队列 C.树 D.图
点评：此题考察对各种数据结构的特点的理解及应用。栈的特点是后进先出。队列的特点是先进先出。树的特点是除根以外的结点有且只有唯一的前驱（双亲）。图是最复杂的数据结构，它的任一结点都可以有多个前驱和后继。据题意“输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据”，处理应是先来先服务，因此答案为B。
2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是
A．1 B.2 C.3 D.4 点评：此题考察对栈和队列的特点及基本操作的应用。根据元素的出队顺序可知元素的进栈、出栈顺序，从而判断栈中同时容纳多少元素，得出栈的容量。因bdcfeag依次出队，故元素的出栈顺序也是这样的，那么他们在栈中操作顺序依次为：a入栈、b入栈、b出栈、c入栈、d入栈、d出栈、c出栈、e入栈、f入栈、f出栈、e出栈、a出栈、g入栈、g出栈。这其间栈中数据最多有3个。因此答案为C。
3.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，7，5，6，1,2，4，则其遍历方式是
A．LRN B.NRL C.RLN D.RNL 点评：此题考察对二叉树的六种遍历的理解及应用。二叉树有六种遍历方式：先序遍历、中序遍历、后序遍历。每种遍历访问根结点的顺序不一样。先序遍历先访问根，中序遍历中间访问根，后序遍历最后访问根。一般教材中都是先左子树，后右子树，但该题用另一种方式，先右子树，后左子树。从遍历得到的序列中第一个遍历出来的元素是3，可知是中序遍历，因此答案是D。
4.下列二叉排序树中，满足平衡二叉树定义的是
A．B.C.D.点评：此题考察对平衡二叉树的定义的掌握，平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。因此答案为B。
5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是
A．39 B.52 C.111 D.119 点评：此题考察对完全二叉树的定义的理解及对二叉树每层最大结点个数的计算。完全二叉树第一层到倒数第二层结点个数均达到每层的最大值，2(i为层数)，第6层有8个叶结点，说明这棵完全二叉树最多7层，第6层的32个结点有24（32-8）结点有孩子结点，孩子结点最多有48个（24*2）,所以完全二叉树的结点数最多为：1+2+4+8+16+32+48=111。
i-
1故答案为C。
6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是
I．父子关系 II.兄弟关系 III.u的父结点与v的父结点是兄弟关系 A.只有II B.I和II C.I和III D.I、II和III 点评：此题考察森林转化为二叉树时结点之间的关系的变化。根据森林转化为二叉树的转化过程可知，一个结点ｕ和它的第二个孩子结点ｖ转化为二叉树后就变为结点u是结点v的父结点的父结点，同一个结点的第一个孩子u和第三个孩子v转化为二叉树后也变为结点u是结点v的父结点的父结点，因此可以推出u和v在原来的森林中要么是父子关系，要么是兄弟关系。因此答案是B。
7.下列关于无向连通图特性的叙述中，正确的是
I．所有顶点的度之和为偶数 II.边数大于顶点个数减1 III.至少有一个顶点的度为1 A.只有I B.只有II C.I和II D.I和III 点评：此题考察图的度与边的关系、无向连通图特性。在图中所有顶点的度之和为边数的2倍，而连通图中边数不为零，所以一定是偶数。N个顶点的无向连通图至少有n-1条边，顶点的度至少是1。因此答案为A。
8.下列叙述中，不符合m阶B树定义要求的是
A．根节点最多有m棵子树 B.所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接
点评：此题考察对m阶B树的定义的理解与应用。B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
①树中每个结点至多有m棵子树；
②若根结点不是叶子结点，则它至少有两棵子树； ③除根之外的所有非叶子结点至少有「m/2]棵子树；
④所有的非叶子结点中包含下列数据信息
(n，A0，K1，A1，K2，A2，„，Kn，An)
其中：Ki(i=1，2，„，n)为关键字，且Ki n+1为子树个数） ⑤所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。据此定义可知答案为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 点评：此题考察对堆调整算法--“筛选”算法的应用。筛选算法要求根的左右子树必须是堆。把3插入后，关键序列变为5，8，12，19，28，20，15，22，3，以5为根的左右子树的堆结构可能被破坏，因此必须重建堆，从n/2个结点开始调用筛选算法，直到第一个结点，就可重建堆。答案为A。 10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是 A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序 点评：此题考察对各种排序方法的步骤、特点的理解及应用。起泡排序第i趟结束后可以把第i大的数放到正确位置。插入排序第i趟结束后前i个元素是有序的，但不一定是这些元素的最后位置。选择排序第i趟结束后可以把第i小的数放到正确位置。二路归并排序第i趟结束后可以得到长度为2i 的有序子序列。故答案为B。 二、综合应用题 综合应用题主要考察综合运用基本知识分析问题、解决问题的能力。41-42为数据结构部分的题。一道问答题、一道算法设计题。 41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法： ①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点； ②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v； ③重复步骤②，直到u是目标顶点时为止。 请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。点评：此题考察对最短路径的理解及应用。最短路径就是从初始顶点到目标顶点之间的路径上权值和最小的路径。题目中的方法在选择顶点时并没有找到下一条权值最下的边，所以该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为 A→D→C。 42.（15分）已知一个带有表头结点的单链表，结点结构为 data link 假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求： （1）描述算法的基本设计思想（2）描述算法的详细实现步骤 （3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。 点评：此题是一道算法设计题，算法设计是数据结构课程的一个重点内容，也是一个难点。此题考察对单链表的基本运算的理解及灵活运用。一般教材中在单链表中查找结点都是从头数第i个结点，而本题中要倒数第k个结点，难度就大了，要把单链表的基本运算进行改写，关键在于要查倒数第K个位置上的结点，此时需要两个流动指针，一个整型变量，从链表头向后遍历，其中指针P1指向当前遍历的结点，指针P指向P1所指向结点的前K个结点，如果P1之前没有K个结点，那么P指向表头结点。用整型变量i表示当前遍历了多少结点，当i>k时，指针P随着每次遍历，也向前移动一个结点。当遍历完成时，P或者指向表头就结点，或者指向链表中倒数第k个位置上的结点。 算法描述： int LocateElement(linklist list,int k){ P1=list->link;P=list;i=1;while(P1){ P1=P1->link;i++;if(i>k)P=P->next;//如果i>k,则p也往后移 } if(P==list)return 0;//说明链表没有k个结点 else { printf(“%dn“,P->data);return 1;} } 一、选择题 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)的算法在时间上总是优于复杂度nO(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分）】 A．栈 B.哈希表 C.线索树 D.双向链表 11．在下面的程序段中，对x的赋值语句的频度为（C）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; 2nA． O(2n)B．O(n)C．O(n)D．O(log2)12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（D） 32A.O（n）B.O(nlogn)C.O(n)D.O(n)【南京理工大学1998 一、1(2分)】 13．以下哪个数据结构不是多型数据类型（D）【中山大学 1999 一、3（1分）】 A．栈 B．广义表 C．有向图 D．字符串 14．以下数据结构中，（A）是非线性数据结构【中山大学 1999 一、4】 A．树 B．字符串 C．队 D．栈 15.下列数据中，（C）是非线性数据结构。【北京理工大学 2001 六、1（2分）】 A．栈 B.队列 C.完全二叉树 D.堆 16．连续存储设计时，存储单元的地址（A）。【中山大学 1999 一、1（1分）】 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 17．以下属于逻辑结构的是（C）。【西安电子科技大学应用 200 1一、1】 A．顺序表 B.哈希表 C.有序表 D.单链表 二、判断题 1.数据元素是数据的最小单位。(X)【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1（1分）】 【上海交通大学 1998 一、1】 【山东师范大学 2001 一、1（2分）】 2.记录是数据处理的最小单位。(X)【上海海运学院 1998 一、5（1分）】 3.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(X)【北京邮电大学2002 一、1（1分）】 4．算法的优劣与算法描述语言无关，但与所用计算机有关。(X)【大连海事大学 2001 一、10（1分）】 5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(O)【大连海事大学 2001 一、11（1分）】 6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(X)【西安交通大学 1996 二、7（3分）】 7．程序一定是算法。(X)【燕山大学 1998 二、2（2分）并改错】 8．数据的物理结构是指数据在计算机内的实际存储形式。(O)【山东师范大学2001 一、2（2分）】 9.数据结构的抽象操作的定义与具体实现有关。(X)【华南理工大学 2002 一、1（1分）】 10.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(X)【华南理工大学 2002 一、2（1分）】 11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(X)【上海海运学院 1999 一、1（1分）】 12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(O)【华南理工大学 2002 一、5（1分）】 13.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(X)【上海海运学院 1998 一、1（1分）】 三、填空 1．数据的物理结构包括数据元素的表示和数据元素间关系的表示。【燕山大学 1998 一、1（2分）】 2.对于给定的n个元素,可以构造出的逻辑结构有集合 线性结构 树形结构 图状结构(或网状结构)四种。 【中科院计算所 1999 二、1（4分）】 3．数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。【北京邮电大学 2001 二、1（2分）】 4．一个数据结构在计算机中表示（又称映像）称为存储结构。【华中理工大学 2000 一、1（1分）】 5．抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。【山东大学 2001 三、3（2分）】 6．数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度【北京理工大学 2001 七、1（2分）】 7.数据结构是研讨数据的_逻辑结构和物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作（运算），设计出相应的算法。【西安电子科技大学 1998 二、2（3分）】 8． 一个算法具有5个特性:（1）有穷性（2）确定性（3）可行性，有零个或多个输入、有一个或多个输出。 【华中理工大学 2000 一、2（5分）】 【燕山大学 1998 一、2（5分）】 9．已知如下程序段 FOR i:= n DOWNTO 1 DO {语句1} BEGIN x:=x+1； {语句2} FOR j:=n DOWNTO i DO {语句3} y:=y+1; {语句4} END； 语句1执行的频度为 n+1 ；语句2执行的频度为n；语句3执行的频度为n(n+3)/2；语句4执行的频度为n(n+1)/2。【北方交通大学 1999 二、4（5分）】 10．在下面的程序段中，对ｘ的赋值语句的频度为1+（1+2++（1+2+3） 3+„+（1+2+„+n）=n(n+1)(n+2)/6 O(n)（表示为n的函数） FOR i：＝１ TO n DO FOR j：＝１ TO i DO FOR k：＝1 TO j DO ｘ：＝ｘ＋delta； 【北京工业大学 1999 一、6（2分）】 11.下面程序段中带下划线的语句的执行次数的数量级是：log2n【合肥工业大学1999 三、1（分）】 i：=1； WHILE i 三、1（2分）】 i:=1;WHILE i 三、1（2分）】 i：=n*n WHILE i<>1 DO i:=i div 2;14.计算机执行下面的语句时，语句s的执行次数为(n+3)(n-2)/2。【南京理工大学2000 二、1（1.5分）】 FOR(i=l；i for(i=0;sum 二、1（2分）】 16．设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整 int f(m,n)int m,n;{ if(m==1)return 1;if(n==1){ return 1;} if(m 二、1（9分）】 17.在有n个选手参加的单循环赛中，总共将进行n(n-1)/2 场比赛。【合肥工业大学1999 三、8（2分）】 四、应用题 1.数据结构是一门研究什么内容的学科？【燕山大学 1999 二、1（4分）】 数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。 2.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1999 二、2（4分）】 四种表示方法 （1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。 （3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标），兼有静态和动态特性。 （4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。3.数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学 1994 一（8分）】 数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如C语言中的整型、实型、字符型等。整型值的范围（对具体机器都应有整数范围），其操作有加、减、乘、除、求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。“抽象数据类型（ADT）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅取决于它的逻辑特性，而与其在计算机内部如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提供接口），而不必了解实现细节。抽象数据类型的出现使程序设计不再是“艺术”，而是向“科学”迈进了一步。 4.回答问题（每题2分）【山东工业大学 1997 一（8分）】（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？ 数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。 （2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。 逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。 （3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。 栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。 （4）评价各种不同数据结构的标准是什么？ 数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征；二是是否容易实现（如对数据分解是否恰当；逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现；基本运算的选择是否恰当。） 5．评价一个好的算法，您是从哪几方面来考虑的？ 评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。 【大连海事大学 1996 二、3（2分）】【中山大学 1998 三、1（5分）】 6．解释和比较以下各组概念【华南师范大学 2000 一（10分）】 （1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型【哈尔滨工业大学 2000 一、1（3分）】（4）算法的时间复杂性 【河海大学 1998 一、2（3分）】（5）算法【吉林工业大学1999 一、1（2分）】（6）频度【吉林工业大学 1999 一、2（2分）】（1）见上面题3（2）见上面题4（3）见上面题3 （4）算法的时间复杂性是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。 （5）算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有五个重要特性：有穷性、确定性、可行性、输入和输出。 （6）频度。在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。7.根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？ 集合、线性结构、树形结构、图形或网状结构。 【北京科技大学 1998 一、1】【同济大学 1998】 8．对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学 1999 一、1（2分）】 逻辑结构、存储结构、操作（运算）。 9.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学 2000】 通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。 10.若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？ 【北京科技大学 2001 一、1（2分）】 D是数据元素的有限集合，S是D上数据元素之间关系的有限集合。11．数据结构与数据类型有什么区别？【哈尔滨工业大学 2001 三、1（3分）】 “数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。12．数据的存储结构由哪四种基本的存储方法实现？【山东科技大学 2001 一、1（4分）】 12．见上面题2。 13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？ 【山东师范大学 1996 二、2（2分）】 将学号、姓名、平均成绩看成一个记录（元素，含三个数据项），将100个这样的记录存于数组中。因一般无增删操作，故宜采用顺序存储。typedef struct {int num;//学号 char name[8];//姓名 float score;/平均成绩 }node； node student[100];14.运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。 【北京大学 1998 一、1（5分）】 见上面题4（3）。 15.在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?【 长沙铁道学院1998 四、3(6分)】 应从两方面进行讨论：如通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；若通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况作为一个元素（即一个结点存放一个人），设姓名作关键字，链表安排成有序表，这样可提高查询速度。16.试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。 【北京理工大学 2000 三、1（4.5分）】 线性表中的插入、删除操作，在顺序存储方式下平均移动近一半的元素，时间复杂度为O（n）；而在链式存储方式下，插入和删除时间复杂度都是O（1）。 17.有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为n2Tl=O(2)，A2的时间复杂度为T2=O(n)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。【北京航空航天大学 2000 二（10分）】 2n对算法A1和A2的时间复杂度T1和T2取对数，得nlog和2log。显然，算法A2好于A1。 18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学 1994 一、3（5分）】 struct node {int year,month,day;};typedef struct {int num;//帐号 char name[8];//姓名 struct node date;//开户年月日 int tag;//储蓄类型，如：0-零存，1-一年定期„„ float put;//存入累加数； float interest;//利息 float total;//帐面总数 }count； 19.写出下面算法中带标号语句的频度。 TYPE ar=ARRAY[1..n] OF datatype;PROCEDURE perm(a: ar;k, n: integer);VAR x: datatype;i:integer;BEGIN（1）IF k=n THEN BEGIN（2）FOR i:=1 TO n DO（3）write(a[i]);writeln;END ELSE BEGIN（4）FOR i:=k TO n DO（5）a[i]:=a[i]+i*i;（6）perm(a, k+1, n);END;END;设k的初值等于1。 【北京邮电大学 1997二（10分）】 (1)n (2)n+1(3)n(4)(n+4)(n-1)/2(5)(n+2)(n-1)/2(6)n-1 这是一个递归调用，因k的初值为1，由语句（6）知，每次调用k增1，故第(1)语句执行n次。（2）是FOR循环语句，在满足(1)的条件下执行，该语句进入循环体(3)n次，加上最后一次判断出界，故执行了n+1次。(4)也是循环语句，当k=1时判断n+1次（进入循环体(5)n次），k=2时判断n次，最后一次k=n-1时判断3次，故执行次数是（n+1）+n+„+3=(n+4)(n-1)/2次。语句(5)是(4)的循环体，每次比(4)少一次判断，故执行次数是n+(n-1)+„+2=(n+2)(n-1)/2次。注意分析时，不要把(2)分析成n次，更不是1次。 20.分析下面程序段中循环语句的执行次数。 i:=0;s:=0;n:=100;REPEAT i:=i+1;s:=s+10*i;UNTIL NOT((i 四、1（5分）】（这时i=4，s=100）REPEAT语句先执行循环体，后判断条件，直到条件为真时退出循环。 21．下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。 TYPE num=ARRAY [1..n] of [0..1]； PROCEDURE Inc（VAR a：num）； VAR i：integer； BEGIN i：=n； WHILE A[i]=1 DO BEGIN A[i]：=0； i：=i-1；END； END； A[i]：=1； END Inc； 【东南大学1998 三(8分)1994 二（15分）】 算法在最好情况下，即二进制数的最后一位为零时，只作一次判断，未执行循环体，赋值语句A[i]执行了一次；最坏情况出现在二进制数各位均为1（最高位为零，因题目假设无溢出），这时循环体执行了n-1次，时间复杂度是O(n)，循环体平均执行n/2次，时间复杂度仍是O(n)。22.阅读下列算法，指出算法A的功能和时间复杂性 PROCEDURE A(h,g:pointer);(h,g分别为单循环链表（single linked circular list）中两个结点指针)PROCEDURE B(s,q:pointer)； VAR p:pointer;BEGIN p:=s;WHILE p^.next<>q DO p:=p^.next;p^.next:=s;END;(of B)BEGIN B(h,g);B(g,h);END;（of A） 【东南大学 1999 二（10分）】 该算法功能是将原单循环链表分解成两个单循环链表：其一包括结点h到结点g的前驱结点；另一个包括结点g到结点h的前驱结点。时间复杂度是O(n)。 23.调用下列C函数f(n)或PASACAL函数f(n)回答下列问题 :（1）试指出f(n)值的大小，并写出f(n)值的推导过程;（2）假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。 C函数： int f(int n){ int i,j，k,sum= 0;for(i=l;i sum++;printf(“sum=%dn”,sum)； } return(sum);} 【华中理工大学 2000 六（10分）】 第一层FOR循环判断n+1次，往下执行n次，第二层FOR执行次数为(n+(n-1)+(n-2)+„+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表： i= 1 2 3 „ n j=n n n n „ n j=n-1 n-1 n-1 n-1 „ „ „ „ „ j=3 3 3 j=2 2 2 j=1 1 2执行次数为(1+2+„+n)+(2+3+„+n)+„+n=n*n(n+1)/2-n(n-1)/6。在n=5时，f(5)=55，执行过程中，输出结果为：sum=15,sum=29,sum=41,sum=50,sum=55（每个sum= 占一行,为节省篇幅，这里省去换行）。 24．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m:=0;FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1;【南京邮电大学 2000 一、1】 2O(n),m的值等于赋值语句m:=m+1的运行次数，其计算式为n2(n2i1)4 i1n/2 25．有下列运行时间函数： 2（1）T1(n)=1000; （2）T2(n)=n+1000n; （3）32T3(n)=3n+100n+n+1;分别写出相应的大O表示的运算时间。 23(1)O(1)(2)O(n)(3)O(n)【吉林工业大学 1999 二（12分）】 26.试给出下面两个算法的运算时间。 （1）for i←1 to n do x ← x+1 END（2）for i← 1 to n do for j←1 to n do x← x+1 end end 【中科院自动化研究所 1995 二、2（6分）】 2(1)O(n)(2)O(n)27.斐波那契数列Fn定义如下 F0=0，Fl=1，Fn=Fn-1+Fn-2，n=2,3...请就此斐波那契数列，回答下列问题。 (1)(7分)在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，„, Fl, F0精确计算多少次? (2)(5分)如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少? 【清华大学 2000 二（12分）】（1）由斐波那契数列的定义可得： Fn=Fn-1+Fn-=2Fn-2+Fn-=3Fn-3+2Fn-=5Fn-4+3Fn-=8Fn-5+5Fn-6 …… =pF1+qF0 设Fm的执行次数为Bm(m=0、1、2、„、n-1)，由以上等式可知，Fn-1被执行一次，即Bn-1=1；Fn-2被执行两次，即Bn-2=2；直至F1被执行p次、F0被执行q次，即B1=p，B0=q。Bm的执行次数为前两等式第一因式系数之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列。可以解得： 15515n-m+2n-m+2Bm=5[(2)-(2)](m=0,1,2,„,n-1)（2）时间复杂度为O(n) 28．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。 2nn35n/231/2n ,n!, n, n-n+7n, nlogn, 2, n, logn, n+logn,(3/2), n+logn 【中科院计算所 1995 080385】 1/22335从小到大排列为：logn, n+logn, n, nlogn, n+logn，n, n-n+7n, 22nn/2nn 2,(3/2), n!, 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 考研政治变化 考生等待考试 2012年全国招收攻读硕士学位研究生简章日前公布，其中最大的变化是，工商管理、公共管理、旅游管理、工程管理、会计、图书情报、审计专业学位硕士的思想政治理论考试将由研究生招生单位在复试中进行。 变化一： 7类专业学位硕士初试取消政治 据了解，公共管理硕士、工商管理硕士、旅游管理硕士、工程管理硕士、会计硕士、图书情报硕士、审计硕士这7个管理类专业学位硕士的初试科目设两个单元，即外国语、管理类联考综合能力，满分分别为100分、200分。管理类联考综合能力考试全国统一命题，外国语考试中，英语、俄语和日语全国统一命题，统考外国语以外的其他语种，由各招考单位自己命题。 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 机构考研项目总监甘源(微博)说，今年7个专业学位硕士初试取消政治，初试分值也随之调整，这一变化反映了我国专业学位硕士的改革力度在加强，专业型硕士将更加重视对考生专业实践能力的考察和培养，这一趋势值得考生关注。 考研专家陈治国认为，7类专业学位硕士思想政治考试调整到复试，对报考这些专业学位硕士的考生来说，是一件好事，这在一定程度上减少了考生初试的压力。报考上述7类专业学位硕士的考生，要根据个人情况适当调整复习计划，前期复习可以减少一些用在政治学科上的时间，用更多的时间和精力来准备外语和管理类专业学位联考综合能力考试。然而，考生要注意，后考并不是不考，考生千万不能因此放弃政治复习，否则很有可能功亏一篑。 变化二： 研考学科门类新增艺术学 明年研考学科门类将从原先的12个增加到13个，艺术学首次从文学门类中独立出来，单列为一个学科门类。相应，原先招生的部分专业方向也转变为独立的专业。值得注意的是，此次调整引起部分高校相关专业考试科目的调整。例如电影学专业，考试科目明年将变化。 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 变化三： 专业学位硕士招生比例增至30% 专业学位硕士研究生招收比例近年来一直在增加，明年这一比例将达到30%。考研专家张雪峰说，目前，我国研考录取比例约为三分之一，其中学术型研究生的录取比例约为四分之一，而专业学位硕士的录取比例约为二分之一，专业学位硕士录取难度明显小于学术型硕士。但考生报考需根据专业就业前景区别对待。例如医学专业，目前三级甲等医院均要求博士学历，且导师更愿意招收学术型硕士研究生，因此，医学专业仍是学术型硕士占主流。 变化四： 经管类硕士初试科目有变化 经济管理类专业硕士考试科目有变化，其中经济类专业硕士不再考数学3，而考经济类综合能力联考，包括数学、逻辑和写作三部分内容；管理类专业学位硕士初试不考政治也不考专业课，而考核英语和管理 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 类综合能力联考，其中今年审计类专业硕士首次开考。 张雪峰说，考试内容的调整增大了对在职考生的吸引力，相应增加了应届生的竞争难度。预计综合能力联考中数学占分比例不高，重点在于逻辑和写作的考察。 专业学位硕士备考建议 教育部近年来重点扶植专业学位硕士教育，最终目的是让专业硕士和学术硕士的比例达到1:1。对于很多职场人士来说，专业学位硕士读成后拿双证(学位证和学历证)，在职学习也不会耽误工作，同时就业形势被看好，是吸引他们报考的重要原因。 虽说专业学位硕士的考试相比学术型研究生简单，但对于那些已经离开校园近多年的考生来说，一边要复习一边要应对工作，不容易兼顾。现在离考试还有100多天，考研专家也给备考生们提出了一些建议：首先，结合考试大纲，查补缺漏，全面复习。英语单词要过2遍，在熟练掌握单词的基础上，多做阅读真题，强化训练。 其次，合理选择辅导班，争取笔试高分。考生大多数在职，时间有限，选择一个辅导班进行系统化的学习非常重要。考生选择辅导班时要注意学校的办学资质、师资水平、口碑等。 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 最后，工作再忙每天都要抽出一点时间坚持复习。 2012考研政治新大纲 总体稳定，变化有限，虚实结合，以虚为主 变化：一.文字表述的调整 二.考点的分合 三.位置的移动 注意：其中多处假变化 实体变化 ① 增加五个考点（有效考点一个，无效增加四个） ② 减少15个考点（马原减少一个） 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 ③ 调整时政范围（考2011全年） 有效变化 删除的十五个考点： 马原 1.第二章第二节：联系与发展 2.第二节：唯物辩证法是认识世界和改造世界的根本方法 毛中特 1.第三章：革命统一战线的建立及其主要经验.2.武装斗争是中国革命的主要斗争形式.3.党的建设和主要内容和基本经验.精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 4.十四章第二节:中国特色军事变革 近代史 1.第八章第三节:社会主义改造基本完成2.第九章第一节:整风运动,反右派斗争 3.第九章第二节:庐山会议与纠左进程的中断 4.第十章第一节:工作重心转移到经济建设上来 5.第十章第三节:三个代表重要思想的提出 思修 1.第一章:学习和践行社会主义核心价值体系的重大意义 2.当代大学生的历史使命 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 3.第四章第二节:继承和弘扬中华民族优良道德传统的重大意义.4.第七章第三节:确定新的国家安全观 新增了四个考点 马原 1.第七章:社会主义在改革中的自我发展和自我完善 社会主义改革应当追寻的原则有:①.坚持正确的理论指导.②坚持改革的正确方向③选择正确的改革方式和步骤.④妥善处理改革,发展,稳定的关系 毛中特 一、第六章:十二五规划关于发展战略的主要内容.①.主题:科学发展,为了实现科学发展要做到四个更加注重 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 ②.主线:加快转变经济发展方式,其基础要求是五个坚持 ③.实现十二五规划的重大措施:五点； 二、: 2011胡锦涛七一讲话 ①.建党九十年来,中共完成的三件大事.A,实现了民族独立,人民解放,开启新的历史纪元.B确定了社会的基本制度,实现了中国历史上最广泛最深刻的社会变革.C开创,坚持,发展了中国特色社会主义,推动社会主义现代化建设取得了举世瞩目的伟大成就.以上三件大事中得出的结论:A在近代以来中共社会发展,社会的进程中,历史和人民选择了中国共产党.B中国共产党不愧为领导人民不断开创事业发展的核心力量 （2）中国共产党的三大伟大成就：A.开辟了中国特色社会主义道路B.形成了中国特色社会主义理论体系C.确立了社会主义制度 三、在推进改革开放中，走好中国道路需要做到五个坚定不移； 四、毛中特第十二章：武力解决台湾的方针； 精心收集 精心编辑 精致阅读 如需请下载！ 演讲稿 工作总结 调研报告 讲话稿 事迹材料 心得体会 策划方案 五、重点关注的2个考点：A.近现代史第八章第二节：社会主义道路：历史和人民的选择B.司法：爱国主义与民族精神、时代精神的关系（分析题） PS:这是文都辅导班徐之明老师得到的关于新大纲变化的第一手资料，我刚听过他的视频课，虽然改动处较多，但基本都属于虚变化，大家无需紧张，只需要关注一下需要重点关注的变化内容即可 精心收集 精心编辑 精致阅读 如需请下载！ 数据结构参考题目 一、选择 1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（） A.栈 B.队列 C.树 D.图 2.下面程序段的时间复杂度为（）for(i=0;i A.串的长度相等 B.含有相同的字符集 C.都是非空串 D.串的长度相等且对应的字符相同 5．若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（） A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0 B.1 C.48 D.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为 （35，51，24，13，68，56，42，77，93） （35，24，13，51，56，42，68，77，93）所采用的排序方法是（） A.插入排序 B.冒泡排序 C.快速排序 D.归并排序 8.已知散列表的存储空间为T[0..16]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（） A.T[2] B.T[4] C.T[8] D.T[10] 9.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（） A.Dout B.Dout-1 C.Dout+1 D.n 11．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 12．栈的插入和删除操作在()进行。 A．栈顶 B.栈底 C.任意位置 D指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24 B.71 C.48 D.53 14．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15．关于栈和队列的说法中正确的是（） A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间 C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间 17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A.q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q； 18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 19．执行下面程序段时，S语句被执行的次数为：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A.n*n B.n*n/2 C.n(n+1)D.n(n+1)/2 20．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（） A.a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 22．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（） A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front 24．设有二维数组 1A［n］［n］表示如下：23456，则A［i］［i］（0≤i≤n-1）的D.i2/2 值为（） A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 25．高度为h的完全二叉树中，结点数最多为（） hA．2h-1 B.2h+1 C.2-1 D.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（） A.mn B.mn-1 C.n(m-1)D.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A.n B.n-1 C.n+1 D.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）A.矩阵中非全零元素的行数等于图中的顶点数 B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等 29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（） A.36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81 二、填空题 1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。 3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。 5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。 9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。 10.单链表结点的指针域是用来存放其直接后继结点的首地址的（） 11.数据的存储结构是数据的逻辑结构的存储映象（）。 12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。 13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。 16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（） 19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。 27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。 28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。 30.将插入和删除限定在表的同一端进行的线性表是队列（）。 三、画图题 1.请根据下列二元组画出相应的数据结构 K={15,11,20,8,14,13 } R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构 K={A,B,C,D,E,F,G,H,I,J} R={ K={1,2,3,4,5} R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．请根据下列二元组画出相应的数据结构 K={0,1,2,3,4,5,6,7} R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．请根据下列二元组画出相应的数据结构 K={1,2,3,4,5,6,7} R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）} 四、运算题 1．已知一个图的顶点集V和边集H分别为： V＝{0，1，2，3，4，5，6，7} E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。 2.一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 平均查找长度：（写出计算过程） 3．已知一个图的顶点集V和边集H分别为： V＝{0，1，2，3，4，5，6，7} E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}； 按照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发） ____ __，___ _，___ ___，__ ____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果： 前序： 中序： 后序： 5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。 五、编程题 1.请编写一个算法，实现十进制整数与二进制数的转换。Void shi_to_er(unsigned x){ 2.写出二分法查找的算法： Int search_bin(Keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。LINKLIST *INVERTLINK(LINKLIST *H){第三篇：数据结构考研真题及其答案
第四篇：考研政治变化
第五篇：数据结构参考材料
![下载2014考研数据结构变化[五篇模版]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 