第六章数据结构与算法

《第六章数据结构与算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章　数据结构与算法考情分析　　本章要求了解数据结构与算法的基本概念和相关术语。重点掌握线性表、栈、队列、数组、树和图等数据结构的概念、存储方式和相关算法。熟悉排序和查找的基本方法。对于在招聘计算机专业单独考试中是考试重点，出现频率大。第一节　数据结构及算法概述　　一、数据结构　　　　【要点】　　1.数据元素是数据的基本单位。　　2.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。　　3.4类基本的逻辑结构:集合、线性结构、树形结构和网状结构。　　4.4种数据存储方式：顺序、链式、索引和散列。　　【例题·单选题】（2009年×省信用社招聘考试真题）下列说法不正确的是（　）。　　A.

2、数据元素是数据的基本单位　　B.数据项是数据中不可分割的最小标志单位　　C.数据可由若干个数据元素构成　D.数据项可由若干个数据元素构成『正确答案』D『答案解析』数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是不可分割的、含有独立意义的最小数据单位。因此D选项不正确。　　二、算法　　算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。　　算法的特性：有穷性、确定性、可行性、输入和输出。　　【要点】　　评价算法优劣标准：正确性、可读性、健壮性、高效率与低存储量需求。第二节　线性表　　线性表是n

3、（n≥0）个数据元素a1，a2，…，an组成的有限序列，n=0时称为空表。　　非空的线性表，有以下特征:　　1.有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2。　　2.有且仅有一个终结结点an，没有直接后继，有且仅有一个直接前趋an-1。　　3.其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前趋ai-1和一个直接后继ai+1。　　线性表的链式存储包括单链表、循环链表和双链表。　　　　【注意】　　与单链表的插入和删除操作不同的是，在双链表中插入和删除须同时修改两个方向上的指针。第三节　栈和队列　　一、栈　　栈是一种“特殊的”线性表，这种线性表中的插入和删除运算限定在表的

4、某一端进行。不含任何数据元素的栈称为空栈。　　栈的基本运算：构造一个空栈InitStack（S）、判栈空StackEmpty（S）、判栈满StackFull（S）、进栈Push（S，x）、退栈Pop（S）、取栈顶元素StackTop（S）。　　　　【要点】　　栈的修改是按后进先出的原则进行。　　二、队列　　队列是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。当队列中没有元素时称为空队列。　　栈和队列一般有两种存储结构：顺序存储结构和链式存储结构。　　　　【要点】　　队列的修改是按照先进先出的原则进行的。　　【例题·单选题】（2007年×省信用社招聘考试真题）以下（　）不是栈的基本

5、运算？　　A.删除栈顶元素　B.删除栈底元素　C.判断栈是否为空　D.将栈置为空栈『正确答案』B『答案解析』栈是一种特殊的线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的这一端称为栈顶，另一端称为栈底。处于栈顶位置的数据元素称为栈顶元素。栈的修改是按后进先出的原则进行。栈的运算在栈顶进行。因此，删除栈底元素不属于栈的基本运算。第四节　数组　　数组：把具有相同类型的若干变量按有序的形式组织起来的同类数据元素的集合。第五节　树　　一、树　　（一）基本概念　　　　树是n（n>0）个结点的有穷集合，满足以下条件：　　（1）有且仅有一个称为根的结点。　　（2）其余结点分为m

6、（m≥0）个互不相交的非空集合T1,T2,…,Tm,这些集合中的每一个都是一棵树，称为根的子树。　　森林是m（m≥0）棵互不相交的树的集合。　　树中的一个结点拥有的子树数称为该结点的度。一棵树的度是指该树中结点的最大度数。　　树中某个结点的子树的根称为该结点的孩子或儿子。　　树中结点的最大层数称为树的高度或深度。　　（二）树和森林的遍历　　1.树的遍历　　　　先序遍历：若树不空，则先访问根结点，然后依次先序遍历各棵子树。ABCDE　　后序遍历：若树不空，则先依次后序遍历各棵子树，然后访问根结点。BDCEA　　层次遍历：若树不空，则自上而下自左至右访问树中每个结点。ABCED　　2.森林的遍历　

7、　　　前序遍历森林：　　若森林非空，则：　　①访问森林中第一棵树的根结点。　　②前序遍历第一棵树中根结点的各子树所构成的森林。　　③前序遍历除第一棵树外其他树构成的森林。　　右图前序遍历序列为ABCDEFIGJH。　　后序遍历森林：　　若森林非空，则:　　①后序遍历森林中第一棵树的根结点的各子树所构成的森林。　　②访问第一棵树的根结点。　　③后序遍历除第一棵树外其他树构成的森林。　　右图后序遍历序