PAGE
8
第六章 模板与数据结构题
第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 deduction)
（2）一组实际类型或（和）值
6.1.3 顺序查找可以用于 （1） 线性
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
，而对半查找可以用于 （2） 线性表。
答案：（1）无序的（所有）
（2）有序的
6.1.4 最常见的排序方式有 （1） 、 （2） 和 （3） 。如果现有一个已排好序的线性表，在表尾添加了一个元素，采用 （4） 排序法使它重新成为有序的所需工作量最小。
答案：（1）选择
（2）插入
（3）交换
（4）交换（可利用原来的有序性）
6.1.5 给出以下指针的说明方式：指向一个4元素整型数组的指针为 （1） ；指向一个返回整型数，参数为两个整型数的函数的指针 （2） ；指向一个数组的指针，而该数组元素都是指向一个返回整型指针的无参函数 （3） 。
答案：（1）int(*p)[4]
（2）int(*p)(int,int)
（3）以指向6元素数组为例：int*(*)() (*p)[6]
6.2简答题
6.2.1 需要编写一个对多维数组通用的算法（即各维的大小未定），怎样才能把实参多维数组的信息全部传递到函数中去？
答：最佳
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
是用函数模板，多维数组用模板类型参数传递，各维的大小作为参数传递。也可以用一维数组加各维的大小都作为参数传递。
6.2.2 什么叫函数模板？什么叫模板函数？什么叫类模板？什么叫模板类？
答：不受数据类型限制的通用型的函数使代码的可重用性大大提高。把数据类型改为一个设计参数是一个可行的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。这种程序设计类型称为参数化(Parameterize) 程序设计。这样的软件模块由模板(Template) 构造。包括函数模板和类模板。
函数模板定义如下：
template<模板参数表> 返回类型 函数名(形式参数表){
……;//函数体
}
模板参数主要是模板类型参数。模板类型参数代表一种潜在的内置或用户定义的类型，由关键字typename或class后加一个标识符构成。函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，简化重载函数的设计。
由调用函数模板(functron template) 而生成的函数，称为模板函数(template function)。
类模板定义如下：
template<模板参数表> class 类名{
……;//类声明体
};
模板参数有两种：模板类型参数和模板非类型参数。模板类型参数(template type parameter)，它代表一种类型，由关键字 typename或class后加一个标识符。模板非类型参数由一个普通的参数声明构成。模板非类型参数表示该参数名代表了一个潜在的常量。如数组类模板，可以有一个数组长度的非类型参数。
为通用的类模板定义中的模板类型参数指定了具体类型而生成的类称为模板类。
6.2.3 什么叫线性表？其基本操作包括哪些？其中插入一个元素的关键在哪儿？
答：线性表是数据结构中的概念：每两个相邻元素之间都有直接前驱和直接后继的关系。这里除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱；除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素无后继。这样的特性称为线性关系。
基本操作包括：计算表长度，寻找变量或对象x（其类型与表元素相同）在表中的位置（下标值），判断x是否在表中，删除x，将x插入列表中第i个位置，寻找x的后继，寻找x的前驱，判断表是否空，判断表是否满，取第i个元素的值等。
当需要在顺序表的指定位置i插入一个数据x时，必须为它腾出这个位置，把从该位置开始向后的所有元素数据，后移一个位置，最后才插入。关键是后移时从最后一个元素开始。否则先移的数据会冲掉未移的数据。
6.2.4 采用索引查找有哪些优点？它需要被查找数据有序吗？
答：索引，就象一本书的目录，找到标题，再看一下页号，立即可以翻到。索引查找不
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
被查找数据有序，只要求索引有序。
6.2.5 简单叙述阅读理解复杂指针的方法。设Node为类，下面两个标识符fa和pa分别代表什么？Node* (*fa(int))(); Node* (*(*pa)[])();
答：理解和构造对象说明的方法是：先撇开标识符，按从右到左的顺序逐个解释每个说明符，如果有括号则改变解释的先后，先解释括号内再解释括号外。
fa是有一个整型参数的函数，其返回值是指针，该指针是指向无参函数的指针，而该无参函数的返回值是指向Node类的指针。pa是指向数组的指针，该数组的元素均为函数指针，所指向的函数无参、返回值是指向Node类的指针。
二、.编程与综合练习题
6.3 使用自定义字符串类，编写求数组元素中最大值的函数模板。
解：函数模板有三种应用方式：
1．类模板的成员函数，在模板类型参数中重载函数和运算符，直接访问私有数据成员，实现通用算法。这是
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
的面向对象的方法。
2．函数模板处理模板类，以类模版为参数，用模板类型参数中重载的函数或运算符，实现通用算法。但调用类模板的接口函数间接访问私有数据成员，也是常见的。
3．函数模板处理普通数据，往往要用函数作为参数，实现通用算法。这是面向过程的方法。
解：使用独立的函数模板，相对简单。
#include
using namespace std;
const int n=256;
class mystring{//为简单只保留用到的函数
char str[n]; //存放字符串的数组容器
int maxsize; //最大可用元素数，可防止数组出界，提高健壮性
int last; //已用元素数
public:
mystring(){
last=-1;
maxsize=n;
str[0]='\0';
cout<<"缺省构造函数"<Groap max(Groap *r_array,int size){//这里是一个独立的函数模板
Groap max_val=r_array[0];
for (int i=1;i(ms,6)).show();
return 0;
}
6.4 将自定义字符串类用于对半查找的函数模板。
解1：为简化，使用独立的函数模板
#include
using namespace std;
const int n=256;
//class mystring定义略
template int BinarySearch(T *array,T & x,int size){//独立的函数模板
int high=size-1 ,low=0,mid; // size 当前有序表元素数量
while(low<=high){
mid=(low+high)/2;
if(x
using namespace std;
const int n=256;
//class mystring定义略
template class Orderedlist{
int maxsize;
int last;
T slist[size];
public:
int getlast(){return last;}
T getslist(int k){return slist[k];}
void putslist(T t,int k){slist[k]=t;}
Orderedlist(){last=-1;maxsize=size;}
bool Insert(T & elem,int i);
void print();
int BinarySearch(T);
// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
template bool Orderedlist::Insert(T & elem ,int i){
if (i<0||i>last+1||last==maxsize-1) return false;
else{
last++;
for (int j=last;j>i;j--) slist[j]=slist[j-1];
slist[i]=elem;
return true;
}
}
template void Orderedlist::print(){
int i;
for(i=0;i<=last;i++){
slist[i].show();
if(i%5==4) cout< int Orderedlist::BinarySearch(T x){//成员函数模板
int high=last,low=0,mid; //size当前有序表元素数量
while(low<=high){
mid=(low+high)/2;
if(x ordlist;
mystring n[h];
char sp[h][10]={"东南大学","复旦大学","交通大学","南京大学","清华大学",
"天津大学","同济大学","浙江大学"};
for(i=0;i
#include
using namespace std;
template class Orderedlist{
int maxsize;
int last;
T slist[size];
public:
Orderedlist(){last=-1;maxsize=size;}
void BubbleSort();
bool Insert(T & elem,int i);
void print();
// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
//Insert(T & elem ,int i)和print()不再重复定义
template void Orderedlist::BubbleSort(){//降序
bool noswap;
int i,j;
T temp;
for (i=last;i>0;i--){//从上往下冒泡，对比例6.8有何不同？
noswap=true;
//未交换标志为真
for(j=0;j ordlist;
string n[h];
string sp[h]={"南京大学","东南大学","交通大学","清华大学",
"天津大学","复旦大学","浙江大学","同济大学"};
for(i=0;i
#include
using namespace std;
template class Orderedlist{
int maxsize;
int last;
T slist[size];
public:
Orderedlist(){last=-1;maxsize=size;}
void BubbleSort();
bool Insert(T & elem,int i);
void print();
void Merge(Orderedlist &,Orderedlist &);
// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
//Insert(T & elem ,int i)和print()不再重复定义
template void Orderedlist::BubbleSort(){//升序
bool noswap;
int i,j;
T temp;
for (i=last;i>0;i--){//从上往下冒泡，对比例6.8有何不同？
noswap=true;
//未交换标志为真
for(j=0;j void Orderedlist::Merge(Orderedlist & ls1,Orderedlist & ls2){
int i=0,j=0,k=0;
while((i<=ls1.last)&&(j<=ls2.last)){
if(ls1.slist[i] ordlist,ordlist1,ordlist2;
string n[h],m[h];
char sp1[h][10]={"南京大学","东南大学","交通大学","清华大学",
"天津大学","复旦大学","浙江大学","同济大学"};
for(i=0;i
#include
using namespace std;
template class Orderedlist{
int maxsize;
int last;
T slist[size];
void Shellinsert(const int);
public:
int getlast(){return last;}
T getslist(int k){return slist[k];}
void putslist(T t,int k){slist[k]=t;}
Orderedlist(){last=-1;maxsize=size;}
bool Insert(T & elem,int i);
void print();
void Shellsort();
// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
template bool Orderedlist::Insert(T & elem ,int i){
if (i<0||i>last+1||last==maxsize-1) return false;
else{
for (int j=last;j>i;j--) slist[j]=slist[j-1];
slist[i]=elem;
last++;
return true;
}
}
template void Orderedlist::print(){
int i;
for(i=0;i<=last;i++){
cout< void Orderedlist::Shellsort(){//成员函数
int gap=(last+1)/2;
while(gap){
Shellinsert(gap);//一趟排序
gap/=2;
}
}
template void Orderedlist::Shellinsert(const int gap){
int i,j;
T temp;
//注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号，
//插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。
for(i=gap;i<=last;i++){//从第一个子序列开始直接插入排序，但不是完成一个子序列，
//再做下一个子系列，而是先做每个子序列的第一步，再做每个子序列的第二步，等等，
//穿插完成。直接插入排序总是从后逐个向前，找到第一个比待插元素大的，则插在前面。
temp=slist[i];//待插元素放temp中
j=i;
while(j>=gap&&temp ordlist;
string n[h];
char sp[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
"浙江大学","同济大学"};
for(i=0;i
#include
using namespace std;
template class Orderedlist{
int maxsize;
int last;
T slist[size];
public:
int getlast(){return last;}
T getslist(int k){return slist[k];}
void putslist(T t,int k){slist[k]=t;}
Orderedlist(){last=-1;maxsize=size;}
bool Insert(T & elem,int i);
void print();
// 无关成员函数省略,缺省的=等不必定义
};//再次指出分号不可少
template bool Orderedlist::Insert(T & elem ,int i){
if (i<0||i>last+1||last==maxsize-1) return false;
else{
for (int j=last;j>i;j--) slist[j]=slist[j-1];
slist[i]=elem;
last++;
return true;
}
}
template void Orderedlist::print(){
int i;
for(i=0;i<=last;i++){
cout< void Shellsort(Orderedlist & list){//非成员函数，仅以表模板类为参数
int gap=(list.getlast()+1)/2;
while(gap){
Shellinsert(list,gap);//一趟排序
gap/=2;
}
}//int size必须保留
template void Shellinsert(Orderedlist & list,const int gap){
int i,j;
T temp;
//注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号，
//插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。
for(i=gap;i<=list.getlast();i++){//从第一个子序列开始直接插入排序，但不是完成一个
//子序列，再做下一个子系列，而是先做每个子序列的第一步，再做每个子序列的第二步，
//等等,穿插完成。直接插入排序总是从后逐个向前,找到第一个比待插元素大的,则插在前面。
temp=list.getslist(i);//待插元素放temp中
j=i;
while(j>=gap&&temp ordlist;
string n[h];
char sp[h][10]={"南京大学","东南大学","交通大学","清华大学","天津大学","复旦大学",
"浙江大学","同济大学"};
for(i=0;i
本文档为【vc++习题答案C++第六章习题解答】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483