zdq第11章-多态

CHAPTER 11Data StructuresReview Questions1.We need data structures to hold a collection of related variables so that we cansolve complex problems more efficiently.3.An array is a fixed-size sequenced collection of elements of the same data type.5.Elements of an array are contiguous in memory and can be accessed by use of anindex. Elements of a linked list are stored in nodes that may be scattered through-out memory and can only be accessed via the access functions for the list (i.e., aspecific node is returned by a search function).7.A frequency array shows the number of elements with the same value found in aparticular collection of data.9.An array is stored contiguously in memory. A two-dimensional array uses row-major storage in which the array is essentially stored as an array of arrays.11.The fields of a node in a linked list are the data itself and a pointer (address) to thenext node in the list.13.The head pointer contains the address of the first node in the list.15.A singly linked list is a linked list in which each node contains only one pointerthat contains the address of the following node. There are multi-linked lists inwhich each node contains more than one pointer, allowing for much more complexdata structures.Multiple-Choice Questions17.d19.d21.b23.d25.c27.b29.d34CHAPTER 11DATA STRUCTURES31.a33.a35.bExercises37.CompareInput: Two arrays (A and B) of 10 integers1. Set Index equal to 02. While Index is less than 102.1 If A [Index] is not equal to B [Index]2.1.1 Return falseEnd if2.2 Increment IndexEnd loop3. Return trueEnd39.PrintInput: An array (A), the number of rows (I), and the number columns (J)1. Set RowIndex equal to 02. Set ColIndex equal to 03. While RowIndex is less than I3.1 While ColIndex is less than J3.1.1 Print A [RowIndex][ColIndex]3.1.2 Increment ColIndexEnd loop3.2 Move to next line in output3.3 Increment RowIndexEnd loopEnd41.AddFractionsInput: Two fractions (Fr1 and Fr2)1. Allocate new fraction object (Fr3)2. Set Fr3.denominator equal to Fr1.denominator * Fr2.denominator3. Set Fr3.numerator equal to (Fr1.numerator * Fr2.denominator) +(Fr2.numerator *Fr1.denominator)4. Return Fr3EndSECTION 543.MultiplyFractionsInput: Two fractions (Fr1 and Fr2)1. Allocate new fraction object (Fr3)2. Set Fr3.denominator equal to Fr1.denominator * Fr2.denominator3. Set Fr3.numerator equal to Fr1.numerator * Fr2.numerator4. Return Fr3End45.See Figure 11.1Figure 11.1Exercise 4547.When an element is to be added to the array, a new array must be allocated and allof the old elements and the new element must be moved to the new array.49.Adding an element to a linked list is easier because a linked list does not have to betotally reallocated.51.Accessing an element of an array is easier because an index can be used.53.Sorting an array is easier because the elements can just be swapped rather thanhaving to redirect up to four different pointers.6CHAPTER 11DATA STRUCTURESSECTION 78CHAPTER 11DATA STRUCTURES。

编译原理第六章到第十一章课后习题答案p116/1.已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 计算FIRSTVT -- LASTVT表(2) 构造算符优先关系表（OPERATER PRIORITY RELATION TABLE），说明是否为算符优先文法。

=: #=#, (=)<: (< FIRSTVT(T) , ,<firstvt(s)<="" ,="" p="">>:LASTVT(S)># , LASTVT(T)>), LASTVT(T)> ,表中无多重人口所以是算符优先（OPG）文法。

（3）计算G[S]的优先函数。

收敛（4）对输入串（a,a）#的算符优先分析过程为Success!3.有文法G（S）：s->Vv->T/ViTT->F/T+FF->)V*|((1)(+(i(的规范推导S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)F+Fi（的短语、句柄、素短语。

短语S: F+Fi（T1:F+F （素短语）T2:F （句柄）F:( （素短语）(3) G(S)是否为OPG？若是，给出（1）中句子的分析过程！S’->#S# S->V V->T/ViT T->F/T+F F->)V*|(算符优先关系表（OPERATER PRIORITY RELATION TABLE）对输入串(+(I(的算符优先分析过程为:p152/2文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→SI3若产生式排序为：0 S' →S1 S →L.L2 S →L3 L →LB4 L →B5 B →06 B →1由产生式知：First (S' ) = {0,1}First (S ) = {0,1}First (L ) = {0,1}First (B ) = {0,1}Follow(S' ) = {#}Follow(S ) = {#}Follow(L ) = {.,0,1,#}Follow(B ) = {.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：I5B →.0和B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

2018年上半年软件设计师真题+答案解析上午选择1、对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（1）。

A. O(n2)B. O(e2)C. O(n+e)D. O(n*e)答案：A在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。

也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O(n+e)。

在邻接矩阵中，算法需要遍历邻接矩阵的每一个点，而邻接矩阵有n*n个点，所以时间复杂度是O(n*n)。

2、浮点数的表示分为阶和尾数两部分。

两个浮点数相加时，需要先对阶，即（）（n为阶差的绝对值）。

A. 将大阶向小阶对齐，同时将尾数左移n位B. 将大阶向小阶对齐，同时将尾数右移n位C. 将小阶向大阶对齐，同时将尾数左移n位D. 将小阶向大阶对齐，同时将尾数右移n位答案：D对阶时，小数向大数看齐；对阶是通过较小数的尾数右移实现的。

3、计算机运行过程中，遇到突发率件，要求CPU暂时停止正在运行的程序，转去为突发事件服务，服务完毕，再自动返回原程序继续执行，这个过程称为（3），其处理过程中保存现场的目的是（4）。

A. 阻塞B. 中断C. 动态绑定D. 静态绑定答案：B4、 A. 防止丢失数据B. 防止对其他部件造成影响C. 返回去维续执行原程序D. 为中断处理程序提供数据答案：C中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。

5、海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某些被校位的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误。

对于32位的数据，至少需要加（5）个校验位才能构成海明码。

以10位数据为例，其海明码表示为D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，其中Di（0≤i≤9）表示数据位，Pj（1 ≤j≤4）表示校验位，数据位D9由P4、P3和P2进行校验（从右至左D9的位序为14，即等于8＋4＋2，因此用第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（6）进行校验。

第七章面向对象学习方法学面向对象方法学的出发点和基本原则,是尽可能按照人类的习惯思维方式,使开发软件的方法与过程尽可能接近人类认识世界解决问题的方法与过程,也就是使描述问题域空间与实现解法的解空间在结构上尽可能一致.与传统的结构化方法相比,使用面向对象方法开发的软件,其稳定性,可修改性和可重用性都比较好.本章内容主要包括:传统方法学的缺点,面向对象的基本概念,面向对象模型.7.1 基础知识7.1.1 传统方法学的缺点结构化几其他方法学的本质,是在具体的软件开发之前,通过需求分析预先定义软件需求.然后一个一个阶段地开发用户所需要的软件,实现预先定义的软件需要.过去的经验需要告诉我们,结构化及其他方法学并不能完全消除软件危机.结构化及其他方法学仍然有许多不足之处.1.问题的表现1)生产效率低在生命周期方法学中,特别重视软件开发的阶段性.为了提高了软件开发的效率,减少重大返工次数,强调必须早每个阶段结束之前进行评估.从而开发过程中实行严格的质量管理,确实提高了许多软件的开发的成功率.但是,时间表明,开发高利率仍然很有用.2)不能满足用户需要实践表明,在开发需要模糊或需求动态变化的系统时,软件系统的结果往往不能满足用户需求的变化.主要表现在两个方面:一种是开发人员不能完全获得彻底理解用户的需要,以至开发的软件系统与用户预期的系统不一致;另一种表现是,所开发的系统不能适应用户需求变化,系统的稳定性和可扩充性不能满足需要.3)软件服用就是将已有的软件成分用于构造新的软见系统.软件复用是节约人力,提高软件效率的重要途径.结构分析.设计,几乎每一次开发一个系统时都需要针对这个具体的系统做大量的重复劳动..思维成果的可复用性差.4)软件很难维护实践经验告诉我们,即使是用生命周期方法学开发出来的软件,维护起来仍然相当困难,软件维护成本很高.2．问题的原因1）结构化技术本身的问题结构分析和设计技术的基本思想是从目标系统整体功能的单个处理着手，自顶向下不断的把复杂的处理分解为子处理，一层一层的分解下去，直到剩下若干个容易实现的子处理为止。

多态的深⼊理解对于Java的多态概念的理解 在学习Java的过程中,我们⽆论如何也绕不过多态这个东西。

它到底是个什么东西呢？ 其实，它就是指调⽤相同名字的⽅法，但是得到的结果是不同的。

第⼀：对象是⽅法 多态的作⽤范围是⽅法，不是类不是对象，也不是对象⾥⾯的属性第⼆：多态产⽣的条件 1、有继承---在⼦类中有⽅法重写---在⽅法的调⽤中，有指向⼦类的⽗类的引⽤ 2、有⽅法的重载，就是相同⽅法名，但参数不同（个数，类型，顺序）第三：为什么需要多态？ 因为真实世界中的情况是纷繁复杂的，为了应对⽣活中的种种情况，我们就需要程序能够分别应对各种情况。

即增加了程序的灵活性，来满⾜客户需求。

第四：Java运⾏时的多态性 运⾏时多态性或动态⽅法分派是⼀个过程，它对重写⽅法的调⽤在运⾏时体现⽽不是编译时。

在此过程中，通过超类的引⽤变量调⽤重写的⽅法。

要调⽤的⽅法基于引⽤的对象。

了解运⾏时多态性之前，让我们先来向上转换。

向上转换 当⽗类的引⽤变量引⽤⼦类的对象时，称为向上转换。

例如：class A{}class B extends A{}A a=new B(); //向上转换...Java运⾏时多态性⽰例1在这个例⼦中，我们创建两个类：Bike和Splendar。

Splendar类扩展Bike类并覆盖其run()⽅法。

通过⽗类(Bike)的引⽤变量调⽤run⽅法。

因为它引⽤⼦类对象，并且⼦类⽅法覆盖⽗类⽅法，⼦类⽅法在运⾏时被调⽤。

因为⽅法调⽤是由JVM不是编译器决定的，所以它被称为运⾏时多态性。

class Bike {void run() {System.out.println("running");}}class Splender extends Bike {void run() {System.out.println("running safely with 60km");}public static void main(String args[]) {Bike b = new Splender();// upcasting - 向上转换b.run();}}执⾏上⾯代码得到以下结果 -running safely with 60km.Java运⾏时多态性⽰例2：Bank考虑⼀种情况，Bank类是⼀个提供获得利率的⽅法的类。

第八章继承与多态习题一.基本概念与基础知识自测题8.1填空题8.1.1 如果类α继承了类β，则类α称为（1）类，而类β称为（2）类。

（3）类的对象可作为（4）类的对象处理，反过来不行，因为（5）。

如果强制转换则要注意（6）。

答案：（1）基类（2）派生类（3）派生类（4）基类（5）派生类有一些新成员（6）只能派生类强制转换为基类8.1.2 当用public继承从基类派生一个类时，基类的public成员成为派生类的（1）成员，protected成员成为派生类的（2）成员，对private成员是（3）。

公有派生可以使其类的（4），所以公有派生是主流。

答案：（1）public成员（2）protected成员（3）不可访问（4）接口不变8.1.3 利用继承能够实现（1）。

这种实现缩短了程序开发的时间，VC++中的（2）很好地体现了这一点。

答案：（1）代码的复用（2）MFC编程8.1.4 一个派生类只有一个直接基类的情况称为（1），而有多个直接基类的情况称为（2）。

继承体现了类的（3）概念，这在MFC中得到了很好表现，MFC中只采用了（4）。

答案：（1）单继承（2）多重继承（3）层次（4）单继承8.1.5 C++中多态性包括两种多态性：（1）和（2）。

前者是通过（3）实现的，而后者是通过（4）和（5）来实现的。

答案：（1）编译时的（2）运行时的（3）函数和运算符的重载（4）类继承关系（5）虚函数8.1.6 在基类中将一个成员函数说明成虚函数后，在其派生类中只要（1）、（2）和（3）完全一样就认为是虚函数，而不必再加关键字（4）。

如有任何不同，则认为是（5）而不是虚函数。

除了非成员函数不能作为虚函数外，（6）、（7）和（8）也不能作为虚函数。

答案：（1）同虚函数名（2）同参数表（3）同返回类型。

如基类中返回基类指针，而派生类中返回派生类指针是允许的（4）virtual（5）重载（6）静态成员函数（7）内联函数（8）构造函数8.1.7 纯虚函数定义时在函数参数表后加（1），它表明程序员对函数（2），其本质是将指向函数体的指针定为（3）。

面向对象分析与设计（第二版）习题答案第一章：面向对象基础知识1.1 什么是面向对象分析和设计？面向对象分析和设计（Object-Oriented Analysis and Design，OOAD）是软件工程中一种常用的方法论，通过将问题领域进行建模，通过对象、类、继承、封装等概念来描述现实世界中的实体、关系和行为。

面向对象分析和设计的目标是开发出可复用、可维护、可扩展、高质量的软件系统。

1.2 面向对象分析和设计的优势有哪些？面向对象分析和设计有以下优势： - 高度模块化：通过将系统划分为多个独立的对象，便于理解和设计系统的各个部分。

- 可复用性：面向对象设计强调对象的复用，通过定义通用的类和接口，可以提高代码的复用程度。

- 可维护性：面向对象的封装特性使得系统的各个部分具有独立性，便于维护和修改。

- 可扩展性：通过继承和多态等特性，可以方便地扩展和修改系统的功能。

- 高可靠性：面向对象的封装和隐藏特性可以减少系统中的错误和安全漏洞。

- 开发效率高：面向对象的分析和设计提供了一种更自然的思考和描述问题的方法，可以提高开发效率。

第二章：面向对象建模2.1 对象的特征有哪些？对象具有以下特征： - 状态（State）：对象的状态是对象的属性值的集合，表示对象的某个时刻的状态。

- 行为（Behavior）：对象可以执行的操作，描述了对象能够做什么。

- 身份（Identity）：每个对象都有唯一的身份，可以通过身份来区分不同的对象。

2.2 类和对象之间的关系有哪些？类和对象之间有以下关系： - 实例化（Instantiation）：类是对象的模板，对象是类的一个具体实例。

- 继承（Inheritance）：一个类可以继承另一个类的属性和方法。

- 聚合（Aggregation）：一个类可以包含其他类的对象作为成员变量。

- 关联（Association）：两个类之间存在某种关系，一个类的对象可以访问另一个类的对象。