利用指针输入若干个数放入一维数组，用0结束输入，求正数，负数的个数以及正数的平均数？

点击联系发帖人 时间：2022-06-05 08:57
一维数组指针定义

Java核心技术第十版源码：

  • Java中int永远是32位的，C++的int可能是16位、32位，也可能是编译器提供商指定的其他大小，唯一的限制是不能小于short int，不能大于long int

  • Java中所有函数都属于某个类的方法（标准术语称其为方法，而不是成员函数

  • 静态成员函数（static member function），这些函数定义在类的内部，并且不对对象进行操作，Java中的main方法必须是静态的

  • Java的main方法没有为操作系统返回『退出代码』，若想返回非0值，则要调用pareTo("Hello") == 0)，但Java还是equals方法更加清晰一点

  • 空串""是长度为0的字符串。可以调用以下代码检查一个字符串是否为空：if (str.length() == 0)或if (str.equals(""))，空串是一个Java对象，有自己的串长度（0）和内容（空）

  • 不过，String变量还可以存放一个特殊的值，名为null，这表示目前没有任何对象与该变量关联，要检查一个字符串是否为null，要使用以下条件：if (str == null)

  • 有时要检查一个字符串既不是null也不为空串，这种情况下就一定要两者结合使用，if (str != null && str.length() != 0)，判断顺序很重要，如果在一个null值上调用方法，将会出现错误

  • Java字符串由char值序列组成。从3.3.3节“char类型”已经看到，char数据类型是一个采用UTF-16编码表示Unicode码点的代码单元。大多数的常用Unicode字符使用一个代码单元就可以表示，而辅助字符需要一对代码单元表示。

  • String的length方法将返回采用UTF-16编码表示的给定字符串所需要的代码单元数量

如果某个方法是在这个版本之后添加的，就会给出一个单独的版本号。

  • 返回给定位置的代码单元。除非对底层的代码单元感兴趣，否则不需要调用这个方法。

  • 返回从给定位置开始的码点。

  • 返回从startIndex代码点开始，位移cpCount后的码点索引。

  • 按照字典顺序，如果字符串位于other之前，返回一个负数；如果字符串位于other之后，返回一个正数；如果两个字符串相等，返回0。

  • 将这个字符串的码点作为一个流返回。调用toArray将它们放在一个数组中。

  • 用数组中从offset开始的count个码点构造一个字符串。

  • 如果字符串与other相等，返回true。

  • 如果字符串与other相等(忽略大小写)，返回true。

  • 如果字符串以suffix开头或结尾，则返回true。

  • 返回与字符串str或代码点cp匹配的第一个子串的开始位置。这个位置从索引0或fromIndex开始计算。如果在原始串中不存在str，返回-1。

  • 返回与字符串str或代码点cp匹配的最后一个子串的开始位置。这个位置从原始串尾端或fromIndex开始计算。

  • 返回startIndex和endIndex-1之间的代码点数量。没有配成对的代用字符将计入代码点。

  • 返回一个新字符串。这个字符串包含原始字符串中从beginIndex到串尾或或endIndex–1的所有代码单元。

  • 返回一个新字符串。这个字符串将原始字符串中的大写字母改为小写，或者将原始字符串中的所有小写字母改成了大写字母。

  • 返回一个新字符串。这个字符串将删除了原始字符串头部和尾部的空格。

  • 返回一个新字符串，用给定的定界符连接所有元素。

  • 每次连接字符串，都会构建一个新的String对象，既耗时，又浪费空间。使用StringBuilder类就可以避免这个问题的发生。

  • 在JDK5.0中引入StringBuilder类。这个类的前身是StringBuffer，其效率稍有些低，但允许采用多线程的方式执行添加或删除字符的操作。如果所有字符串在一个单线程中编辑（通常都是这样），则应该用StringBuilder替代它。这两个类的API是相同的。java.lang.StringBuilder 5.0

  • 构造一个空的字符串构建器。

  • 返回构建器或缓冲器中的代码单元数量。

  • 追加一个字符串并返回this。

  • 追加一个代码单元并返回this。

  • 追加一个代码点，并将其转换为一个或两个代码单元并返回this。

  • 将第i个代码单元设置为c。

  • 在offset位置插入一个字符串并返回this。

  • 在offset位置插入一个代码单元并返回this。

  • 返回一个与构建器或缓冲器内容相同的字符串。

Scanner类定义在java.util包中。当使用的类不是定义在基本java.lang包中时，一定要使用import指示字将相应的包加载进来

因为输入是可见的，所以Scanner类不适用于从控制台读取密码。Java SE 6特别引入了Console类实现这个目的

  • 用给定的输入流创建一个Scanner对象。

  • 读取输入的下一行内容。

  • 读取输入的下一个单词（以空格作为分隔符）。

  • 读取并转换下一个表示整数或浮点数的字符序列。

  • 检测输入中是否还有其他单词。

  • 检测是否还有表示整数或浮点数的下一个字符序列。

  • 如果文件名中包含反斜杠符号，就要记住在每个反斜杠之前再加一个额外的反斜杠：“c：\mydirectory\myfile.txt”。

  • Java的控制流程结构与C和C++的控制流程结构一样，只有很少的例外情况。没有goto语句，但break语句可以带标签，可以利用它实现从内层循环跳出的目的（这种情况C语言采用goto语句实现）

  • 块（即复合语句）是指由一对大括号括起来的若干条简单的Java语句。块确定了变量的作用域。一个块可以嵌套在另一个块中

  • 但是，不能在嵌套的两个块中声明同名的变量，否则会无法通过编译。在C++中，可以在嵌套的块中重定义一个变量。在内层定义的变量会覆盖在外层定义的变量。这样，有可能会导致程序设计错误，因此在Java中不允许这样做。

  • 在处理多个选项时，使用if/else结构显得有些笨拙。Java有一个与C/C++完全一样的switch语句。

    • 从Java SE 7开始，case标签还可以是字符串字面量

  • 尽管Java的设计者将goto作为保留字，但实际上并没有打算在语言中使用它。通常，使用goto语句被认为是一种拙劣的程序设计风格。

  • 与C++不同，Java还提供了一种带标签的break语句，用于跳出多重嵌套的循环语句。有时候，在嵌套很深的循环语句中会发生一些不可预料的事情。此时可能更加希望跳到嵌套的所有循环语句之外。通过添加一些额外的条件判断实现各层循环的检测很不方便。只能跳出语句块，而不能跳入语句块。

  • 如果基本的整数和浮点数精度不能够满足需求，那么可以使用java.math包中的两个很有用的类：BigInteger和BigDecimal。这两个类可以处理包含任意长度数字序列的数值。BigInteger类实现了任意精度的整数运算，BigDecimal实现了任意精度的浮点数运算。

  • 遗憾的是，不能使用人们熟悉的算术运算符（如：+和*）处理大数值。而需要使用大数值类中的add和multiply方法。

  • 与C++不同，Java没有提供运算符重载功能。程序员无法重定义+和*运算符，使其应用于BigInteger类的add和multiply运算。Java语言的设计者确实为字符串的连接重载了+运算符，但没有重载其他的运算符，也没有给Java程序员在自己的类中重载运算符的机会。

  • 返回这个大整数和另一个大整数other的和、差、积、商以及余数。

  • 如果这个大整数与另一个大整数other相等，返回0；如果这个大整数小于另一个大整数other，返回负数；否则，返回正数。

  • 返回值等于x的大整数。

  • 返回这个大实数与另一个大实数other的和、差、积、商。要想计算商，必须给出舍入方式（rounding mode）。RoundingMode.HALF_UP是在学校中学习的四舍五入方式（即，数值0到4舍去，数值5到9进位）。它适用于常规的计算。有关其他的舍入方式请参看API文档。

  • 如果这个大实数与另一个大实数相等，返回0；如果这个大实数小于另一个大实数，返回负数；否则，返回正数。

  • 数组是一种数据结构，用来存储同一类型值的集合。通过一个整型下标可以访问数组中的每一个值。例如，如果a是一个整型数组，a[i]就是数组中下标为i的整数。

  • 创建一个数字数组时，所有元素都初始化为0。boolean数组的元素会初始化为false。对象数组的元素则初始化为一个特殊值null，这表示这些元素（还）未存放任何对象。

  • 一旦创建了数组，就不能再改变它的大小（尽管可以改变每一个数组元素）。如果经常需要在运行过程中扩展数组的大小，就应该使用另一种数据结构——数组列表（array list）

  • 在Java中，允许数组长度为0。在编写一个结果为数组的方法时，如果碰巧结果为空，则这种语法形式就显得非常有用。注意，数组长度为0与null不同。此时可以创建一个长度为0的数组：

  • foreach循环定义一个变量用于暂存集合中的每一个元素，并执行相应的语句（当然，也可以是语句块）。collection这一集合表达式必须是一个数组或者是一个实现了Iterable接口的类对象（例如ArrayList）

  • for each循环语句显得更加简洁、更不易出错（不必为下标的起始值和终止值而操心）

  • 有个更加简单的方式打印数组中的所有值，即利用Arrays类的toString方法。调用Arrays.toString（a），返回一个包含数组元素的字符串，这些元素被放置在括号内，并用逗号分隔，例如，“[2，3，5，7，11，13]

  • 将一个数组变量拷贝给另一个数组变量。这时，两个变量将引用同一个数组：

  • 如果希望将所有值都拷贝到一个新的数组里面，则要使用Array类的copyOf方法，第二个参数是新数组的长度，如果长度更大，那么多余元素则赋值默认值，如果长度更小，则只拷贝前面的元素

  • 在Java应用程序的main方法中，程序名并没有存储在args数组中

  • 返回包含a中数据元素的字符串，这些数据元素被放在括号内，并用逗号分隔。

  • 返回与a类型相同的一个数组，其长度为length或者end-start，数组元素为a的值。

    start　起始下标（包含这个值）。

    end　终止下标（不包含这个值）。这个值可能大于a.length。在这种情况下，结果为0或false。

    length　拷贝的数据元素长度。如果length值大于a.length，结果为0或false；否则，数组中只有前面length个数据元素的拷贝值。

  • 采用优化的快速排序算法对数组进行排序。

  • 采用二分搜索算法查找值v。如果查找成功，则返回相应的下标值；否则，返回一个负数值r。-r-1是为保持a有序v应插入的位置。

    start　起始下标（包含这个值）。

    end　终止下标（不包含这个值）。

    v　同a的数据元素类型相同的值。

  • 将数组的所有数据元素值设置为v。

  • 如果两个数组大小相同，并且下标相同的元素都对应相等，返回true。

  • for each循环语句不能自动处理二维数组的每一个元素。它是按照行，也就是一维数组处理的。要想访问二维数组a的所有元素，需要使用两个嵌套的循环，

  • 要想快速地打印一个二维数组的数据元素列表，可以调用

  • 实际上Java没有多维数组的概念，只有一维数组，多维数组可以理解为数组的数组

  • Java的二维数组相当于C++的：

在Java中，只有基本类型（primitive types）不是对象，例如，数值、字符和布尔类型的值都不是对象。
所有的数组类型，不管是对象数组还是基本类型的数组都扩展了Object类。

  • 对象变量定义后，但没有引用具体的对象，所以调用该对象变量的方法将会编译报错，这时可以new一个对象初始化这个变量，也可以引用一个已存在的对象（变量），这时两个变量引用一个对象

  • 一定要认识到：一个对象变量并没有实际包含一个对象，而仅仅引用一个对象。

  • 在Java中，任何对象变量的值都是对存储在另外一个地方的一个对象的引用。new操作符的返回值也是一个引用

  • 可以显式地将对象变量设置为null，表明这个对象变量目前没有引用任何对象。

  • 如果将一个方法应用于一个值为null的对象上，那么就会产生运行时错误。局部变量不会自动地初始化为null，而必须通过调用new或将它们设置为null进行初始化

  • Java中的对象引用其实相当于C++的对象指针，C++没有空引用。在Java中的null引用对应C++中的NULL指针。

  • 所有的Java对象都存储在堆中。当一个对象包含另一个对象变量时，这个变量依然包含着指向另一个堆对象的指针。

  • 在C++中，指针十分令人头疼，并常常导致程序错误。稍不小心就会创建一个错误的指针，或者造成内存溢出。在Java语言中，这些问题都不复存在。如果使用一个没有初始化的指针，运行系统将会产生一个运行时错误，而不是生成一个随机的结果。同时，不必担心内存管理问题，垃圾收集器将会处理相关的事宜。

  • 在Java中，必须使用clone方法获得对象的完整拷贝。

更改器方法与访问器方法

  • 访问对象且有可能修改对象的方法叫更改器方（mutator method），只访问对象而不修改对象的方法有时称为访问器方法（accessor method）。

  • 在C++中，带有const后缀的方法是访问器方法；默认为更改器方法。但是，在Java语言中，访问器方法与更改器方法在语法上没有明显的区别。

  • 构造器与类同名。在构造Employee类的对象时，构造器会运行，以便将实例域初始化为所希望的状态。

  • 构造器与其他的方法有一个重要的不同。构造器总是伴随着new操作符的执行被调用，而不能对一个已经存在的对象调用构造器来达到重新设置实例域的目的

  • Java构造器的工作方式与C++一样。但是，要记住所有的Java对象都是在堆中构造的，构造器总是伴随着new操作符一起使用。C++程序员最易犯的错误就是忘记new操作符：

  • 警告：请注意，不要在构造器中定义与实例域重名的局部变量。

  • 隐式（implicit）参数，是出现在方法名前的Employee类对象。显式参数是明显地列在方法声明中的参数。

  • 在每一个方法中，关键字this表示隐式参数

  • 在C++中，通常在类的外面定义方法，如果在类的内部定义方法，这个方法将自动地成为内联（inline）方法。

  • 在Java中，所有的方法都必须在类的内部定义，但并不表示它们是内联方法。是否将某个方法设置为内联方法是Java虚拟机的任务。即时编译器会监视调用那些简洁、经常被调用、没有被重载以及可优化的方法。

  • C++也有同样的原则。方法可以访问所属类的私有特性（feature），而不仅限于访问隐式参数的私有特性。

  • 可以将实例域定义为final。构建对象时必须初始化这样的域。也就是说，必须确保在每一个构造器执行之后，这个域的值被设置，并且在后面的操作中，不能够再对它进行修改。

  • final修饰符大都应用于基本（primitive）类型域，或不可变（immutable）类的域（如果类中的每个方法都不会改变其对象，这种类就是不可变的类。例如，String类就是一个不可变的类）。

  • 但是final关键字对于可变的类可能会引起歧义：

  • 如果将域定义为static，1000个类的对象，也只有这一个static域，因为它是属于类的，而不属于任何独立的对象。举例，下面的nextId维护了Employee类的static域，所有对象都可以访问，且唯一，所以用来做全局唯一的ID值，是非常合适的

  • 静态方法是一种不能向对象实施操作的方法。例如，Math类的pow方法就是一个静态方法。Math.pow(x,a)，不使用任何Math对象，换句话说，没有隐式参数

  • 静态方法不能访问非静态域，但可以访问自身类中的静态域，可以通过类名调用静态方法，

  • 两种情况使用静态方法比较好

    • 一个方法不需要访问对象状态，其所需参数都是通过显式参数提供（例如：Math.pow）。

    • 一个方法只需要访问类的静态域（例如：Employee.getNextId）。

  • Java中的静态域与静态方法在功能上与C++相同。但是，语法书写上却稍有所不同。在C++中，使用：：操作符访问自身作用域之外的静态域和静态方法，如Math::PI

  • 术语“static”有一段不寻常的历史。起初，C引入关键字static是为了表示退出一个块后依然存在的局部变量。在这种情况下，术语“static”是有意义的：变量一直存在，当再次进入该块时仍然存在。随后，static在C中有了第二种含义，表示不能被其他文件访问的全局变量和函数。为了避免引入一个新的关键字，关键字static被重用了。最后，C++第三次重用了这个关键字，与前面赋予的含义完全不一样，这里将其解释为：属于类且不属于类对象的变量和函数。这个含义与Java相同。

  • 静态方法还有另外一种常见的用途。类似LocalDate和NumberFormat的类使用静态工厂方法（factory method）来构造对象。

  • main方法不对任何对象进行操作。事实上，在启动程序时还没有任何一个对象。静态的main方法将执行并创建程序所需要的对象。

  • 提示：每一个类可以有一个main方法。这是一个常用于对类进行单元测试的技巧。

  • Java程序设计语言总是采用按值调用(call by value)。也就是说，方法得到的是所有参数值的一个拷贝，特别是，方法不能修改传递给它的任何参数变量的内容。

  • 方法参数共有两种类型：

    • 基本数据类型（数字、布尔值）。所以一个方法不能修改数值型或布尔型的参数

    • 对象引用。一个方法得到的是对象引用的拷贝，对象引用及其他的拷贝同时引用同一个对象。

    • 读者已经看到，一个方法不可能修改一个基本数据类型的参数。而对象引用作为参数就不同了，比如

      1）x被初始化为harry值的拷贝，这里是一个对象的引用。

      3）方法结束后，参数变量x不再使用。当然，对象变量harry继续引用那个薪金增至3倍的雇员对象

    • 所以，一个方法可以改变一个对象参数的状态，一个方法不能让对象参数引用一个新的对象。

  • Java允许重载任何方法，而不只是构造器方法。因此，要完整地描述一个方法，需要指出方法名以及参数类型。这叫做方法的签名（signature）。注意返回类型不是签名的一部分

  • 如果在构造器中没有显式地给域赋予初值，那么就会被自动地赋为默认值：数值为0、布尔值为false、对象引用为null。然而，只有缺少程序设计经验的人才会这样做。确实，如果不明确地对域进行初始化，就会影响程序代码的可读性。

  • 这是域与局部变量的主要不同点。必须明确地初始化方法中的局部变量。但是，如果没有初始化类中的域，将会被自动初始化为默认值（0、false或null）。

  • 很多类都包含一个无参数的构造函数，对象由无参数构造函数创建时，其状态会设置为适当的默认值

  • 如果在编写一个类时没有编写构造器，那么系统就会提供一个无参数构造器。这个构造器将所有的实例域设置为默认值。

  • 如果类中提供了至少一个构造器，但是没有提供无参数的构造器，则在构造对象时如果没有提供参数就会被视为不合法。

  • 如果确实想调用无参构造器，那么程序员就得显示提供一个默认的无参构造器，

  • Java中的域初始值不一定是常量值，也可以是调用常量来初始化，这是和C++很大的区别

  • C++注释：在C++中，不能直接初始化类的实例域。所有的域必须在构造器中设置。但是，有一个特殊的初始化器列表语法，如下所示：

  • 参数变量用同样的名字将实例域屏蔽起来，但可以加上this访问实例域

  • C++注释：在C++中，经常用下划线或某个固定的字母（一般选用m或x）作为实例域的前缀。Java程序员一般不这么做

构造器调用另一个构造器

  • Java可以在构造器内部使用this调用另一个构造器

  • 采用这种方式使用this关键字非常有用，这样对公共的构造器代码部分只编写一次即可。

  • C++注释：在Java中，this引用等价于C++的this指针。但是，在C++中，一个构造器不能调用另一个构造器。在C++中，必须将抽取出的公共初始化代码编写成一个独立的方法。

  • 由于Java有自动的垃圾回收器，不需要人工回收内存，所以Java不支持析构器。

  • 可以为任何一个类添加finalize方法。finalize方法将在垃圾回收器清除对象之前调用。在实际应用中，不要依赖于使用finalize方法回收任何短缺的资源，这是因为很难知道这个方法什么时候才能够调用。

  • 使用包的主要原因是确保类名的唯一性。假如两个程序员不约而同地建立了Employee类。只要将这些类放置在不同的包中，就不会产生冲突。

  • 从编译器的角度来看，嵌套的包之间没有任何关系。例如，java.util包与java.util.jar包毫无关系。每一个都拥有独立的类集合。

  • 但是，需要注意的是，只能使用星号（*）导入一个包，而不能使用import java.*或import java.*.*导入以java为前缀的所有包。

  • C++注释：C++程序员经常将import与#include弄混。实际上，这两者之间并没有共同之处。在C++中，必须使用#include将外部特性的声明加载进来，这是因为C++编译器无法查看任何文件的内部，除了正在编译的文件以及在头文件中明确包含的文件。Java编译器可以查看其他文件的内部，只要告诉它到哪里去查看就可以了。

  • import语句不仅可以导入类，还增加了导入静态方法和静态域的功能。

  • 要想将一个类放入包中，就必须将包的名字放在源文件的开头，包中定义类的代码之前。

  • 如果没有在源文件中放置package语句，这个源文件中的类就被放置在一个默认包（defaulf package）中。默认包是一个没有名字的包。

  • 标记为public的部分可以被任意的类使用；标记为private的部分只能被定义它们的类使用。如果没有指定public或private，这个部分（类、方法或变量）可以被同一个包中的所有方法访问。

  1. 不要在类中使用过多的基本类型

  2. 不是所有的域都需要独立的域访问器和域更改器

  3. 将职责过多的类进行分解

  4. 类名和方法名要能够体现它们的职责
    命名类名的良好习惯是采用一个名词（Order）、前面有形容词修饰的名词（RushOrder）或动名词（有“-ing”后缀）修饰名词（例如，BillingAddress）。对于方法来说，习惯是访问器方法用小写get开头（getSalary），更改器方法用小写的set开头（setSalary）。

  • 继承已存在的类就是复用（继承）这些类的方法和域。在此基础上，还可以添加一些新的方法和域，以满足新的需求。

  • 反射（reflection）是指在程序运行期间发现更多的类及其属性的能力

  • "is-a”关系是继承的一个明显特征

  • C++注释：Java与C++定义继承类的方式十分相似。Java用关键字extends代替了C++中的冒号（:）。在Java中，所有的继承都是公有继承，而没有C++中的私有继承和保护继承。

  • class）。超类和子类是Java程序员最常用的两个术语，而了解其他语言的程序员可能更加偏爱使用父类和孩子类，这些都是继承时使用的术语。

  • 前缀“超”和“子”来源于计算机科学和数学理论中的集合语言的术语。所有雇员组成的集合包含所有经理组成的集合。可以这样说，雇员集合是经理集合的超集，也可以说，经理集合是雇员集合的子集。

  • 在通过扩展超类定义子类的时候，仅需要指出子类与超类的不同之处。因此在设计类的时候，应该将通用的方法放在超类中，而将具有特殊用途的方法放在子类中，这种将通用的功能放到超类的做法，在面向对象程序设计中十分普遍。

  • 子类可以定义同名方法来覆盖超类的方法

  • super关键字指示编译器调用超类方法，注释：有些人认为super与this引用是类似的概念，实际上，这样比较并不太恰当。这是因为super不是一个对象的引用，不能将super赋给另一个对象变量，它只是一个指示编译器调用超类方法的特殊关键字。

  • 正像前面所看到的那样，在子类中可以增加域、增加方法或覆盖超类的方法，然而绝对不能删除继承的任何域和方法。

  • 由于Manager类的构造器不能访问Employee类的私有域，所以必须利用Employee类的构造器对这部分私有域进行初始化，我们可以通过super实现对超类构造器的调用。使用super调用构造器的语句必须是子类构造器的第一条语句。

  • 如果子类的构造器没有显式地调用超类的构造器，则将自动地调用超类默认（没有参数）的构造器。如果超类没有不带参数的构造器，并且在子类的构造器中又没有显式地调用超类的其他构造器，则Java编译器将报告错误。

  • 回忆一下，关键字this有两个用途：一是引用隐式参数，二是调用该类其他的构造器。同样，super关键字也有两个用途：一是调用超类的方法，二是调用超类的构造器。在调用构造器的时候，这两个关键字的使用方式很相似。调用构造器的语句只能作为另一个构造器的第一条语句出现。构造参数既可以传递给本类（this）的其他构造器，也可以传递给超类（super）的构造器。

  • C++注释：在C++的构造函数中，使用初始化列表语法调用超类的构造函数，而不调用super。在C++中，Manager的构造函数如下所示：

  • is-a”规则的另一种表述法是置换法则。它表明程序中出现超类对象的任何地方都可以用子类对象置换。

  • 在Java程序设计语言中，对象变量是多态的。一个Employee变量既可以引用一个Employee类对象，也可以引用一个Employee类的任何一个子类的对象（例如，Manager、Executive、Secretary等）

理解方法调用（重要!）

  • 弄清楚如何在对象上应用方法调用非常重要。下面假设要调用x.f（args），隐式参数x声明为类C的一个对象。下面是调用过程的详细描述：

    • 编译器查看对象的声明类型和方法名。假设调用x.f（param），且隐式参数x声明为C类的对象。需要注意的是：有可能存在多个名字为f，但参数类型不一样的方法。例如，可能存在方法f（int）和方法f（String）。编译器将会一一列举所有C类中名为f的方法和其超类中访问属性为public且名为f的方法（超类的私有方法不可访问）。至此，编译器已获得所有可能被调用的候选方法。

    • 接下来，编译器将查看调用方法时提供的参数类型。如果在所有名为f的方法中存在一个与提供的参数类型完全匹配，就选择这个方法。这个过程被称为重载解析（overloading resolution）。例如，对于调用x.f（“Hello”）来说，编译器将会挑选f（String），而不是f（int）。由于允许类型转换（int可以转换成double，Manager可以转换成Employee，等等），所以这个过程可能很复杂。如果编译器没有找到与参数类型匹配的方法，或者发现经过类型转换后有多个方法与之匹配，就会报告一个错误。至此，编译器已获得需要调用的方法名字和参数类型。

      • 因为方法返回类型不影响方法签名，所以允许子类将覆盖方法定义为原返回类型的子类型

    • 如果是private方法、static方法、final方法（有关final修饰符的含义将在下一节讲述）或者构造器，那么编译器将可以准确地知道应该调用哪个方法，我们将这种调用方式称为静态绑定（static binding）。与此对应的是，调用的方法依赖于隐式参数的实际类型，并且在运行时实现动态绑定。在我们列举的示例中，编译器采用动态绑定的方式生成一条调用f（String）的指令。

    • 当程序运行，并且采用动态绑定调用方法时，虚拟机一定调用与x所引用对象的实际类型最合适的那个类的方法。假设x的实际类型是D，它是C类的子类。如果D类定义了方法f（String），就直接调用它；否则，将在D类的超类中寻找f（String），以此类推。

      • 每次调用方法都要进行搜索，时间开销相当大。因此，虚拟机预先为每个类创建了一个方法表（method table），其中列出了所有方法的签名和实际调用的方法。这样一来，在真正调用方法的时候，虚拟机仅查找这个表就行了。在前面的例子中，虚拟机搜索D类的方法表，以便寻找与调用f（Sting）相匹配的方法。这个方法既有可能是D.f（String），也有可能是X.f（String），这里的X是D的超类。这里需要提醒一点，如果调用super.f（param），编译器将对隐式参数超类的方法表进行搜索。

  • 在运行时，调用e.getSalary（）的解析过程为：

    • 首先，虚拟机提取e的实际类型的方法表。既可能是Employee、Manager的方法表，也可能是Employee类的其他子类的方法表。

    • 接下来，虚拟机搜索定义getSalary签名的类。此时，虚拟机已经知道应该调用哪个方法。

    • 最后，虚拟机调用方法。

  • 动态绑定有一个非常重要的特性：无需对现存的代码进行修改，就可以对程序进行扩展。假设增加一个新类Executive，并且变量e有可能引用这个类的对象，我们不需要对包含调用e.getSalary（）的代码进行重新编译。如果e恰好引用一个Executive类的对象，就会自动地调用Executive.getSalary（）方法。

  • 警告：在覆盖一个方法的时候，子类方法不能低于超类方法的可见性。特别是，如果超类方法是public，子类方法一定要声明为public。经常会发生这类错误：在声明子类方法的时候，遗漏了public修饰符。此时，编译器将会把它解释为试图提供更严格的访问权限。

阻止继承：final类和方法

  • 有时候，可能希望阻止人们利用某个类定义子类。不允许扩展的类被称为final类。如果在定义类的时候使用了final修饰符就表明这个类是final类。例如，假设希望阻止人们定义Executive类的子类，就可以在定义这个类的时候，使用final修饰符声明。声明格式如下所示：

  • 类中的特定方法也可以被声明为final。如果这样做，子类就不能覆盖这个方法（final类中的所有方法自动地成为final方法）

  • 前面曾经说过，域也可以被声明为final。对于final域来说，构造对象之后就不允许改变它们的值了。不过，如果将一个类声明为final，只有其中的方法自动地成为final，而不包括域。

  • 将方法或类声明为final主要目的是：确保它们不会在子类中改变语义。

  • C++注释：C++默认所有方法都不具有多态性，而Java反过来，作者提倡在两者之间寻找一个平衡

  • 正像有时候需要将浮点型数值转换成整型数值一样，有时候也可能需要将某个类的对象引用转换成另外一个类的对象引用。对象引用的转换语法与数值表达式的类型转换类似，仅需要用一对圆括号将目标类名括起来，并放置在需要转换的对象引用之前就可以了。

  • 进行类型转换的唯一原因是：在暂时忽视对象的实际类型之后，使用对象的全部功能。

  • 将一个值存入变量时，编译器将检查是否允许该操作。将一个子类的引用赋给一个超类变量，编译器是允许的。但将一个超类的引用赋给一个子类变量，必须进行类型转换，这样才能够通过运行时的检查。

  • 在将超类转换成子类之前，应该使用instanceof进行检查。如果变量是null，用instanceof检查也不会产生异常

  • Java的强制类型转换转换很像像C++的dynamic_cast操作，它们之间只有一点重要的区别：当类型转换失败时，Java不会生成一个null对象，而是抛出一个异常。从这个意义上讲，有点像C++中的引用（reference）转换。真是令人生厌。在C++中，可以在一个操作中完成类型测试和类型转换。

    在Java中，需要将instanceof运算符和类型转换组合起来使用：

  • 为了提高程序的清晰度，人们只将抽象类作为派生其他类的基类，而不作为想使用的特定的实例类。包含一个或多个抽象方法的类本身必须被声明为抽象的。但注意抽象类内部是可以有具体数据和具体方法的

  • 类即使不含抽象方法，也可以将类声明为抽象类。

  • 抽象类不能被实例化。也就是说，如果将一个类声明为abstract，就不能创建这个类的对象。需要注意，可以定义一个抽象类的对象变量，但是它只能引用非抽象子类的对象

  • 在C++中，有一种在尾部用=0标记的抽象方法，称为纯虚函数。只要有一个纯虚函数，这个类就是抽象类。在C++中，没有提供用于表示抽象类的特殊关键字。

  • 大家都知道，最好将类中的域标记为private，而方法标记为public。任何声明为private的内容对其他类都是不可见的。前面已经看到，这对于子类来说也完全适用，即子类也不能访问超类的私有域。

  • 然而，在有些时候，人们希望超类中的某些方法允许被子类访问，或允许子类的方法访问超类的某个域。为此，需要将这些方法或域声明为protected。

  • C++注释：事实上，Java中的受保护部分对所有子类及同一个包中的所有其他类都可见。这与C++中的保护机制稍有不同，Java中的protected概念要比C++中的安全性差。

  • Java用于控制可见性的4个访问修饰符：

    • 仅对本类可见——private。

    • 对所有类可见——public。

    • 对本包和所有子类可见——protected。

    • 对本包可见——默认（很遗憾），不需要修饰符。

  • Object类是Java中所有类的始祖，在Java中每个类都是由它扩展而来的。如果一个类没有明确指出超类，Object类就是这个类的超类

  • C++注释：在C++中没有所有类的根类，不过，每个指针都可以转换成void*指针。

  • 在子类中定义equals方法时，首先调用超类的equals。如果检测失败，对象就不可能相等。如果超类中的域都相等，就需要比较子类中的实例域。

  • 一个比较好的equals方法

  • 有些程序员喜欢在equals方法中调用instanceof方法，但是这有一些麻烦，比如Java语言规范要求equals方法具有以下特性

    • 自反性：对于任何非空引用x，x.equals（x）应该返回true。

    • 对称性：对于任何引用x和y，当且仅当y.equals（x）返回true，x.equals（y）也应该返回true。

    • 一致性：如果x和y引用的对象没有发生变化，反复调用x.equals（y）应该返回同样的结果。

    • 显式参数命名为otherObject，稍后需要将它转换成另一个叫做other的变量。

    • 这条语句只是一个优化。实际上，这是一种经常采用的形式。因为计算这个等式要比一个一个地比较类中的域所付出的代价小得多。

    • 比较this与otherObject是否属于同一个类。如果equals的语义在每个子类中有所改变，就使用getClass检测：

      • 所有的子类都拥有统一的语义，就使用instanceof检测：

    • 将otherObject转换为相应的类类型变量：

    • 现在开始对所有需要比较的域进行比较了。使用==比较基本类型域，使用equals比较对象域。如果所有的域都匹配，就返回true；否则返回false。

  • 如果确定一个方法是覆盖方法，可以添加@Override告知编译器这个 方法要对超类的某个方法进行覆盖，如果没有找到对应的超类方法，则编译器报错

  • 由于hashCode方法定义在Object类中，因此每个对象都有一个默认的散列码，其值为对象的存储地址。

  • hashCode方法应该返回一个整型数值（也可以是负数），并合理地组合实例域的散列码，以便能够让各个不同的对象产生的散列码更加均匀。

  • 如果存在数组类型的域，那么可以使用静态的Arrays.hashCode方法计算一个散列码，这个散列码由数组元素的散列码组成。

  • // 还可以用hash()方法直接组合，hash()方法会对各参数分别调用Object.hashCode()方法，并组合这些散列值

  • 在Object中还有一个重要的方法，就是toString方法，它用于返回表示对象值的字符串。

  • 绝大多数（但不是全部）的toString方法都遵循这样的格式：类的名字，随后是一对方括号括起来的域值。

  • 只要对象与一个字符串通过操作符“+”连接起来，Java编译就会自动地调用toString方法，以便获得这个对象的字符串描述

  • 在调用x.toString（）的地方可以用""+x替代。这条语句将一个空串与x的字符串表示相连接。这里的x就是x.toString（）。与toString不同的是，如果x是基本类型，这条语句照样能够执行。

  • 提示：强烈建议为自定义的每一个类增加toString方法。这样做不仅自己受益，而且所有使用这个类的程序员也会从这个日志记录支持中受益匪浅

  • 数组列表管理着对象引用的一个内部数组。最终，数组的全部空间有可能被用尽。这就显现出数组列表的操作魅力：如果调用add且内部数组已经满了，数组列表就将自动地创建一个更大的数组，并将所有的对象从较小的数组中拷贝到较大的数组中。

  • 如果已经清楚或能够估计出数组可能存储的元素数量，就可以在填充数组之前调用ensureCapacity方法：

    这个方法调用将分配一个包含100个对象的内部数组。然后调用100次add，而不用重新分配空间。（有点像C++的vector的reserve方法）

  • 一旦能够确认数组列表的大小不再发生变化，就可以调用trimToSize方法。这个方法将存储区域的大小调整为当前元素数量所需要的存储空间数目。垃圾回收器将回收多余的存储空间。
    一旦整理了数组列表的大小，添加新元素就需要花时间再次移动存储块，所以应该在确认不会添加任何元素时，再调用trimToSize。（有点像C++的vector的shrink_to_fit方法

  • C++注释：ArrayList类似于C++的vector模板。ArrayList与vector都是泛型类型。但是C++的vector模板为了便于访问元素重载了[]运算符。由于Java没有运算符重载，所以必须调用显式的方法。此外，C++向量是值拷贝。如果a和b是两个向量，赋值操作a=b将会构造一个与b长度相同的新向量a，并将所有的元素由b拷贝到a，而在Java中，这条赋值语句的操作结果是让a和b引用同一个数组列表。

    • 用指定容量构造一个空数组列表。

    • 在数组列表的尾端添加一个元素。永远返回true。
      参数：obj　添加的元素

    • 返回存储在数组列表中的当前元素数量。（这个值将小于或等于数组列表的容量。）

    • 确保数组列表在不重新分配存储空间的情况下就能够保存给定数量的元素。
      参数：capacity　需要的存储容量

    • 将数组列表的存储容量削减到当前尺寸。

设置数组列表指定位置的元素值，这个操作将覆盖这个位置的原有内容。 参数：index　位置（必须介于0~size（）-1之间） 获得指定位置的元素值。 参数：index　获得的元素位置（必须介于0~size（）-1之间） 向后移动元素，以便插入元素。 参数：index　插入位置（必须介于0~size（）-1之间） 删除一个元素，并将后面的元素向前移动。被删除的元素由返回值返回。 参数：index　被删除的元素位置（必须介于0~size（）-1之间）

  • 有时，需要将int这样的基本类型转换为对象。所有的基本类型都有一个与之对应的类。例如，Integer类对应基本类型int。通常，这些类称为包装器（wrapper）。这些对象包装器类拥有很明显的名字：Integer、Long、Float、Double、Short、Byte、Character、Void和Boolean（前6个类派生于公共的超类Number）。对象包装器类是不可变的，即一旦构造了包装器，就不允许更改包装在其中的值。同时，对象包装器类还是final，因此不能定义它们的子类。

  • 假设想定义一个整型数组列表。而尖括号中的类型参数不允许是基本类型，也就是说，不允许写成ArrayList<int>。这里就用到了Integer对象包装器类。我们可以声明一个Integer对象的数组列表。由于每个值分别包装在对象中，所以ArrayList<Integer>的效率远远低于int[]数组。

    n++; //算数表达式也可以自动装箱

  • 包装器的==是检测对象是否指向同个区域，所以大概率是不相等的

  • 首先，由于包装器类引用可以为null，所以自动装箱有可能会抛出一个NullPointerException异常

  • 另外，如果在一个条件表达式中混合使用Integer和Double类型，Integer值就会拆箱，提升为double，再装箱为Double

  • 要想将字符串转换成整形，可以使用Integer类的静态方法

  • 比如printf方法，这里的省略号...是Java代码的一部分，它表明这个方法可以接收任意数量的对象（除fmt参数之外

  • main方法甚至可以改成

  • 这个声明定义的类型是一个类，它刚好有4个实例，在此尽量不要构造新对象。因此，在比较两个枚举类型的值时，永远不需要调用equals，而直接使用“==”就可以了。

  • 如果需要的话，可以在枚举类型中添加一些构造器、方法和域。当然，构造器只是在构造枚举常量的时候被调用。

  • 所有的枚举类型都是Enum类的子类。它们继承了这个类的许多方法。其中最有用的一个是toString，这个方法能够返回枚举常量名。例如，Size.SMALL.toString（）将返回字符串“SMALL”。

  • 反射库（reflection library）提供了一个非常丰富且精心设计的工具集，以便编写能够动态操纵Java代码的程序。这项功能被大量地应用于JavaBeans中，它是Java组件的体系结构（有关JavaBeans的详细内容在卷Ⅱ中阐述）。特别是在设计或运行中添加新类时，能够快速地应用开发工具动态地查询新添加类的能力。

  • 能够分析类能力的程序称为反射（reflective）。反射机制的功能极其强大，在下面可以看到，反射机制可以用来：

    • 在运行时分析类的能力。

    • 在运行时查看对象，例如，编写一个toString方法供所有类使用。

    • 实现通用的数组操作代码。

    • 利用Method对象，这个对象很像C++中的函数指针。

  • 在程序运行期间，Java运行时系统始终为所有的对象维护一个被称为运行时的类型标识。这个信息跟踪着每个对象所属的类。虚拟机利用运行时类型信息选择相应的方法执行。

  • 然而，可以通过专门的Java类访问这些信息。保存这些信息的类被称为Class，这个名字很容易让人混淆。Object类中的getClass()方法将会返回一个Class类型的实例。

  • 如同用一个Employee对象表示一个特定的雇员属性一样，一个Class对象将表示一个特定类的属性。最常用的Class方法是getName()。这个方法将返回类的名字。如果类在一个包里，包的名字也作为类名的一部分

  • 还有静态方法forName获得类名对应的Class对象

  • 获得Class类对象的第三种方法非常简单。如果T是任意的Java类型（或void关键字），T.class将代表匹配的类对象。例如：

    请注意，一个Class对象实际上表示的是一个类型，而这个类型未必一定是一种类。例如，int不是类，但int.class是一个Class类型的对象。

  • 虚拟机为每个类型管理一个Class对象。因此，可以利用==运算符实现两个类对象比较的操作。还有一个很有用的方法newInstance()，可以用来动态地创建一个类的实例。例如，e.getClass().newInstance();创建了一个与e具有相同类类型的实例。newInstance方法调用默认的构造器（没有参数的构造器）初始化新创建的对象。如果这个类没有默认的构造器，就会抛出一个异常。

  • 将forName与newInstance配合起来使用，可以根据存储在字符串中的类名创建一个对象。

  • C++注释：newInstance方法对应C++中虚拟构造器的习惯用法。然而，C++中的虚拟构造器不是一种语言特性，需要由专门的库支持。Class类与C++中的type_info类相似，getClass方法与C++中的typeid运算符等价。但Java中的Class比C++中的type_info的功能强。C++中的type_info只能以字符串的形式显示一个类型的名字，而不能创建那个类型的对象。

  • 当程序运行过程中发生错误时，就会“抛出异常”。抛出异常比终止程序要灵活得多，这是因为可以提供一个“捕获”异常的处理器（handler）对异常情况进行处理。

  • 如果没有提供处理器，程序就会终止，并在控制台上打印出一条信息，其中给出了异常的类型。可能在前面已经看到过一些异常报告，例如，偶然使用了null引用或者数组越界等。

  • 异常有两种类型：未检查异常和已检查异常。对于已检查异常，编译器将会检查是否提供了处理器。然而，有很多常见的异常，例如，访问null引用，都属于未检查异常。编译器不会查看是否为这些错误提供了处理器。毕竟，应该精心地编写代码来避免这些错误的发生，而不要将精力花在编写异常处理器上。

  • 如果类名不存在，则将跳过try块中的剩余代码，程序直接进入catch子句（这里，利用Throwable类的printStackTrace方法打印出栈的轨迹。Throwable是Exception类的超类）。如果try块中没有抛出任何异常，那么会跳过catch子句的处理器代码。

  • 对于已检查异常，只需要提供一个异常处理器。可以很容易地发现会抛出已检查异常的方法。如果调用了一个抛出已检查异常的方法，而又没有提供处理器，编译器就会给出错误报告。

  • 反射机制最重要的内容——检查类的结构

  • 在java.lang.reflect包中有三个类Field、Method和Constructor分别用于描述类的域、方法和构造器。这三个类都有一个叫做getName的方法，用来返回项目的名称。Field类有一个getType方法，用来返回描述域所属类型的Class对象。Method和Constructor类有能够报告参数类型的方法，Method类还有一个可以报告返回类型的方法。

在运行时使用反射分析对象

  • 如果知道想要查看的域名和类型，查看指定的域是一件很容易的事情。而利用反射机制可以查看在编译时还不清楚的对象域。

  • 查看对象域的关键方法是Field类中的get方法。如果f是一个Field类型的对象（例如，通过getDeclaredFields得到的对象），obj是某个包含f域的类的对象，f.get（obj）将返回一个对象，其值为obj域的当前值。

  • 实际上，这段代码存在一个问题。由于name是一个私有域，所以get方法将会抛出一个IllegalAccessException。只有利用get方法才能得到可访问域的值。除非拥有访问权限，否则Java安全机制只允许查看任意对象有哪些域，而不允许读取它们的值。

  • 反射机制的默认行为受限于Java的访问控制。然而，如果一个Java程序没有受到安全管理器的控制，就可以覆盖访问控制。为了达到这个目的，需要调用Field、Method或Constructor对象的setAccessible方法。setAccessible方法是AccessibleObject类中的一个方法，它是Field、Method和Constructor类的公共超类。这个特性是为调试、持久存储和相似机制提供的。

  • 刚才说明的是读域，有读就有写，用f.set(obj, value)可以修改域

  • 下面介绍一个可供任意类使用的通用toString方法。其中使用getDeclaredFileds获得所有的数据域，然后使用setAccessible将所有的域设置为可访问的。对于每个域，获得了名字和值。泛型toString方法需要解释几个复杂的问题。循环引用将有可能导致无限递归。因此，ObjectAnalyzer将记录已经被访问过的对象。另外，为了能够查看数组内部，需要采用一种不同的方式。有关这种方式的具体内容将在下一节中详细论述。

使用反射编写泛型数组代码

  • 当一个Employee[]数组临时转换为Object[]数组是可行的，但是再也无法转回原来的Employee[]数组，当编写一个通用的copyOf方法时，得按照以下步骤考虑：

    • 首先获得a数组的类对象。Array类的静态方法

    • 使用Class类（只能定义表示数组的类对象）的getComponentType方法确定数组对应的类型。

  • 在C和C++中，可以从函数指针执行任意函数。从表面上看，Java没有提供方法指针，即将一个方法的存储地址传给另外一个方法，以便第二个方法能够随后调用它。事实上，Java的设计者曾说过：方法指针是很危险的，并且常常会带来隐患。他们认为Java提供的接口（interface）（将在下一章讨论）是一种更好的解决方案。然而，反射机制允许你调用任意方法（相当于方法/函数指针）。

    • 第一个参数是隐式参数，其余的对象提供了显式参数

    • 对于静态方法，第一个参数可以被忽略，即可以将它设置为null。

    • 如果返回类型是基本类型，invoke方法会返回其包装器类型。例如，假设m2表示Employee类的getSalary方法，那么返回的对象实际上是一个Double，必须相应地完成类型转换。可以使用自动拆箱将它转换为一个double：double s = (Double) m2.invoke(harry);

  1. 将公共操作和域放在超类

    这就是为什么将姓名域放在Person类中，而没有将它放在Employee和Student类中的原因。

  2. 然而，protected机制并不能够带来更好的保护，其原因主要有两点。第一，子类集合是无限制的，任何一个人都能够由某个类派生一个子类，并编写代码以直接访问protected的实例域，从而破坏了封装性。第二，在Java程序设计语言中，在同一个包中的所有类都可以访问proteced域，而不管它是否为这个类的子类。

  3. 使用继承实现“is-a”关系

  1. 除非所有继承的方法都有意义，否则不要使用继承

  2. 在覆盖方法时，不要改变预期的行为

  3. 使用多态，而非类型信息

    使用多态方法或接口编写的代码比使用对多种类型进行检测的代码更加易于维护和扩展。像下面这种代码完全可以用继承与多态来解决

反射机制使得人们可以通过在运行时查看域和方法，让人们编写出更具有通用性的程序。这种功能对于编写系统程序来说极其实用，但是通常不适于编写应用程序。反射是很脆弱的，即编译器很难帮助人们发现程序中的错误，因此只有在运行时才发现错误并导致异常。

}

《2022年软考-程序员考前模拟强化练习题67（附答案详解）》由会员分享，可在线阅读，更多相关《2022年软考-程序员考前模拟强化练习题67（附答案详解）（27页珍藏版）》请在装配图网上搜索。

1、2022年软考-程序员考前模拟强化练习题（附答案详解）1. 案例题阅读下列说明和C+代码，填写代码中的空缺，将解答写入答题纸的对应栏内。【说明】球类比赛记分系统中，每场有两支球队（Team）进行比赛（Game），分别记录各自的得分。图6-1所示为记分系统的类图。【C+代码】【答案】（1） int goals或int goals= 0（2）this-name（3）goals+或+goals或等价表示（4）Team*（5）new Game(t1, t2)【解析】本题考查考生应用C+语言进行程序设计的能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，阅读并完成程序填空。本题

2、中涉及比赛和球队。根据说明进行设计，题目给出了类图（图6-1类图所示）。图中类Game和Team之间是聚合关系。Game类有两个public的函数：getResults() 和incrementGoal：分别表示获取比赛结果和某支球队进1球后增加比分；private属性就是参加比赛的两支球队。Team类中有3个public函数，分别为本球队进1球后增加得分、获得本队得分和获得球队名称；private的属性为球队名称和得分。球队名采用string类型，得分信息从上下文可知是goals，用int类型。在Team对象创建时，初始化球队名称和得分。C+11标准之后，对象的属性定义时才可显式初始化；对象

3、的属性name类型为string，需要在构造器中对球队名称加以显式初始化。其构造器接收球队名称，参数名称与对象的属性名均为name，用this关键字加以区分。其中this关键字用来引用当前对象或类实例，可以用-取属性或行为，即：this-name = name;this-goals =0;注：没有同名时是否有this-都表示名称所表示的对象属性。从函数getGoals()中的return goals判断，缺少属性goals来表示得分。再从上下文判断，函数increamentGoal()中，表示在比赛中某球队进1球，即goals的值增加1。创建Game对象表示两支球队的一场比赛。构造器参数为两支

Game对象的两个属性。函数getResults()用于输出当前比分。函数incrementGoal()用于表示一支球队进1球，具体是哪支球队由参数给定，所以参数类型为Team*。主控逻辑代码在程序主入口函数main()中实现。在main()函数中，先创建两支球队(用new关键字)，即两个Team类的对象指针，球队名称分别为“TA”和“TB”，指针名称分别为t1和t2，即:Team

6、(或c+11标准之后int goals=0也支持)；空（2）需要表示Team对象指针的name属性，即this-name；空（3）需要表示当前球队得分加1， 因为只有一条语句，只要表示goals加1即可，即goals+或+goals(等价表示)；空(4）需要表示参数类型为球队指针，即 Team*；空(5）处为创建Game类的对象football， 需要两个Team类型对象的指针，从其后面语句可知，两个指针名称为t1和t2，即new Game(t1, t2)。2. 单选题对n个关键码构成的序列采用简单选择排序法进行排序的过程是：第一趟经过n-1次关键码之间的比较，确定出最小关键码在序列中的位置后

7、，再将其与序列的第一个关键码进行交换，第二趟则在其余的n-1个关键码中进行n-2次比较，确定出最小关键码的位置后，再将其与序列的第二个关键码进行交换以此类推，直到序列的关键码从小到大有序排列。在简单选择排序过程中，关键码之间的总比较次数为（ ）。问题1选项A.n(n-1)/2B.n2/2C.n(n+1)/2D.nlogn【答案】A【解析】本题考查数据结构简单选择排序的基础知识。根据题目描述，简单选择排序第一趟经过n-1次关键码之间的比较，第二趟经过n-2次关键码之间的比较，第三趟经过n-3次关键码之间的比较最后第n-1趟经过1次关键码之间的比较，总的比较次数为n-1+n-2+.+1=n(n-1

8、)/2。3. 案例题阅读以下说明和C代码，填写程序中的空缺，将解答写入答题纸的对应栏内。【说明】规定整型数组a中的元素取值范围为0,N)，函数usrSort( int n, int a )对非负整型数组a的前n个元素进行计数排序。排序时，用temp_arri表示i在数组a中出现的次数， 因此可以从0开始按顺序统计每个非负整数在a中的出现次数，然后对这些非负整数按照从小到大的顺序，结合其出现次数依次排列。例如，对含有10个元素0,8,5,2,0,1,4,2,0,1的数组a排序时，先计算出有3个0、2 个1、2个2、1个4、1个5和1个8，然后可确定排序后a的内容为0,0,0,1,1,2,2,4,

cnt = temp_arri或cnt= *(temp_arr+i)或等效形式(5）k+或+k或k=k+1或k+=1或等效形式【解析】本题考查考生对C程序基本结构、函数定义及调用和运算逻辑的理解和应用。根据空（1）所在语句的注释，明确

12、是对函数usrSort进行调用。usrSort的原型声明为“void usrSort(int n, int a)，第一个参数表示需要排序的元素个数，第二个参数表示对哪个数组进行排序，题目中，需要对含有10个元素的数组进行排序，因此空(1)应填入“usrSort(10,a)” 或其等效形式。注意：第二个参数需要传入的数组（数组首地址），用数组名数组名或下标为0的数组元素取地址都可以，因此。空（2）所在语句是调用memset对申请的存储区域进行初始化。根据注释，要求将 temp_arr指向的内存区域清零，根据声明memset时的定义，void*memset (void *p, int ch, si

。空（3）所在的循环语句遍历数组a的所有元素，将元素ai作为temp_arr的下标， 从而使得temp_arrai表示了ai表示的值在数组a中出现的次数。例如：数组a中函数元素1，则需要temp_arr1的值+1，数组a中函数元素5，则需要temp

14、_arr5的值+1。空（4）、（5）主要是通过temp_arr中的元素取值情况来对数组a中元素进行重排，假设tem_arr0=3，则表示0元素出现了3次。首先用cnt保留元素出现的次数，可知空(4）处应设置cnt的初始值，为“temp_arri”。 当cnt0时，表示元素i出现的次数超过了1次，需要进行循环填入，每在数组中放入1个i元素后，cnt自减（表明还需要放置的次数要减1），而k需要自增（表明元素放置位置要往后一个），以给出下一个i要放入的数组位置，因此空（5）处应填入“k+”或其等效形式。4. 单选题HTML中使用（ ）标记对来标记一个超链接元素。问题1选项A.B.C.D.【答案】A【

15、解析】本题考查HTML语言方面的基础知识。在HTML语言中，基本是使用标记对来对文本格式进行排版和提供一定的功能的。要在页面中使用超级链接，需使用锚标记来实现。标签定义超链接，用于从一个页面链接到另一个页面。元素最重要的属性是href属性，它指示链接的目标。例如：网站页面该行代码的作用是为文字“网站页面”定义超链接功能，使其能够连接到href属性 所指的页面上，在该例子中，当用户单击“网站页面”，将会跳转到http：/ 页面。另外，表示加粗，表示倾斜标签， 标签定义短的引用。5. 单选题判定覆盖法要求测试用例能使被测程序中每个判定表达式的每条分支都至少通过一次。若某程序的流程图如下图所示，则用

16、判定覆盖法对该程序进行测试时，至少需要设计（ ）个测试用例。问题1选项A.4B.5C.6D.8【答案】B【解析】本题考查软件工程的基础知识。上述流程图中，从begin到return result有五条路使所有的判定分支都至少通过一次：(1)b=0；(2)b为正数，a为非负数；(3)b为正数，a为负数；(4)b为非正数，a为非负数；(5)b为非正数，a为负数。而且用例不能再少了。6. 单选题某高校教学管理系统中的院系关系Department和学生关系Students的模式分别 为：Department (院系号，院系名，负责人，办公电话)，学生关系Students (学号，姓名，身份证号，院系号

17、，联系电话，家庭住址)。Department中的“院系号”唯一标识 一个院系，Students中的“学号”能唯一标识一名学生，“家庭住址”可进一步分为邮编、 省、市、街道。根据以上描述可知，关系Students的候选键为（ ）, “家庭住址” 为（ ）。创建Students的SQL语句如下，请填补其中的空缺。CREATE TABLE Students(学号 CHAR(8)

(学号)【答案】第1题:C第2题:B第3题:B【解析】本题考查数据库基础知识。在关系模型中，候选键又称候选码（英语：candidate key），是某个关系变量的一组属性所组成的集合，它需要同时满足下列两个条件：1.这个属性集合始终能够确保

19、在关系中能唯一标识元组。2.在这个属性集合中找不出合适的真子集能够满足条件。在这里，学生的候选键有身份证号和学号。家庭住址是复合属性。该题为外键的考查，院系号作为院系关系的主键，所以在学生关系中院系号是外键。7. 单选题若某二叉树的先序遍历序列是ABDCE，中序遍历序列是BDACE，则该二叉树为（ ）。问题1选项A.B.C.D.【答案】D【解析】本题考查数据结构基础知识。根据先序遍历序列可确定树（及子树）的根结点，根据中序遍历序列可分割左、右子树上的结点，据此可逐步确定每个结点的位置。如下判断：1）已知先序遍历序列是ABDCE，则根节点为A；然后中序遍历序列是BDACE，则BD是左子树中的元素

20、，CE是右子树中的元素。可排除AB选项。2）然后看左子树BD，在先序遍历中先访问B结点，B作为该子树的树根。回到中序遍历，先访问的是B，然后访问的是D，则D是B的右孩子结点。3）然后看右子树CE，在先序遍历中先访问C结点，C作为该子树的树根。回到中序遍历，先访问的是C，然后访问的是E，则E是C的右孩子结点。因此结果选择D。该题也可以对每个二叉树进行先序遍历和中序遍历运算，根据所得序列确定正确选项。即：选项A所示二叉树的先序遍历序列为ABDEC，中序遍历序列为DBEAC。选项B所示二叉树的先序遍历序列为ABCDE，中序遍历序列为BADCE。选项C所示二叉树的先序遍历序列为ABDCE，中序遍历序列

21、为BDAEC。选项D所示二叉树的先序遍历序列为ABDCE，中序遍历序列为BDACE。综合判断后选择D选项。8. 单选题在以用户界面（UI）层、系统交互（SI）层、问题领域（PD）层和数据管理（DM）层构成的软件架构中，业务实体和业务逻辑属于（ ）层。问题1选项A.UIB.SIC.PDD.DM【答案】C【解析】本题考查软件工程的基础知识。业务实体和业务逻辑属于企业需要解决的实际问题的领域。9. 单选题以下关于CPU与I/O设备交换数据所用控制方式的叙述中，正确的是（ ）。问题1选项A.中断方式下，CPU与外设是串行工作的B.中断方式下，CPU需要主动查询和等待外设C.DMA方式下，CPU与外设可

22、并行工作D.DMA方式下，CPU需要执行程序来传送数据【答案】C【解析】本题考查计算机系统基础知识。CPU与I/O设备交换数据时常见的控制方式有程序查询方式、中断方式、DMA方式和通道方式等。在程序查询方式下，CPU执行指令查询外设的状态，在外设准备好的情况下才输入或输出数据。在中断方式下，是外设准备好接收或发送数据时发出中断请求，CPU无需主动查询外设的状态。在DMA方式下，数据传送过程是直接在内存和外设间进行的，不需要CPU执行程序来进行数据传送。DMA方式简化了CPU对数据传送的控制，提高了主机与外设并行工作的程度，实现了快速外设和主存之间成批的数据传送，使系统的效率明显提高。10.

23、选题计算机中最基本的单位基准时间是（ ）。问题1选项A.时钟周期B.指令周期C.总线周期D.CPU周期【答案】A【解析】时钟周期又叫作振荡周期、节拍周期，定义为时钟晶振频率的倒数。时钟周期是计算机中最基本的、最小的时间单位。在一个时钟周期内，CPU仅完成一个最基本的动作。指令周期是指取出并完成一条指令所需的时间，一般由若干个机器周期组成。在计算机中，为了便于管理，常把一条指令的执行过程划分为若干个阶段，每一阶段完成一项工作。例如，取指令、存储器读、存储器写等，每一项工作称为一个基本操作，完成一个基本操作所需要的时间称为机器周期（也称为CPU周期）。通常把CPU通过总线对微处理器外部（存储器或I

24、/O端口）进行一次访问所需要的时间称为一个总线周期。综上所述，正确的答案为A选项。11. 单选题下面的网络地址中，不能作为目标地址的是（ ）。问题1选项A.0.0.0.0B.127.0.0.1C.10.255.255.255D.192.168.0.1【答案】A【解析】本题考查网络的基础知识。在IPv4中，0.0.0.0 地址被用于表示-一个无效的、未知的或者不可用的目标。以127开头的IP地址都是回环地址(Loop back address)，其所在的回环接口一般被理解为虚拟网卡，并不是真正的路由器接口。发送给127 开头的IP地址的数据包会被发送的主机自己接收，根本传不出去，外部设备也无法通

25、过回环地址访问到本机。127.0.0.1 经常被默认配置为localhost的IP地址。一般会通过ping127.0.0.1来测试某台机器上的网络设备是否工作正常。一个A类IP地址由1字节的网络地址和3字节主机地址组成，而且网络地址的最高位必须是0。A类IP中的10.0.0.0到10.255.255.255是私有地址，一个A类网络可提供的主机地址为16 777 214个，也就是224-2个，减2的原因是主机地址全0表示“本主机”所连接到的单个网络地址，而全1表示“所有”，即该网络上所有主机。12. 单选题高并发是互联网分布式系统架构设计中必须考虑的因素之一。影响并发性能的因素不包括（ ）。问题

26、1选项A.响应时间B.吞吐量C.并发用户数D.注册用户总数【答案】D【解析】本题考查软件工程基础知识。注册用户总数再多，如果同时使用的并发用户数不多，就不会造成高并发。13. 单选题计算机启动时CPU从（ ）读取硬件配置的重要参数。问题1选项A.SRAMB.CMOSC.DRAMD.CD-ROM【答案】B【解析】本题考查计算机系统基础知识。SRAM（Static RandomAccess Memory，静态随机存取存储器）是指这种存储器只要保持通电，里面储存的数据就可以恒常保持。DRAM（Dynamic Random Access Memory，动态随机存取存储器）隔一段时间要刷新充电一次，否则

27、内部的数据会消失。注意：SRAM和DRAM都是属于RAM，其内容断电之后会消失，每次开机后内容随机，不固定。CMOS（Complementary Metal Oxide Semiconductor，互补金属氧化物半导体）是指制造大规模集成电路芯片用的一种技术或用这种技术制造出来的芯片，是计算机主板上的一块可读写的RAM 芯片，用来保存BIOS设置完计算机硬件参数后的数据，这个芯片仅用来存放数据。14. 单选题在白盒测试中，（ ）覆盖是指设计若干个测试用例，运行被测程序，使得程序中的每条语句至少执行一次。问题1选项A.语句B.判定C.条件D.路径【答案】A【解析】本题考查软件工程的基础知识。对程

28、序模块进行白盒测试时，语句覆盖是指设计若干个测试用例，运行被测程序，使得程序中的每条语句至少执行一次。15. 案例题阅读以下说明和C代码，填补C代码中的空缺，将解答写在答题纸的对应栏内。【说明】下面程序中，函数convertion(char *p)的功能是通过调用本程序中定义的函数，将p所指示字符串中的字母和数字字符按如下约定处理：（1）大写字母转换为小写字母；（2）小写字母转换为大写字母；（3）数字字符转换为其伙伴字符（当两个十进制数字相加为9时，这两个十进制数字对应的数字字符互为伙伴字符）。例如，字符2的伙伴字符为7、8的伙伴字符为1、0的伙伴字符为9等。【C代码】【答案】(1) *c-0

30、针类型，调用这些函数时实参应为指向字符的指针(字符变量的地址)。根据题干部分的描述，求解数字字符的伙伴字符时，需要进行算术运算，用9减去数字字符对应的数值(即数字字符- 0)，得到的值再加上0从而再次转换为数字字符，因此空(1)处应填入“*c-0” 或其等效形式。函数convertion(char *p)根据题干描述的要求对字符进行转换，满足空(2)所给的条件时需要调用toLower(p)将字符转换为小写字母，因此空(2)处应判断字符是否为大写字母，应填入“isUpper(*p)或其等效形式；满足空(3)所给的条件时需要调用toUpper(p)将字符转换为大写字母，因此空(3)处应判断字符是否

31、为小写字母，应填入“isLower(*p)或其等效形式;满足空(4)所给的条件时需要调用cDigit(p)将数字字符转换为其伙伴字符，因此空(4)处应判断字符是否为数字字符，应填入“isDigit(*p)”或其等效形式。在while循环中还需要对指针变量p进行递增，处理完p指向的当前字符后再指向下一字符，因此空(5)处应填入“p+”或其等效形式。16. 单选题编译和解释是实现高级程序设计语言的两种基本方式，（ ）是这两种方式的主要区别。问题1选项A.是否进行代码优化B.是否进行语法分析C.是否生成中间代码D.是否生成目标代码【答案】D【解析】本题考查程序语言基础知识。解释程序和编译程序都是针对

32、于高级语言进行处理的程序，两者在词法、语法和语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，解释程序直接执行源程序或源程序的内部形式，并不产生源程序的目标代码，而编译程序一定会生成目标代码，因此是否生成目标代码是解释和编译程序的主要区别。17. 单选题设r是在(0，1)内均匀分布的随机数，则随机变量（

）。问题1选项A.直接寻址B.相对寻址C.间接寻址D.立即寻址【答案】D【解析】若操作数就包含在指令中，则是立即寻址。若操作数存放在内存单元中，指令中直接给出操作数所在存储单元的地址，则是直接寻址。间接寻址是相对于直接寻址而言的，指令地址字段的形式地址D不是操作数的真正地址，而是操作数地址的指示器。若操作数存放在某一寄存器中，指令中给出存放操作数的寄存器名，则是寄存器寻址。若操作数存放在内存单元中，操作数所在存储单元的地址在某个寄存器中，则是寄存器间接寻址。20. 单选题在某C程序中有下面的类型和变量定义（设字符型数据占1字节,整型数据占4字节），则运行时系统为变量rec分配的空间大小为（ ）。问题1选项A.1字节B.4字节C.5字节D.8字节【答案】B【解析】本题考查程序语言的基础知识。共用体变量的大小取决于其所需存储空间最大的成员，最大的整形字符4字节。

}

1.把二元查找树转变成排序的双向链表

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

首先我们定义的二元查找树 节点的数据结构如下：

2.设计包含min函数的栈。

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。

要求函数min、push以及pop的时间复杂度都是O(1)。

输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)。

因此输出为该子数组的和18。

4.在二元树中找出和为某一值的所有路径

题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如 输入整数22和如下二元树

二元树节点的数据结构定义为：

5.查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。

例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数

要求下排每个数都是先前上排那十个数在下排出现的次数。

【0，1，2，3，4，5，6，7，8，9】

0在下排出现了6次，1在下排出现了2次，

2在下排出现了1次，3在下排出现了0次....

微软亚院之编程判断俩个链表是否相交

给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。

为了简化问题，我们假设俩个链表均不带环。

1.如果链表可能有环列?

2.如果需要求出俩个链表相交的第一个节点列?

此贴选一些 比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。

1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，

这两个房间是 分割开的，从一间里不能看到另一间的情况。

现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。

如果你只能将金条切割两次，你怎样分给这些工人?

3.　★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

　　★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。

　　★用一种算法整理一个数组。你为什么选择这种方法?

　　★用一种算法使通用字符串相匹配。

　　★颠倒一个字符串。优化速度。优化空间。

　　★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，

实现速度最快，移动最少。

　　★找到一个子字符串。优化速度。优化空间。

　　★比较两个字符串，用O(n)时间和恒量空间。

　 　★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现 两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不 用这种方式的算法吗?

　　★不用乘法或加法增加8倍。现在用同样的方法增加7倍。

判断整数序列是不是二元查找树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

翻转句子中单词的顺序。

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。

求二叉树中节点的最大距离...

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，

我们姑且定义"距离"为两节点之间边的个数。

求一棵二叉树中相距最远的两个节点之间的距离。

要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

题目：输入一个已经按升序排序过的数组和一个数字，

在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

题目：输入一颗二元查找树，将该树转换为它的镜像，

即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

用递归和循环两种方法完成树的镜像转换。

定义二元查找树的结点为：

输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

分析：这道题是2006年google的一道笔试题。

题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，

每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。

当一个数字删除后，从被删除数字的下一个继续删除第m个数字。

求出在这个圆圈中剩下的最后一个数字。

July：我想，这个题目，不少人已经 见识过了。

题目：定义Fibonacci数列如下：

输入n，用最快的方法求该数列的第n项。

分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。

因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。

题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。

例如输入字符串"345"，则输出整数345。

输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,

使其和等于 m ,要求将其中所有的可能组合列出来.

有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，再分别在A、B、C三人额头上贴任意两张牌，

A、B、C三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，

A说不知道，B说不知道，C说不知道，然后A说知道了。

请教如何推理，A是怎么知道的。

如果用程序，又怎么实现呢？

用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。"

（1）.单链表就地逆置，

在字符串中找出连续最长的数字串，并把这个串的长度返回，

并把这个最长数字串付给其中一个函数参数outputstr所指内存。

定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。

如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。

要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。

题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。

求总共有多少总跳法，并分析算法的时间复杂度。

这道题最近经常出现，包括MicroStrategy等比较重视算法的公司

都曾先后选用过个这道题作为面试题或者笔试题。

28.整数的二进制表示中1的个数

题目：输入一个整数，求该整数的二进制表达中有多少个1。

例如输入10，由于其二进制表示为1010，有两个1，因此输出2。

这是一道很基本的考查位运算的面试题。

包括微软在内的很多公司都曾采用过这道题。

题目：输入两个整数序列。其中一个序列表示栈的push顺序，

判断另一个序列有没有可能是对应的pop顺序。

为了简单起见，我们假设push序列的任意两个整数都是不相等的。

比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。

因为可以有如下的push和pop序列：

这样得到的pop序列就是4、5、3、2、1。

但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

30.在从1到n的正数中1出现的次数

题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

分析：这是一道广为流传的google面试题。

一类似于蜂窝的结构的图，进行搜索最短路径（要求5分钟）

有两个序列a,b，大小都为n,序列元素的值任意整数，无序；

要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。

实现一个挺高级的字符匹配算法：

给一串很长字符串，要求找到符合要求的字符串，例如目的串：123

其实就是类似一些和谐系统。。。。。

一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列

求一个矩阵中最大的二维矩阵(元素和最大).如:

要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码

第36题-40题（有些题目搜集于CSDN上的网友，已标明）：

n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，

存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j的队伍中更强的一支。

所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，

胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，

下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名

编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，

有n个长为m+1的字符串，

如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，

问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，

最多可以从y个小球中找出较轻的那个，求y与x的关系式。

2.有一个很大很大的输入流，大到没有存储器可以将其存储下来，

而且只输入一次，如何从这个输入流中随机取得m个记录。

3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度

求一个二叉树中任意两个节点间的最大距离，

两个节点的距离的定义是 这两个节点间边的个数，

比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。

求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，

有向图不再连通，描述算法。

1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。

设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。

并分析时间复杂度与空间复杂度。

3)设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，

则中国人民 人民中国都有效。要求：

*系统每秒的查询数量可能上千次；

*词语的数量级为10W；

*每个词至多可以与1W个词搭配

当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。

41.求固晶机的晶元查找程序

晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，

照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，

若匹配不过，照相机则按测好的晶元间距移到下一个位置。

求遍历晶元盘的算法 求思路。

42.请修改append函数，利用这个函数实现：

另外只能输出结果，不能修改两个链表的数据。

43.递归和非递归俩种方法实现二叉树的前序遍历。

1.设计一个魔方（六面）的程序。

2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

请用5分钟时间，找出重复出现最多的前10条。

3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）

1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）

某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值

四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}

是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

49.一道看上去很吓人的算法面试题：

如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)

1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 这两个节点间边的个数，

比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。

2.求一个有向连通图的割点，割点的定义是，

如果除去此节点和与其相关的边，有向图不再连通，描述算法。

51.和为n连续正数序列。

题目：输入一个正数n，输出所有和为n连续正数序列。

分析：这是网易的一道面试题。

题目：输入一棵二元树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

二元树的结点定义如下：

分析：这道题本质上还是考查二元树的遍历。

题目：输入一个字符串，打印出该字符串中字符的所有排列。

例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串

分析：这是一道很好的考查对递归理解的编程题，

因此在过去一年中频繁出现在各大公司的面试、笔试题中。

54.调整数组顺序使奇数位于偶数前面。

题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，

所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

题目：类CMyString的声明如下：

请实现其赋值运算符的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对象的状态不能改变。

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，

则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。

请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，

则输出它们的长度4，并打印任意一个子串。

因此一些重视算法的公司像MicroStrategy都把它当作面试题。

57.用俩个栈实现队列。

题目：某队列的声明如下：

分析：从上面的类的声明中，我们发现在队列中有两个栈。

因此这道题实质上是要求我们用两个栈来实现一个队列。

相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，

因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，

我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。

58.从尾到头输出链表。

题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：

分析：这是一道很有意思的面试题。

该题以及它的变体经常出现在各大公司的面试、笔试题中。

59.不能被继承的类。

题目：用C++设计一个不能被继承的类。

分析：这是Adobe公司2007年校园招聘的最新笔试题。

这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。

60.在O（1）时间内删除链表结点。

题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：

分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，

更重要的是，还能考察我们对时间复杂度的理解。

61.找出数组中两个只出现一次的数字

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：这是一道很新颖的关于位运算的面试题。

62.找出链表的第一个公共结点。

题目：两个单向链表，找出它们的第一个公共结点。

分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，

因此在微软的面试题中，链表出现的概率相当高。

63.在字符串中删除特定的字符。

题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，

则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，

因为写程序操作字符串能很好的反映我们的编程基本功。

题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，

但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。

求按从小到大的顺序的第1500个丑数。

分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。

65.输出1到最大的N位数

题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，

则输出1、2、3一直到最大的3位数即999。

分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。

题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。

2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。

把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，

打印出S的所有可能的值出现的概率。

68.把数组排成最小的数。

题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。

请给出解决问题的算法，并证明该算法。

分析：这是09年6月份百度的一道面试题，

从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

69.旋转数组中的最小元素。

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，

输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

    分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，

时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

70.给出一个函数来输出一个字符串的所有排列。

ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，

还有逆序生成排列和一些不需要递归生成排列的方法。

印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，

也需要一定的灵感，有兴趣最好看看。

71.数值的整数次方。

分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：

题目：设计一个类，我们只能生成该类的一个实例。

分析：只能生成一个实例的类是实现了Singleton模式的类型。

73.对策字符串的最大长度。

题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。

比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

74.数组中超过出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都

曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，

除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。

75.二叉树两个结点的最低共同父结点

题目：二叉树的结点定义如下：

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。

题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，

还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：

下图是一个含有5个结点的该类型复杂链表。

图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，

分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。

要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，

对数据结构透彻的理解以及扎实的编程功底。

77.关于链表问题的面试题目如下：

1.给定单链表，检测是否有环。

使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，

说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。

下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，

否则说明两个链表没有交点。

3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。

一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。

4.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。

办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。

  办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，

然后再将要插入的数据记录在p中。

78.链表和数组的区别在哪里？

分析：主要在基本概念上的理解。

但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，

谁比较仔细，谁获胜的机会就大。

1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？

2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？

3.请编写能直接实现strstr()函数功能的代码。

80.阿里巴巴一道笔试题

12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

这个笔试题,很YD,因为把某个递归关系隐藏得很深。

}

我要回帖

更多关于 一维数组指针定义 的文章

更多推荐

版权声明：文章内容来源于网络，版权归原作者所有，如有侵权请点击这里与我们联系，我们将及时删除。

点击添加站长微信