0.1.3课程学习指导 学牛在初学时往往感到“数据结构”课程内容多、面授容易接受,但自学难度大,特别足 在编写小程序时常常无从者手。为改善自学效果以有限的时问和精力学好这门课程,应当 注意以下儿点 (1)注意先修课程的知识准备 在学习今课程之初,必须注意复习在用CC+程序设计亡编写小程序时的谙法规 则和方法,为本谍程的学习打下基础 ℃语言与 Pasca浯言一样,是一种面向过程的语言、C程序结构的特点是遵循“输入 处理输出”的模式来解决问题。(+一保留了C的亩向过程编程的成分,但由于引入了面 向对象的成分,在数据组织方囿很自然地实现了抽象数据类型的思想、并利用模板机制实现 了软件复用。在复习CC++语;时应注意 ①函数的概念和相关问题。包括函数类型,函数特征,函数名重载,函数参数的传递 特别注意传值参数和引用参数在使用上的别。还有函数返回值的1种类型之间的区别。 ②函数中局部变量的作用域,它的创建和回收的有效范围。特别注意在函数中对局部 变量的任何改变,因为在退出函数过稈时局部变量被释放而不能当作数返回值返回 ③类和对象的定义方式。特别注意为保证信息隐蔽,对类屮的所有数杯成员和成员 数将规定其存取级别: public, privale和 protected。放在 public域中表示对于其他程序都 是可用的;放在 privale域中表小对于其他程序是不叮用的,对于其派生类也是不可用的;放 在 protected域中表示对于其他程序是不可用的,对于其派生类是可用的 ④在C+十中的动态存储分和动态存储叫收方式 ⑤类的实例对象的建立和同收方式,构造函数和析构函数的使用,对象数据成初始 化的方式等。特別注意成员函数的作用或 ⑥在CC+十中的输入输出流文件的定义和使用。特别注意文件的连接, strean类 和 offstream类,文件的打开与关闭、文件模式的作用。 O友元类与友元函数的定义和使用 ⑧模板类的定义和模板类的使用 (2)在学习“数据结构”时,要注意知识体系 结构谍程中的知识本身具有良好的结构性。从总体上来说,课程的七嬃内容是 绕着数组、线性表、顺序表、链表、栈、队列、优先级队列、广义表、树与二义树、图、集合与搜索 结构、索引与散列结构等常用的数据结构和递归、排序等常用算法来组织的。其中有些结构 是面向应用的,有些结构是面向实现的。在课文中要注意这两个层次以及它们之间的联系 为了完全了解数据结构的机制以及为便于数据结构的复用课文中对轷一个结构都做 了较为完整的介绍,学习者最好将课文中介绍的每一结构都能以“模板类”和“模板类的成员 函数的实现”的形式存于“,h”文件中,并在后续的算法或类的实现中直接复用它们 3)注意比较 在学习中应当注意从“橫向”和“纵向”进行对比以加深埋解。纵向对比将种结构与它 的各种不同的实现加以比较,从继承的角度或从聚合的角度建立类的实例之间的联系;横向
对比包括具有相同逻辑结构的不同数据结构(如线性表、栈、队列、优先级队列和串)的比较 具有相同功能的不问算法的比较等,了解类的层次结构和利用包的概念将不同语义的类关 联起来,从而加深对抽象类和虚函数的使用 (1)注意复习和反复阅读 有些内容在初读时难以透彻理解或熟练掌据,或者看起来似乎明白了,但用的时候容易 犯暈,在继续学习的过程中如遇到或用到有关内容时,应当及时复习或电读,这往往能够化 难为易,温故知新 (5)充分利用考核说明及有关学习的难点和重点的说明 在进入每一帝学习之前或在每一章学习之后,仔细阅读考核说明和各章学习的难点和 重点·有助于集中思路和自我检查。如自我检查的效果不理想,千万不要将就,更不要急于 向后读应回过头来把握住要求,有计划地重读课本,重看学习导引,重做习题,直到本章内 容掌揭为止。 (6)注意循斥渐进 在进入具体内容(如类的定义和类的成员函数的实现)之前,首先领会基本概念、基本思 想这一点极为重要。特别是在阅读算法之前,一定要先弄清其基不思想、基本骤,这将大 大降低理解算法的难度。如果读“懂”了算法而不知其基本思想,仍不算是真懂。可以通过 事例学习以加深理解。 (7)注意练习 习题练习是课程的基本婴求之一。只看书不做题不可能真正学会有关知识更不能达 到技能培养的目的。另一方面,做题也是自我检查的重要手段。此外,在做算法设计型的习 题时应优先考虑数据结构的定义,可直接使用以前定义的类和相应的操作(成员函数),综 合已学过的知识以提高编程的能力。为此,可以逐渐积累学过的数据结构的实现,以模板 类的方式标准化,以方便在后缤学习中复用它们。这样做所获得的回报是相当丰厚的,但不 要指望立即获得回报。 (8)算法思路的理解 算法及其思想、评价是本课程的重点之一,在课文中占了相当大的比例。在学习每一个 算法时,建议首先理解问题的要求,在此基础上利用一个事例来模拟间题的求解.自已试着 构思一下解题的思路能够写出来更好。然后再阅读算法在读懂之后,不要急于往下进行 而应停下来思考下列问题:该算法从逻辑上可以划分为哪几个部分(步骤)?每一部分的功 能是什么?这一功能又是如何实现的?能否用别的方法实现?各部分之间的关系如何?如 果间题的要求有所不同,应当如何修改算法? 将思考的结果记载下来,在复习时会有很大帮助。另外,这样的分析也是灵活运用所学 知识的关键。 (9)努力培养算法设计的能力 在课程学习中最令学习者感到吃力的是设计和編写算法。算法的设计水平是软件设计 的基础,要提高算法的设计水平,首先需要掌握问题要求的基本内容通过反复体会和练习 来实现。通常需要根据具体问题的要求选择合适的数据结构,设计有效的算法,有条件的 学生应当在机器七多做练小
(10)及时总结 在学习完每-节、章后,要及时地进行总结,用简短的文宇记录这部分的内容,尽可能用 自己的话复述一遍。在本课程全部学完后还应对本课程进行全面系统的复习和总结,认真 做模拟试卷,在进行总复习叶,可通过对比各种数据结构的异同和它们之间的相互关系,加 深对各种数据结构的理解。 在复习时,可以按所记录的要点反向地进行,即依据要点找出其体内容。按这样的方 法进行,也许还能够节省时间,提高学习效果 最后应当强调的是,学习方法主要靠自己摸索,多总结,多思考勤上机,勤交流,这是把 数据结构”这门课程真正学好的关键 0.2考试指导 数据结构考试可能的题型有以下5种: 单选题:给出一些有关数据结构性质、特点及一些简单算法性能的不完全叙述.要求学 生从题后给出的供选择的答案巾选择合适的答案,补足这些叙述 填空题:给出程序说明及一段部分语句缺失的程序,让学生补充成为完整的程序 简答题:应用作图方法或简单计算,使用给定数据建立或操作一些数据结构: 判断題:绐出-些有关数据结构或算法的叙述,要求学生回答这些叙述正确与否: 综合算法题:给出算法设计要求·编制出部分算法程序·用来考察几个知识点的综合 应用 下面根据各种题型举例分析,说明解题方法及考试时的注意事项。 0.2.1单选题 【例L1】从供选择的答案中选出正确的答案,将其编号填入下列叙述中的()内。 (1)向一个有127个元素的顺序表中插人一个新元素并保持原米顺序不变,平均要移 动(A)个元素。 (2)设有个二维数组Am][n,假设A[OJ[0]存放付置在614,4[227存放位置 在6760,每个元素占一个空问则A15]在(B)位置,,長明用10进数表示。 (3)一个有序顺序表有255个对象,采用顺序搜索法查表,平均搜索长度为( (4)含5个结点(元索值均不相同)的二叉搜索树有(D)种 5)在分析折半搜索的性能时常加入失败结点,即外结点,从而形成扩充的二叉树。若 设失败结点所在层次为l,那么搜索失败到达失败结点时所做的数据比较次数是(E) (6)设有一个含200个麦项的散列表,用线性探查法解决冲褒,按关键码查询时找到一 个表项的平均探耷次数不超过1.5,则散列表项应能够至少容纳(F)个表项。(设搜索 成功的平均搜素长度为Sn={1+1(1-a)}:2,其中a为装填子) (7)n个顶点的连通图至少有(G)条边
(8)一个二义树按顺序方式存储在一个一维数组中,如将 0 6789C11121311 A B 则结点E在二叉树的第(H)层 供选择的答案 A.①8 ②63.5 ③63 ①69 ②6261 ③709c:④724 C.①128 ③126 ④255 D.①54 ③36 ④65 E.①l,+1 ③l1-1 ①l 676 ①n-1 ③n+1 ③3 【解答】A.②B.③C.①D.②E.④ 分析】此类题主要是考核学对基本知识的掌握程度,涉及范围较广。所有各章内容都可 能牵涉到。主要考察对各种数据结构的定义、特点、性质(包括公式计算)、主要操作的性能 分析(包括算法中多趟执行时每一趟的通项公式),因此要求复时必须仔细看书。不提倡 死记硬背,但要学会推导 0.2.2判断题 【例2.1】判断下列各个叙述的正误。对,在题号前的括号内填入“√”;错,在题号前的折号 内填入 ()(1)有丌个结点的不同的二叉树有n!棵 ()(2)直接选择排序是一种不稳定的排序方法 )(3)在2048个π不相同的关键中选揉最小的个关键码.用堆排序比用锦标赛排 序更快。 ()(4)当3阶B_树中有255个关键码时,其最大高度(包括尖败结点层)不超过8 〈)(5)一棵3阶B树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶B_树 )(6)在川散列表存储关鍵码集合时,可以用双散列法寻找下个空桶。在没计再散列 函数时,要求计算出的值与表的大小m互质。 ()(7)在只有度为0和度为k的结点的k叉树屮,设度为0的结点有n,个.度为k的结 点有n个,则有n:-n4+1。 ()(8)折半搜索只适用于有序表,包括有序的顺序表和有序的链表。 【解答】(1) 5)×(5)√(7)x 【分析】此类题要求对课文各章中许多细节比较清楚。事实1,数据结构课程屮讲到的许多 数据结构的细节是最基础的知识,将这些内谷理解透彻了,以后学生在自主开发软件时将会 得到回报的。在解答此类题肘,不要立即提笔就答.应当把题看完,分析前后叙述是否矛盾
是否叙述中有漏洞,必要时,还需要做·下简单的推导。 0.2.3阅读理解题 【例3.1】说明下列递归过程的功能 int unknown( Bin Node.t) 指针t是二叉树的枨指针 if(t=" NUlL)return 0: if(t->leftChild=--NCLL &&1->>rightChild= NUI. 1. )return I Ieft+ unknown(r.".rghihi 【解答】计算二叉树的叶结点的个数。 【分析】此类题是递归算法问题,一般要求读懂它即可。但要理解它首先需要掌握递归算決 的结构,以及相应问题的背景。有时需要用一个简单的例子来帮助理解 0.2.4简答题 【例4.1】如下所示的连通图,请画出: (1)以顶点①为根的深度优先生成树 (2)如果有关节点请找出所有的关节点 【解答】 ()该连通图从①出发做深度优先搜索,得到的深度优先生成树为 结果不唯一 (2)关节点为①②、③、⑦、⑧ 【分析】这是有关重连通图的问题。深度优先搜索是一个需要重点掌握的方法,包括实例分