1.1习题1解答
1.
（1）机器语言是计算机直接理解执行的语言，由一系列（二进制）指令组成，其助记符构成了汇编语言；接近人的自然语言习惯的程序设计语言为高级语言。
（2）结构化程序设计方法主要内容有：自顶向下，逐步求精；面向对象方法将现实世界中的客观事物描述成具有属性和行为的对象，抽象出共同属性和行为，形成类。
（3）C++程序开发通常要经过5个阶段，包括：编辑，编译，连接，运行，调试。首先是编辑阶段，任务是编辑源程序，C++源程序文件通常带有.c p p扩展名。接着，使用编译器对源程序进行编译，将源程序翻译为机器语言代码（目标代码），过程分为词法分析、语法分析、代码生成3个步骤。
在此之前，预编译器会自动执行源程序中的预处理指令，完成将其他源程序文件包括到要编译的文件中，以及执行各种文字替换等。
连接器的功能就是将目标代码同缺失函数的代码连接起来，将这个“漏洞”补上，生成可执行文件。程序运行时，可执行文件由操作系统装入内存，然后CPU从内存中取出程序执行。若程序运行进程中出现了错误，还在需要对程序进行调试。
（4）对象与对象之间通过消息进行相互通信。
（5）类是具有相同属性和行为的一组对象的抽象；任何一个对象都是某个类的一个实例。（6）多态性是指在一般类中定义的属性或行为，被特殊类继承之后，可以具有不同的数据类型或表现出不同的行为。
（7）面向对象的软件开发过程主要包括面向对象的方法分析、面向对象的设计、面向对象的编程、面向对象的测试和面向对象的维护。
（8）泛型程序设计是指在程序设计时，将数据类型参数化，编写具有通用性和可重用的程
序。
（9）#include
（10）C++中使用cin作为标准输入流对象，通常代表键盘，与提取操作符>>连用；使用cout作为标准输出流对象，通常代表显示设备，与<<连用。
2.简答题
（1）叙述机器语言、汇编语言、高级语言的特点。
机器语言是计算机直接执行的语言，由二进制的０和１构成的一系列指令组成；
汇编语言是机器语言的助记符；
高级语言是接近人的自然语言习惯的编程语言，通过编译变成机器语言。
（2）结构化的语言与面向对象的语言是截然分开的吗？
不是截然分开的，面向对象的程序设计中也包含过程，含有结构化的思想。
（3）C编写的程序不加修改就可以在C++编译器中编译。
（5）C++程序通过编译变成带扩展名.obj的目标文件；再通过连接变成带扩展名.exe的可执行文件。
（6）如果要求不使用include包含头文件，有什么办法使程序正常编译运行？
在相应的文件夹（子目录）中，找到需要包含的头文件，将头文件复制到包含处。
3.单选
C++语言程序能够在不同操作系统下编译、运行，说明C++具有良好的移植性。
（可以说C++语言完全兼容C语言，但是在这不能说C++语言程序能兼容不同的操作系统；对于计算机硬件，一般使用“兼容”一词，对于程序使用“移植”）。
（3）#include语句在程序运行前就执行了。
（4）C++程序运行时总是起始于main();
（5）用C++写程序时一个语句可分几行写。
（6）面向对象编程方法有：对象、继承、类等。
1.2习题2解答
1.
（1）C++的基本数据类型可分为5大类：逻辑型（或布尔型）、字符型、整形、实型、空值型。分别用关键字bool,char,int,float/double,void定义。长度分别为１，１，４，４/8，不定字节。整型、字符型的默认符号修饰为signed。
（2）十进制数值、八进制数值、十六进制数值的前缀分别为1～9,0,0x(或0X)。（3）一个整数值的数据类型为int，一个带小数点的数据类型为double。
（4）C++预定义的常用转义序中，在输出流中用于换行、空格的转义序列分别为\n,\t。（5）布尔型数值只有两个；true,false。在C++的算术运算式中，分别当作１，０。（6）字符由单引号’’括起来，字符串由双引号“”括起来。字符只能有１个字符，字符串可以有多个字符。空串的表示方法为“\0”（或“”）。
（7）标识符以英文字母，下划线开头。
（8）定义变量的同时赋初值的方法有赋值运算符＝，括号。定义常变量初值的方法有赋值运算符＝，括号。
（9）关系运算符操作数的类型可以是任何基本数据类型，对其中的实数类型不能进行直接比较。（if(a （－10）&&与||表达式按从左到右的顺序进行计算，以&&连接的表达式，如果左边的计算结果为false(或０)，右边的计算不需要进行，就能得到整个逻辑表达式的结果：false； 以||连接的表达式，如果左边的计算结果为true(或非０)，就能得到整个逻辑表达式的结果：true。 （11）>>运算符将一个数右移n位，相当于将该数除以2n，<<运算符将一个数左移n位，相当于将该数乘以2N。 （12）所有含赋值运算的运算符左边要求是左值。 （13）前置++、――的优先级高于后置++、――。 （14）按操作数数目分，运算符的优先级从高到低排列为单目、双目、三目，按运算符的性分，优先级从高到低排列为算术、移位、关系、按位、逻辑。 （15）在表达式中会产生副作用的运算符有++、--、各类赋值。 1.3习题3解答 1. （1）if语句中的表达式可以是任意表达式（关系表达式、逻辑表达式、算术表达式、常量）。 1.4习题4解答 1. （1）一个C++程序就是由一个个函数组成的即使是最简单的程序也有一个main()函数。（2）函数执行过程中通过return语句将函数值返回，当一个函数不需要返回值，此时需要使用void作为类型名。 （3）在C++中，如果函数定义在后，调用在先，需要进行函数原型声明，告诉编译器函数的（返回）类型，函数名，形式参数。其格式和定义函数时的函数头的形式基本相同，它必须以分号；结尾。 （4）函数调过程的3个步骤为：函数调用（或参数传递），函数体执行，返回。 （5）函数参数传递过程的实质是将实参值通过堆栈一一传送给实参。（实参传给实参？）（6）递归程序分两个阶段执行调用，回代。 （7）带inline关键字定义的函数为内联函数，在编译时将函数体展开到所有调用处。内联函数的好处是节省执行时间开销。 （8）函数名相同，但对应形参表不同的一组函数称为重载函数，参数表不同是指参数个数、类型不同。 （9）确定对重载函数中函数进行绑定的优先次序为精确匹配，对实参的类型向高类型转换后的匹配，实参类型向低类型及相容类型转换后的匹配。 （10）当既存在重载函数、又有函数模板，函数调用优先绑定重载函数，只有不能精确匹配重载函数时，才实例化类模板。 （11）内联函数的展开、重载函数的绑定、类模板的实例化与绑定均在编译阶段进行。（12）在C++中，函数不允许嵌套定义，允许嵌套调用。 2. （1）void fun(void)的定义是正确的。 double fun(int x；int y)和int fun();和double fun(int x,y)这都是不正确的（定义是不能以；结尾的）。 （2）函数int fun(int x,int y)的声明形式可以是int fun(int,int)；和int fun(int y,int x);和int fun(int i,int j);int fun(int x,int y)是不正确的因为函数的声明必须以；结尾）。 （3）C++语言中规定函数的返回值的类型是由定义该函数时所指定的数据类型所决定。（5）在C++中默认的形参值应该先从右边的形参开始向左边依次设置。 （6）重载函数参数个数相同时，参数类型必须不同。 （7）系统在调用重载函数时，依据的是函数名称、实参个数、实参类型。不能是函数类型。 （9）为了取代C中带参数的宏，在C++中使用内联函数。 （10）函数模板定义的头部template （11）若fun(8，3.1)调用的可以是fun(double,double) ――（当没有精确匹配时，优先进行向高类型转换后的匹配） （12）若fun(8，3.1)调用的可以是template 1.5习题５解答 1. （－1）enum weekday{sun,mon,tue,wed=4,thu,fri,sat}; weekday workday=mon; cout< 输出：5（怎么加的？） （2）在C++中，引用数组元素时，其数组下标的数据类型允许是非浮点型表达式，整形常量、整形表达式（整型表达式实际上包含了整型常量）。 （3）设有数组定义：char array[]=”China”;则数组array所占的空间为6个字节（’\0’）。（4）若：int a[][3]={1,2,3,4,5,6,7};则a数组高维的大小为：3。 （6）若二维数组a有m列，则在a[i][j]前的元素个数为i*m+j; 1.6习题六解答 1 （1）从变量的定义位置分，可分为全局变量与局部变量。其中，局部变量定义在函数或复合语句中，供函数或复合语句中使用。（2）变量的存储类型分为auto,extern,register,static。当声明一个静态（static）变量，它既具有局部变量的性质，又具有全 局变量的性质。 （3）Ｃ++程序的内存分为４个区：全局数据区，代码区，栈区，堆区。全局变量，静态变量，字符串常量存放在全局数据区，所 有在函数和代码存放在代码区，为运行函数而分配的函数参数，局部变量，返回地址存放在栈区。动态分配的内存在堆区。（4）全局变量，静态变量具有静态生存期；局部变量生存期为动态。（5）函数原型中形参标识符的作用域为为函数原型，函数的形参与函数体作用域为块作用域；函数，全局变量与常量有文件作用 域。 （6）Ｃ++源程序中以#开头，以换行符结尾的行称为预处理命令。预处理命令编译前由预处理器执行。 （7）可以通过３种方法使用名字空间，个别使用声明方式，全局声明方式，全局声明个别成员。 2. （1）在Ｃ++中，函数默认的存储类别为：auto。 （2）函数的形式参数是局部变量，在一个函数体内定义的变量只在本函数范围内有效，在函数的复合语句中定义的变量只在此复合语句中有效。 （3）#define PI3.14预处理命令必须以#开头，凡是以#开头的都是预处理命令行，在程序执行前执行预处理命令。 （4）动态分配的内存要用delete释放，局部auto变量分配的内存在函数调用结束时释放，全局变量的内存在程序结束时释放。 1.7习题7解答 1. （1）类的私有成员只能被该类的成员函数或友元函数访问。 （2）类的数据成员不能在定义的时候初始化，而应该通过构造函数初始化。 （3）类成员默认的访问方式是private. （4）类的公有成员函数的集合是该类给外界提供的接口。 （5）类的公有成员可以被类作用域内的任何对象访问。 （6）为了能够访问到某个类的私有成员，必须在该类中声明该类的友元。 （7）类的静态成员为该类的所有对象所共享。 （8）每个对象都有一个指向自身的指针，称为this指针，通过使用它来确定其自身的地址。 （9）运算符new自动建立一个大小合适的对象并返回一个具有正确 类型的指针。 （10）Ｃ++禁止非const成员函数访问const对象。 （11）定义类的动态对象数组时，系统只能够自调用该类的构造函数对其进行初始化。 （12）Ｃ++中语句const char*const p=”hello”;所定义的指针p和它所指的内容都不能被以改变。 （13）假定AB为一个类，则语句AB(AB&x);为该类拷贝构造函数原型说明。 （14）在C++中访问一个对象的成员所用的运算符是.，访问一个指针所指向的对象的成员所用的运算符是->。 （15）析构函数在对象的生存期结束时被自动调用，全局对象和静态对象的析构函数在程序运行结束时调用。 （16）设p是指向一个类的动态对象的指针变量，则执行delete P;语句时，将自动调用该类的析构函数。 2. （1）数据封装就是将一组数据和与这组数据有关操作组装在一起，形成一个实体，这实体也就是类。 （2）类的实例化就是创建类的对象。 （3）已知p是一个指向类Sample数据成员m的指针，s是类Sample 的一个对象。如果要给m赋值为５：s.*p=5; （4）类与对象的关系和数据类型与变量的关系是相似的，对象是类的一个实例，一个对象只能属于一个具体的类。 （5）封装要求对象就具有明确的功能，它使得一个对象可以像一个部件一样用在各种程序中。封装是将一组数据和这组数据有关的操作组装在一起。 （6）内联函数是在编译时（而不是运行时）将该函数的目标代码插入到每一个调用该函数的地方。 （7）类中的函数成员可以在类体中定义，也可以在类体之外定义。（8）Ｃ++中的对象并不是Ｃ语言中的结构体变量，它是一个状态和操作（或方法）的封装体，对象代表着正在创建的系统中的一个实体，对象之间的信息传递是通过消息进行的。 （9）在建立类的对象时只为每个对象分配用于保存数据成员的内存。3. （1）类和数据类型有何关联？ 类相当于一种包含函数的自定义数据类型，它不占内存空间，是一个抽象的“虚”体，使用已定义的类建立对象就像用数据类型定义变量一样。对象建立后，对象占据内存，变成了一个“实”体。类与对象的关系就像数据类型与变量的的关系一样。其实，一个变量就是一个简单的不含成员函数的数据对象。 （2）类和对象的内存分配关系？ 为节省内存，编译器在创建对象时，只为各对象分配用于保存各对象数据成员初始化的值，并不为各对象的成员函数分配单独的内存空间，而是共享类的成员函数定义，即类中成员函数的定义为该类的所有对象所共享，这是C++编译器创建对象的一种方法，实际应用中， 我们仍将对象理解为由数据成员和函数成员两部分组成。 （3）什么是浅拷贝？什么是深拷贝？二者有何异同？ 构造函数用于建立对象时给对象赋初值以初始化新建立的对象。如果有一个现存的对象，在建立新对象时希望利用现存对象作为新对象的初值，即用一个已存在的对象去初始化一个新建立的对象。C++提供的拷贝构造函数用于在建立新对象时将已存在的对象的数据成员值复制给新，以初始化新对象。拷贝构造函数在用类的一个对象去初始化该类的另一个对象时调用，以下3种情况相当于用一个已存在的对象去初始化新建立的对象，因此，调用拷贝构造函数：1当用类的一个对象去初始化该类的另一个对象时。 2如果函数的形参是类的对象，调用函数时，将对象作为函数 实参传递给函数的形参时。 3如果函数的返回值是类的对象，函数执行完成，将返回值返 回时。 原因在于默认的拷贝构造函数实现的只能是浅拷贝，即直接将原对象的数据成员值依次复制给新对象中对应的数据成员，并没有为新对象另外分配内存资源。这样，如果对象的数据成员是指针，两个指针对象实际上指向的是同一块内存空间。 当类的数据成员中有指针类型时，我们就必须定义一个特定的拷贝构造函数，该拷贝构造函数不仅可以实现原对象和新对象之间的数据成员的复制，而且可以为新的对象分配单独的内存资源，这就是深拷贝构造函数。 （4）什么是this指针？它的作用是什么？ 一个类的成员函数中，有时希望引用调用它的对象，对此，C++采用隐含的this指针来实现。this指针是一个系统预定义的特殊指针，指向当前对象，表示当前对象的地址。系统利用this指针明确指出成员函数当前操作的数据成员所属的对象。实际上，当一个对象调用其成员函数时，编译器先将该对象的地址赋给this指针，然后调用成员函数，这样成员函数对对象的数据成员进行操作时，就隐含使用了this指针。 一般而言，通常不直接使用this指针来引用对象的成员，但在某些少数情况下，可以使用this指针，如重载某些运算符以实现对象的连续赋值等。 This指针不是调用对象的名称，而是指向调用对象的指针的名称。This的值不能改变，它总是指向当前调用对象。 （5）C++中静态成员有何作用？它有何特点？ C++提供了静态成员，用以解决同一个类的不同对象之间数据成员和函数的共享问题。 静态成员的特点是：不管这个类创建了多少个对象，其静态成员在内存中只保留一份副本，这个副本为该类的所有对象所共享。 面向对象方法中还有类属性（class attribute）的概念，类属性是描述类的所有对象的共同特征的一个数据项，对于任何对象实像实例，它的属性值是相同的，C++通过静态数据成员来实现类属性。（6）友元关联有何性质？ ①友元关联是不能传递的，不能被继承。如B类是A类的友元，C类是B类的友元，C类和A类之间如果没有声明，就没有任何友元关系，不能进行数据共享。 ②友元关系是单向的，不具有交换性，如果声明B类是A类的友元，B类的成员函数就可以访问A类的私有和保护数据，但A类的成员函数却不能访问B类的私有和保护数据。 （7）在C++程序设计中，友元关系的优点和缺点是什么？ 友元概念的引入，提高了数据的共享性，加强了函数与函数之间、类与类之间的相互联系，大大提高了程序的效率，这是友元的优点，但友元也破坏了数据隐蔽和数据封装，导致程序的可维护性变差，给程序的重用和扩充埋下了深深的隐患，这是友元的缺点。 （8）如何实现不同对象的内存空间的分配和释放？ 当类被实例化成对象后，不同类别的对象占据不同类型的内存，其规律与普通变量相同： 1类的全局对象占有数据段的内存。 2类的局部对象内存分配在栈中。 3函数调用时为实参建立的临时对象内存分配在栈中。 4使用动态内存分配语句new建立的动态对象，内存在堆中分 配。 虽然类（对象）是由数据成员与成员函数组成。但是，程序运行时，系统只为各对象的数据成员分配单独内存空间，而该类的所有对象则共享类的成员函数定义以及为成员函数分配的空间。对象的内存 空间分配有下列规则： 1对象的数据成员与成员函数占据不同的内存空间，数据成员 的内存空间与对象的存储类别相关，成员函数的内存空间在 代码段中。 2一个类所有对象的数据成员拥有各自的内存空间。 3一个类所有对象的成员函数为该类的所有对象共享，在内存 中，只有一个副本随着对象的生命周期的结束，对象所占的 空间就会释放，各类对象内存空间释放时间与方法如下： a．全局对象的数据成员占有的内存空间在程序结束时释放。 b．局部对象与实参对象数据成员的内存空间在函数调用 结束时释放。 c．动态对象数据成员的内存空间要使用delete语句释放。 d．对象的成员函数的内存空间在该类的所有对象生命周 期结束时自动释放。 1.8习题８解答1. （1）Ｃ++程序设计的关键之一是利用继承实现软件重用，有效地缩短程序的开发时间。（2）基类的对象可以作为派生类的对象使用，这称为类型兼容（或赋值兼容）。 （3）在Ｃ++中，三种派生方式的说明符号为public,private,protected,如果不加说明，则默认的派生方式为private。 （4）当私有派生时，基类的的公有成员成为派生类的私有成员；保护成员成为派生类的私有成员；私有成员成为派生类的不可访问成员。 （5）相互关联的各个类之间的关系主要分为组成关系和继承关系。 （6）在派生类中不能直接访问基类的私有成员否则破坏了基类的封装性。 （7）保护成员具有双重角色，对派生类的成员函数而言，它是公有成员，但对所在类之外定义的其它函数而言则是私有成员。 （8）多继承时，多个基类中的同名的成员在派生类中由于标识符不唯一而出现二义性。在派生类中采用成员名限定或重定义具有二义性的成员来消除该问题。 （9）Ｃ++提供的多继承机制允许一个派生类继承多个基类。 2. （1）一个派生类可以作为另外一个派生类的基类；派生类至少有一个基类；派生类的成员除了它自己的成员外，还包含了它的基类的成员。 （2）在多继承中，公有派生和私有派生对于基类成员在派生类中的可访问性与单继承的规则是完全相同的。 （3）友元关系是不能继承的。 （4）派生类一般都是公有派生；对基类成员的访问必须是无二义性的；赋值兼容规则也是适用于多重继承的场合。 （5）基类的保护成员在公有派生中仍然是保护的；基类的保护成员在私有派生中却是私有的；对基类成员的访问必须是无二义性的。 （6）在公有派生的情况下，派生类中定义的成员函数只能访问原基类中的公有成员和保护成员。 （7）每个派生类的构造函数都要为虚基类构造函数提供实参；多继承时有可能出现对基类成员访问的二义性问题；建立派生类对象时，虚基类数的构造函数会首先被调用。（8）在一个派生类对象结束其生命周期时先调用基类的析构函数后调用派生类的析构 函数。 （9）当保护继承时，基类的公有成员和保护成员在派生类中成为保护成员，不能通过派生类的对象来直接访问。 （10）若派生类的成员函数不能直接访问基类中继承来的某个成员，则该成员一定是基类中的私有成员。 （11）设置虚基类的目的是消除二义性。 （12）继承具有传递性，即当基类本身也是某个类的派生类时，底层的派生类也会自动继承间接基类的成员。 （13）在派生类构造函数的初始化列表中不能包含派生类中一般数据成员的初始化。（14）在公有派生情况下，派生类的对象可以赋给基类的对象；派生类的对象可以初始化基类的引用；派生类的对象的地址可以赋给指向基类的指针。 3. （1）派生类如何实现对基类私有成员的访问？ 无论使用哪一种继承方式，基类的私有成员都不允许外部函数直接访问，也不允许派生的成员函数直接访问，但是可以通过基类的公有成员函数间接访问该类的私有成员。 （2）什么是赋值兼容？它会带来什么问题？ 类型兼容是指在公有派生的情况下，一个派生类对象可以作为基类的对象来使用。类型兼容又称为类型赋值值兼容或类型适应。 在C++中，类型兼容主要指以下3种情况： 1派生类对象可以赋值给基类对象； 2派生类对象可以初始化基类的引用； 3派生类对象的地址可以赋给指向基类的指针； 由于派生类对象中包含基类子对象，所以这种引用方式是安全的，但是这种 方法只能引用从基类继承的成员。如果试图通过基类指针引用那些只有在派 生类中才有的成员，编译器将会报告语法错误。 （3）多重继承时，构造函数和析构函数的执行顺序是如何实现的？ 多得继承时，构造函数的执行顺序是：先执行基类的构造函数，再执行对象成员的构造函数，最后执行派生类的构造函数。 在多个基类之间则严格按照派生类声明时从左到右的顺序来执行各基类的构造 函数，而析构函数的执行顺序则正好与构造函数的执行顺序相反。 （4）继承与组合之间的区别和联系是什么？ 继承描述的是一般类与特殊类的关系，类与类之间体现的是”is a kind of”，即如果在逻辑上A是B的一种，允许A继承B的功能和属性。例如汽车（automobile）是交通工具（vehicle）的一种，小汽车（car）是汽车的一种。那么类automobile可以从类vehicle 派生，类car可以从类automobile派生。 组合描述的是整体与部分的关系，类与类之间体现的是”is a part of”，如果在逻辑上A是B的一部分，则允许A和其他数据成员组合为B。例如：发动机、车轮、电池、车门、方向盘、底盘都是小汽车的一部分，它们组合成汽车，而不能说汽车是发动机的一种。 在C++中，类的继承与类的组合很相似，继承和组合既有区别，也有联系，主要表现在描述的关系不同。某些比较复杂的类，既需要使用继承，也需要使用组合，二者一起使用。 在某些情况下，继承与组合的实现还可以互换。在多继承时，一个派生类有多个 直接基类，派生类实际上是所有基类属性和行为的组合。派生类是对基类的扩充，派生 类的成员一部分是从基类中来，因此派生类组合了基类。既然这样，派生类也可以通过 组合类实现。什么时候用继承，什么时候使用组合，要根据问题中类与类之间的具体关系，顺其自然，权衡考虑。 （5）什么是虚基类？它有什么作用？ 在多继承中，当派生类的部分或全部直接基类又是从另一个共同基类派生而来 时，这些直接基类中从上一级共同基类继承来的成员就拥有相同的名称。在派生类的对 象中，同名数据成员在内存中同时拥有多个副本，同一个成员函数会有多个映射，出现 二义性，因此，C++将共同基类设置为虚基类。虚基类使得从不同的路径继承过来的同 名数据成员在内存中只有一个副本，同一个函数也只有一个映射。这样不公解决了二义 性的问题，也节省了内存，避免了数据不一致的问题。 1.9习题9解答 1. （1）将一个函数调用链接上相应函数体的代码，这一过程称为联编（绑定）。 （2）Ｃ++支持两种多态性：静态多态性和动态多态性。 （3）在编译时就确定的函数调用称为静态联编，它通过使用重载函数实现。 （4）在运行时才确定的函数调用称为动态联编，它通过继承和虚函数来实现。 （5）虚函数的声明方法是在函数原型前加上关键字virtual。 （6）Ｃ++的静态多态性是通过重载函数实现的。 （7）Ｃ++的动态多态性是通过虚函数实现的。 （8）当通过基类指针使用虚函数时，Ｃ++会在与对象关联的派生类中正确地选择重定义的函数。 （9）如果一个类包含一个或多个纯虚函数，则该称为抽象类。 （10）若以非成员函数形式，为类Bounce重载!运算符，其操作结果为bool型数据，则该运算符重载函数的原型是：friend bool operate!(Bounce); 2. （1）在Ｃ++中：：运算符不能被重载。 （2）运算符重载不能改变运算数的个数、优先级、结合性和语法结构。 （3）如果表达式++i*k中的++和*都是重载的友元运算符，则采用运算符函数调用格式，该表达式还可表示为operator*(operator++(i),k)。 （4）5.0+2.0和5+2两个表达式中的+的意义不相同。 （5）有的运算符只能作为成员函数重载。 （6）已知在一个类体中包含如下函数原型：VOLUME operator-(VOLUME)const；。 这是运算符－的重载运算符函数；这是一个成员函数；这个函数不改变类的任何数据成员的值。 （7）在表达式x+y*z中，+是作为成员函数重载的运算符，*是作为非成员函数重载的运算符。operator+有一个参数，operator*有两个参数； （8）在Ｃ++中，对象之间的相互通信通过调用成员函数来实现。 （9）Franction operator+(Franction,Franction);Franction&operator=(Franction&,Franction); Franction&operator+=(Franction&,Franction)以上是重载为非成员函数的运算符函数原型。 （10）当一个类的某个函数被说明为virtual时，该函数在该类的所有派生类中都是虚函数。（11）纯虚函数是一个在基类中说明的虚函数，它在该基类中没有定义，但要求在任何派生类都必须定义自己的版本。 （12）virtual void vf()=0;这个基类中的成员函数表示纯虚函数。 （13）如果一个类至少有一个纯虚函数，那么就称该类为抽象类。 （14）纯虚函数是一种特殊的虚函数，它没有具体的定义；抽象类是指具有纯虚函数的类； 抽象类只能作为基类来使用，其纯虚函数的定义同派生类给出。 （15）抽象类的特性:不能定义其对象。 （16）抽象类应含有至少一个纯虚函数。 （17）类Ｂ是类Ａ的公有派生类，类Ａ和类Ｂ中都定义了虚函数fun(),p是一个指向类Ａ对象的指针，则p->A:：：func()将调用类Ａ中的函数func()。 （18）在Ｃ++中，用于实现运行时多态性的是虚函数。 （19）Class A{ Public: Virtual void func1(){} void func2(){} }; Class B:public A{ Public: V oid func1(){cout<<”class B func1”< Virtual void func2(){cout<<”class B func2”< }; 以上代码中Ｂ：：func1是虚函数，而Ａ：：func2不是虚函数。 （20）虚函数不得是静态成员函数。 （21）如果派生类没有实现基类的一个纯虚函数，则该派生类是一个抽象类。 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构 第一章绪习题一 1.有下列几种用二元组表示的数据结构，试画出它们分别对应的图形表示（当出现多个关系时， 对每个关系画出相应的结构图），并指出它们分别属于何种结构。 ⑴ A=(K,R)其中 K={a1,a2,a3...,an} R={} ⑵ B=(K,R)其中 K={a,b,c,d,e,f,g,h} R={r} r={ 第六章运行时存储空间组织 6.1 完成下列选择题： (1) 过程的DISPLAY表中记录了。 a. 过程的连接数据 b. 过程的嵌套层次 c. 过程的返回地址 d. 过程的入口地址 (2) 过程P1调用P2时，连接数据不包含。 a. 嵌套层次显示表 b. 老SP c. 返回地址 d. 全局DISPLAY地址 (3) 堆式动态分配申请和释放存储空间遵守原则。 a. 先请先放 b. 先请后放 c. 后请先放 d. 任意 (4) 栈式动态分配与管理在过程返回时应做的工作有。 a. 保护SP b. 恢复SP c. 保护TOP d. 恢复TOP (5) 如果活动记录中没有DISPLAY表，则说明。 a. 程序中不允许有递归定义的过程 b. 程序中不允许有嵌套定义的过程 c. 程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程 d. 程序中允许有递归定义的过程，也允许有嵌套定义的过程 【解答】 (1) b (2) a (3) d (4) b (5) b 6.2 何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？ 【解答】当过程定义允许嵌套时，一个过程在运行中应能够引用在静态定义时包围它的任一外层过程所定义的变量或数组。也就是说，在栈式动态存储分配方式下的运行中，一个过程Q可能引用它的任一外层过程P的最新活动记录中的某些数据。因此，过程Q运行时必须知道它的所有(静态)外层过程的最新活动记录的地址。由于允许递归和可变数组，这些外层过程的活动记录的位置也往往是变迁的。因此，必须设法跟踪每个(静态)外层的最新活动记录的位置，而完成这一功能的就是DISPLAY嵌套层次显示表。 也即，每当进入一个过程后，在建立它的活动记录区的同时也建立一张DISPLAY表，它自顶而下每个单元依次存放着现行层、直接外层等，直至最外层(主程序层)等每一层过程的最新活动记录的起始地址。 6.3 (1) 写出实现一般递归过程的活动记录结构以及过程调用、过程进入与过程返回的指令； (2) 对以return(表达式)形式(这个表达式本身是一个递归调用)返回函数值的特殊函数过程，给出不增加时间开销但能节省存储空间的实现方法。假定语言中过程参数只有传值和传地址两种形式，为便于理解，举下例说明这种特殊的函数调用： int gcd (int p,int q) { if (p % q ==0) return q; else return gcd (q, p % q) } 【解答】(1) 一般递归过程的活动记录如图6-1所示。 首页入门学 习 程序 员 计算机考 研 计算机电子书 下载 硬件知 识 网络知 识 专业课程答案 下载 视频教程下载 第一章 作者：佚名来源：网络 1、有一台计算机，具有IMB 内存，操作系统占用200KB ，每个用户进程各占200KB 。如果用户进程等待I/O 的时间为80 % ，若增加1MB 内存，则CPU 的利用率提高多少？ 答：设每个进程等待I/O 的百分比为P ，则n 个进程同时等待刀O 的概率是Pn ，当n 个进程同时等待I/O 期间CPU 是空闲的，故CPU 的利用率为1-Pn。由题意可知，除去操作系统，内存还能容纳4 个用户进程，由于每个用户进程等待I/O的时间为80 % , 故： CPU利用率＝l-（80%)4 = 0.59 若再增加1MB 内存，系统中可同时运行9 个用户进程，此时：cPu 利用率＝l-（1-80%)9 = 0.87 故增加IMB 内存使CPU 的利用率提高了47 % : 87 ％/59 ％=147 % 147 ％-100 % = 47 % 2 一个计算机系统，有一台输入机和一台打印机，现有两道程序投入运行，且程序A 先开始做，程序B 后开始运行。程序A 的运行轨迹为：计算50ms 、打印100ms 、再计算50ms 、打印100ms ，结束。程序B 的运行轨迹为：计算50ms 、输入80ms 、再计算100ms ，结束。试说明（1 ）两道程序运行时，CPU有无空闲等待？若有，在哪段时间内等待？为什么会等待？( 2 ）程序A 、B 有无等待CPU 的情况？若有，指出发生等待的时刻。 答：画出两道程序并发执行图如下： （1）两道程序运行期间，CPU存在空闲等待，时间为100 至150ms 之间（见图 第七章目标代码生成 7.1 对下列四元式序列生成目标代码： T=A-B S=C+D W=E-F U=W/T V=U*S 其中，V是基本块出口的活跃变量，R0和R1是可用寄存器。 【解答】简单代码生成算法依次对四元式进行翻译。我们以四元式T=a+b为例来说明其翻译过程。 汇编语言的加法指令代码形式为 ADD R, X 其中，ADD为加法指令；R为第一操作数，第一操作数必须为寄存器类型；X为第二操作数，它可以是寄存器类型，也可以是内存型的变量。ADD R,X指令的含意是：将第一操作数R与第二操作数相加后，再将累加结果存放到第一操作数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能需要下面三条汇编指令： MOV R, a ADD R, b MOV T, R 第一条指令是将第一操作数a由内存取到寄存器R中；第二条指令完成加法运算；第三条指令将累加后的结果送回内存中的变量T。是否在翻译成目标代码时都必须生成这三条汇编指令呢？从目标代码生成的优化角度考虑，即为了使生成的目标代码更短以及充分利用寄存器，上面的三条指令中，第一条和第三条指令在某些情况下是不必要的。这是因为，如果下一个四元式紧接着需要引用操作数T，则第三条指令就不急于生成，可以推迟到以后适当的时机再生成。 此外，如果必须使用第一条指令，即第一操作数不在寄存器而是在内存中，且此时所有可用寄存器都已分配完毕，这时就要根据寄存器中所有变量的待用信息(也即引用点)来决定淘汰哪一个寄存器留给当前的四元式使用。寄存器的淘汰策略如下： (1) 如果某寄存器中的变量已无后续引用点且该变量是非活跃的，则可直接将该寄存器作为空闲寄存器使用。 (2) 如果所有寄存器中的变量在基本块内仍有引用点且都是活跃的，则将引用点最远的变量所占用寄存器中的值存放到内存与该变量对应的单元中，然后再将此寄存器分配给当前的指令使用。 因此，本题所给四元式序列生成的目标代码如下： MOV R0, A SUB R0, C /*R0=T*/ MOV R1, C ADD R1, D /*R1=S*/ MOV S, R1 /*S引用点较T引用点远，故将R1的值送内存单元S*/ MOV R1, E SUB R1, F /*R1=W*/ SUB R1, R0 /*R1=U*/ MUL R1, S /*R1=V*/ 7.2 假设可用的寄存器为R0和R1，且所有临时单元都是非活跃的，试将以下四元式基本 第4章存储管理 “练习与思考”解答 1．基本概念和术语 逻辑地址、物理地址、逻辑地址空间、内存空间、重定位、静态重定位、动态重定位、碎片、碎片紧缩、虚拟存储器、快表、页面抖动 用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为相对地址或逻辑地址。 内存中各物理存储单元的地址是从统一的基地址开始顺序编址的，这种地址称为绝对地址或物理地址。 由程序中逻辑地址组成的地址范围叫做逻辑地址空间，或简称为地址空间。 由内存中一系列存储单元所限定的地址范围称作内存空间，也称物理空间或绝对空间。 程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称作重定位。 静态重定位是在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的内存地址。 动态重定位是在程序执行期间，每次访问内存之前进行重定位。这种变换是靠硬件地址转换机构实现的。 内存中这种容量太小、无法被利用的小分区称作“碎片”或“零头”。 为解决碎片问题，移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。这种技术称为紧缩（或叫拼凑）。 虚拟存储器是用户能作为可编址内存对待的虚拟存储空间，它使用户逻辑存储器与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间。 为了解决在内存中放置页表带来存取速度下降的矛盾，可以使用专用的、高速小容量的联想存储器，也称作快表。 若采用的置换算法不合适，可能出现这样的现象：刚被换出的页，很快又被访问，为把它调入而换出另一页，之后又访问刚被换出的页，……如此频繁地更换页面，以致系统的大部分时间花费在页面的调度和传输上。此时，系统好像很忙，但实际效率却很低。这种现象称为“抖动”。 2．基本原理和技术 （1）存储器一般分为哪些层次？各有何特性？ 存储器一般分为寄存器、高速缓存、内存、磁盘和磁带。 CPU内部寄存器，其速度与CPU一样快，但它的成本高，容量小。 高速缓存（Cache），它们大多由硬件控制。Cache的速度很快，它们放在CPU内部或非常靠近CPU的地方。但Cache的成本很高，容量较小。 内存（或称主存），它是存储器系统的主力，也称作RAM（随机存取存储器）。CPU可以直接存取内存及寄存器和Cache中的信息。然而，内存中存放的信息是易变的，当机器电源被关闭后，内存中的信息就全部丢失了。 磁盘（即硬盘），称作辅助存储器（简称辅存或外存），它是对内存的扩展，但是CPU不能直接存取磁盘上的数据。磁盘上可以永久保留数据，而且容量特别大。磁盘上数据的存取速度低于内存存取速度。 磁带保存的数据更持久，容量更大，但它的存取速度很慢，而且不适宜进行随机存取。所以，磁带设备一般不能用做辅存。它的主要用途是作为文件系统的后备，存放不常用的信息或用做系统间传送信息的介质。 （2）装入程序的功能是什么？常用的装入方式有哪几种？ 装入程序的功能是根据内存的使用情况和分配策略，将装入模块放入分配到的内存区中。 程序装入内存的方式有三种，分别是绝对装入方式、可重定位装入方式和动态运行时装入方式。 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（） 和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的 关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若 为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关 系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数 组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中 的指针表示。 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不 能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 编译 原理 课后题答案 第二章 P36-6 (1) L ( G 1 ) 是 0~9 组成的数字串 (2) 最左推导 : N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 N ND DD 3D 34 N ND NDD DDD 5DD 56D 568 最右推导 : N ND N 7 ND 7 N 27 ND 27 N 127 D127 0127 N ND N 4 D 4 34 N ND N 8 ND 8 N 68 D68 568 P36-7 G(S) O 1|3|5|7|9 N 2|4|6|8|O D 0|N S O| AO A AD | N P36-8 文法： E T| E T|E T T F |T * F |T / F F ( E)|i 最左推导 : E E T T T F T i T i T * F i F * F i i * F i i * i E T T * F F * F i * F i *( E ) i *( E T) i *( T T ) i *( F T ) i *( i T ) i *( i F ) i *( i i ) 最右推导 : E E T E T * F E T * i E F * i E i * i T i * i F i * i i i * i E T F * T F * F F *( E) F *( E T) F *( E F ) F *( E i ) F *( T i ) F *( F i ) F *( i i ) i *( i i ) 语法树： /******************************** E E+T E+T F T F i F i i i+i+i *****************/ P36-9 句子 iiiei有两个语法树： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei E E E+T E-T T T*F E-T F F F i T F i i i F i i i-i-i i+i*i P36-10 /************** S TS | T T( S) | ( ) ***************/ P36-11 /*************** L1: S AC A aAb | ab C cC | L2: 第一章绪论 1．什么是操作系统的基本功能? 答：操作系统的职能是管理和控制汁算机系统中的所有硬、软件资源，合理地组织计算 机工作流程，并为用户提供一个良好的工作环境和友好的接口。操作系统的基本功能包括： 处理机管理、存储管理、设备管理、信息管理(文件系统管理)和用户接口等。 2．什么是批处理、分时和实时系统?各有什么特征? 答：批处理系统(batchprocessingsystem)：操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序(monitor)自动依次处理。其主要特征是：用户脱机使用计算机、成批处理、多道程序运行。 分时系统(timesharingoperationsystem)：把处理机的运行时间分成很短的时间片，按时间片轮转的方式，把处理机分配给各进程使用。其主要特征是：交互性、多用户同时性、独立性。 实时系统(realtimesystem)：在被控对象允许时间范围内作出响应。其主要特征是：对实时信息分析处理速度要比进入系统快、要求安全可靠、资源利用率低。 3．多道程序(multiprogramming)和多重处理(multiprocessing)有何区别? 答；多道程序(multiprogramming)是作业之间自动调度执行、共享系统资源，并不是真正地同时执行多个作业；而多重处理(multiprocessing)系统配置多个CPU，能真正同时执行多道程序。要有效使用多重处理，必须采用多道程序设计技术，而多道程序设计原则上不一定要求多重处理系统的支持。 4．讨论操作系统可以从哪些角度出发，如何把它们统一起来? 答：讨论操作系统可以从以下角度出发： (1)操作系统是计算机资源的管理者； (2)操作系统为用户提供使用计算机的界面； (3)用进程管理观点研究操作系统，即围绕进程运行过程来讨论操作系统。 数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法 答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素 ②关系 （4）在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 ② 后继结点，其余每个结点有且只有1个后继结点。 答：①没有 ②没有 （5）在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点没有 ③ 结点，其余每个结点的后继结点数可以是 ④ 。 答：①前驱 ②1 ③后继 ④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（ ）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是 ① 、 ② 、 ③ 和 ④ 存储结构。 答：①顺序 ②链式 ③索引 ④哈希 （8）一个算法的效率可分为 ① 效率和 ② 效率。 答：①时间 ②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a ,b ,…,i }，R={(a ,b ),(a ,c ),(c ,d ),(c ,f ),(f ,h ),(d ,e ),(f ,g ),(h ,i )}，问相对于关系R ，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a 结点没有前驱结点，称为根结点，b 、e 、g 、i 结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n 为问题规模，给出对应的时间复杂度： T 1(n )=n log 2n -1000log 2n T 2(n )=3log 2n -1000log 2n T 3(n )=n 2 -1000log 2n T 4(n )=2n log 2n -1000log 2n 答：T 1(n )=O(n log 2n )，T 2(n )=O( )，T 3(n )=O(n 2 )，T 4(n )=O(n log 2n )。 （5）分析下面程序段中循环语句的执行次数。 int j=0,s=0,n=100; do { j=j+1; s=s+10*j; } while (j 第四章语义分析和中间代码生成 4.1 完成下列选择题： (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示： S→bAb {print″1″} A→(B {print″2″} A→a {print″3″} B→Aa) {print″4″} 若输入序列为b(((aa)a)a)b，且采用自下而上的分析方法，则输出序列为。a. 32224441 b. 34242421 c. 12424243 d. 34442212 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。 【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。 用语法制导翻译(SDTS)生成中间代码的要点如下： (1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理，如无条件跳转等。 例如下面的程序段： if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值，例如对输入串101.101，则S.val= 5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下： G[S]: S→L.L|L 《操作系统教程》习题答案 习题1 1．单项选择题 （1）大中小型计算机是以为中心的计算机系统。 A、CPU B、存储器 C、系统总线 D、通道 （2）以下关于操作系统的说法正确的是。 A、批处理系统是实现人机交互的系统 B、批处理系统具有批处理功能，但不具有交互能力 C、分时系统是实现自动控制，无须人为干预的系统 D、分时系统即具有分时交互能力，又具有批处理能力 （3）操作系统的职能是管理软硬件资源、合理地组织计算机工作流程和。 A、为用户提供良好的工作环境和接口 B、对用户的命令作出快速响应 C、作为服务机构向其它站点提供优质服务 D、防止有人以非法手段进入系统 （4）设计实时操作系统时，首先应考虑系统的。 A、可靠性和灵活性 B、实时性和可靠性 C、优良性和分配性 D、灵活性和分配性 （5）多道程序设计是指。 A、在分布式系统中同一时刻运行多个程序 B、在一台处理器上并行运行多个程序 C、在实时系统中并发运行多个程序 D、在一台处理器上并发运行多个程序 （6）以下关于并发性和并行性的说法正确的是。 A、并发性是指两个及多个事件在同一时刻发生 B、并发性是指两个及多个事件在同一时间间隔内发生 C、并行性是指两个及多个事件在同一时间间隔内发生 D、并发性是指进程，并行性是指程序 （1）B （2）B （3）A （4）B （5）D （6）B 2．填空题 （1）微机是以总线为纽带构成的计算机系统。 （2）在批处理兼分时系统中，往往把由分时系统控制的作业称为前台作业，把由批处理系统控制的作业称为后台作业。 （3）在分时系统中，若时间片长度一定，则用户数越多，系统响应时间越慢。 （4）分布式操作系统能使系统中若干台计算机协同完成一个共同的任务，分解问题成为子计算并使之在系统中各台计算机上并行执行，以充分利用各计算机的优势。 （5）用户通过网络操作系统可以网络通信、资源共享，从而大大扩展了计算机的应用范围。 3．简答题 （1）什么是操作系统？现代操作系统的基本特征是什么？并发性 （2）什么是批处理系统，衡量批处理系统好坏的主要指标是什么？及时性 （3）试述分时系统的原理及其特性。时间片原则交互性同时性独立性及时性 1. 画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索 遍历该图所的顶点序列和边的序列。 邻接表： 深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6 边的序列：（1，2） （2，3） （3，4） （4，5） （5，6） 广度优先搜索：顶点序列：1 -2 -3 -6 -5-4 边的序列：（1，2） （1，3） （1，6） （1，5） （5，4） 2 已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进 行遍历所得的深度优先生成树和广度优先生成树。 1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 0 0 1 0 1 0 2 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 4 0 0 0 0 1 0 0 0 1 0 5 0 0 0 0 0 1 0 0 0 1 6 1 1 0 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 1 1 5 2 4 6 3 8 1 0 0 1 0 0 0 0 1 0 9 0 0 0 0 1 0 1 0 0 1 10 1 0 0 0 0 1 0 0 0 0 解：邻接矩阵所表示的图如下： 自顶点1出发进行遍历所得的深度优先生成树： 自顶点1出发进行遍历所得的广度优先生成树： 3 请对下图的无向带权图 （1）写出它的邻接矩阵，并按普里母算法求其最小生成树。 （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 解：（1） 邻接矩阵： ∞ 4 3 ∞ ∞ ∞ ∞ ∞ 4 ∞ 5 5 9 ∞ ∞ ∞ 3 5 ∞ 5 ∞ ∞ ∞ 5 ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞ ∞ 5 4 ∞ ∞ 6 ∞ 普里母算法求得的最小生成树： 7 5 9 6 4 5 6 3 5 5 3 4 e d 2 5 c b h f g a 第一章： 一、3、10、15、23、27、35 3.什么是操作系统？操作系统在计算机系统中的主要作用是什么？ 操作系统是管理系统资源、控制程序执行、改善人机界面、提供各种服务,并合理组织计算机工作流程和为用户有效地使用计算机提供良好运行环境的一种系统软件. 主要作用 (1)服务用户—操作系统作为用户接口和公共服务程序 (2)进程交互—操作系统作为进程执行的控制者和协调者 (3)系统实现—操作系统作为扩展机或虚拟机 (4)资源管理—操作系统作为资源的管理者和控制者 10.试述系统调用与函数（过程）调用之间的区别。 （1）调用形式和实现方式不同； （2）被调用的代码位置不同； （3）提供方式不同 15.什么是多道程序设计？多道程序设计有什么特点？ 多道程序设计是指允许多个作业（程序）同时进入计算机系统内存并执行交替计算的方法。从宏观上看是并行的，从微观上看是串行的。 （1）可以提高CPU、内存和设备的利用率； （2）可以提高系统的吞吐率，使单位时间内完成的作业数目增加； （3）可以充分发挥系统的并行性，使设备和设备之间，设备和CPU之间均可并行工作。 23.现代操作系统具有哪些基本功能？请简单叙述之。 （1）处理器管理； （2）存储管理； （3）设备管理； （4）文件管理； （5）联网与通信管理。 27.什么是操作系统的内核？ 内核是一组程序模块，作为可信软件来提供支持进程并发执行的基本功能和基本操作，通常驻留在内核空间，运行于内核态，具有直接访问计算机系统硬件设备和所有内存空间的权限，是仅有的能够执行特权指令的程序。 35.简述操作系统资源管理的资源复用技术。 系统中相应地有多个进程竞争使用资源，由于计算机系统的物理资源是宝贵和稀有的，操作系统让众多进程共享物理资源，这种共享称为资源复用。 （1）时分复用共享资源从时间上分割成更小的单位供进程使用； （2）空分复用共享资源从空间上分割成更小的单位供进程使用。 . 二、2、5 2、答：画出两道程序并发执行图如下： (1) (见图中有色部分)。 (2)程序A无等待现象，但程序B有等待。程序B有等待时间段为180ms至200ms间(见 图中有色部分)。 5、答：画出三个作业并行工作图如下(图中着色部分为作业等待时间)： 1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/******************************** 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/《数据结构》课后习题答案
数据结构实用教程第二版答案_徐孝凯
编译原理教程课后习题答案——第六章
操作系统教程_孙钟秀(第四版)课后习题答案
编译原理教程课后习题答案——第七章
操作系统》第章教材习题解答
数据结构(第二版)课后习题答案(王红梅主编)
编译原理_第三版_课后答案.docx
计算机操作系统教程课后答案
数据结构课后习题答案
数据结构课程 课后习题答案
编译原理教程课后习题答案——第四章
操作系统教程习题答案
数据结构课后作业答案
操作系统教程第5版部分习题标准答案
数据结构课后习题答案清华大学出版社殷人昆
编译原理课后习题答案(陈火旺+第三版)
数据结构课后习题及答案
相关主题
文本预览