实验：数据结构与算法

《数据结构与算法》实验

提交实验结果的要求：

实验完成后，将文件夹中的Debug文件夹删除，然后将整个文件夹打包成压缩文件，并以“学号姓名”的方式重命名，提交该压缩包。

实验1：VC环境的面向对象程序设计

实验目的：掌握VC环境下面向对象编程的基本步骤

实验准备：

1. 复习面向对象程序设计的有关概念

2. 阅读VC有关编程操作的说明

实验步骤及要求：

按照实验指导教师的指导，逐条完成以下要求：

1. 启动VC，新建空的控制台工程myproj，新建C++源程序文件main，查看目前文件夹中

有哪些文件

2. 新建一个名为CA的类，查看文件夹中新添了哪些文件

3. 为CA类添加1个int型私有数据成员x和1个char*型私有数据成员y

4. 在CA类的构造函数中添加代码，令x赋值为0，y赋值为空指针

5. 在CA类的析构函数中添加代码：如果y不是空指针，则释放y所指向的内存区域

6. 为CA增加带int型和char*型双参数的构造函数，在代码部分令x赋值为int型参数，令

y指向动态申请的内存空间(字节数为char*型参数所指字符串的串长加1)，并将char*型参数所指字符串复制到新申请的空间中

7. 为CA类增加函数成员Display，用于显示x的值和y所向的指字符串

8. 编写下面的主函数，添加相应的#include预处理命令，并编译、运行程序：

void main( )

{

CA a,b(12,"abcdefg");

a.Display( );

b.Display( );

}

9. 在主函数main中添加以下三行：

a=b;

a.Display( );

b.Display( );

再运行可发现正确显示了信息后程序运行出错，请说明原因。

10. 为CA类重载赋值运算符“=”，在其中对指针型数据成员y重新申请空间并做字符串复制。再次编译、运行程序，观察是否出错。

11. 为CA类建立拷贝构造函数，实现深拷贝，代码与重载赋值运算符“=”基本相同(不需要return语句)。再次编译、运行程序，观察是否出错。

12. 为CA类重载“+”运算符，做两个对象的加法运算：整数部分相加，字符串部分拼接。

在主函数中增加一个CA 类的对象c ，并在主函数中的“a=b;”语句后面增加一行：

c=a+b;

在程序的最后增加一行：

c.Display( );

再次编译、运行程序，观察结果。

实验2：顺序表

实验目的：掌握顺序表的基本运算相关算法并编程实现

实验准备：

1. 阅读以下“用顺序表存储多项式”的方法：

一元多项式表现为：

0111...a x a x a x a n n n n ++++--

用顺序表存储多项式时，一个数据元素由一个用于存储系数的实型分量coe(coefficient)和一个用于存储指数的整型分量exp(exponent)构成，在顺序表中只存储coe 和exp 即可表示多项式的一项。例如，多项式

43225--+x x x

在顺序表中依次存放(2,5)、(3,2)、(-1,1)、(-4,0)共4个元素即可。注意，系数为0的项不存储，各个数据元素必须按指数降序排列。

2. 阅读、理解以下算法：顺序表的遍历、两个多项式相加

3. 将压缩包ex02.rar 中的内容解压，双击文件夹中的dsw 工程文件。当前工程中包含三个

文件：关于类与类型定义的SeqList.h 、类的函数成员SeqList.cpp 、主函数文件main.cpp 。查看各个文件中的内容。

实验步骤及要求：

1. 针对存储多项式的顺序表，修改SeqList.h 中的类型定义SeqNode ，使其符合多项式的存

储要求。

2. 为CSeqList 类增加Display 方法，用于显示一个多项式。

3. 为CSeqList 类重载“+”，实现多项式加法。

4. 去掉主函数main 中各语句的注释符号，使得各条语句可以正确执行。

//以下是关于数据元素的类型定义，请根据实际情况修改

typedef struct datatype

{

double coe; //存放系数

int exp; //存放指数

} DataType;

typedef DataType SeqNode;

//以下是关于SeqList类型的声明

class CSeqList

{

public:

friend CSeqList operator+(const CSeqList &x , const CSeqList &y);

void Display();

virtual bool DeleteData(int i); //删除顺序表的第i号元素

virtual bool GetData(int i,SeqNode *q); //取顺序表的第i号元素，存放到q所指向的位置

virtual void Empty(); //将当前顺序表置为空表

virtual bool InsertData(SeqNode x,int i); //将新元素x插入到顺序表的第i号位置

virtual void InputData();

CSeqList& operator=(const CSeqList &x); //重载赋值运算符

virtual int GetLength(); //取表长

virtual bool IsFull(); //判断表是否已满

virtual bool IsEmpty(); //判断表是否为空

CSeqList(int maxlen);

CSeqList(CSeqList &x); //拷贝构造函数

virtual ~CSeqList();

private:

int m_MaxLength; //最大表长

int m_CurLength; //当前表长

SeqNode *m_List; //初始化时指向申请的空间，存放表的各个元素

};

#include "SeqList.h"

#include "iostream.h"

#include "windows.h"

#include "math.h"

//构造函数

CSeqList::CSeqList(int maxlen)

{

if(maxlen<=0)

{

cout<<"构造函数创建顺序表失败：表中最多存储元素数量必须是正数\n";

exit(1);

}

m_List=new SeqNode[maxlen];

if(m_List==NULL)

{

cout<<"构造函数创建顺序表失败：内存空间不够\n";

exit(1);

}

m_CurLength=0;

m_MaxLength=maxlen;

}

//拷贝构造函数

CSeqList::CSeqList(CSeqList &x)

{

int i;

m_MaxLength=x.m_MaxLength;

m_List=new SeqNode[m_MaxLength];

if(m_List==NULL)

{

cout<<"拷贝构造函数创建顺序表失败：内存空间不够\n";

exit(1);

}

m_CurLength=x.m_CurLength;

for(i=0;i

m_List[i]=x.m_List[i];

}

//析构函数，清理内存

CSeqList::~CSeqList()

{

delete m_List;

}

//判空

bool CSeqList::IsEmpty()

{

return m_CurLength==0;

}

//判满

bool CSeqList::IsFull()

{

return m_CurLength==m_MaxLength;

}

//取表长

int CSeqList::GetLength()

{

return m_CurLength;

}

//从键盘输入数据存入顺序表中

void CSeqList::InputData()

{

int x1,x2;

cout<<"请每次输入系数和指数，用空格分隔，输入两个值均<0表示输入结束\n";

while(m_CurLength

{

cout<<"List["<

x1=x2=-1;

cin>>x1;

cin>>x2; //输入两个数值

if(x1<0 && x2<0)

break; //如果两个值都<0则表示输入完毕m_List[m_CurLength].coe=x1;

m_List[m_CurLength].exp=x2; //否则将这两个值存入顺序表

m_CurLength++;

}

}

//重载赋值运算符

CSeqList& CSeqList::operator =(const CSeqList& x)

{

int i;

m_MaxLength=x.m_MaxLength;

m_List=new SeqNode[m_MaxLength];

if(m_List==NULL)

{

cout<<"=重载时创建顺序表失败：内存空间不够\n";

exit(1);

}

m_CurLength=x.m_CurLength;

for(i=0;i

m_List[i]=x.m_List[i];

return *this;

}

//将新元素x插入到顺序表的第i号位置

bool CSeqList::InsertData(SeqNode x, int i)

{

int j,k=GetLength();

if(IsFull() || i<0 || i>k+1)

return false;

for(j=k;j>i;j--)

m_List[j]=m_List[j-1];

m_List[i]=x;

m_CurLength++;

return true;

}

/将当前顺序表置为空表

void CSeqList::Empty()

{

m_CurLength=0;

}

//取顺序表的第i号元素，存放到q所指向的位置

bool CSeqList::GetData(int i, SeqNode *q)

{

int k=GetLength();

if(i<0 || i>=k)

return false;

*q=m_List[i];

return true;

}

//删除顺序表的第i号元素

bool CSeqList::DeleteData(int i)

{

int j,k=GetLength();

if(i<0 || i>=k)

return false;

for(j=i;j

m_List[j]=m_List[j+1];

m_CurLength--;

return true;

}

//以下为新增函数

void CSeqList::Display()

{

int i;

if(m_CurLength==0)

cout<<"该顺序表为空表";

else

{

for(i=0;i

{

//显示系数

cout<<' '; //系数前面先显示一个空格

if(m_List[i].coe<0) //系数为负数,直接显示

{

if(m_List[i].exp==1 && fabs(m_List[i].coe+1)<1e-10) //-1X^1显示成-X

cout<<"-";

else

cout<

}

else

{

if(i>0) //如果不是最前面一项，则显示'+'[

cout<<'+';

if(m_List[i].exp!=1 || fabs(m_List[i].coe-1)>1e-10) //系数和指数均为1,不

显示系数

cout<

}

//显示“X^指数”

if(m_List[i].exp>0)

{

if(m_List[i].exp==1)

cout<<"X";

else

cout<<"X^"<

}

}

}

cout<

}

CSeqList operator +(const CSeqList &x , const CSeqList &y)

{

int i,j,k,m;

SeqNode p;

k=y.m_MaxLength;

if(k

k=x.m_MaxLength; //最大表长取两个表中较大的一个CSeqList z(k);

i=j=m=0;

while(i

{

if(m>k) //相加后的表长超过最大表长

{

cout<<"重载+时两表相加超过最大表长限制\n";

exit(1);

}

if(x.m_List[i].exp>y.m_List[j].exp)

z.InsertData(x.m_List[i++],m++); //将指数大的x表中第i项添加到z 中

else if(x.m_List[i].exp

z.InsertData(y.m_List[j++],m++); //将指数大的y表中第j项添加到z 中

else

{

p.coe=x.m_List[i].coe+y.m_List[j].coe;

p.exp=x.m_List[i].exp;

if(fabs(p.coe)>1e-10)

z.InsertData(p,m++);

i++;

j++;

}

}

return z;

}

#include "iostream.h"

#include "seqlist.h"

void main()

{

CSeqList list1(100),list2(100),list3(100);

list1.InputData();

list1.Display();

list2.InputData();

list2.Display();

list3=list1+list2;

list3.Display();

}

实验3 链表

实验目的：掌握单链表的基本运算相关算法并编程实现

实验准备：

1. 阅读、理解以下算法：单链表的遍历、两个单链表的合并、在单链表中删除重复元素、

单链表的排序(冒泡排序法)

2. 将压缩包ex0

3.rar中的内容解压，双击文件夹中的dsw工程文件。当前工程中包含三个

文件：关于类与类型定义的LinkList.h、类的函数成员LinkList.cpp、主函数文件main.cpp。

查看各个文件中的内容。

实验步骤及要求：

1. 创建CLinkList类的派生类CMyLinkList。如果创建成功，在工程文件夹中将新增

MyLinkList.h和MyLinkList.cpp两个文件。

2. 为CMyLinkList类添加用于输入的函数InputData，调用该函数可以从键盘上输入若干组

数据存放到链表中。注意调用父类中的InsertData函数时，如果想在链表原来的表头结点(记为1号结点)前面添加新结点，则调用的第二参数应为0。

3. 为CMyLinkList类添加用于显示链表的函数Display，调用该函数可以显示链表中各结点

的数据信息。

4. 为CMyLinkList类重载“+”，用于将两个链表合并

5. 为CMyLinkList类添加函数DelRepeat，调用该函数可以删除链表中整型数据项重复的元

素，即：从前向后查看每一个结点，记当前查看的结点的整型数据域的值为K，则删除后续所有整型数据域的值为K的结点。

6. 编写主函数main，实现以下功能：

(1) 建立CMyLinkList类的三个对象，其中两个对象的数据值从键盘输入

(2) 利用重载的“+”运算符把上述两个对象合并，结果存放到第三个对象中

(3) 调用第5步建立的函数删除链表中的重复元素

(4) 对链表进行排序

这些功能的相应语句已经以注释的形式编写在主函数中，逐个地去掉注释符号，检查各语句是否能正确执行。

//此处定义数据元素的类型，请根据实际问题作相应的修改

typedef struct dataofnode

{

double coe;

int exp;

} DataType;

typedef struct linknode

{

DataType data;

struct linknode* next;

} LinkNode ;

class CLinkList

{

public:

CLinkList(); //构造函数，生成带有头结点的空链表CLinkList(const CLinkList& x); //拷贝构造函数

virtual ~CLinkList(); //析构函数，清理内存

public:

LinkNode* GetLink(); //取指向1号结点的指针，如果是空链表则返回值为NULL CLinkList& operator =(const CLinkList &x); //重载赋值运算符"="

virtual bool DeleteData(int i); //删除链表的第i号结点，头结点为第0号结点virtual bool GetData(int i,DataType *q); //取链表第i号结点，将其数据域复制到q所指向的位置

virtual int GetLength(); //取链表的表长

virtual bool InsertData(DataType x,int i); //在链表第i号结点的后面插入新结点

virtual bool IsEmpty(); //判断链表是否为空

private:

LinkNode* m_Head;

};

#include "LinkList.h"

#include "iostream.h"

#include "windows.h"

//构造函数，生成带有头结点的空链表

CLinkList::CLinkList()

{

m_Head=new LinkNode;

if(m_Head==NULL)

{

cout<<"构造函数创建链表失败：内存空间不够\n";

exit(1);

}

m_Head->next=NULL; //头结点的指针域置为空指针

*((int*)&(m_Head->data))=0; //用数据域存放表长

}

//拷贝构造函数

CLinkList::CLinkList(const CLinkList& x)

{

LinkNode *q1,*q2;

int n=0;

m_Head=new LinkNode;

if(m_Head==NULL)

{

cout<<"拷贝构造函数创建链表失败：内存空间不够\n";

exit(1);

}

m_Head->next=NULL; //头结点的指针域置为空指针

q1=m_Head;

q2=x.m_Head->next;

while(q2!=NULL)

{

q1->next=new LinkNode;

if(q1->next==NULL)

{

cout<<"拷贝构造函数创建链表失败：内存空间不够\n";

exit(1);

}

*(q1->next)=*q2;

q1=q1->next;

q2=q2->next;

n++;

}

q1->next=NULL;

*((int*)&(m_Head->data))=n; //用数据域存放表长

}

//析构函数，清理内存

CLinkList::~CLinkList()

{

LinkNode *q;

while(m_Head!=NULL)

{

q=m_Head;

m_Head=m_Head->next;

delete q;

}

}

//判断链表是否为空

bool CLinkList::IsEmpty()

{

return m_Head->next==NULL;

}

//在链表第i号结点的后面插入新结点

bool CLinkList::InsertData(DataType x, int i)

{

LinkNode *q1,*q2;

int k,len;

len=*((int*)&(m_Head->data)); //取表长

if(i<0 || i>len)

return false; //如果位置有错则返回false

q1=new LinkNode;

if(q1==NULL)

exit(1); //如果申请空间失败则程序结束

q1->data=x; //为新结点填充数据域

q2=m_Head;

for(k=0;k

q2=q2->next; //令q2指向第i-1号结点，以头结点为第0号结点q1->next=q2->next; //为新结点连接后继

q2->next=q1; //为新结点连接前趋

(*((int*)&(m_Head->data)))++; //表长加1

return true;

}

//取链表的表长

int CLinkList::GetLength()

{

return *((int*)&(m_Head->data));

}

//取链表第i号结点，将其数据域复制到q所指向的位置

bool CLinkList::GetData(int i,DataType *q)

{

int len,k;

LinkNode *q1;

len=*((int*)&(m_Head->data)); //取表长

if(i<=0 || i>len)

return false; //如果位置有错则返回false

q1=m_Head->next;

for(k=1;k

q1=q1->next; //令q1指向第i号结点，以头结点为第0号结点

*q=q1->data;

return true;

}

//删除链表的第i号结点，头结点为第0号结点

bool CLinkList::DeleteData(int i)

{

int k,len;

LinkNode *q1,*q2;

len=*((int*)&(m_Head->data)); //取表长

if(i<=0 || i>len)

return false; //如果位置有错则返回false

q1=m_Head;

for(k=1;k

q1=q1->next; //令q1指向第i-1号结点，以头结点为第0号结点q2=q1->next; //令q2指向待删结点

q1->next=q2->next; //修改链接关系

delete q2; //释放被删结点的空间

(*((int*)&(m_Head->data)))--; //表长减1

return true;

}

//重载赋值运算符"="

CLinkList& CLinkList::operator =(const CLinkList &x)

{

LinkNode *q1,*q2;

while(m_Head!=NULL)

{

q1=m_Head;

m_Head=m_Head->next;

delete q1;

}

m_Head=new LinkNode;

if(m_Head==NULL)

{

cout<<"重载赋值号创建链表失败：内存空间不够\n";

exit(1);

}

m_Head->next=NULL; //头结点的指针域置为空指针

q1=m_Head;

q2=x.m_Head->next;

while(q2!=NULL)

{

q1->next=new LinkNode;

if(q1->next==NULL)

cout<<"重载赋值号创建链表失败：内存空间不够\n";

exit(1);

}

*(q1->next)=*q2;

q1=q1->next;

q2=q2->next;

}

q1->next=NULL;

*((int*)&(m_Head->data))=*((int*)&(x.m_Head->data)); //用数据域存放表长return *this;

}

//取指向1号结点的指针，如果是空链表则返回值为NULL

LinkNode* CLinkList::GetLink()

{

return m_Head->next;

}

#include "MyLinkList.h"

#include "iostream"

#include "math.h"

using namespace std;

CMyLinkList::CMyLinkList()

{

}

CMyLinkList::~CMyLinkList()

{

}

void CMyLinkList::InputData()

{

DataType x;

cout<<"请每次输入两个数据，用空格分隔，输入中有负数表示输入结束\n";

while(1)

{

cin>>x.coe>>x.exp; //输入两个数值

if(x.coe<0 || x.exp<0)

break; //如果有负数则表示输入完毕

this->InsertData(x,0);

}

}

void CMyLinkList::Display()

{

int i,k;

DataType x;

k=this->GetLength();

cout<<"数据表为空表\n";

else

{

for(i=1;i<=k;i++)

{

this->GetData(i,&x);

cout<<"( "<

}

cout<

}

}

CMyLinkList operator+(CMyLinkList x,CMyLinkList y) {

CMyLinkList z;

int i,k,m;

DataType w;

m=0;

k=x.GetLength();

for(i=1;i<=k;i++)

{

x.GetData(i,&w);

z.InsertData(w,m++);

}

k=y.GetLength();

for(i=1;i<=k;i++)

{

y.GetData(i,&w);

z.InsertData(w,m++);

}

return z;

}

void CMyLinkList::DelRepeat()

{

int i,j,k;

DataType a,b;

k=GetLength();

for(i=1;i<=k;i++)

{

this->GetData(i,&a);

j=i+1;

while(j<=k)

{

GetData(j,&b);

if(fabs(a.coe-b.coe)<1e-10 && a.exp==b.exp)

{

DeleteData(j);

k--;

}

else

j++;

}

}

}

void CMyLinkList::Sort(bool m)

{

int i,j,k;

DataType a,b;

k=GetLength();

for(i=1;i

{

for(j=1;j<=k-i;j++)

{

GetData(j,&a);

GetData(j+1,&b);

if(a.exp

{

DeleteData(j);

DeleteData(j);

InsertData(a,j-1);

InsertData(b,j-1);

}

}

}

}

#include "iostream"

#include "MyLinkList.h"

using namespace std;

void main()

{

CMyLinkList list1,list2,list3;

cout<<"\n请输入第1个链表的数据：\n";

list1.InputData();

cout<<"\n第1个链表的当前情况是：\n";

list1.Display();

cout<<"\n请输入第2个链表的数据：\n";

list2.InputData();

cout<<"\n第2个链表的当前情况是：\n";

list2.Display();

list3=list1+list2;

cout<<"\n合并后的链表是：\n";

list3.Display();

list3.DelRepeat();

cout<<"\n删除重复元素后的链表是：\n";

list3.Display();

list3.Sort(false);

cout<<"\n按降序排列元素后的链表是：\n";

list3.Display();

}

实验4 栈

实验目的：运用栈解决实际问题

实验准备：

1. 复习栈的基本运算及其实现

2. 提取实验2或者实验3的结果，找到其中的SeqList或者LinkList文件

3. 阅读、理解中缀表达式转换成后缀表示法的算法

4. 将压缩包ex04.rar中的内容解压，双击文件夹中的dsw工程文件。当前工程中只有一个

主函数文件main.cpp。

实验步骤及要求：

1. 选取顺序结构者链式结构(任选其一)作为本题栈的物理结构，将相应的.cpp和.h文件复制到本工程的文件夹中。并修改.h文件中关于数据元素类型的定义，使其符合本实验的要求

2. 以CSeqList或者CLinkList为基类创建CStack派生类，并实现栈的基本运算。要求各函数的名称如下：

bool GetTop(DataType *q); //取栈顶元素

bool Pop(DataType *q); //退栈

bool Push(DataType x); //进栈

CStack(); //构造函数，用于创建空栈

3. 将主程序文件expchg函数补充完整，使得程序可以正确运行。

//以下是关于数据元素的类型定义，请根据实际情况修改

typedef struct datatype

{

char varible;

} DataType;

typedef DataType SeqNode;

//以下是关于SeqList类型的声明

class CSeqList

{

public:

virtual bool DeleteData(int i); //删除顺序表的第i号元素

virtual bool GetData(int i,SeqNode *q); //取顺序表的第i号元素，存放到q所指向的位置

virtual void Empty(); //将当前顺序表置为空表

virtual bool InsertData(SeqNode x,int i); //将新元素x插入到顺序表的第i号位置

CSeqList& operator=(const CSeqList &x); //重载赋值运算符

virtual int GetLength(); //取表长

virtual bool IsFull(); //判断表是否已满

virtual bool IsEmpty(); //判断表是否为空

CSeqList(int maxlen);

CSeqList(CSeqList &x); //拷贝构造函数

virtual ~CSeqList();

private:

int m_MaxLength; //最大表长

int m_CurLength; //当前表长

SeqNode *m_List; //初始化时指向申请的空间，存放表的各个元素

};

#include "SeqList.h"

#include "iostream.h"

#include "windows.h"

#include "math.h"

//构造函数

CSeqList::CSeqList(int maxlen)

{

if(maxlen<=0)

{

cout<<"构造函数创建顺序表失败：表中最多存储元素数量必须是正数\n";

exit(1);

}

m_List=new SeqNode[maxlen];

if(m_List==NULL)

{

cout<<"构造函数创建顺序表失败：内存空间不够\n";

exit(1);

}

m_CurLength=0;

m_MaxLength=maxlen;

}

//拷贝构造函数

CSeqList::CSeqList(CSeqList &x)

{

int i;

m_MaxLength=x.m_MaxLength;

m_List=new SeqNode[m_MaxLength];

if(m_List==NULL)

{

cout<<"拷贝构造函数创建顺序表失败：内存空间不够\n";

exit(1);

}

m_CurLength=x.m_CurLength;

for(i=0;i

m_List[i]=x.m_List[i];

}

//析构函数，清理内存

CSeqList::~CSeqList()

{

delete m_List;

}

//判空

bool CSeqList::IsEmpty()

{

return m_CurLength==0;

}

//判满

bool CSeqList::IsFull()

{

return m_CurLength==m_MaxLength;

}

//取表长

int CSeqList::GetLength()

{

return m_CurLength;

}

//从键盘输入数据存入顺序表中

//DEL void CSeqList::InputData()

//DEL {

//DEL int x1,x2;

//DEL cout<<"请每次输入系数和指数，用空格分隔，输入两个值均<0表示输入结束\n"; //DEL while(m_CurLength

//DEL {

//DEL cout<<"List["<

//DEL x1=x2=-1;

//DEL cin>>x1;

//DEL cin>>x2; //输入两个数值

//DEL if(x1<0 && x2<0)

//DEL break; //如果两个值都<0则表示输入完毕//DEL m_List[m_CurLength].coe=x1;

//DEL m_List[m_CurLength].exp=x2; //否则将这两个值存入顺序表

//DEL m_CurLength++;

//DEL }

//DEL }

//重载赋值运算符

CSeqList& CSeqList::operator =(const CSeqList& x)

{

int i;

m_MaxLength=x.m_MaxLength;

m_List=new SeqNode[m_MaxLength];

if(m_List==NULL)

{

cout<<"=重载时创建顺序表失败：内存空间不够\n";

exit(1);

}

m_CurLength=x.m_CurLength;

for(i=0;i

m_List[i]=x.m_List[i];

return *this;

}

//将新元素x插入到顺序表的第i号位置

bool CSeqList::InsertData(SeqNode x, int i)

{

int j,k=GetLength();

if(IsFull() || i<0 || i>k+1)

return false;

for(j=k;j>i;j--)

m_List[j]=m_List[j-1];

m_List[i]=x;

m_CurLength++;

return true;

}

//将当前顺序表置为空表

void CSeqList::Empty()

{

m_CurLength=0;

}

//取顺序表的第i号元素，存放到q所指向的位置

bool CSeqList::GetData(int i, SeqNode *q)

{

int k=GetLength();

if(i<0 || i>=k)

*q=m_List[i];

return true;

}

//删除顺序表的第i号元素

bool CSeqList::DeleteData(int i) {

int j,k=GetLength();

if(i<0 || i>=k)

return false;

for(j=i;j

m_List[j]=m_List[j+1];

m_CurLength--;

return true;

}

#include "Stack.h"

CStack::CStack(int n):CSeqList(n) {

}

CStack::~CStack()

{

}

void CStack::Push(DataType x) {

int k;

k=this->GetLength();

this->InsertData(x,k);

}

bool CStack::GetTop(DataType *q) {

int k;

if(IsEmpty())

return false;

else

{

k=GetLength();

GetData(k-1,q);

return true;

}

}

bool CStack::Pop(DataType *q) {

int k;

if(IsEmpty())

数据结构与算法设计实验

《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的

按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：

（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满

数据结构与算法C语言版期末复习题

《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构 习题 第一章 绪论

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（） A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（）

18春北理工《计算机组成原理》在线作业

(单选题) 1: 某数在计算机中用8421码表示为0111 1000 1001，其真值为（） A: 789 B: 789H C: 1929 D: 11110001001B 正确答案: (单选题) 2: 取指令操作（） A: 受上一条指令操作码的控制 B: 受当前指令操作码的控制 C: 不受指令操作码的控制 D: 受运算器中的条件码（或标志码）的控制 正确答案: (单选题) 3: 16K×32位存储器芯片的地址线有（） A: 5条 B: 14条 C: 32条 D: 46条 正确答案: (单选题) 4: 存储器进行一次完整的读写操作所需的全部时间称为（） A: 存取时间 B: 存取周期 C: CPU周期 D: 机器周期 正确答案: (单选题) 5: 浮点数的表示范围和精度取决于（） A: 阶码的位数和尾数的位数 B: 阶码采用的编码和尾数的位数 C: 阶码采用的编码和尾数采用的编码 D: 阶码的位数和尾数采用的编码 正确答案: (单选题) 6: 在主存和CPU之间增加高速缓冲存储器的目的是() A: 解决CPU和主存之间的速度匹配问题 B: 扩大主存容量 C: 扩大CPU通用寄存器的数目 D: 既扩大主存容量又扩大CPU中通用寄存器的数量 正确答案: (单选题) 7: CPU响应中断的时间是（） A: 一条指令结束 B: 外设提出中断 C: 取指周期结束 D: 任一机器周期结束 正确答案: (单选题) 8: 定点8位字长的字，采用2的补码表示时，一个字所表示的整数范围是() A: -128～127 B: -129～128 C: -127～127 D: -128～128 正确答案: (单选题) 9: 在定点机中执行算术运算时会产生溢出，其原因是（） A: 主存容量不够 B: 操作数过大 C: 操作数地址过大 D: 运算结果无法表示

计算机学院数据结构与算法分析期末试题(2007级B)_无答案

四川大学期末考试试题 （2008-2009学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师： 1．数据类型为（）。 A）数据项的集合B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合D）关键字的集合 2．链表不具有的特点是（）。 A）可随机直接访问任一元素B）插入删除不需要移动元素 C）不必事先估计元素个数D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵A nxn压缩存储在一维数组B[m]中，则m的值至少为（）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A）2k-1-1 B）2k-1C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGH IJ 中序序列：CBEDAGHFJI 注：试题字迹务必清晰，书写工整。本题2页，本页为第1页 教务处试题编号：

北京交通大学数据结构与算法期末测验考试参考答案

北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s;

(B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为 （ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有n 个结点的树中，边数只能是n-1条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ） 6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有n 个数存放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无 ?????? ? ???? ? ??=n n n n a a a a a a A ,2,1,2 ,21,21 ,1Λ Λ

数据结构与算法第1章参考答案

习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相

全国计算机二级考试 数据结构与算法

全国计算机二级考试 第一章数据结构与算法 1.一个算法一般都可以用_____、_____ 、 _____三种控制结构组合完成。 [解析]顺序、选择（分支）、循环（重复） 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是________。 [解析]算法的控制结构 在一般的计算机系统中，有算术运算、逻辑运算、关系运算和________四类基本的操作和运算。 [解析]数据传输 2.常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定方程的问题）的算法涉及基本方法是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]列举就是列举出所有可能性，将所有可能性统统列举出来，然后解决问题的方法。所以A 3.根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，这是算法设计基本方法中的____。 [解析]列举法

4.通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]B 5.在用二分法求解方程在一个闭区间的实根时，采用的算法设计技术是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]二分法就是从一半处比较，减半递推技术也称分治法，将问题减半。所以D 6.将一个复杂的问题归结为若干个简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止，这是算法设计基本方法中的___。如果一个算法P显式地调用自己则称为___。如果算法P调用另一个算法Q,而算法Q又调用算法P，则称为_____. [解析]递归法直接递归间接递归调用 7.算法中各操作之间的执行顺序称为_____。描述算法的工具通常有_____、_____ 、 _____。 [解析]控制结构传统流程图、N-S结构化流程图、算法描述语言 8.从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这

数据结构与算法实验报告

竭诚为您提供优质文档/双击可除数据结构与算法实验报告 篇一：数据结构与算法实验报告-图 沈阳工程学院 学生实验报告 （课程名称：数据结构与算法） 实验题目： 班级网络本112学号27姓名郑乐乐地点F606指导教师吕海华祝世东实验日期:20XX年11月13日 1 2 3 4 篇二：《数据结构与算法》实验报告模板 软件工程系实验报告封面 课程名称：数据结构与算法 课程代码：ss1005 实验指导老师:钟迅科

实验报告名称： 本实验报告包括以下几个内容： 一、实验(实践)目的 二、实验(实践)环境 三、实验(实践)实现过程 四、实验(实践)分析与总结 五、指导教师评语与评分 我申明，本报告内的实验已按要求完成，报告完全是由我个人完成，并没有抄袭行为。我已经保留了这份实验报告的副本。 申明人(签名): 学生姓名：张三学号：1140888888教学班：FJ01递交日期：20XX年10月11日 篇三：数据结构与算法实验报告c++版 算法与数据结构 实验报告 实验一：栈与队列 一、实验目的 1、掌握栈和队列特点、逻辑结构和存储结构 2、熟悉对栈和队列的一些基本操作和具体的函数定义。 3、利用栈和队列的基本操作完成一定功能的程序。 二、实验任务

1.出顺序栈的类定义和函数实现，利用栈的基本操作完成十进制数n与其它d进制数 的转换。（如n=1357,d=8） 2.给出顺序队列的类定义和函数实现，并利用队列计算并打印杨辉三角的前n行的内 容。(n=8) 3.给出链栈的类定义和函数实现，并设计程序完成如下功能：读入一个有限大小的整 数n，并读入n个数，然后按照与输入次序相反的次序输出各元素的值。 三、实验原理 1、将十进制数n转化为d进制时，用除去余数法，用d 除n所得余数作为d进制当前个位，将相除所得的商的整数部分作为新的n值重复上述计算，直到n为0为止。将前所得到的各余数反过来连接便得到最终结果。将每次求出的余数入栈，求解结束后，再依次出栈。 2、在杨辉三角中可用上一行的数来求出对应位置的下一行的内容。用队列保存上行内容，每当由上行的两个数求出下行的一个数时，其中的前一个便需要删除，而求出的数就 入队。为便于求解，在每行的第一个位置添加一个0作为辅助。 3、输出操作应在读入所有输入的整数后才能进行，用

北理工计算机组成原理作业题(含北理工计组高频考点)

计算机组成原理 第一章：P2存储程序概念；P3计算机的硬件组成；P7冯诺依曼结构和哈佛结构的存储器思想； 所布置题目：1-2；1-3；1-4；1-6 第二章：P16原码表示法；P17补码表示法；P18反码表示法；P19 3种机器数的比较与转换；P20机器数的定点表示和浮点表示P27例题2-13 所布置作业：2-1；2-2；2-3；2-4；2-8；2-20；2-21；2-24 第三章：P49机器指令的基本格式；P50地址码结构；P54寻址技术；P63堆栈与堆栈操作；P65指令类型； 所布置作业：3-4；3-12；*3-14；3-15；3-16 第四章：P80进位的产生和传递；P83定点加减运算+例题4-5,4-6；P91定点乘法运算+*例题4-8表4-3+*例题4-9+*例题4-10+*例题4-12+*例题4-13；P98定点除法运算；P105规格化浮点运算 所布置题目：4-4；4-5；*4-8；*4-10；4-12；4-13 第五章：P122存储器的组成；P128数据在主存中的存放；P129半导体随机储存器和只读存储器<动态RAM刷新>；P134RAM芯片分析；P139主存储器的连接与控制；P155多体交叉存储技术；P156高速缓冲存储器<地址映像>;P161虚拟存储器 所布置题目：5-4；*5-5；*5-7；*5-8；*5-10；*5-11；*5-13；*5-14；5-16；5-19 第六章：P167CPU功能+CPU中的主要寄存器；P169CPU的组成；P170CPU的主要技术参数；P172控制器的组成和实现方法；P175时序系统与控制方式<控制方式>；P181微程序控制原理 所布置作业;*6-4;6-8;*6-14;6-15 第七章:P213总线概述；P216总线仲裁； 所布置题目：7-2；7-7 注：1.带*为高概率考试题； 2.页码代表着那个标题所开始的页码，不代表结束。 3.计算机组成原理（第三版）为蒋本珊编著

数据结构与算法的实验报告

数据结构与算法第二次实验报告 电子105班 赵萌 2010021526

实验二：栈和队列的定义及基本操作 一、实验目的： . 熟练掌握栈和队列的特点 . 掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用 . 掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作 . 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力 二、实验内容: 定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素; 实现十进制数与八进制数的转换; 定义链式队列，完成队列的基本操作：入队和出队; 1．问题描述： （1）利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作： . 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底; . 完成一个元素的入栈操作，修改栈顶指针; . 完成一个元素的出栈操作，修改栈顶指针; . 读取栈顶指针所指向的元素的值; . 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除 d 取余法。例如：（1348）10=（2504）8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 从中我们可以看出，最先产生的余数 4 是转换结果的最低位，这正好符合栈的特性即后进先出的特性。 所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换; . 编写主程序，实现对各不同的算法调用。 （2）利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作： . 初始化一个空队列，形成一个带表头结点的空队; . 完成一个元素的入队操作，修改队尾指针; . 完成一个元素的出队操作，修改队头指针; . 修改主程序，实现对各不同的算法调用。

常用的大数据结构与算法

常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。

数据结构与算法上海第二工业大学二工大期末考试试卷

选择题： 1、在数据结构中，线性结构中元素之间存在____关系。 A: 一对一 B: 一对多 C: 多对一 D: 多对多 2、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的____和运算等的学科。 A: 结构 B: 关系 C: 操作 D: 算法 3、算法分析的两个主要方面是____。 A: 空间复杂度和时间复杂度 B: 正确性和简明性 C: 可读性和文档性 D: 数据复杂性和程序复杂性 4、顺序表中逻辑上相邻的节点其物理位置也____。 A: 一定相邻 B: 不必相邻 C: 按某种规律排列 D: 无要求 5、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。 A: s->next=p->next; p->next=s; B: p->next=s->next; s->next=p; C: q->next=s; s->next=p; D: p->next=s; s->next=q; 6、一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是____。 A: edcba B: decba C: dceab D: abcde 7、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。 A: (rear-front+m)%m B: rear-front+1 C: rear-front-1 D: rear-front 8、关于空格串，下列说法中正确的有____。 A: 空格串就是空串

B: 空格串是零个字符的串 C: 空格串的长度为零 D: 空格串的长度就是其包含的空格个数 9、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为____。A: SA+140 B: SA+144 C: SA+222 D: SA+225 10、对于一棵满二叉树，m个树叶，n个节点，深度为h，则____。 A: n=h+m B: h+m=2n C: m=h-1 D: n=2h-1 11、具有65个结点的完全二叉树其深度为____。（根的层次号为1） A: 8 B: 7 C: 6 D: 5 12、满二叉树____二叉树。 A: 一定是完全 B: 不一定是完全 C: 不是 D: 不是完全 13、将一棵有100个节点的完全二叉树从上到下，从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子编号为____。 A: 99 B: 98 C: 50 D: 48 14、如果T2是由森林T转换而来的二叉树，那么T中结点的后序遍历就是T2中结点的____。A: 先序遍历 B: 中序遍历 C: 后序遍历 D: 层次遍历 15、将递归算法转换成对应的非递归算法时，通常需要使用____。 A: 栈 B: 队列 C: 链表 D: 树 16、如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为____。 A: uwvts B: vwuts C: wuvts

数据结构与算法

[试题分类]：数据结构与算法 1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 A.操作 B.存储映像 C.关系 D.数据元素 答案:C 题型:单选题 知识点:1.2 基本概念和术语 难度:1 2.一般而言，最适合描述算法的语言是( )。 A.自然语言 B.计算机程序语言 C.介于自然语言和程序设计语言之间的伪语言 D.数学公式 答案:C 题型:单选题 知识点:1.4 算法和算法分析 难度:1 3．在下列序列中，不是线性表的是( )。 A. (‘a’,‘b’) B. (a, b) C. (‘AB’,‘CD’) D. (‘a’, b) 答案:D

题型:单选题 知识点:2.1 线性表的类型定义 难度:2 4.对于顺序表的优缺点，以下说法错误的是( )。 A.插入和删除操作较方便 B.可以方便地随机存取表中的任一结点 C.无需为表示结点间的逻辑关系而增加额外的存储空间 D.由于顺序表要求占用连续的空间，存储分配只能预先进行 题型:单选题 知识点:2.2线性表的顺序表示和实现 难度:2 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 A. s->next=p->next;p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q; 题型:单选题 知识点:2.3线性表的链式表示和实现 难度:2 6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。 A.单链表 B.带头结点的单链表 C.单循环链表

软件学院数据结构与算法分析期末试题(2006级B)

四川大学期末考试试题 （2007-2008学年第1学期） 课程号：课程名称：数据结构与算法分析（B卷）任课教师：适用专业年级：06级软件工程学号：姓名： （1）The primary purpose of most computer programs is a) to perform a mathematical calculation. b) to store and retrieve information. c) to sort a collection of records. d) all of the above. （2）Assume that P contains n elements. The number of sets in the powerset of P is a) n b) n^2 c) 2^n d) 2^n - 1 e) 2^n + 1 （3）Pick the growth rate that corresponds to the most efficientalgorithm as n gets large: a) 5n b) 20 log n c) 2n^2 d) 2^n （4）A sequence has the following properties: a) May have duplicates, element have a position. b) May have duplicates, elements do not have a position. c) May not have duplicates, elements have a position. d) May not have duplicates, elements do not have a position.

北理工18秋学期《计算机组成原理》在线作业

(单选题) 1: 一台显示器的图形分辨率为1 024 * 768，要求显示256种颜色，显示存储器VRAM的容量至少为（） A: 512KB B: 1MB C: 3MB D: 4MB 正确答案: (单选题) 2: 微程序控制器中，机器指令与微指令的关系是（） A: 每一条机器指令由一条微指令来执行 B: 一条机器指令由一段用微指令编成的微程序来解释执行 C: 一段机器指令组成的程序可由一个微程序来执行 D: 每一条微指令由一条机器指令来解释执行 正确答案: (单选题) 3: 16K×32位存储器芯片的地址线有（） A: 5条 B: 14条 C: 32条 D: 46条 正确答案: (单选题) 4: 运算器虽由许多部件组成，但核心部件是（） A: 算术逻辑运算单元 B: 多路开关 C: 数据总线 D: 累加寄存器 正确答案: (单选题) 5: EPROM是指（） A: 只读存储器 B: 可编程的只读存储器 C: 可擦除可编程的只读存储器 D: 闪速存储器 正确答案: (单选题) 6: 通常计算机的主存储器可采用（） A: RAM和ROM B: ROM C: RAM D: RAM或ROM 正确答案: (单选题) 7: 为组成2K×8的主存，可用两片（） A: 1K×4位芯片串联 B: 1K×8位芯片并联 C: 2K×4位芯片串联 D: 2K×4位芯片并联 正确答案: (单选题) 8: 微程序控制器的速度比硬布线控制器慢，主要是因为（） A: 增加了从磁盘存储器读取微指令的时间 B: 增加了从主存储器读取微指令的时间 C: 增加了从指令寄存器读取微指令的时间 D: 增加了从控制存储器读取微指令的时间 正确答案: (单选题) 9: 16K×32位存储器芯片的数据线有（） A: 5条 B: 14条

数据结构与算法分析实验报告

《数据结构与算法分析》实验报告 姓名学号_ _____ __年 __月__ __日 1.上机题目：以静态链表为存储结构，编写给定权值 {7,19,2,6,32,3}构造哈夫曼树的算法。（输出以存储结构表示或以树型显示(90度旋转)） 2.需求分析 （1）输入数据必须为int的整形数据，其数值范围为：-～47 （2）输出的数据格式为：%d （3）测试数据的数据为：{7,19,2,6,32,3} 3.详细设计 （1）该程序采用顺序表的存储结构，其数据结构定义如下：#define n 6 #define m 2*n-1 #define max 100typedef struct {int data; int lchild,rchild,prnt; }hufmtree; 所用数据类型中每个操作的伪码算法如下： 创建哈夫曼树 Program hufm(hufmtree t[m]) FOR i=0;i

p1=0;p2=0; small1=max;small2=max FOR j=0;j<=i-1;j++ TO IFt[j].prnt？=0 IF(t[j].data

数据结构与算法基础习题

数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 三．从供选择的答案中选取正确的答案天趣下面叙述中的横线上： 1． A 是描述客观事物的数、字符以及所能输入到计算机中并呗计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个_______组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 Ｇ：ａ规则ｂ集合ｃ结构ｄ运算 Ｈ：ａ现实性ｂ难度ｃ复杂性ｄ效率 四.分析一下各程序段，并用大“O”表示执行时间为n（正整数）的函数。 1. i:=1 k:=0; WHILE(i＜＝ｎ－１) DO BEGIN k:=ｋ＋１０*ｉ；ｉ：＝ｉ＋１ ＥＮＤ