中国矿业大学2010年数据结构试卷及答案

计算机学院2010-2011学年第一学期 《数据结构》试卷（A 卷）（考试时间：100分钟）

专业： 计算机专业 班级： 序号： 姓名：

注意：所有答案都必须写在答题纸上！！！

三．简答（每小题10分，共50分）

1．有如图所示的有向图，请给出该图的:

1) 邻接矩阵表示； 2) 逆邻接表表示。

2．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题：

1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13

的哈希表，（利用线性探测）请画出存放状态；

2) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数；

3．请写出对序列{21，25，49，28，16，22，25，38}的二叉排序树构造过程。

4．试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。

5．如果一个项目由10个主要任务构成，其计划图展示了任务之间关系与任务所需天数，则项目关键路径如何求解，请展示其过程。

四．算法（10分，共10分）

请写出折半查找方法的函数Search_Bin( SSTable S, value v)。

要求：

1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；

2）如果找到，则函数返回值为该数在序列中的位置，否则返回负1；

3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。

计算机学院2010-2011学年第一学期

《数据结构》答题纸（A卷）一．填空（2*20=40分）

二．简答题（10*5=50分）

1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0

1

2 24,63,102共计比较了3次 3

插入第二个25返回false

4 v1

5

三．算法（10分）见书

数据结构试题及答案(免费)

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。

数据结构课程设计实验报告

《空间数据结构基础》 课程实习报告（测绘10级） 姓名 班级 学号 环境与测绘学院

1C++面向对象程序设计基础 【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。 【实验内容】 1.定义三维空间的坐标点TPoint 2.描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输出空间坐标 等）。 【主要代码】 头文件： TPoint.h: #ifndef TPOINT_H #define TPOINT_H #include using namespace std; class TPoint { public: TPoint(double xx,double yy,double zz):x(xx),y(yy),z(zz){} TPoint(TPoint &TP):x(TP.x),y(TP.y),z(TP.z){} double getX()const{return x;}//取x坐标值 double getY()const{return y;}//取y坐标值 double getZ()const{return z;}//取z坐标值 void DisplayTP() const {cout<<"("<

中国矿业大学2010年数据结构试卷及答案

计算机学院2010-2011学年第一学期 《数据结构》试卷（A 卷）（考试时间：100分钟） 专业： 计算机专业 班级： 序号： 姓名： 注意：所有答案都必须写在答题纸上！！！ 三．简答（每小题10分，共50分） 1．有如图所示的有向图，请给出该图的: 1) 邻接矩阵表示； 2) 逆邻接表表示。 2．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13 的哈希表，（利用线性探测）请画出存放状态； 2) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 3．请写出对序列{21，25，49，28，16，22，25，38}的二叉排序树构造过程。

4．试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。 5．如果一个项目由10个主要任务构成，其计划图展示了任务之间关系与任务所需天数，则项目关键路径如何求解，请展示其过程。 四．算法（10分，共10分） 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。 要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回负1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。

计算机学院2010-2011学年第一学期 《数据结构》答题纸（A卷）一．填空（2*20=40分）

数据结构试题答案

第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s

中国矿业大学 空间数据结构上机实验报告

《空间数据结构基础》上机实验报告（2010级） 姓名 班级 学号 环境与测绘学院 1.顺序表的定义与应用（课本P85习题） 【实验目的】 熟练掌握顺序表的定义与应用，通过上机实践加深对顺序表概念的理解。 【实验内容】

设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均从小到大排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也从小到大排列。【主要代码】 #include//定义在头文件“SeqList.h”中 #include const int defaultSize=100; template class SeqList{ protected: T *data;//存放数组 int maxSize;//最大可容纳表象的项数 int Last;//当前已存表象的项数 void reSize(int newSize);//改变data数组空间大小 public: SeqList(int sz=defaultSize); SeqList(SeqList& L); ~SeqList(){delete[]data;} int Size() const{return maxSize;} int Length()const{return Last+1;} int Search(T& x)const; int Locate(int i) const; T getData(int i) const; bool setData(int i,T& x) {if(i>0&&i<=Last+1) data[i-1]=x;} bool Insert(int i,T& x); bool Remove(int i,T& x); bool IsEmpty() {return (Last==-1)?true:false;} bool IsFull() {return(Last==maxSize-1)?true:false;} void input(); void output(); SeqList operator=(SeqList& L); friend void rank(SeqList& L); friend void hebing(SeqList& LA,SeqList& LB); }; //构造函数，通过指定参数sz定义数组的长度 template SeqList::SeqList(int sz){ if(sz>0){ maxSize=sz; Last=-1; data=new T[maxSize];

数据结构试题及答案

数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

中国矿业大学数据结构课程设计报告

《空间数据结构基础》 课程实习报告（地信12级） 姓名朱红鑫 班级地信12-2 学号 07122960 环境与测绘学院

目录 实验一：C++面向对象程序设计基础 (2) 实验三：通讯簿管理（顺序表的应用） (6) 实验五：将中缀表达式转换为后缀表达式 (13) 实验七：二叉树的操作 (18) 实验九：字符串 (24)

1C++面向对象程序设计基础 【实验简介】学会用算法语言C++描述抽象数据类型，使用模板建立数据结构。理解数据结构的组成分为两部分，第一部分是数据集（数据元素），第二部分是在此数据集上的操作。从面向对象的观点看，这两部分代表了对象的属性和方法。掌握用C++描述数据结构的基本方法，即通过建立类来描述抽象数据类型。类的数据成员提供对象属性，成员函数提供操作方法，方法是公共接口，用户通过调用方法实现对属性的访问。 【实验内容】 1.定义三维空间的坐标点TPoint 2.描述三维空间的球TBall，实现其主要操作（如计算体积和表面积，输 出空间坐标等）。 【主要代码】 #include #include class TPoint { protected: double x; //虚拟类型的水平坐标值 double y; //虚拟类型的垂直坐标值 double z; //z坐标 public: TPoint(){x = 0; y = 0; z = 0; } //缺省构造函数 TPoint(double px, double py,double pz){x = px;y = py;z=pz;} //带参数的构造函数 void move(double mx,double my,double mz){x = mx;y = my;z=mz;} //移动位置(修改坐标值) void show(){cout<<"x="<