2012贵州省数据结构考试技巧与口诀

1、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。

A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，12、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;3、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的4、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值5、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)6、在数据结构中，从逻辑上可以把数据结构分为（ C ）。

A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构7、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。

A）top不变 B）top=0 C）top-- D）top++8、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。

A) 4 B)3 C)2 D)129、线索二叉树中某结点D，没有左孩子的条件是（ B ）。

A）D->Lchild=Null B) D->ltag=1C) D->Rchild=Null D) D->ltag=010、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a??11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。

数据结构复习参考2012年一、单选题：。

1、在表长为n的顺序表上做删除运算，在等概率的情况下，平均要移动的结点数为（）。

（A）n/2 (B) （n-1）/2 (C) n/3 (D) n/42、一个队列的入队序列是a，b，c，d，则队列的输出序列是（）。

（A）dcba （B）abcd （C）adcb （D）cbda3、设长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为（）。

（A）O(1) (B) O(lgn) (C) O(n) （D）O(n2)4、将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。

编号为49的结点X的双亲的编号为（）。

(A) 24 (B) 25 (C) 23 (D) 无法确定5、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）。

(A)front=front+1 (B)front=(front+1)%(m-1)(C)front=(front-1)%m (D)front=(front+1)%m6、空串是指（）。

（A）空白串（B）长度为零的串（C）长度为1的串（D）仅由空格组成的串7、设n阶方阵是一个上三角矩阵，则需存储的元素个数为( )。

（A）n (B) n2 (C)n2/2 (D)n(n+1)/28、有m个叶结点的哈夫曼树所具有的结点数为（）。

(A)m (B) m+1 (C) 2m (D) 2m-19、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )。

(A)e (B)2e (C)n2－e (D)n2－2e10、一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

(A) 250 (B) 501 (C)254 (D)50511、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

(A)5 (B)6 (C)7 (D)812、无向图的邻接矩阵是一个( )。

数据结构习题课（2012）复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各⾃包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。

3.线性表的顺序/链式存储结构的特点，插⼊、删除算法。

4.栈和队列的逻辑特性，顺序栈的⼊栈/出栈、循环队列的⼊队/出队算法。

5.以三元组顺序表存放的稀疏矩阵的转置算法。

6.⼆叉树的性质及其四种遍历算法。

7.森林与⼆叉树的相互转换。

8.WPL、前缀编码的概念，哈夫曼树的构造算法。

9.图的相关概念，邻接矩阵及邻接表的存储结构。

10.图的深度优先/⼴度优先遍历算法。

11.最⼩⽣成树的两种算法。

12.拓扑排序的意义和算法。

13.最短路径算法。

14.顺序表、有序表的查找算法。

15.⼆叉排序树的性质、插⼊/删除算法、平衡⼆叉树的性质、插⼊算法。

16.哈希表的相关概念，常⽤的冲突处理⽅法。

17.直接插⼊排序、希尔排序、快速排序、堆排序、归并排序的算法。

注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。

2.红⾊（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。

其他的算法则可能会出现在“算法题”中。

⾃测题第1章绪论⼀、判断1.顺序存储⽅式只能⽤于存储线性结构。

（错）2.顺序查找法适⽤于存储结构为顺序或链式存储的线性表。

（对）⼆、选择1.计算机算法必须具备输⼊、输出、（ B ）等5个特性。

A.可⾏性、可移植性和可扩展性B.可⾏性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发⽣⾮法操作时可以作出处理的特性称为（C ）。

A.正确性B.易读性C.健壮性D.可靠性3.数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。

A.操作对象B.计算⽅法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和⾮线性结构C.紧凑结构和⾮紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个⼈之间的同学关系，可⽤（C ）结构表⽰A.线性表B.树C.图D.队列7.下⾯的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可⾏性D.健壮性三、问答1.什么是逻辑结构和物理结构？各⾃包含哪⼏种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表⽰数据元素之间关系上的只要区别。

考试万能口诀
考试万能口诀如下：
1. 最准的万能选择题口诀——排除法。

(1)在单项选择题中，如其中两个或两个以上的选项存在承接、递进关系，即这两个或两个以上选项会同时成立，则正确项只能在上述选项之外去寻找。

(2)在单项选择题中，如其中两个或两个以上的选项内容相近或类似，即这两个或两个以上选项会同时成立，则正确项只能在上述选项之外去寻找。

(3)单项选择题中，一旦出现一对内容互相对立的选项，则正确选项往往由这两个对立选项中产生。

请注意，以上口诀并不能保证在所有情况下都适用，具体还需结合题目内容进行判断和选择。

第1章绪论内容提要：◆数据结构研究的内容。

针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

数据——所有能被计算机识别、存储和处理的符号的集合。

数据元素——是数据的基本单位，具有完整确定的实际意义。

数据对象——具有相同性质的数据元素的集合，是数据的一个子集。

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。

◆算法的定义及五个特征。

算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。

①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。

时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。

◆用计算语句频度来估算算法的时间复杂度。

第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

通过指针来实现！◆线性表的操作在两种存储结构中的实现。

数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。

核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2)插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i 位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。

快速掌握数据结构与算法的七个技巧在计算机科学和软件工程领域，数据结构和算法是基础中的基础。

无论是在编程竞赛中还是在实际的开发中，掌握数据结构和算法的技巧都是至关重要的。

然而，由于数据结构和算法的复杂性，许多人在学习和应用中都感到困惑。

本文将分享七个技巧，帮助您快速掌握数据结构和算法。

一、理清基本概念在学习任何新的领域之前，理清基本概念是至关重要的。

数据结构和算法并不例外。

在开始学习之前，确保您对基本概念有一个清晰的理解。

例如，您应该清楚地了解数组、链表、栈、队列等常见数据结构的定义和特性。

并且要有能够分辨它们之间区别的能力，这样在实际应用中才能正确地选择和使用。

二、学习常见算法了解数据结构之后，理解和学习常见的算法也是必不可少的。

常见的算法包括排序、查找、图算法等。

可以通过阅读相关的教材、参加在线课程或者参考开源项目的源代码来学习这些算法。

有了对算法的理解，您将能够更好地应用和优化代码。

三、编写和调试代码理论知识虽然重要，但实践经验同样不可或缺。

需要大量的编写代码和调试代码的实践来应用所学的数据结构和算法。

通过编写简单而有效的代码，可以更好地理解和掌握不同的数据结构和算法。

同时，调试代码能够帮助您发现并解决潜在的问题，提高代码的质量和性能。

四、刻意练习掌握数据结构和算法需要不断的练习和实践。

通过刻意练习，您可以提高代码的编写速度和质量。

可以使用在线编程平台或者刷题网站来进行练习，这些平台提供了大量的算法问题，例如LeetCode、HackerRank等。

通过坚持不懈地刻意练习，您将更加熟悉和熟练地运用不同的数据结构和算法。

五、理解时间和空间复杂度在优化代码性能和效率时，理解时间和空间复杂度是必不可少的。

时间复杂度是衡量算法执行时间的度量，空间复杂度是衡量算法占用内存空间的度量。

了解不同数据结构和算法的复杂度特性，可以帮助您选择合适的数据结构和算法，以及优化代码的性能。

六、研究高级数据结构和算法在掌握基本的数据结构和算法之后，可以开始学习和研究一些高级的数据结构和算法。

简单方法巧解行测数字推理难题数字推理试题难度正逐年加大，等差数列及其变式、幂数列已成为考试的热点，考生应重点掌握。

对于数字推理不少考生都选择放弃，其实，这部分经过有效训练之后，是可以提高的。

经过多年经验的积累，专家特别总结等差及等比数列题目的解题方法。

希望考生攻克数字推理难关，踏上公务员之路。

根据公务员考试行测数字推理题目的特点，等差数列已成为近年考试的热点，以下本文主要针对二级和三级数列给考生做详细介绍。

数字推理当中的数列题目，往往都需要把数列当中子项目做数学运算才能找到一定的规律，就先拿等差数列来说，相邻两项的差为定值，然而二级等差数列是相邻两项的差组成的新数列为等差数列，由此数列再来推上级数列的每一项，下面举例给大家详细介绍。

例1：2, 5, 11, 20, 32，（）A.43B.45C.47D.49此题的答案为C。

相邻两项作差，其差为等差数列。

例2：60，77, 96，（），140A.111B.117C.123D.127此题的答案为B。

原数列的后项减前项得17,19,21（23），此为等差数列。

二级等差数列主要是成单调递增或递减趋势，并且增减幅度较小。

然而三级等差数列是相邻项两两作差，得到的新数列相邻项再两两作差，得到一个等差数列，则称原数列为三级等差数列。

三级的等差数列相对来说稍难一点，大家只要仔细辨别是没有问题的。

例1：3, 8, 9, 0，-25，-72，（）A.-124B. -132C.-147D.-171此题的答案为C。

对数列做两次差即可得一等差数列。

例2: 187，160, 102，60, 81，（）A.40B.108C.176D.212此题的答案为D。

做两次差得：-31,16,63，此为等差数列，可反推出答案。

公务员考试专家提醒大家，在做三级等差数列题目时要注意它与二级的趋势差异，就是说他会出现有增有减的情况，但增减的幅度仍然不会很大，并且项数一定大于5。

由于竞争日益激烈，故三级数列考核的概率加大。

公共基础知识常识速记口诀公共基础知识是各类考试中常见的考察内容，涉及的知识面广泛，内容丰富。

为了方便记忆和掌握，本文整理了一些常见的基础知识常识速记口诀，帮助大家快速记忆。

一、政治类口诀1、马哲理论：唯物辩证，对立统一，质量互变，否定之否定的哲学理论。

2、社会主义核心价值观：富强、民主、文明、和谐；自由、平等、公正、法治；爱国、敬业、诚信、友善。

3、中国特色社会主义：五位一体，全面深化改革，依法治国，全面建成小康社会。

4、四个全面：全面建设社会主义现代化国家、全面深化改革、全面依法治国、全面从严治党。

二、经济类口诀1、市场经济：市场调节，市场体系，市场主体，市场监管。

2、宏观调控：财政政策，货币政策，产业政策，价格政策。

3、国际贸易：贸易顺差，贸易逆差，出口创汇，进口付汇。

4、税法知识：增值税，营业税，消费税，个人所得税。

三、法律类口诀1、法律体系：宪法，刑法，民法，商法，行政法，经济法。

2、法律制度：法制，法治，法律渊源，法律适用。

3、法律关系：权利，义务，责任，法律后果。

4、法律程序：起诉，审判，执行，申诉。

四、管理类口诀1、管理学：计划，组织，指挥，协调，控制。

2、领导科学：领导权威，领导方式，领导艺术，领导团队。

3、人力资源管理：招聘，培训，考核，薪酬，福利。

4、行政管理：政府职能，行政机构，行政法规，行政效率。

五、历史类口诀1、中国历史：炎黄子孙，夏商西周，春秋战国，秦汉魏晋。

2、世界历史：古希腊罗马，中世纪欧洲，文艺复兴，资产阶级革命。

3、近现代史：鸦片战争，洋务运动，戊戌变法，辛亥革命。

4、历史人物：秦始皇，汉武帝，唐太宗，成吉思汗。

六、文化类口诀1、中国文化：儒家思想，道家思想，墨家思想，法家思想。

2、世界文化：西方文艺复兴，启蒙运动，浪漫主义，现实主义。

3、文学常识：唐诗，宋词，元曲，明清小说。

4、艺术知识：绘画，音乐，舞蹈，雕塑。

七、科技类口诀1、物理学：力学，电磁学，热学，光学，量子力学。

●__(4)__的特点是数据结构中元素的存储地址与其关键字之间存在某种映射关系。

(4)A．树形存储结构B．链式存储结构C．索引存储结构D．散列存储结构●若循环队列以数组 Q[O..m-1] 作为其存储结构变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是__(5)__。

(5)A．rear-length B．(rear-length+m) mod mC．(1+rear+m-length) mod m D．m-length●一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有__(6)__个零元素。

(6)A．e B．2e C．n2-e D．n2-2e●若一棵哈夫曼(Huffman)树共有9个顶点，则其叶子结点的个数为__(7)__。

(7)A．4 B．5 C．6 D．7●若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵__(8)__。

(8)A．第i行中值为1的元素个数 B．所有值为1的元素总数C．第i行及第i列中值为1的元素总个数D．第i列中值为1的元素个数●在—棵度为3的树中，若有2个度为3的结点，有1个度为2的结点，则有__(9)__个度为0的结点。

(9)A．4 B．5 C．6 D．7●设结点x和y是二叉树中任意的两个结点，在该二叉树的先根遍历序列中x在y之前，而在其后根遍历序列中x在y之后，则x和y的关系是__(10)__。

(10)A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先D．x是y的后裔●设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。

若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为__(11)__。

(11)A．21 B．23 C．41 D．62DCDBDCCB(顺序查找平均查找长度是：（n+1）/2 (1+3)/2+(41+1)/2=23 123/3=41)●在一棵完全二叉树中，其根的序号为1，_(33)_可判定序号为p和q的两个结点是否在同一层。

考试小技巧小口诀考场填写信息全，平稳定情绪；总览全卷题，区别难与易。

审题要仔细，用时别吝惜；思路要清晰，稳中再求快。

难题先跳过，手熟好得分；如遇容易题，小心莫轻视。

注意要检查，回头可救分；相信第一感，改动需谨慎。

心态放平和，规范牢牢记；积极暗示多，发挥易超常！相信自己能，目标必达成！选择题拿到题目定时空，阅读题干抓主旨；图文材料仔细看，理顺逻辑助分析；多个概念找关系，注意整体防片面；发问方式读明白，四个选项比仔细；概念准确三度清，材料所学莫机械；排除对应做判断，答案选定涂卡准。

大题整体大题审题要四定，紧紧围绕中心词；材料所学或结合，答案来源看清楚；方法问题心明白，限定代词要注意；信息提取要针对，全面筛选追准确；材料不忘边角料，逐段逐句分层次；信息围绕中心词，由表及里要全面；表达史实加结论，要点多个可得分；表达序号要点化，位置准确字迹清。

类型题概括类型每句找，巧抄改写和提炼；不抄描述抄概括，不抄细节抄宏观；不抄长句抄关键，全面获取不留白；概括特点深思考，求同求异求变化；原因分析找时间，中心词里定逻辑；主客政经和思文，材料所学恰运用。

影响思路类原因，事件先后找关联；找准对象谈影响，政经思文内和外；积极消极宜完整，直接深远需思量。

比较异同互参照，一一对应格式好；异同原因分开列，条理清晰易得分。

评价人物据事迹，评价事件看影响；评析观点看内容，回到材料找信息；结合史实来论述，赞扬批判析本质。

启示认识做小结，纵观材料和提问；中心词语需带入，多个角度谈看法。

图表题目有方法，图文互补寻信息；关注概念找方向，材料所学两结合；漫画解读悟寓意，作者态度要明白；数据图表照方法，三看三比一相联；曲线态势和拐点，柱状左右看趋势；表格纵横看变化，饼状圆缺看大小；数据类型分清楚，比重百分非总量；表达主语要明确，表头项目和主体；定量分析加定性，趋势特点分析全。

四十一题开放强，探究味浓须重视；基础题型仍须用，提调释结常规路；围绕问题中心词，大胆提取亮看法；所学史实来阐释，评析说明或探讨；表现原因或影响，材料所学觅答案；影响认识三因素，史料时代还有人；必要时候议史料，类型材料弄清楚；各种类型皆可用，考订鉴别可靠性；一手无意和实物，证据力量相对强；文献口述二有意，主观意图需警惕；判断方法有背景，读史征信定事实；史料不能单一用，需与其他互印证。