面向对象的概述——习题
1 什么是面向对象的程序设计？它与结构化程序设计有什么不同？
2 解释以下概念：
（1）对象 （2）消息 （3）类 （4）实例 （5）公有消息 （6）私有消息
3 对象有哪些特性？对象是如何确定和划分的？
4 类与实例的关系如何？
5 叙述面向对象系统的特性。这些特性在面向对象系统中起什么作用？
7 为什么说C++是一种混合型编程语言？
10 简述C++程序的编写与实现过程。
类及其对象的封装性——习题
1 类中可以包含几种类型的成员？它们是什么？
2 简述类和结构体类型的异同。
3 请描述构造函数和析构函数的功能和特点。如何定义构造函数和析构函数？
4 分析以下程序的执行结果：
#include <iostream.h>
class Sample
{
int n；
public：
Sample（）{ }
Sample（int m）{ n＝m；}
Sample add（Sample s1，Sample s2）
{
this->n＝s1.n＋s2.n；
return （*this）；
}
void disp（）
{ cout <<“n＝”<< n << endl；}
}；
int main（）
{
Sample s1（10），s2（5），s3；
cout <<“s1：”；
s1.disp（）；
cout <<“s2：”；
s2.disp（）；
s3.add（s1，s2）；
cout <<“执行s3.add（s1，s2）\ns3：”；
s3.disp（）；
return 0；
}
5 定义一个通信录类，该类中有数据成员姓名、地址、电话、邮政编码等。成员函数有构造函数，ChangeName函数，Display函数。构造函数初始化每个成员，ChangeName函数用来逐个修改姓名，Display函数把完整的数据打印出来。
6 编写一个基于对象的程序求3个长方柱的体积。数据成员包括length（长）、width（宽）、height（高）。要求用成员函数实现以下功能：
（1）从键盘输入3个长方柱的长、宽、高；
（2）计算并输出3个长方柱的体积。
7 定义一个日期类Date，该类存放一个日期，要求提供以下操作：
（1）void GetDate（）； // 取日期值，格式如“
（2）GetYear（）； //取年份
（3）GetMonth（）； //取月份
（4）GetDay（）； //取日期
（5）SetDate（int year，int month，int day）； //设置日期值
（6）从键盘输入年、月、日，计算并显示出该天的日期和星期，同时打印昨天和明天的日期。
8 定义一个学生类，要处理的学生信息有学号、姓名、年龄和所学专业。请编程实现对学生记录的插入、查找和删除，并显示输出结果。
例：编一个主程序，输入5个学生记录，查找出学好为03的记录，显示后删除，再列出剩余学生的信息。
友员、重载和引用——习题
1 什么是友元？友元的作用是什么？
2 什么是重载？函数重载有哪些表现形式？ 运算符重载有哪几种实现方式？
3 什么是引用？如何定义引用？引用和指针有何区别？C＋＋使用引用的好处有哪些？
4 分析以下程序的执行结果：
#include <iostream.h>
class Sample
{
int n；
public：
Sample（）{ }
Sample（int m）{ n＝m； }
friend void square（Sample &s，int k）
{ s.n＝k；}
void disp（）
{ cout <<“n＝”<< n << endl； }
}；
int main（）
{
Sample a（10）；
a.disp（）；
square（a，100）；
cout <<“Now n is changed to：”；
a.disp（）；
return 0；
}
5 写出下列程序的执行结果：
#include <iostream.h>
class Sample
{
int x；
public：
Sample（）{ }
Sample（int p）{ x＝p；}
void operator ＋（int p）{ x＝x＋p；}
void Show（）
{ cout <<“x＝”<< x << endl； }
}；
int main（）
{
Sample obj（100）；
Sample &p＝obj；
p.Show（）；
p＋100；
obj.Show（）；
return 0；
}
6 设计并测试一个名为R的矩形类，其属性为矩形左上角和右下角两点的坐标，要求输入两点坐标后计算出矩形的面积。
7 设计一个表示时间的类，实现时间的加、减和输出，其中加、减用重载运算符实现。
8 定义一个复数类Complex的加法与减法，使之能够执行下列运算：
Complex a（5，5），b（10，10），c（0，0）；
c＝a＋b；
c＝4.1＋a；
c＝b＋5；
9 有10个学生的5门课的成绩，要求编写程序统计学生中A类学生与不及格类学生的人数各占多少？A类学生的标准是每门课成绩在80分以上。
10 编写一个程序，通过执行结果的分析来检验在引用类对象时是否执行了类的构造函数与析构函数。
11 编写一个密码类，其中包含一个str密码字符串私有成员函数，以及一个“＝＝运算符重载成员函数，用于比较用户输入的密码是否正确，并用数据测试该类。
继承与派生——习题
1 派生类有哪几种继承方式？对于不同的继承方式，基类中各类成员在派生类中的访问属性如何？
2 声明一个Document类，有数据成员name，从Document公有派生出Book类，增加数据成员PageCount。
3 派生类构造函数和析构函数的执行顺序是怎样的？
4 派生类能否直接访问基类的私有成员？若否，应如何实现？
5 如果派生类B已经重载了基类A的一个成员函数f1（），没有重载基类的成员函数f2（），如何在派生类的函数中调用基类的成员函数f1（）、f2（）？
6 在类的派生中为何要引入虚基类？有何作用？
7 有以下程序结构，请分析所有成员在各类的范围内的访问权限。
class A
{
public：
void f1（）；
protected：
void f2（）；
private：
int i；
}；
class B：public A
{
public：
void f3（）；
int k；
private：
int m；
}；
class C：protected B
{
public：
void f4（）；
protected：
int m；
private：
int n；
}；
class D：private C
{
public：
void f5（）；
protected：
int p；
private：
int q；
}；
int main（）
{
A a1；
B b1；
C c1；
D d1；
return 0；
}
8 给出以下程序的执行结果。
#include <iostream.h>
class Data
{
public：
data（int x）{data：：x = x；cout <<“class Data”<< endl；}
private：
int x；
}；
class A
{
public：
A（int x）：d1（x）{cout <<“class A”<< endl；}
private：
data d1；
}；
class B：public A
{
public：
B（int x）；A（x），d2（x）{cout <<“class B”<< endl；}
private：
data d2；
}；
class C：public B
{
public：
C（int x）：B（x）{cout <<“class C”<< endl；}
}；
void main（）
{
c obj（5）；
}
9 给出以下程序的执行结果。
#include <iostream.h>
class A
{
public：
A（int i，int j）{a = i； b = j；}
void move（int x，int y）{a+= x；b+= y；}
void show（）{cout <<“（”<< a <<“，”<< b <<“）”<< endl；}
private：
int a，b；
}；
class B：private A
{
public：
B（int i，int j，int k，int l）：A（i，j）{x = k；y = l；}
void show（）{cout << x <<“，”<< y << endl；}
void fun（）{move（3，5）；}
void f1（）{A：：show（）；}
private：
int x，y；
}；
void main（）
{
A e（1，2）；
e.show（）；
B d（3，4，5，6）；
d.fun（）；
d.show（）；
d.f1（）；
}
10 编写一个学生和老师数据输入和显示的程序，学生数据有学号、姓名、系名和成绩，老师数据有工号、姓名、职称和部门。要求将学号（或工号）、姓名输入和显示设计成一个类 person，并作为学生类 student 和老师类 teacher 的基类。
虚函数与多态性——习题
1 什么叫做多态性？在C++中是如何实现多态的？
2 什么是虚函数？什么是纯虚函数？
3什么是抽象类？抽象类有什么用途？抽象类的派生类是否一定要给出纯虚函数的实现？
4 在 C + +中能否声明虚构造函数？为什么？能否声明虚析构函数？有何用途？
5 给出以下程序的执行结果。
#include <iostream.h>
class A
{
public：
virtual void f（） //虚函数
{cout <<“A：：f（）called.”<< endl；}
}；
class B：public A
{
public：
virtual void f（） //虚函数
{cout <<“B：：f（）called.”<< endl；}
}；
void main（）
{
A *ptr；
A a；
B b；
ptr = &a；
ptr-> f（）；
ptr = &b；
ptr-> f（）；;
}
6 分析以下程序的错误并改正。
#include <iostream.h>
class A
{
public：
A（int i）{x = i；}
void dispa（）{cout <<“x =”<< x << endl；}
private：
int x；
}；
class B： public A
{
public：
B（int i，int j）：A（i） { y = j；}
void dispb（）{cout <<“y=”<< y << endl；}
private：
int y；
}；
void main（）
{
A *p，a（1）；
B b（2，3）；
p = &a；
p-> dispa（）；
p = &b；
p-> dispb（）；
}
7 写一个程序，定义抽象基类Shape，由它派生出3个派生类：Circle（圆形）、Rectangle（矩形）、Triangle（三角形），用一个函数printArea分别输出以上三者的面积，3个图形 的数据在定义对象时给定。
8 写一个程序，定义抽象基类Shape，由它派生出5个派生类：Circle（圆形）、Square（正方形）、Rectangle（矩形）、Trapezoid（梯形）、Triangle（三角形）。用虚函数分别计算几种图形的面积，并求它们的和。要求用基类指针数组，使它的每一个元素指向一个派生类对象。
 |
9 设计一个评选优秀教师和学生的程序，其类结构如下图所示。当输入一系列教师或学生的记录后，将优秀教师及学生的姓名列出来，并采用相关数据进行测试。
模板——习题
1 什么是函数模板？
2 什么是类模板？
3 函数模板与同名函数重载时的调用规则是什么？
4 试定义一个 min（）函数模板，使该函数模板能接受各种类型的三个参数，找出并输出其中最小者。
5 建立类模板 input，在调用构造函数时，完成以下工作：
1）提示用户输入；
2）让用户输入数据；
3）如果数据不在预定范围内，重新提示输入。input型的对象应当按以下形式定义： input ob（“promputmessage”，min_value，max_value）其中，promputmessage是提示输入的信息。可接受的最小值和最大值分别由 min_value与max_value指定。
6 编写一个使用类模板对数组进行排序、查找和求元素和的程序，并采用相关数据进行测试。
线性表——习题
1 线性表可以用顺序表或链表存储，试问：
（1） 两种存储表示主要的优缺点是什么？
（2） 如果有n个表同时并存，并且在处理过程中各表的长度会动态变化，表的总数也可能变化，应该选用哪种存储表示？为什么？
（3） 如果表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，应采用哪种存储表示？为什么？
2 试编写一个算法，在带表头结点的单链表中寻找第i个结点。若找到，函数返回第i个结点的地址；否则，则函数返回0。
3 试设计一个实现线性表逆置的算法，即利用原表空间将线性表遍历顺序由（a0，a1，……，an-1）转换成（an-1，an-2，……，a1，a0），表头指针指向an-1。
4 设顺序表va中的数据元素为非降次序，试编写一个算法，将x插入顺序表的适当位置上，以保持该表的有序性。
5 设ha和hb分别是两个带表头结点的非降次序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非降次序的单链表。要求：
（1） 最终的链表仍然使用原来两个链表的存储空间，不另外占用其他的存储空间。
（2） 先合并成一个允许出现重复的元素的单链表，再删除表中重复的元素。
6 根据一个结点数据类型为整型的单链表生成两个单链表，使第一个单链表包含原单链表中所有数据值为奇数的结点，使第二个单链表包含原单链表中所有数据值为偶数的结点，原有单链表保持不变。
7 如果用单链表表示一元多项式，试设计一个算法计算给定x时的表达式的值。比如，对一元多项式A（x）= 4x21 + 5x10 + 7x4 + x，如果给定x = 1，则可求出A（1）= 17。
8 如果用单向循环链表来表示一元多项式，试编写一个算法计算两个多项式a和b的乘积c = a * b。
9 假设某个单向循环链表的长度大于1，且表中即无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写在链表中删除指针s所指结点的前驱结点的算法。
10 试设计一个实现如下要求的Locate操作的算法：
（1） 设计一个带表头的双向链表L，每个结点有4个数据域，分别指向前驱结点的指针pre，指向后继结点的指针next，数据data，访问频度freq。
（2） 所有结点freq初始化为0。
（3） 每当链表执行一次Locate（L. x）操作，元素值为x的结点的freq加1；同时调整链表中结点之间的次序，使其按访问频度递减顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。
堆栈与队列——习题
1 简述栈和线性表的差别。
2 设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1、2、3、4的相对次序），请写出所有可能的出栈次序。
3 已知Ackerman函数的定义如下：
（1）写出递归算法，并画出akm (2，1) 时的栈的变化过程；
（2）写出非递归算法，并画出akm (2，1) 时的栈的变化过程。
4 假设以顺序栈存储结构实现一个双向栈，即在一个一维数组A [m]的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点A [ 0 ]和A [m - 1]。试构造一个类，并要求实现这个双向栈的3个基本操作：
（1）初始化操作；
（2）入栈操作；
（3）出栈操作。
5 试编写一个程序，让计算机随机产生出100以内的20个正整数并输出，同时把它们中的偶数依次存入到第一个栈中，奇数依次存入到第二个栈中，然后按后进先出的原则输出每个栈中的所有元素（方法不限，用链栈或顺序栈都可以）。
6 试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个整数，按照下列要求分别进入不同栈：
（1）若输入的整数x小于60，则进入第一个栈；
（2）若输入的整数x大于等于60并小于100，则进入第二个栈；
（3）若输入的整数x大于100，则进入第三个栈；
最后分别输出每个栈的内容。
7 简述队列和栈这两种数据类型的异同点。
8 假设以数组A [m]存放循环队列中的元素，同时以rear和length分别指示环形队列的队尾位置和所包含的元素个数。试给出该循环队列的队空和队满条件，写出相应的入队和出队算法。
9 假设以数组A [m]存放循环队列中的元素，同时设置一个标志tag，当队头指针（front）的队尾指针（rear）相等时，tag = 1表示队满。试给出该循环队列相应的入队和出队算法。
10 假设以带头结点的循环队列表来表示队列，并且只设一个指针指向队尾元素结点（注意：不设头指针）。试编写相应队列初始化、入队和出队算法。
11 试建立一个继承结构，以栈、队列和优先队列为派生类，建立它们的抽象基类Base类。写出各个类的声明。统一命名各派生类的插入操作为Add，删除操作为Remove，存取操作为Get和Put，判空操作为IsEmpty，判满操作为IsFull，计数操作为GetLenth。
12 编写一个程序，使用两个链队q1和q2，用来分别存储由计算机产生的20个100以内的奇数和偶数，然后每行输出q1和q2中一个值，即奇数和偶数配对输出，直到任一队列为空为止。
树和二叉树——习题
1 一棵度为2的树与二叉树有何区别？
2 试分别画出具有3个结点的树和3个结点的二叉树的所有不同状态？
3 在结点个数为n（n > 1）的各棵树中，试问：
（1）高度最小的树的高度是多少？它有多少个叶子结点？多少个分支结点？
（2）高度最大的树的高度是多少？它有多少个叶子结点？多少个分支结点？
4 一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上的结点均有k棵非空子树。如果按层次顺序从0开始编号，问：
（1）各层的结点数目有多少？
（2）编号为p的结点的父结点（若存在）的编号是多少？
（3）编号为p的结点的儿子结点（若存在）的编号是多少？
（4）编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
5 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？
6 使用顺序存储表示和二叉链表表示法，分别画出如下图所示的二叉树的存储表示。
7 请画出题7图（a）所示的一棵和题7图（b）所示的森林各自对应的二叉树。
8 请给出如题12.8图所示的一棵二叉树前序遍历、中序遍历和后序遍历的序列结果。
9 假设一棵树的前序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树。
10 假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为ABCDEFGHIJK，请画出该树。
11 假设一棵二叉树的层序序列为ABCDEFGHIJ和 中序序列为DBGEHJACIF，请画出该树。
12 编写递归算法，将二叉树中所有结点的左、右子树相互交换。
13 编写按层次顺序（同一层自左至右）遍历二叉树的算法
14 对以孩子—兄弟链表表示的树编写算法，分别完 成以下操作：
（1）计算树的高度；
（2）计算树的深度；
（3）统计叶子结点的个数。
 |
|
15 设计一算法来完成Huffman树的构造。