数据结构习题解答
计算机科学与工程学院
2004年10月
第0章C++基础
一、基本概念题
0-1函数和成员函数有什么区别？
[解]: C++中有两种类型函数：常规函数和成员函数.二者既有区别又有联系。
（1）二者作用不同：
常规函数通常用于表示一个特定的功能；成员函数用于某个特定类方法的定义。
（2）二者定义方法不同：
常规函数通常可以存放在程序的任意位置；成员函数只能用于存放在特定类的实现文件中。（3）二者的调用规则不同：
常规函数通常可以在其作用域内的任意调用；成员函数必须通过特定类或特定类的实例调用。
（4）二者的作用域不同：
常规函数通常具有全局作用域内；成员函数必须则具有封装性、继承性和多态性等特征。
0-2在函数中，什么叫输入型参数？什么叫输出型参数？
[解]:
输入型参数：是指调用函数只通过该参数传送数据给被调用函数，被调用函数在执行过程中对该参数的修改不能传递给调用函数；
输出型参数：是指调用函数只通过该参数把被调用函数处理后得到的结果数据传送给调用函数，由于这样的参数是从被调用函数得到数据的，所以称为输出型参数.
0-3什么叫引用？函数的引用类型参数是怎样实现输出型参数功能的？
[解]:
所谓引用是给变量或对象起一个别名，即引用引人了一个变量或对象的同义词.
由于函数被调用时，函数的引用类型参数传递给被调用函数的是调用函数中某个对象（实际参数）的引用，所以被调用函数种任何给引用参数的赋值就是给实际参数的赋值，所以引用参数能实现输出型参数的功能.
0-4一个成员函数的参数类型为引用类型和常值引用类型有什么不同？
[解]:C++中函数(包括常规函数和成员函数)的参数有四种方式：值参数、常值参数、引用参数和常值引用参数方式.
其中，值参数、常值参数和常值引用参数均为输入型参数。即这些参数方式的函数调用不会改变对应形式参数的实际参数的值.但他们又各有不同的特点：
值参数方式在运行时对应的实际参数的值拷贝给形式参数，被调用函数可以修改形式参数的值，当函数终止时，形式参数的值不拷贝回实际参数。
常值参数方式在运行时将对应的实际参数的值拷贝给形式参数，被调用函数不能修改形式参数的值.
常值引用参数方式在运行时将对应的实际参数的引用（地址）拷贝给形式参数，被调用函数不能修改形式参数的值.
所以，当参数的存储空间较大时，常值引用参数方式将更节省存储空间和运行时间。
0-5一个成员函数的返回值类型为引用类型和常值引用类型有什么不同？
[解]:当成员函数返回值为引用方式时，由于引用型变量不是单独定义的，所以该成员函数返回值是一个已存在变量(或对象)的别名.当该成员函数被重新赋值时则其对应的变量(或对象)值将改变.
当成员函数返回值为常值引用方式时，其返回值和引用方式的成员函数返回值类同，只是该成员函数返回值不能被重新赋值.
0-6函数的返回值是全局变量还是局部变量？函数中能否用函数的返回值给其他变量对象
赋值？为什么？
[解]:函数的返回值属于全局变量. 函数中可以用函数的返回值给其他变量对象赋值。
0-7什么叫类？一个类中主要包括哪两部分？
[解]:类是对具有相同属性和相同方法的一组对象的抽象.
类定义包括类中成员变量(或称属性)的定义和成员函数(或称方法)的定义.C++中使用标识符class定义类。
0-8类有哪几种访问权限？各种访问权限的定义有什么不同？
[解]:类的成员变量和成员函数有三种访问权限：私有(private)、公有(public)和保护(protected).
其中私有权限（private）成员是外部不可见的，只能由该类对象的成员函数以及被声明为友元的函数或声明为友元的类的对象的成员函数访问.
公有权限 (public)成员都是外部程序可见的.公有部分中的成员变量和成员函数既允许该类对象的成员函数访问，也允许程序中其他函数或其他类的对象的成员函数访问.一个类的公有部分构成了这个类的操作界面.外部函数和对象通过该操作界面对该类对象进行操作.
保护权限(protected)成员和私有权限(private)成员一起构成类的私有部分，保护权限(protected)成员允许该类的派生类访问.
0-9类的构造函数是什么时候执行的？类的析构函数是什么时候执行的？
[解]:构造函数是当定义对象时被自动调用的特殊成员函数，用来在内存中建立类的具体对象(即在内存中为该对象分配适当的空间)并对其进行初始化赋值的成员函数.
析构函数是当对象被撤销时被自动调用的特殊成员函数.当一个对象被撤销时，析构函数提供了释放该类对象占用内存空间的方法.
0-10什么叫重载？在软件设计中，类的成员函数重载有什么作用？
[解]:重载就是两个或两个以上的函数(或运算符)使用相同的名字.
重载功能除了可以增强函数设计和类设计的灵活性和通用性以外，还可以支持类的多态性.
0-11什么叫友元？哪些成分可以定义为一个类的友元？
[解]:
在C++中，一个类的友元可以存取这个类的私有成分. 一个类的友元可以是其他类的成员函数、外部函数和其他类.
0-12派生类有哪几种派生方式？
[解]:派生类的派生方式主要有public派生方式和private派生方式两种.
0-13什么叫多态性？什么叫虚函数？
[解]:多态性是指当相同对象收到不同的消息或不同对象收到相同的消息时产生不同的方法调用的特性.
C++支持两种多态性：
一种是编译时的多态性，编译时的多态性是指这种多态性在编译时即进行了确认和绑定.编译时的多态性是通过重载函数来实现的.
另一种是运行时的多态性. 运行时的多态性是指这种多态性在运行时才进行识别和绑定.
虚函数是在基类中被说明为virtual，并在派生类中重新定义的成员函数.系统在识别到虚函数时，在运行时才决定当前实际调用的是基类中的成员函数还是派生类中的成员函数，因此，虚函数实现多态性的方法也可看做是成员函数的动态重载.
0-14什么叫纯虚函数？什么叫抽象类？
[解]:纯虚函数是在基类中说明的虚函数，它在基类中没有定义，但要求任何派生类都要定义各自的实现方法.
包含有纯虚函数的类称为抽象类.由于抽象类包含了没有函数定义的纯虚函数，所以不允许定义抽象类的对象.
0-15抽象数据类型和模板各自是怎样实现程序的通用化设计的？
[解]:在C++中，实现通用化的软件设计的方法主要有抽象数据类型法和模板法.
抽象数据类型方法是在定义类时，其成员变量的数据类型使用抽象数据类型，当应用程序具体包含该类头文件前再对该抽象数据类型进行具体定义.
模板方法是把函数或类中的数据类型作为参数设计模板函数或模板类，经过参数实例化，变为一个类型参数具体的函数或类的实例，完成具体的功能.
0-16什么叫静态内存分配？什么叫动态内存分配？动态内存分配有什么优点？
[解]:程序中使用的数组元素个数或占用内存单元的大小是在程序编译时就确定的，因此在程序运行时这些数组的元素个数或占用内存单元的大小是确定的，这种内存分配方法称做静态内存分配.
静态内存分配的缺点是程序中数组个数或占用内存单元的大小是固定的，在程序运行过程中不能修改.
动态内存分配是在程序运行时确定数组元素个数或占用内存单元的大小，从而可在程序运行时根据需要分配内存空间.
0-17写出new运算符的语法格式和delete运算符的语法格式.
[解]:new运算符的语法格式为：
new类型名(初始值);
其中，类型名指定了要分配存储空间的类型.
delete运算符用于释放单个对象内存空间的语法格式为：
delete指针;
delete运算符用于释放对象数组内存空间的语法格式为：
delete［］指针;
二、上机实习．
0-18定义和实现复数的C+＋类．要求：
(1)复数的数据城包括复数的实部和虚部，复数的实部和虚部定义为浮点数.
(2)构造函数包括三个：第一个构造函数没有参数．第二个构造函数有一个参数，即把一个浮点数赋给复数的实部，复数的虚部为0;第三个构造函数有两个参数，即把两个浮点数分别赋给复数的实部和复数的虚部.
(3)复数的成员函数包括获取和修改复数的实部和虚部.
(4)复数的成员函数还包括运算符重载形式的复数的+、-、*、／运算.
(5)定义友元形式的重载的流函数来输入一个复数和输出一个复数.
[解]:
class Complex
{
private:
float mRealPart; //数据成员实部
float mVirtualPart; //数据成员虚部
public:
Complex(void); //构造函数一
Complex(float realPart); //构造函数二
Complex(float realPart, float virtualPart); //构造函数三
float GetRealPart(); //返回实部数据成员
float GetVirtualPart(); //返回虚部数据成员
void SetRealPart(float RealPart); //设置实部数据成员
void SetVirtualPart(float virtualPart); //设置虚部数据成员
float Mod(); //返回复数的模
Complex & operator + (Complex c); //重载复数的加法运算
Complex & operator - (Complex c); //重载复数的减法运算
Complex & operator * (Complex c); //重载复数的乘法运算
Complex & operator / (Complex c); //重载复数的除法运算
//操作符>><<重载,定义为友元函数
friend ostream& operator<<（ostream& ostr，ComPlex & c);
friend istream& operator>>（istream& istr，ComPlex & c);
};
Complex::Complex(void)
{
mRealPart=mVirtualPart=0;
}
Complex::Complex(float realPart)
{
mRealPart= realPart;
mVirtualPart=0;
}
Complex::Complex(float realPart, float virtualPart)
{
mRealPart= realPart;
mVirtualPart= virtualPart;
}
float Complex::GetRealPart()
{
return mRealPart;
}
float Complex::GetVirtualPart()
{
return mRealPart;
}
void Complex::SetRealPart(float realPart)
{
mRealPart= realPart;
}
void Complex::SetVirtualPart(float virtualPart)
{
mVirtualPart= virtualPart;
}
Complex & Complex::operator+(Complex c)
{
Complex *result=new Complex();
result->mRealPart=mRealPart+c.mRealPart ;
result->mVirtualPart =mVirtualPart+c.mVirtualPart;
return *result;
}
Complex & Complex::operator-(Complex c)
{
Complex *result=new Complex();
result->mRealPart=mRealPart-c.mRealPart ;
result->mVirtualPart =mVirtualPart-c.mVirtualPart;
return *result;
}
Complex & Complex::operator*(Complex c)
{
Complex *result;
result=new Complex();
result->mRealPart=mRealPart*c.mRealPart- mVirtualPart*c.mVirtualPart;
result->mVirtualPart =mRealPart*c.mVirtualPart+ mRealPart*c.mVirtualPart;
return *result;
}
Complex & Complex::operator/(Complex c)
{
Complex *result=new Complex();
float m;
m=c.Mod();
if (m==0)
exit(0);
result->mRealPart=(mRealPart*c.mRealPart+ mVirtualPart*c.mVirtualPart)/m;
result->mVirtualPart =(mRealPart*c.mVirtualPart- mRealPart*c.mVirtualPart)/m;
return *result;
}
float Complex::Mod()
{
return sqrt(mRealPart*mRealPart+mVirtualPart*mVirtualPart);
}
ostream& operator<<（ostream& ostr，const Complex & c)
//输出流操作符<<重载
{
cout<<“实部:“<< c.mRealPart;
cout<<“虚部:“<< c.mVirtualPart< return ostr; } istream& operator>>（istream& istr，Complex & c) //输入流操作符>>重载 { cout<<”输入实部：” cin>>c.mRealPart; cout<<”输入虚部：” cin>>c.mVirtualPart; return istr; } 第1章数据结构绪论 1-1什么叫数据？什么叫数据元素？什么叫数据项？ [解]:数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。 表示一个事物的一组数据称做一个数据元素； 构成数据元素的数据称做该数据元素的数据项。 1-2什么叫数据的逻辑结构？什么叫数据的存储结构？什么叫数据的操作？ [解]:数据元素之间的相互联系方式称为数据的逻辑结构。数据元素在计算机中的存储方式称为数据的存储结构。对一种数据类型的数据进行的某种处理称做数据的操作；对一种数据类型的数据进行的所有操作称做数据的操作集合。 1-3数据结构课程主要讨论哪三个方面的问题？ [解]:数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型的常用数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。 1-4分别画出线性结构、树结构和图结构的逻辑示意图。 [解]: 1-5什么叫类型？什么叫数据类型？什么叫抽象数据类型？ [解]: 类型是一组值的集合。数据类型是指一个类型和定义在这个类型上的操作集合。抽象数据类型(Abstract Data Type, ADT)是指一个逻辑概念上的类型和这个类型上的操作集合。 1-6怎样利用抽象数据类型设计大型软件？ [解]:抽象数据类型使软件设计成为工业化流水线生产的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司(或专门设计人员)设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；另一方面，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司(或专门设计人员)可以安全、快速、方便地完成该应用软件系统的设计。 软件的设计采用模块化方法，抽象数据类型(如表、堆栈、队列、串、数组、树、二叉树、图等)就是构造大型软件的最基本模块。用这些专门公司设计好的抽象数据类型，就可以安全、快速、方便地设计功能复杂的大型软件。 数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等抽象数据类型的基本功能和实现方法。在C++语言中，类就是确定了数据元素存储结构的抽象数据类型的具体实现。 1-7什么叫算法？算法的5个性质是什么？ [解]:算法是描述求解问题方法的操作步骤集合。 算法满足以下性质： (1) 输入性：具有0个或若干个输入量； (2) 输出性：至少产生一个输出或执行一个有意义操作； (3) 有限性：执行语句的序列是有限的；图1-4例1-2算法实现方法图示 (4) 确定性：每一条语句的含义明确，无二义性； (5) 可执行性：每一条语句都应在有限的时间内完成。 1-8根据算法的性质解释算法和程序的区别。 [解]:程序和算法的惟一区别是程序允许无限循环，而算法不允许无限循环。 1-9评判算法的优劣有哪几种方法？ [解]:算法设计应满足以下5个目标： (1)正确性：算法应确切地满足具体问题的需求，这是算法设计的基本目标。 (2)可读性：算法的可读性有利于人们对算法的理解，这既有利于程序的调试和维护，也有利于算法的交流和移植。算法的可读性主要体现在两方面：一是变量名、常量名、函数名等的命名要见名知意；二是要有足够多的注释。 (3)健壮性：当输入非法数据时算法要能做出适当的处理，而不应产生不可预料的结果。 (4)高时间效率：算法的时间效率指算法的执行时间。对于同一个问题，如果有多个算法可供选择，应尽可能选择执行时间短的算法。执行时间短的算法称做高时间效率的算法。 (5)高空间效率：算法在执行时一般要求额外的内存空间。对于同一个问题，如果有多个算法可供选择，应尽可能选择内存要求低的算法。内存要求低的算法称做高空间效率的算法。 1-10什么叫算法的时间复杂度？怎样表示算法的时间复杂度？ [解]:算法的时间复杂度也就是算法的时间效率，通常是算法所处理的数据元素个数n（亦称问题规模）的函数。 算法的时间复杂度分析就是分析算法执行时间与算法所处理的数据元素个数n之间的关系。通常采用O(f(n))表示法。 l-11设n为已在算法前边定义的整数类型，并已知n为正整数，分析下列各算法中加下划 线语句的执行次数，并给出各算法的时间复杂度T(n)。 (1) int i=1，k=0; while(i＜n-1) { k=k+10 *I; i=i+1； } (2)int I=1，k=0; do { k=k+10*i：i=i+1； ｝while (i！=n)； (3) int i=1，J=1； while(i＜=n&&j＜=n) ｛i=i+1；J=J+1 } (4)int x=n；//n＞1 int y=0； while(x＞=(y+1)*(y+1)) y++； (5)int i, j，k，x=0； for (i=0；i＜n; I++) for(j=0; j＜i；j++) for(k=0; k＜j；k++) x=x+2； [解]: (1)语句的执行次数为n-2次，T(n)=0(n)。 (2)语句的执行次数为n-1次，T(n)=0（n）。 (3)语句的执行次数为n次，T(n)=0（n）。 (4)语句的执行次数约为n1/2次, T(n)=0(n1/2). (5)语句的执行次数为（n(n-1) (n-2)）/6次，T(n)=0(n3) 1-12设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为0(n2), O(2n)和0(nlgn),哪种算法最可取？为什么？ [解]: 第三种算法最可取，因为三者比较起来，当n充分大时，T(n)=0(nlg n)时间效率最高。 1-13按增长率从小到大的顺序排列下列各组函数： (1)2100，(3/2) n，(2/3)n，(4/3)n (2) n，n3/2，n2/3，n！，n n (3) 1b n，n x lb n，n lbn,n [解]: (1)(2/3)n，2100,(4/3)n，(3/2)n (2) n2/3，n,n3/2，n！，n n、 (3) lbn，n，n x lb，n lbn” 1-14下面是几个典型的时间复杂度函数估值问题： (1)当n为正整数时，n取何值能使2n＞n3？ (2)说明2n+n3是o(2n)。 (3)给出5(n2+6)／(n+3)+7lgn的0值估计。 [解]: （1）当n=1或n>=12时， 2n＞n3 (2)说明2n+n3是o(2n)。 首先，2n+n3>2n总成立。反之，因为当n>12时， n3<2n总成立,所以2n+n3<2*2n成立.所以2n+n3是o(2n)。 (3)5(n2+6)／(n+3)+7lgn的0值估计是O（n）。 第2章线性表 一、基本概念题 2-1什么叫线性表？ [解]: 线性表是一种可以在任意位置进行插入和删除数据元素操作、由n(n≥0)个相同类型数据示素a o，a l，a2，…，a n-1，组成的线性结构. 2-2什么叫线性结构？线性表是线性结构吗？为什么？ [解]:线性结构是除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素。 线性表是一种可以在任意位置进行插入和删除数据元素操作、由n(n≥0)个相同类型数据示素a o，a l，a2，…，a n-1，组成的线性结构. 2-3什么叫顺序存储结构？什么叫链式存储结构？ [解]:顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。 链式存储结构是使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上(即内存存储位置上)不一定相邻，数据间的逻辑关系表现在结点的链接关系上。 2-4写出线性表的抽象数据类型. [解]: 线性表的抽象数据类型 数据集合： 线性表的数据集合可以表示为a o，a l，a2，…，a n-1，每个数据元素的数据类型为抽象数据元素类型DataType. 操作集合： （1）初始化Initiate（L）：初始化线性表Lo (2)求当前数据元素个数Size(L)：求线性表L的当前数据元素个数并由函数返回. (3)插入数据元素Insert（L, i，x）：在线性表L的第i个数据元素前插入数据元素x. (4)删除数据元素Delete(L, i):删除线性表L的第i个数据元素，所删除的数据元素由由函数返回. (5)取数据元素GetData(L, i，x):取线性表L的第i个数据元素，所取的数据元素由函数返回. 2-5什么叫指针？什么叫头指针？什么叫头结点？ [解]:指针是指向物理存储单元地址的变量. 把指向单链表的指针称为头指针. 头指针所指的不存放数据元素的第一个结点称做头结点. 2-6画出有n个数据元素的带头结点的单链表、循环单链表和循环双向链表结构 [解]: 图2-5带头结点的单链表 图2-15带头结点的循环单链表 图2-17带头结点的循环双向链表 2-7在链表设计中，为什么通常采用带头结点的链表结构？ [解]:当选用带头结的单链表时，设头指针用head表示，则在第一个数据元素结点前插入结点时，不会改变头指针head的值.同时，删除第一个数据元素结点时，不会改变头指针head的值，改变的是头指针所指结点的指针域的值. 但若选用不带头结点的单链表，在第一个数据元素前插入结点时，头指针head的值将改变为新插入结点的指针. 类似地，删除不带头结点单链表第一个数据元素结点时，头指针head的值将改变为等于head->next,即指针head等于原head->next的值。 所以采用带头结点的链表结构可以简化链表链表的插入删除等算法。 2-8说明C++语言动态申请和动态释放内存空间的new运算符和delete运算符的功能和使用 方法. [解]: 在C++语言中，用new运算符进行动态内存的申请，用delete运算符进行动态内存的释放. 使用方法如下： new运算符的语法格式为： new类型名(初始值); 其中，类型名指定了要分配存储空间的类型. delete运算符用于释放单个对象内存空间的语法格式为： delete指针; delete运算符用于释放对象数组内存空间的语法格式为： delete［］指针; 2-9在顺序表类中实现插入方法和删除方法时为什么必须移动数据元素？插入方法和删除方法移动数据元素的方向是否相同？ [解]:顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。 当插入和删除数据结点时，数据元素间的关系发生了改变，这也就要求数据的存储位置进行相应的改变以保持“逻辑上相邻的数据元素在物理上也相邻”。所以，在顺序表类中实现插入方法 和删除方法时必须移动数据元素。 插入方法和删除方法移动数据元素的方向恰好相反。 2－10对比顺序表类和单链表类的设计，说明顺序表和单链表的主要优点和主要缺点. [解]:顺序表的主要优点是算法简单，空间单元利用效率高；主要缺点是需要预先确定数据元素的最大个数，并且进行插入和删除操作时需要移动较多的数据元素. 单链表的主要优点是不需要预先确定数据元素的最大个数，插入和删除操作时不需要移动数据元素；主要缺点是每个结点中要有一个指针域，因此空间单元利用效率不高.另外，单链表操作的算法较复杂. 二、算法设计题 (说明：凡要求设计某个类成员函数的作业，均假设该成员函数已在相应类中定义过.） 2-11编写一个逐个输出顺序表中所有数据元素的成员函数. [解]: void SeqList：：List(void） //逐个输出顺序表中所有数据元素 { int i; for (i=0;i { cout< } } 2-12编写一个逐个输出单链表中所有数据元素的成员函数. [解]: template void LinList {//逐个输出单链表中所有数据元素 ListNode P=head->next; //P指向第一个结点 while(p！=NULL) //循环释放结点空间直至初始化状态 { cout< p=p->next; ｝ ｝ 2-13编写顺序表定位操作的成员函数.顺序表定位操作的功能是：在顺序表中查找是否存在数据元素x，如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回-1 [解]: int SeqList：：Find(DataType x) { for(int i=0；i { if（list[i]==x） return i； //查找到元素x else continue； } return-1；//未查找到元素x } 2-14在有些应用中，允许线性表中存在值相同的数据元素.线性表的另一个删除操作GetDeleteMore (L,x)的功能是：删除线性表L中所有等于x的数据元素.要求编写实现带头结点单链表删除操作的成员函数. [解]: template LinList { ListNode While(p!=NULL) { While(p->next!=NULL && p->next->data==x) { s=p->next; p->next=s->next; delete s; size--; } p=p->next; } } 2-15编写实现顺序表逆置的成员函数，即要求把顺序表A中的数据元素序列（a o,a1,….,a n-1）逆置为（a n-1 ,……,a1,a.），并把逆置后的数据元素存储到顺序表B中. [解]: void SeqList::Converse(SeqList a, SeqList b) { int i; b.size=a.size； for（i=0;i b.list[a.size–i-1]=a.list[i]； } 2-16编写实现顺序表就地逆置的成员函数，即要求利用原顺序表的存储单元，把数据元素序列（a o,a1 ,….,a n-1）逆置为（a o,a1 ,….,a n-1）. [解]: void SeqList::Converse(void) { int mid，i; DataType x； mid=size/2； for（i=0; i { x=list[i]； list[i]=list[size-1-i]； list[size-1-i]=x； } } 2-17编写实现带头结点单链表逆置的成员函数，即要求把带头结点单链表la中的数据元素序列（a o,a1,….,a n-1）逆置为（a n-1,……,a1,a.），并把逆置后的数据元素存储到带头结点单链表lb中. [解]: template void Converse(LinList { ListNode lb.head=new ListNode p=la.head->next； while(p！=NULL) { q=new ListNode lb->next=q; P=P->next； } } 2-18编写实现带头结点单链表就地逆置的成员函数，即要求利用原带头结点单链表的结点空间，把数据元素序列（a o,a1 ,….,a n-1）逆置为（a n-1 ,……,a1,a.）. [解]: template void LinList { ListNode p=head->next； head->next=NULL; while(p！=NULL) { g=p； P=P->next； q->next=head->next； head->next=q； } } 三、上机实习题 2-19设计一个静态数组存储结构的顺序表类，要求： (1)包括和动态数组存储结构的顺序表类相同的成员函数. (2)用例2-1的问题要求进行测试. (3)用例2-2的问题要求进行测试. [解]: (1)包括和动态数组存储结构的顺序表类相同的成员函数. 建立类实现文件SeqList.h.其内容如下： class SeqList { protected： DataType ：list[maxSize]；//数组 int size；//当前元素个数 public： SeqList(void)；//构造函数 ~SeqList(void){}；//析构函数 int Size(void)const；//取当前数据元素个数 void Insert（coast DataType& item, int i）； //插入 DataType Delete（const int I ）；//删除 DataType GetData（int i）const；//取数据元素 }； SeqList：：SeqList（void）//构造函数 { size=0； ｝ int SeqList：：Size(void)const //取当前数据元索个数{ return size； } void SeqList：：Insert（Const DataType& item, int i）//播入 //在指定位置I前播入一个数据元素item { if（size >= maxSize） { cout<<“顺序表已满无法插入！”< exit(0)； } if（i<0||i>size=）//参数正确与否判断{ cout<<“参数i越界出错！”< exit（0）; } //从size-1至i逐个元素后移 for（int j=size;j>i;j--） list[j]=list[j-1]； list[i]=item; //在i位置插入 item size++; //当前元素个数加1 } DataType SeqList：：Delete（const int i） //删除指定位置i的数据元素.删除的元素由函数返回 { if（size==0） { cout<<“顺序表已空无元素可删！”< exit(0)： } if（i<0 ||i>size-1） //参数正确与否判断 { cout<<“参数i越界出错！”< exit（0）； } DataType x=list[i]；//取到要删除的元素 //从i+1至size-1逐个元素前移 for(int j=i;j list[j] =list[j+1]； size--; //当前元素个数减1 return x; //返回删除的元素 } DataType SeqList：:GetData（int i）const //取数据元素 //取位置i的教据元素.取到的数据元素由函数返回 { if（i { cout（<<“参数i越界出错！”< exit(0)； } return list[i]；//返回取到的元素 } (2)用例2-1的问题要求进行测试. 建立程序文件Exp2-1.cpp其内容如下： #include #include typedef int DataType；//定义具体问题元素的数据类型 #define maxSize 100 #include “SeqList.h“//包含顺序表类 void main（void) { SeqList myList（）；//定义顺序表类对象myList int n=10； for（int i=0；i myList.Insert（i+1,I）； myList.Delete(4)；//删除myList中数据元素5 for（i=0；I } 程序运行结果如下：1 2 3 4 5 6 7 8 9 10 (3)用例2-2的问题要求进行测试. 建立程序文件Exp2-2.cpp其内容如下： #include #include struct StudentType //结构体StudentType { long number； //学号数据项 char name[10]； //姓名数据项 char sex[3]； //性别数据项 int age； //年龄数据项 }； typedef StudentType DataType；//定义DataType为StudentType数据类型#define maxSize 100 #include "SeqList.h"//包含顺序表类 void main(void) { SeqList myList()； StudentType x[3]={{2000001，”张三”，”男”，20} {12000002，”李四”，”男”，21} {2000003，”王五”，”女”，22}} int n=3; DataType s； for（int i=0：i for（i=0；i { s=myList.GetData（i）； cout< } } 2-20设计一个带头结点的循环单链表类，要求： (1)带头结点循环单链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素. (2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性. [解]: (1)结点类的定义和实现如下, 其实现文件为CircleList.h template template { friend class CircleList private: ListNode T data; //定义为公有成员方便使用 public: //构造函数!,用于构造头结点 ListNode(ListNode //构造函数2,用于构造其他结点 ListNode(const T & item,ListNode ~ListNode(void){} //析构函数 }; //单链表类的定义 template class CircleList { private: ListNode int size; //当前的数据元素个数 ListNode public: CircleList(void); //构造函数 ~CircleList(void); //析构函数 int Size(void){return size;} //取当前数据元素个数 void Insert(const T &item,int i); //插入 T Delete(int i); //删除 T GetData(int i); //取数据元素 }; //单链表类的实现 template Chap1 一、选择题 1.算法的计算量的大小称为计算的（）。 A．效率 B.复杂性 C.现实性 D.难度 2.计算机算法指的是（1），它必须具备（2）这三个特性。 (1)A．计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法 (2)A．可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 3.下面关于算法说法错误的是（）。 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的 4．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 5．以下数据结构中，哪一个是线性结构（）？ A．广义表 B.二叉树 C.稀疏矩阵 D.串 6．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1TO n DO FOR j:=1TO n DO x:=x+1; n) A．O(2n)B．O(n)C．O(n2)D．O(log 2 7．程序段FOR i:=n-1DOWNTO1DO FOR j:=1TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中n为正整数，则最后一行的语句频度在最坏情况下是（）。 A.O（n） B.O(nlogn) C.O(n3) D.O(n2) 8．以下哪个数据结构不是多型数据类型（） A．栈B．广义表C．有向图D．字符串 9．以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 二、判断题 1．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。() 2．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。() 3．程序一定是算法。() 4．数据的物理结构是指数据在计算机内的实际存储形式。() 5.数据结构的抽象操作的定义与具体实现有关。() 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。() 《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 《数据结构》第一章练习题 1、单项选择题 1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 ①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像 ②A 结构 B 关系 C 运算 D 算法 1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。 ①A 算法B 数据元素C 数据操作D 逻辑结构 ②A 操作B 映像C 存储D 关系 1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A 逻辑 B 存储 C 逻辑和存储 D 物理 1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。①A 找出数据结构的合理性 B 研究算法中输入与输出的关系 C 分析算法效率以求改进 D 分析算法的易懂性和文档性 ②A 空间复杂度和时间复杂度 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 ②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性 1.8在以下的叙述中，正确的是（ ）。 A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 1.9在决定选择何种存储结构时，一般不考虑（ ）。 、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况 ，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 排序算法（19） 1.以单链表为存储结构，写一个直接选择排序算法。 2.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关 键字之前。请分析算法的时间复杂度。 3.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 4. 4.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进 行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if([j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 5.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 6.对给定的j(1 ≤ j ≤ n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 7.以单链表为存储结构，写一个直接选择排序算法。 8.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R 中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 9.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆其中。 10.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性： （1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。 （2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 （4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。 （5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理； 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 第1章习题解答 1.1什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其含义。 [解答] 概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是什么？ [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素，所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在： 有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。 1.4什么是线性结构？什么是非线性结构？举例说明。 [解答] 1.数据的四种存储结构是( ) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少， 下列选项中，应选择的存储结构是( ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=head 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n B. C. +1 D.n/2 9.在图G中求最小生成树可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.深度优先遍历(DFS)算法 D.广度优先遍历(BFS)算法 10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18 11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解 决冲突，散列地址为1的链中记录个数为( ) A.1 B.2 C.3 D.4 14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( )数据结构第一章试题
数据结构复习题目和答案
经典数据结构面试题(含答案)
数据结构课后习题及解析第一章
数据结构模拟卷(含答案)经典习题培训讲学
数据结构课后习题及解析第二章
数据结构习题库汇总
数据结构模拟卷(含答案)经典习题
数据结构第一章练习题
数据结构习题
经典数据结构上机题_答案解析
数据结构例题解析(1)
数据结构习题汇编01 第一章 绪论 试题
数据结构1-4章习题答案
数据结构经典题目c语言代码
数据结构第一章课后习题与答案
数据结构第1章习题解答..
数据结构习题2011级
相关主题
文本预览