前言
（先写点感想吧，但为什么要放在第一页呢？因为这都是我的肺腑之言，纯手打，希望老师能看到 +_+）
不积跬步，无以至千里；不积小流，无以成江海。
是的，没有打下扎实的基础无法进一步发展，没有坚持的努力无法能人所不能。这是我这次课程设计最大的感想。
一个月前，我的困惑………..
“为什么这么难？这是什么错误？为什么不能实现？我不想做了！”
这是一个月前这数据结构课程给我的感觉。为什么会有这样的感觉呢？不是因为数据结构这个课程很难，其实就是C++基础不过关，由于这一限制，让我无法在数据结构这门课程有更大的发展。大一下学期C++课程和考试都结束得比较匆忙，自己也没有认真复习，所以C++学得不好，程序根本不能轻松做出来，更别说改进算法和提升性能了。
渐渐地，我发觉了差距…………
本次课程设计有一点令我很不满。就是上机实习时间，期间刚好有两场考试，英语四级和物理，面对考试和实习这个二叉路口，选其一意味着多多少少要放弃另一，这种无形的压力让我带着抱怨去上机实习。于是，为了复习考试，我马马虎虎地应对实习，以便有更多精力去复习考试。我仿造了网上的题目做了一两个题目交给老师检查，不是不想完成，是因为确实代码不会写，也因为当时觉得考试更重要。可是，我发现一些做得好的同学，他们能在规定时间内做完，为什么他们想到的东西我也能想到，他们能写出代码我就不能呢？是因为他们C++基础好，写代码没语法错误，懂得怎样调试，也能运用书上的代码。而我就困于各种语法错误，自己的想法不能用代码实现，浪费了不少时间。顿时，我深深地感觉到C++基础这一道屏障，彻底把我围住了…………
冲破困惑，做出改变…………
正所谓“偷得半日闲”，趁着寒假的清静和放松，厌倦了游戏的虚无，没有各种烦扰嘈杂，在静静的书房内，我重拾学习C++的激情。经过一个星期，我把整本C++重新看了一遍，而且我有一种豁然开朗的感觉。渐渐地明白到以前C++的问题都是由于自己没有认真对待，得过且过，以致于日积月累形成一道屏障，连书上一些简单的程序都看不懂，编写的程序也语法错漏百出，影响的自己对C++的心情和耐性。经过一步一步的重新学习，我对C++的基础知识基本掌握，自然而然编程能力得到提升，课本上二叉树，排序等那些代码也看得懂了。课程设计的题目变得不再难，心中也收获了难得的喜悦。
Now……….
由于C++语法的掌握，我现在不再有一些无谓的时间浪费，始于编程，终于程序实现的成就感。
回顾了我的学习经历以及一些同学的例子，我发觉有好多同学为什么编程能力这么差，一方面是由于游戏诱惑实在太大了（在一些同学的眼中，游戏中的级数排名的成就感比你编写一个成功的程序大得多）和在人生道路上没有远大的目标（正所谓人各有志，一些同学觉得一个游戏高手比一个编程高手更值得称赞），另一方面是由于学习方法不当，好多基础都没掌握，限制了发展。
有一句话，成功的道路注定是孤独的。
要想获得成功，少不了寂寞和痛楚。有时梦想看似飘拂，有时现实又那么残酷，那么，在没有直行的丁字路口，你会如何选择呢？——坚持自己的信念。
End。转入正题 skipping……
目录
一、停车场管理系统 (3)
1.1 问题描述 (3)
1.2 设计思想 (3)
1.3设计表示 (3)
1.4详细设计 (4)
1.5程序测试 (10)
1.6分析小结 (11)
二、个人电话号码查询系 (11)
2.1 问题描述 (11)
2.2 设计思想 (11)
2.3设计表示 (12)
2.4详细设计 (13)
2.5程序测试 (19)
2.6分析小结 (21)
三、排序应用 (22)
3.1 问题描述 (22)
3.2 设计思想 (22)
3.3详细设计 (22)
3.4程序测试 (26)
3.5分析小结 (27)
四、“火烧连营”问题 (27)
4.1 问题描述 (27)
4.2 设计思想 (27)
4.2 设计表示 (27)
4.4详细设计 (27)
4.5程序测试 (30)
4.6分析小结 (33)
1、停车场管理
【问题描述】
设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
【设计思想】
基本要求：每一组输入数据包括三个数据项：汽车“到达”或“离去”信息，汽车牌照号以及到
达或离去的时刻。对每一组输入的数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。
实现思路：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进
行模拟管理。栈以顺序结构实现，队列以链表结构实现。需另设一个栈，临时停放为给要离去的汽车让路而从停车场推出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
【设计表示】
【详细设计】
（1）建立汽车信息类
struct car
{
int number;
int time;
};
（2）建立栈类模板，模拟停车场和倒车场
//栈以顺序结构实现
template
class Stack
{
public:
Stack(int sz=50);
~Stack(){delete[]elements;}
void Push(const T &x);
bool Pop(T &x);
bool getTop(T &x);
bool IsEmpty()const {return (top==-1)?true:false;}
bool IsFull()const {return (top==maxSize-1)?true:false;} int getSize()const {return top+1;}
void MakeEmpty() {top=-1;}
private:
T *elements;
int top;
int maxSize;
};
template
Stack
{
elements=new T[maxSize];
}
template
void Stack
{
elements[++top]=x;
}
template
bool Stack
{
if(IsEmpty()==true) return false;
x=elements[top--];
return true;
}
template
bool Stack
{
if(IsEmpty()==true) return false;
x=elements[top];
return true;
}
（3）建立队列类模板，模拟便道
//队列以链表结构实现
template
struct LinkNode
{//结点类
T data;
LinkNode
LinkNode(LinkNode
LinkNode(const T &item,LinkNode
template
class LinkedQueue
{
public:
LinkedQueue():rear(NULL),front(NULL){};
~LinkedQueue(){makeEmpty();}
bool EnQueue(const T &X);
bool DeQueue( T &X);
bool getFront(T &x)const;
void makeEmpty();
bool IsEmpty()const {return (front==NULL)?true:false;} int getSize()const;
protected:
LinkNode
};
template
void LinkedQueue
{
LinkNode
while(front!=NULL)
{
p=front;front=front->link;delete p;
}
};
template
bool LinkedQueue
{
if(front==NULL)
{
front=rear=new LinkNode
if(front==NULL) {return false;}
}
else
{
rear->link=new LinkNode
if(rear->link==NULL){return false;}
rear=rear->link;
}
return true;
}
template
bool LinkedQueue
{
if(IsEmpty()==true){return false;}
LinkNode
x=front->data;
front=front->link;delete p;
return true;
}
template
bool LinkedQueue
{
if(IsEmpty()==true){return false;}
x=front->data;
return true;
}
template
int LinkedQueue
{
LinkNode
while(p!=NULL){p=p->link;k++;}
return k;
}
（4）Arrival函数，处理到达车辆
void Arrival(Stack
{
int number,time;
cout<<"车牌号码：";
cin>>number;
car arrive;
arrive.number =number;
if(Park.IsFull())
{
cout<<"停车场已满，请等候"< line.EnQueue(arrive); cout<<"车牌为"< cout<<"==================================================="< } else { cout<<"进入时间："; cin>>time; arrive.time =time; Park.Push(arrive); cout<<"车牌为"< cout<<"==================================================="< } }; （5）Departure函数，处理离开车辆 void Departure(Stack { int number,time; int flag1=1; int flag2=1; cout<<"车牌号码："; cin>>number; cout<<"离开时间："; cin>>time; car temp; while(flag1) { Park.Pop(temp); if(temp.number ==number) {flag1=0;} else {Back.Push(temp);} } cout<<"停留时间:"< cout<<"==================================================="< while(flag2) { if(Back.IsEmpty ()==true) {flag2=0;} else { car temp; Back.Pop(temp); Park.Push(temp); } } if(line.IsEmpty()==false) { car temp; line.DeQueue(temp); cout<<"车牌为"< cout<<"==================================================="< temp.time=time; Park.Push(temp); } } （6）主函数，建立停车场、倒车场、便道，调用Arrival函数和Departure 函数实现停车场管理 int main(int argc, char* argv[]) { int n; char flag; cout<<"输入停车场大小n:"; cin>>n; Stack Stack LinkedQueue cout<<"** 欢迎进入停车场管理系统 **"< cout<<"==============================================================="< cout<<"** A --- 进入停车场 D --- 离开停车场 E --- 退出程序 **"< cout<<"==============================================================="< do { cin>>flag; switch(flag) { case 'A': Arrival(Park,Line);break; //汽车进车场 case 'D': Departure(Park,Back,Line);break; //汽车出车场 case 'E': exit(0);break; default:cout<<"选择有误，重新选择！"< } }while(flag!='E'); return 0; } 【程序测试】 测试数据： 设n=2，输入数据为：(…A?，1，5)，(…A?，2，10)，(…D?，1，15)，(…A?，3，20)，(…A?，4，25)，(…A?，5，30)，(…D?，2，35)，(…D?，4，40)，(…E?，0，0)。其中：…A?表示到达（Arrival）；… D?表示离去（Departure）；…E?表示输入结束（END）。 【分析小结】 总体上能达到题目要求。此程序的算法需要熟练掌握栈和队列，压栈和出栈，入队列和出队列是重点，选对存储结构也很重要，有利于提升性能和简化程序，而其余的较为简单。程序或许不完善，异常处理没仔细做（例如：同车牌号车进了没离开又再进入），不过这改善也比较容易。只要按照正常操作不会有问题。 2、个人电话号码查询系统 【问题描述】 人们在日常生活中经常需要查找某个人或某个单位的电话号码，本实验将实现一个简单 的个人电话号码查询系统，根据用户输入的信息（例如姓名等）进行快速查询。 【设计思想】 基本要求： （1）在外存上，用文件保存电话号码信息； （2）在内存中，设计数据结构存储电话号码信息； （3）提供查询功能：根据姓名实现快速查询； （4）提供其他维护功能：例如插入、删除、修改等。 实现方式： 由于需要管理的电话号码信息较多，而且要在程序运行结束后仍然保存电话号码信息，所以电话号码信息采用文件的形式存放到外存中。在系统运行时，需要将电话号码信息从文件调入内存来进行查找等操作，为了接收文件中的内容，要有一个数据结构与之对应，可以设计如下结构类型的数组来接收数据： const int max=10; struct TeleNumber { string name; //姓名 string phoneNumber; //固定电话号码 string mobileNumber; //移动电话号码 string email; //电子邮箱 } Tele[max]; 为了实现对电话号码的快速查询，可以将上述结构数组排序，以便应用折半查找，但是，在数组中实现插入和删除操作的代价较高。如果记录需频繁进行插入或删除操作，可以考虑采用二叉搜索树组织电话号码信息，则查找和维护都能获得较高的时间性能。更复杂地，需要考虑该二叉搜索树是否平衡，如何使之达到平衡。 【设计表示】 【详细设计】 （1）建立电话信息类结构体，用于存储从文件提取的电话信息数据 struct tel { string name; //姓名 string phoneNumber; //固定电话号码 string mobileNumber; //移动电话号码 string email; //电子邮箱 bool operator < ( tel& x) //重载：判小于 { return (name < https://www.doczj.com/doc/3d17776763.html,)?true:false; } bool operator > ( tel &x) //重载：判大于 { return name > https://www.doczj.com/doc/3d17776763.html,; } bool operator == ( tel & x) //重载：判等于 { return (name == https://www.doczj.com/doc/3d17776763.html,)?true:false; } }; （2）采用了二叉搜索树组织电话号码信息，建立二叉树类 //树结点类 struct BSTNode { tel data; BSTNode *left,*right; BSTNode():left(NULL),right(NULL){} BSTNode(const tel d,BSTNode *L=NULL,BSTNode *R=NULL):data(d),left(NULL),right(NULL){} }; //二叉搜索树类 class BST { public: BST():root(NULL){}; BSTNode * Search( tel x){return Search(x,root); }; bool Insert(tel& e1){return Insert(e1,root);} bool Remove(tel x){return Remove(x,root);} void PrintTree(){PrintTree(root);} void PrintTree(ofstream &out){PrintTree(root,out);} private: BSTNode *root; BSTNode *Search( tel x,BSTNode * ptr); bool Insert( tel& e1,BSTNode *& ptr); bool Remove(tel x,BSTNode *& ptr); void PrintTree(BSTNode *ptrt); void PrintTree(BSTNode *ptr,ofstream &out); }; //各类成员函数实现 BSTNode *BST::Search( tel x,BSTNode * ptr) { if(ptr==NULL) {return NULL;} else if(x else if(x>ptr->data ) return Search(x,ptr->right ); else {return ptr;} }; bool BST::Insert( tel& e1,BSTNode *& ptr) { if(ptr==NULL) { ptr=new BSTNode(e1); if(ptr==NULL){cout<<"Out of space"< return true; } else if(e1 else if(e1>ptr->data ) Insert(e1,ptr->right ); else return false; }; bool BST::Remove(tel x,BSTNode *& ptr) { BSTNode *temp; if(ptr!=NULL) { if(x else if(x>ptr->data ) Remove(x,ptr->right ); else if(ptr->left !=NULL&&ptr->right !=NULL) { temp=ptr->right ; while(temp->left !=NULL) temp=temp->left; ptr->data =temp->data ; Remove(ptr->data ,ptr->right ); } else { temp=ptr; if(ptr->left ==NULL) ptr=ptr->right ; else ptr=ptr->left ; delete temp;return true; } } else return false; }; void BST::PrintTree(BSTNode *ptr,ofstream &out) { if(ptr!=NULL) { out< < PrintTree(ptr->left,out ); PrintTree(ptr->right,out ); } } void BST::PrintTree(BSTNode *ptr) { if(ptr!=NULL) { cout< < PrintTree(ptr->left ); PrintTree(ptr->right ); } } （3）各功能函数实现，包括查询，添加，删除，显示，保存等 //查找 void Find(BST &Tree) { tel temp; cout<<"请输入要查找联系人姓名："; cin>>https://www.doczj.com/doc/3d17776763.html,; BSTNode *p=Tree.Search (temp); if(p!=NULL) cout<<"固定电话号码："< < else if(p==NULL) cout<<"没有所查找的联系人信息。"< } ; //添加 void Add(BST &Tree) { tel temp; cout<<"请输入联系人信息"< cout<<"姓名："; cin>>https://www.doczj.com/doc/3d17776763.html, ; if(!Tree.Search (temp)) { cout<<"固定电话号码："; cin>>temp.phoneNumber ; cout<<"移动电话号码："; cin>>temp.mobileNumber ; cout<<"邮箱："; cin>>temp.email ; Tree.Insert(temp); cout<<"添加成功"< } else cout<<"此联系人已存在"< } //删除 void Delete(BST &Tree) { cout<<"请输入要删除联系人姓名："; tel temp ; cin>>https://www.doczj.com/doc/3d17776763.html, ; if(Tree.Search (temp)) { if(Tree.Remove (temp)) cout<<"删除成功"< } else cout<<"没有此联系人"< //保存 void Save(BST &Tree) { ofstream ofile("telephone.txt"); Tree.PrintTree (ofile); ofile.close (); cout<<"保存成功"< } //取文件行数 int getTelSize() { ifstream nfile("telephone.txt"); char *line=new char[100]; int telSize=-1; while(!nfile.eof()) { nfile.getline(line,100); telSize++; }; delete line; nfile.close (); return telSize; } //显示全部电话信息 void Show(BST &Tree) { cout<<" （全部电话信息） "< cout<<"=========================================================="< cout< "< Tree.PrintTree (); } (4)主函数实现电话本系统 void main() { BST Tree;int size,telSize; char flag; telSize=getTelSize(); tel *telephone=new tel[telSize]; ifstream ifile("telephone.txt",ios_base::in); for( size=0;size { ifile>>telephone[size].name >>telephone[size].phoneNumber>>telephone[size]. mobileNumber >>telephone[size].email ; } for( size=0;size { Tree.Insert(telephone[size]) ; } cout<<" 欢迎进入电话查询系统 "< cout<<"==================================================="< cout<<"** 1 --- 查询 2 --- 添加 3 --- 删除 4 --- 显示全部 **"< cout<<"** S --- 保存 E --- 退出 **"< cout<<"==================================================="< do{ cin>>flag; switch(flag) { case '1': cout<<"（查询）"< case '2': cout<<"（添加）"< case '3': cout<<"（删除）"< case '4': Show(Tree);break; case 'S': Save(Tree);break; case 'E': exit(0);break; default:cout<<"选择有误，重新选择！"< } }while(flag!='E'); delete telephone; } 【程序测试】 读入前原文件： 运行程序： 依次进行查询，添加，删除，显示，保存操作 二叉树 1 题目 编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主程序完成如下功能（b 为如图示的一棵二叉树）： 输出二叉树b; 输出‘H’节点的左、 右孩子结点值; 输出二叉树b的深度; 输出二叉树b的结点个数; 输出二叉树b的叶子结点个数。 2 目标 熟悉二叉树的定义及其基本操作的实现 3 设计思想 二叉树的每个结点都有指向其左右孩子的指针，对二叉树的表示可以有很多方法，这里采用中序的带括号表示法，以字符串形式读入输出。建立存储结构的时候，从根结点开始，赋值定义其左右指针，由于二叉树的每个结点操作类似，因此可以采用递归的方法。 4 算法描述 （1）输入建立二叉树：读入字符串，根据括号表示法的规则，a（b,c）的括号中左右元素表示结点的左右子树结点，若结点是树（括号中还有括号），则再调用改操作，直至结点全部读入。 （2）输出二叉树：从根结点开始，打印根结点数据，如果结点的左右孩子指针不为空，就打印左括号，并按先左后右的次序调用此操作，最后输出右括号完成括号表示。 （3）输出二叉树的深度：从根结点开始，如果左或右孩子不是树的话返回深度加一，否则继续调用此操作，直到完全返回(返回深度是左、右深度中的最大值)。 （4）输出二叉树叶子结点数：从根结点开始，用ln和r n分别表示结点左右叶子结点数，函数返回叶子结点数之和，递归调用该函数，直到左右指针指空。 （5）输出二叉树结点数：结点数即是叶子数加一。 5 程序结构图 6 源程序 typedef struct node{ char data; struct node *lchild; struct node *rchild; }*Bitree; Bitree bt; void CreateBitree(Bitree &bt,char *str){ Bitree St[100],p=NULL;//100个结点的二叉树 int top=-1,k,j=0; char ch; bt=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case'(':top++;St[top]=p;k=1;break; case')':top--;break; case',':k=2;break; default:p = (struct node*)malloc(sizeof(struct node)); p->data=ch;p->lchild=p->rchild=NULL; if (bt==NULL)//是根结点 bt=p; else//是叶子结点 一、选择题 1.在逻辑上可以把数据结构分成（） A.线性结构和非线性结构 B.动态结构和静态结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 2.单链表中各结点之间的地址（） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （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．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。 程序实现的流程图如下： 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 《数据结构与算法》期末复习题 一、选择题。 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. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 数据结构复习题 第一章概论 一、选择题 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 )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15 (总分：64.00，做题时间：90分钟) 一、选择题(总题数：32，分数：64.00) 1.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （分数：2.00） A.4 √ B.6 C.m-5 D.m-6 解析：解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n．1次，就是4次。因此选项A正确。 2.下列叙述中正确的是 （分数：2.00） A.循环队列属于队列的链式存储结构 B.双向链表是二叉树的链式存储结构 C.非线性结构只能采用链式存储结构 D.有的非线性结构也可以采用顺序存储结构√ 解析：解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。 3.某二叉树中有n个叶子结点，则该二叉树中度为2l的结点数为 （分数：2.00） A.n+1 B.n-1 √ C.2n D.n／2 解析：解析：任意一棵二叉树，如果叶结点数为N 0，而度数为2的结点总数为N 2，则N 0 =N 2 +1；N 2 =N 0 -1。所以如果二叉树中有n个叶子结点，则该二叉树中度为2的结点数为n-1。因此选项B正确。4.下列叙述中错误的是 （分数：2.00） A.算法的时间复杂度与算法所处理数据的存储结构有直接关系 B.算法的空间复杂度与算法所处理数据的存储结构有直接关系 C.算法的时间复杂度与空间复杂度有直接关系√ D.算法的时间复杂度与空间复杂度没有必然的联系 解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。 5.设栈的顺序存储空间为S(0：49)，栈底指针bottom=49，栈顶指针top=30(指向栈顶元素)。则栈中的元素个数为 （分数：2.00） A.30 B.29 C.20 √ D.19 广西科技大学2015 —2016 学年第 1 学期课程考核试题试卷 考核课程数据结构与算法（ B 卷）考核班级物联网141 学生数36 印数40 考核方式闭卷考核时间120 分钟 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案。每小题1分，共33分） 1、算法是（）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 2、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第8个元素的存储地址是（）。 A. 102 B. 104 C. 106 D. 108 3、在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i+1 4、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。 A. p指向头结点 B. p指向尾结点 C. p的直接后继是头结点 D. p的直接后继是尾结点 5、在以下的叙述中，正确的是（）。 A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构 6、在一个单链表中，已知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; 7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。 A. p->next=q; q->prior=p; p->next->prior=q; q->next=q; B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D. q->next=p->next; q->prior=p; p->next=q; p->next=q; 8、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。 A. p=p->next; B. p->next=p->next->next; C. p->next=p; D.p=p->next->next; 9、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 10、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。 A. O(1) B. O(n) C. O(m) D. O(m+n) 11、线性表的顺序存储结构是一种（）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 12、循环链表的主要优点是（）。 A. 不再需要头指针 B. 已知某结点位置后能容易找到其直接前驱 C. 在进行插入、删除运算时能保证链表不断开 D. 在表中任一结点出发都能扫描整个链表 13、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。 《数据结构与算法》模拟试卷五 一、名词解释（5*3=15分） 数据结构完全二叉数 AOE网队列拓扑排序 二、填空题（1*16=16分） 1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为 ______。 2.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点 的条件是______。 3.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出 栈序列中第30个元素为______。 4.一种抽象数据类型包括______和______两个部分。 5.线性表的链式存储方式中，每个结点包括两个域，分别是______和______ 。 6.在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为 空的条件分别为单链表中______ 和 ______ 。 7.在一棵二叉树中，度为0的结点的个数是10，则度为2的结点个数是_________ 8.一个有n个结点的二叉树的深度最大为___________，最小为__________ 9.n个定点的连通图至少有_______条边。 10.二分查找的存储结构仅限于________，且是__________ 11.在对一组记录(54，38，96，72，60，15，60，45，83)进行直接插入排序时， 当把第6个记录60插入到有序表时，为寻找插入位置需比较________次。 三、选择题（1*10=10分） 1.在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点， 则执行 _______。 A、HL=p; p->next=HL; B、p->next=HL; HL=p; C、p->next=HL; p=HL; D、p->next=HL->next; HL->nxet=p; 2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n+1）时， 需要从前向后依次移动_______个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个顺序队列中，队首指针指向队首元素的_______位置。 A、当前 B、后一个 C、前一个 D、后面 4.计算递归函数如不用递归过程通常借助的数据结构是____。 A、线性表 B、双向队列 C、树 D、栈 5.如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的 ____。 A、先序排列 B、中序排列 C、后序排列 D、层序排列 6.栈的插入和删除操作在_____进行。 目录 第8章图 (2) 图的邻接矩阵举例 (2) 图的邻接表举例 (5) 8.3 图的遍历 (6) 8.3.1 深度优先遍历 (7) 8.3.2 广度优先遍历 (8) 8.4 最小生成树 (9) 8.4.1 克鲁斯卡尔（Kruskal）算法 (9) 8.4.2 普里姆（Prim）算法 (12) 8.5 最短路径 (14) 14 16 8.617 (17) 18 第8章图 图的邻接矩阵举例 import networkx as nx #调用networkx import matplotlib.pyplot as plt #调用matplotlib，绘制图 class Graph_Matrix: #邻接矩阵Adjacency Matrix def __init__(self, vertices=[], matrix=[]): self.matrix = matrix self.edges_dict = {} # {(tail, head):weight} self.edges_array = [] # (tail, head, weight) self.vertices = vertices self.num_edges = 0 if len(matrix) > 0: #创建边的列表 if len(vertices) != len(matrix): raise IndexError self.edges = self.getAllEdges() self.num_edges = len(self.edges) elif len(vertices) > 0: #节点列表 self.matrix = [[0 for col in range(len(vertices))] for row in range(len(vertices))] self.num_vertices = len(self.matrix) def isOutRange(self, x): #越界 try: if x >= self.num_vertices or x <= 0: raise IndexError except IndexError: print("节点下标出界") def isEmpty(self): #是否为空 if self.num_vertices == 0: self.num_vertices = len(self.matrix) return self.num_vertices == 0 def add_vertex(self, key): #添加结点 if key not in self.vertices: self.vertices[key] = len(self.vertices) + 1 # 添加一个节点意味着添加行和列, 对每一行都添加一列 for i in range(self.getVerticesNumbers()): self.matrix[i].append(0) self.num_vertices += 1 nRow = [0] * self.num_vertices 四川大学 《数据结构与算法分析》课程 考试模拟试卷 模拟试卷一 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩 子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双 亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表）） 要求：1、定义线性表节点的结构，并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。 四、已知一个单向链表，试给出复制该链表的算法。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。 五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数： int delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。 要求：1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1，2的基础上，完成本题。 4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。 六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面，并将N 链表的表头结点添加到空闲结点链表中。 要求：1、定义静态链表的结点的结构以及结点的型SPACE 以及位置（position ）和游标（cursor ）的型。 2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q 加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点；void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。 3、在1、2的基础上完成本题。 4、在main 函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态 表，最后将这两个静态表合并。 七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：11 11...)(e e m e m x a x a t a x A m m +++= -- 其中，系数a i ≠0，指数e i 满足e m >e m-1>…>e 2>e 1>=0。 要求：1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main 函数中，构建两个多项式，并测试相加和相乘运算。数据结构与算法问题分析及源代码之二叉树
数据结构与算法模拟试题
数据结构与算法习题及答案
大数据结构与算法课程设计程序及报告材料
数据结构与算法复习题10(C语言版)
数据结构与算法C语言版期末复习题
天津科技大学数据结构与算法课程设计
数据结构与算法复习题库含答案
数据结构与算法分析习题与参考答案
数据结构与算法试题
国家二级ACCESS机试选择题(数据结构与算法)模拟试卷15
数据结构与算法试卷(B卷)
数据结构与算法模拟试卷五
源代码--数据结构与算法(Python版)第8章 图
数据结构与算法模拟试卷一、二及参考答案
数据结构与算法练习题
相关主题
文本预览