C++程序设计习题答案第七章

第七章 动态内存分配习题 1

第七章 动态内存分配习题

一、基本概念与基础知识自测题

7.1 填空题

7.1.1 C/C++定义了4个内存区间： （1） 、 （2） 、 （3） 和 （4） 。 答案：（1）代码区，存放程序代码；

（2）全局变量与静态变量区，存放全局变量或对象（包括静态）； （3）局部变量区即栈（stack）区，存放局部变量； （4）自由存储区（free store），即动态存储区或堆（heap）区。

7.1.2 静态定义的变量和对象用标识符命名，称为 （1） ；而动态建立的称为 （2） ，动

态建立对象的初始化是通过 （3） 实现 （4） 。 答案：（1）命名对象

（2）无名对象

（3）初始化式(initializer) （4）显式初始化

7.1.3 在用new运算符建立一个三维数组15*30*10时，使用了 （1） 个下标运算符，对

应的用delete运算符注销这个三维数组时使用了 （2） 个下标运算符。new返回的指针是指向 （3） 的指针。 答案：（1）3个

（2）1个

（3）30行10列的2位数组

7.1.4 当动态分配失败，系统采用 （1） 来表示发生了异常。如果new返回的指针丢失，

则所分配的自由存储区空间无法收回，称为 （2） 。这部分空间必须在 （3） 才能找回，这是因为无名对象的生命期 （4） 。 答案：（1）返回一个空指针（NULL）

（2）内存泄漏

（3）重新启动计算机后

（4）并不依赖于建立它的作用域

7.1.5 按语义的默认复制构造函数和默认复制赋值操作符实现的复制称为 （1） ，假设类

对象obj中有一个数据成员为指针，并为这个指针动态分配一个堆对象，如用obj1按成员语义拷贝了一个对象obj2，则obj2对应指针指向 （2） 。 答案：（1）浅拷贝

（2）同一个堆对象

7.1.6 单链表的结点包含两个域： （1） 和 （2） 。使用链表的最大的优点是 （3） ，即使是动态数组也做不到这一点。 答案：（1）数据域

（2）指针域

（3）用多少空间，开多少空间

第七章 动态内存分配习题 2

7.1.7 进入单链表必须通过单链表的 （1） ，如果它丢失则 （2） ，内存也 （3） ，在单链表中进行的查找只能是 （4） 。 答案：（1）头指针

（2）链表整个丢失 （3）会发生泄漏 （4）顺序查找

7.1.8 对链栈，链的生成必须是向 （1） 生成，最新压栈的元素（结点），放在 （2） 位置，弹出时从 （3） 删除结点。对链队，采用向 （4） 生成，新入队的结点放在链的 （5） ，出队操作在 （6） 位置。 答案：（1）向前

（2）链表头的位置 （3）链表头 （4）向后 （5）尾部 （6）链表头

7.1.9 在计算机中进行表达式的计算，为解决优先级和运算的结合性，必须使用 （1） 和

（2） 。在中缀表达式中，每个双目运算符放在 （3） 。 答案：（1）数栈

（2）运算符栈

（3）它的两个运算符之间

7.1.10 为了能重复利用一个队空间，要求把队说明成一个逻辑上的 （1） 。 答案：（1）循环队列

7.1.11 二叉树的特点是： （1） 和 （2） 。 答案：（1）每个结点最多有两个孩子

（2）子树有左右之分

7.1.12 二叉树的遍历是按 （1） 分类，所谓中序遍历是 （2） 。 答案：（1）访问子树根节点次序

（2）先遍历该子树根结点的左子树回来后，接着再访问根结点，最后遍历右子树

7.1.13 二叉排序树又称 （1） 或 （2） 。其左子树上的所有结点均小于根结点的数据值，而右子树上的所有结点均大于根结点的数据值时，采用 （3） 就可以得到一个 （4） 。 答案：（1）二叉搜索树

（2）树表

（3）中序遍历 （4）升序序列

7.2 简答题

7.2.1 new运算符为一个变量或对象分配存储空间和为一个数组分配存储空间，使用方法

第七章 动态内存分配习题 3

上有什么不同？对应的delete运算符使用有什么不同？

答：为一个变量或对象分配存储空间其使用的格式如下： 指针变量名=new 类型名(初始化式)；

对于数组进行动态分配和撤销的格式为：

指针变量名=new 类型名[下标表达式];

后者多一个[下标表达式]，同时不能进行初始化。 对应的delete运算符使用分别为： delete 指针名;

delete [ ] 指向该数组的指针变量名;

后者多一个方括号，如果delete语句中少了方括号，因编译器认为该指针是指向数组第一个元素的指针，会产生回收不彻底的问题（只回收了第一个元素所占空间），加了方括号后就转化为指向数组的指针，回收整个数组。delete [ ]的方括号中不需要填数组元素数，系统自知。即使写了，编译器也忽略。

7.2.2 用delete删除p所指向的无名对象时，p指针也同时被删除了，对不对？为什么？ 答：不对。注意这时释放了p所指向的无名对象占用的内存空间，也就是撤销了该无名对象，称动态内存释放（dynamic memory deallocation），但指针p本身并没有撤销，它仍然存在，该指针所占内存空间并未释放。

7.2.3 为什么动态建立类对象数组时，类的定义一定要有缺省的构造函数？

答：new后面类（class）类型也可以有参数。这些参数即构造函数的参数。但对创建数组，没有参数，只能调用缺省的构造函数。

7.2.4 要实现深拷贝，自定义的拷贝构造函数应该怎样设计？

答：如果类中有一个数据成员为指针，该类的一个对象中的这个指针p，指向了动态分配的一个堆对象。深拷贝时要给新建立的对象独立分配一个堆对象。这时拷贝的构造函数应该设计为：先拷贝对象主体，再为新建对象的指针分配一个堆对象，最后用原对象的堆对象拷贝新对象的堆对象。即分三步完成。

7.2.5 在单链表模板中为什么要把List类说明成Node的友元类？ 答：为了直接访问结点的私有成员数据，以简化程序。

7.2.6 双向链表与单向链表相比，操作上有什么优点?

答：双向链表可以很方便地找到表结点的前驱和后继。单链表只能找后继。如要找前驱，必须从表头开始搜索，并一般要用两个工作指针。

7.2.7 对比顺序栈与链栈各自的长处和短处。

答：顺序栈可以随机访问其中的元素，而链栈只能顺序访问。顺序栈必须先开一定大小内存空间，执行起来简单，速度快，但可能溢出。链栈内存空间随用随开，不会溢出，但执行复杂（不断地动态分配），速度慢。

7.2.8 写出二叉树的定义。

答：二叉树是结点的一个有限集合，该集合或为空，或是由一个根结点及两棵分别称为左子树和右子树的（注意有左右之分）互不相交的二叉树组成，其中左右子树分别可以为空子树

第七章 动态内存分配习题 4

或均为空树。

7.2.9 什么是二叉树的遍历？

答：所谓二叉树的遍历（binary tree traversal），就是遵从某种次序，查巡二叉树的所有结点，每个结点都被访问一次，而且仅访问一次。所谓“访问”指对结点施行某些操作，但不破坏它原来的数据结构。

二、编程与综合练习题

7.3 给单链表类模板增加两个成员函数：删除链表中所有数据域为指定值的结点和取出链

表中第K个元素（从1开始计数）。

解：这两个成员函数添在单链表类模板中（ep7_3.h） 本例数据域用了标准类string，也可以使用整数型。 //ep7_3.h

#include using namespace std;

//首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数作为成员函数 templateclass List; templateclass Node{ T info; //数据域 Node *link; //指针域 public: Node(); //生成头结点的构造函数 Node(const T & data);//生成一般结点的构造函数 void InsertAfter(Node* P); //在当前结点后插入一个结点 Node* RemoveAfter(); //删除当前结点的后继结点，返回该结点备用 T & Getinfo();//增加取数据域函数 friend class List; //以List为友元类，List可直接访问Node的私有函数，与结构一样方便，但更安全 };

template Node::Node(){link=NULL;} template Node::Node(const T & data){ info=data; link=NULL; }

templatevoid Node::InsertAfter(Node* p){ p->link=link; link=p; }

templateNode* Node::RemoveAfter(){ Node* tempP=link; if(link==NULL) tempP=NULL; //已在链尾,后面无结点 else link=tempP->link; return tempP; }