《整理乐器制造专业(钢琴调律方向) - 北京市教育委员会.doc》由会员分享，可在线阅读，更多相关《整理乐器制造专业(钢琴调律方向) - 北京市教育委员会.doc（58页珍藏版）》请在金锄头文库上搜索。
1、第1章 绪论1-1什么是数据? 它与信息是什么关系?【解答】什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到
2、计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面?【解答】数据结构是指数据以及相互之间的关系。记为：数据结构 = D, R 。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容： 数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； 数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； 施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无
3、关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、 栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？【解答】线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个
4、直接后继。例如，一维数组、线性表等就是典型的线性结构非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。1-4什么是抽象数据类型？试用C+的类声明定义“复数”的抽象数据类型。要求(1) 在复数内部用浮点数定义它的实部和虚部。(2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。(3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。(4) 定义重载的流函数来输出一个复数。【解答】抽象数据类型通常是指由用
5、户定义，用以表示应用问题的数据模型。抽象数据类型由基本的数据类型构成，并包括一组相关的服务。/在头文件complex.h中定义的复数类#ifndef _complex_h_#define _complex_h_#include class comlex public: complex ( ) Re = Im = 0; /不带参数的构造函数 complex ( double r ) Re = r; Im = 0; /只置实部的构造函数 complex ( double r, double i ) Re = r; Im = i; /分别置实部、虚部的构造函数 double getReal ( )
6、return Re; /取复数实部 double getImag ( ) return Im; /取复数虚部 void setReal ( double r ) Re = r; /修改复数实部 void setImag ( double i ) Im = i; /修改复数虚部 complex& operator = ( complex& ob) Re = ob.Re; Im = ob.Im; /复数赋值 complex& operator + ( complex& ob );/重载函数：复数四则运算 complex& operator ( complex& ob ); complex& ope
7、rator * ( complex& ob ); complex& operator / ( complex& ob ); friend ostream& operator ( ostream& os, complex& c );/友元函数：重载private: double Re, Im;/复数的实部与虚部;#endif /复数类complex的相关服务的实现放在C+源文件complex.cpp中#include #include #include “complex.h”complex& complex : operator + ( complex & ob ) /重载函数：复数加法运算。c
8、omplex * result = new complex ( Re + ob.Re, Im + ob.Im );return *result; complex& complex : operator ( complex& ob ) /重载函数：复数减法运算 complex * result = new complex ( Re ob.Re, Im ob.Im );return * result;complex& complex : operator * ( complex& ob ) /重载函数：复数乘法运算complex * result = new complex ( Re * ob.R
9、e Im * ob.Im, Im * ob.Re + Re * ob.Im );return *result;complex& complex : operator / ( complex& ) /重载函数：复数除法运算double d = ob.Re * ob.Re + ob.Im * ob.Im;complex * result = new complex ( ( Re * ob.Re + Im * ob.Im ) / d,( Im * ob. Re Re * ob.Im ) / d );return * result;friend ostream& operator ( ostream&
10、 os, complex & ob ) /友元函数：重载，将复数ob输出到输出流对象os中。 return os ob.Re = 0.0 ) ? “+” : “-” fabs ( ob.Im ) “i”;1-5 用归纳法证明：(1) (2) (3) 【证明】略1-6 什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。【解答】通常，定义算法为“为解决某一特定任务而规定的一个指令序列。”一个算法应当具有以下特性： 有输入。一个算法必须有0个或多个输入。它们是算法开始运算前给予算法的量。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内
11、给定。 有输出。一个算法应有一个或多个输出，输出的量是算法计算的结果。 确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。 有穷性。一个算法无论在什么情况下都应在执行有穷步后结束。 有效性。算法中每一条运算都必须是足够基本的。就是说，它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。算法和程序不同，程序可以不满足上述的特性(4)。例如，一个操作系统在用户未使用前一直处于“等待”的循环中，直到出现新的用户事件为止。这样的系统可以无休止地运行，直到系统停工。此外，算法是面向功能的，通常用面向过程的方式描述；程序可以用面向对象方式搭建
12、它的框架。1-7 设n为正整数, 分析下列各程序段中加下划线的语句的程序步数。 (1) for (int i = 1; i = n; i+) (2) x = 0; y = 0; for (int j = 1; j = n; j+) for (int i = 1; i = n; i+) cij = 0.0; for (int j = 1; j = i; j+) for (int k = 1; k = n; k+) for (int k = 1; k = j; k+) cij = cij + aik * bkj; x = x + y; (3) int i = 1, j = 1; (4) int i =1; while (i=n & j=n) do i = i + 1; j = j + i; for (int j = 1; j = n; j+) i = i + j; while ( i arraySize或者对于某一个
