合工大数据结构 01-概述

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

计算机与信息学院数据结构实验报告专业班级学生姓名及学号课程教学班号任课教师实验指导教师实验地点2015 ~2016 学年第 2 学期说明实验报告是关于实验教学内容、过程及效果的记录和总结，因此，应注意以下事项和要求：1．每个实验单元在4页的篇幅内完成一份报告。

“实验单元”指按照实验指导书规定的实验内容。

若篇幅不够，可另附纸。

2、各实验的预习部分的内容是进入实验室做实验的必要条件，请按要求做好预习。

3．实验报告要求：书写工整规范，语言表达清楚，数据和程序真实。

理论联系实际，认真分析实验中出现的问题与现象，总结经验。

4．参加实验的每位同学应独立完成实验报告的撰写，其中程序或相关的设计图纸也可以采用打印等方式粘贴到报告中。

严禁抄袭或拷贝，否则，一经查实，按作弊论取，并取消理论课考试资格。

5．实验报告作为评定实验成绩的依据。

实验序号及名称：实验一单链表实验实验时间∶ 2016年 5 月二、实验内容与步骤（过程及数据记录）：<1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。

实验测试数据基本要求：第一组数据：链表长度n≥10，i分别为5，n，0，n+1，n+2第二组数据：链表长度n=0，i分别为0，2node* list::address(int i){n ode *p = head->next;i nt n = 1;w hile (n != i&&p != NULL){p = p->next;n++;}i f (p!=NULL) return p;e lse return NULL;}第一组数据第二组数据<2>在第i个结点前插入值为x的结点。

实验测试数据基本要求：第一组数据：链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2第二组数据：链表长度n=0，x=100，i=5errorcode list::insert(const int i, const int x){n ode *p;p = head;i nt n = 1;w hile (n != i&&p != NULL){p = p->next;n++;}i f (i<1 || i>length() + 1) return rangeerror;n ode *s = new node;s->data = x;s->next = p->next;p->next = s;c ount++;r eturn success;}<3>删除链表中第i个元素结点。

第一章绪论计算机科学是一门研究数据表示和数据处理的科学。

数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。

无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。

因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。

1．1 数据结构的概念数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。

所有的计算机系统软件和应用软件都要用到各种类型的数据结构。

要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。

打好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。

1.1.1 为什么要学习数据结构当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试，直至得到最终的解答。

随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。

据统计，当今处理非数值计算性问题占用了90%以上的机器时间。

这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。

因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构，才能有效地解决问题。

下面所列举的就是属于这一类的具体问题。

[例1]学生信息检索系统。

当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。

由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如图1.1所示。

第1章绪论内容提要：◆数据结构研究的内容。

针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

数据——所有能被计算机识别、存储和处理的符号的集合。

数据元素——是数据的基本单位，具有完整确定的实际意义。

数据对象——具有相同性质的数据元素的集合，是数据的一个子集。

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。

◆算法的定义及五个特征。

算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。

①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。

时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。

◆用计算语句频度来估算算法的时间复杂度。

第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

通过指针来实现！◆线性表的操作在两种存储结构中的实现。

数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。

核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2) 插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i 位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。

数据结构实验报告实验一:栈和队列实验目的：掌握栈和队列特点、逻辑结构和存储结构熟悉对栈和队列的一些基本操作和具体的函数定义。

利用栈和队列的基本操作完成一定功能的程序。

实验任务1.给出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数N与其它d进制数的转换。

（如N=1357,d=8）实验原理:将十进制数N转换为八进制时，采用的是“除取余数法”，即每次用8除N所得的余数作为八进制数的当前个位，将相除所得的商的整数部分作为新的N值重复上述计算，直到N为0为止。

此时，将前面所得到的各余数反过来连接便得到最后的转换结果。

程序清单#include<iostream>#include<cstdlib>using namespace std;typedef int DATA_TYPE;const int MAXLEN=100;enum error_code{success,overflow,underflow};class stack{public:stack();bool empty()const;error_code get_top(DATA_TYPE &x)const;error_code push(const DATA_TYPE x);error_code pop();bool full()const;private:DATA_TYPE data[MAXLEN];int count;};stack::stack(){count=0;}bool stack::empty()const{return count==0;}error_code stack::get_top(DATA_TYPE &x)const {if(empty())return underflow;else{x=data[count-1];return success;}}error_code stack::push(const DATA_TYPE x){if(full())return overflow;else{data[count]=x;count++;}}error_code stack::pop() {if(empty())return underflow;else{count--;return success;}}bool stack::full()const {return count==MAXLEN; }void main(){stack S;int N,d;cout<<"请输入一个十进制数N和所需转换的进制d"<<endl; cin>>N>>d;if(N==0){cout<<"输出转换结果:"<<N<<endl;}while(N){(N%d);N=N/d;}cout<<"输出转换结果:"<<endl;while(!()){(N);cout<<N;();}cout<<endl;}while(!()){(x);cout<<x;();}}测试数据：N=1348 d=8运行结果：2.给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内容。