1、第六章 模板与数据结构题第6章模板与数据结构习题一、.基本概念与基础知识自测题6.1 填充题6.1.1 模板是为了实现代码的 （ 1 ） ，它把数据类型改为一个 （ 2 ） ，称为 （ 3 ）程序设计。模板包括 （ 4 ） 和 （ 5 ） 。答案：（1）重用（2）设计参数（3）参数化(parameterize)（4）函数模板(function template)（5）类模板(class template)6.1.2 调用函数模板时，可以显式指定模板参数类型，也可以隐式进行，称为 （ 1 ） ，这是根据 （ 2 ） 来决定的。答案：（1）模板实参推演(template argument dedu
2、ction)（2）一组实际类型或（和）值6.1.3 顺序查找可以用于 （ 1 ） 线性表，而对半查找可以用于 （ 2 ） 线性表。答案：（1）无序的（所有）（2）有序的6.1.4 最常见的排序方式有 （ 1 ） 、 （ 2 ） 和 （ 3 ） 。如果现有一个已排好序的线性表，在表尾添加了一个元素，采用 （ 4 ） 排序法使它重新成为有序的所需工作量最小。答案：（1）选择（2）插入（3）交换（4）交换（可利用 来的有序性）6.1.5 以 指 的 方式：指 一个4元素 型数组的指 为 （ 1 ） 指 一个型数，参数为 个 型数的函数的指 （ 2 ） 指 一个数组的指 ，而数组元素 是指 一个 型指
3、 的无参函数 （ 3 ） 。答案：（1）int(*p)4（2）int(*p)(int,int)（3）以指 6元素数组为 ：int*(*)() (*p)66.2 答题6.2.1 需 一个对 数组 用的 法（ 的 小 定）， 把实参 数组的 函数currency1答：最“方法是用函数模板， 数组用模板类型参数， 的 小作为参数。也可以用一 数组加 的 小 作为参数。6.2.2 函数模板模板函数类模板模板类答：fifl数据类型 的 用型的函数使代码的可重用性 。把数据类型改为1第六章 模板与数据结构题一个设计参数是一个可行的方案。这程序设计类型称为参数化(Parameterize) 程序设计。这的
4、模模板(Template) 构。包括函数模板和类模板。函数模板定”如 ：template 类型 函数(式参数表);/函数 模板参数 是模板类型参数。模板类型参数代表一 在的或用定”的类型，typename或class加一个识 构成。函数模板可以用来一个 用 的函数，以 fi参， 化重函数的设计。调用函数模板(functron template) 而 成的函数，称为模板函数(template function)。类模板定”如 ：template class 类;/类 ;模板参数有 ：模板类型参数和模板 类型参数。模板类型参数(template typeparameter)，它代表一类型， typ
5、ename或class加一个识 。模板 类型参数一个 的参数 构成。模板 类型参数表 参数代表了一个 在的常量。如数组类模板，可以有一个数组 的 类型参数。为 用的类模板定”的模板类型参数指定了 类型而 成的类称为模板类。6.2.3 线性表 基本 作包括 插入一个元素的在 答：线性表是数据结构的概念： 个 元素 有 和 的。这第一个元素， 元素有 有一个 ，第一个元素 有 最一个元素， 元素有 有一个 ，最一个元素无 。这 的 性称为线性。基本 作包括：计 表 ，找 量或对 x（ 类型与表元素 ）在表的 （ 值）， x是 在表，x，x插入表第i个 ，找x的 ，找x的 ， 表是 ， 表是 ， 第
6、i个元素的值 。需 在顺序表的指定 i插入一个数据x时，必须为它腾 这个 ，把从 开始 的所有元素数据，移一个 ，最 插入。是移时从最一个元素开始。 则先移的数据会冲掉 移的数据。6.2.4 采用索引查找有 优点它需 被查找数据有序吗答：索引，就 一本书的目录，找题，再看一 页号，立 可以翻。索引查找fi 求被查找数据有序，只 求索引有序。6.2.5 单叙述阅读理解复杂指 的方法。设Node为类， 面 个识 fa和pa分别代表Node* (*fa(int)(); Node* (*(*pa)();答：理解和构对 的方法是：先撇开识 ，按从右左的顺序逐个解释 个 ，如果有括号则改 解释的先，先解释
7、括号再解释括号。fa是有一个 型参数的函数， 值是指 ， 指 是指 无参函数的指 ，而 无参函数的 值是指 Node类的指 。pa是指 数组的指 ， 数组的元素均为函数指，所指 的函数无参、 值是指 Node类的指 。 二、. 程与综合练习题2第六章 模板与数据结构题6.3 使用自定” 串类， 求数组元素最 值的函数模板。解：函数模板有三应用方式：1类模板的成员函数，在模板类型参数重函数和运 ， 访问私有数据成员，实现 用 法。这是准的面 对 的方法。2函数模板处理模板类，以类模版为参数，用模板类型参数重的函数或运 ，实现用 法。但调用类模板的 口函数 访问私有数据成员，也是常见的。3函数模板
8、处理 数据，往往 用函数作为参数，实现 用 法。这是面 过程的方法。解：使用独立的函数模板，相对简单。#includeusing namespace std;const int n=256;class mystring/为简单只保留用到的函数char strn; /存放字符串的数组容器int maxsize; /最大可用元素数，可防止数组出界，提高健壮性int last; /已用元素数public:mystring()last=-1;maxsize=n;str0=0;coutGroap max(Groap *r_array,int size)/这里是一个独立的函数模板Groap max_val
9、=r_array0;for (int i=1;i(ms,6).show();return 0;6.4 自定” 串类用于对半查找的函数模板。解1：为 化，使用独立的函数模板#includeusing namespace std;const int n=256;class mystring/为简单只保留用到的函数char strn; /存放字符串的数组容器int maxsize; /最大可用元素数，可防止数组出界，提高健壮性int last; /已用元素数public:mystring()last=-1;maxsize=n;str0=0;cout int BinarySearch(T *array
10、,T / size 当 序 元素数 while(lowusing namespace std;const int n=256;class mystring/为简单只保留用到的函数char strn; /存放字符串的数组容器int maxsize; /最大可用元素数，可防止数组出界，提高健壮性int last; /已用元素数public:mystring()last=-1;maxsize=n;str0=0;coutclass Orderedlistint maxsize;int last;T slistsize;public:int getlast()return last;T getslist
11、(int k)return slistk;void putslist(T t,int k)slistk=t;Orderedlist()last=-1;maxsize=size;bool Insert(T void print();int BinarySearch(T);/ 函数省 ,缺省的= 不必定义;/出 不可template bool Orderedlist:Insert(T elselast+;for (int j=last;ji;j-) slistj=slistj-1;slisti=elem;return true;template void Orderedlist:print()in
12、t i;for(i=0;i int Orderedlist:BinarySearch(T x)/ 函数模板int high=last,low=0,mid; /size当 序 元素数 while(low ordlist;mystring nh;char sph10=“东南大学“,“复旦大学“,“交通大学“,“南京大学“,“清华大学“,“天津大学“,“currency1大学“,“大学“;for(i=0;i#includeusing namespace std;template class Orderedlistint maxsize;int last;T slistsize;public:Orderedlist()last=-1;maxsize=size;void BubbleSort();bool Insert(T void print();/ 函数省 ,缺省的= 不必定义;/出 不可template bool Orderedlist:Insert(T elselast+;for (int j=last;ji;j-) slistj=slistj-1;slisti=elem;return true;10
