武汉理工大学数据结构与算法综合实验连连看

《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数（小时）1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

2015-2016学年第二学期《算法与数据结构》课程实验报告专业软件工程学生姓名成晓伟班级软件141学号1410075094实验学时16实验教师徐秀芳信息工程学院实验一单链表的基本操作一、实验目的1.熟悉C语言上机环境，进一步掌握C语言的基本结构及特点。

2.掌握线性表的各种物理存储表示和C语言实现。

3.掌握单链表的各种主要操作的C语言实现。

4.通过实验理解线性表中的单链表存储表示与实现。

二、主要仪器及耗材普通计算机三、实验内容与要求1、用C语言编写一个单链表基本操作测试程序。

（1）初始化单链表（2）创建单链表（3）求单链表长度（4）输出单链表中每一个结点元素（5）指定位置插入某个元素（6）查找第i个结点元素的值（7）查找值为e 的结点，并返回该结点指针（8）删除第i个结点（9）销毁单链表2、实验要求（1）程序中用户可以选择上述基本操作。

程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。

（2）要求用线性表的顺序存储结构，带头结点的单链表存储结构分别实现。

（3）主函数实现对基本操作功能的调用。

3、主要代码（1）初始化单链表LinkList *InitList(){ //创建一个空链表,初始化线性表LinkList *L;L=(LinkList *)malloc(sizeof(LinkList));L->next=NULL;return L;}（2）创建单链表//头插法void CreateListF(LinkList *L){LinkList *s;int i=1,a=0;while(1){printf("输入第%d个元素(0表示终止)",i++);scanf("%d",&a);if(a==0)break;s=(LinkList *)malloc(sizeof(LinkList));s->data=a;s->next=L->next;L->next=s;}}（3）求链表长度int ListLength(LinkList *L){ //求链表长度int n=0;LinkList *p=L;while(p->next!=NULL){p=p->next;n++;}return(n);}（4）在指定位置插入元素int InsertList(LinkList *L,int i,ElemType e){LinkList *p=L,*s;int j=0;while(p!=NULL&&j<i-1){p=p->next;j++;} //找出要插入的位置的前一个位置if(p==NULL){return 0;}else{s=(LinkList *)malloc(sizeof(LinkList));s->data=e;s->next=p->next;p->next=s;return 1;}}（5）输出链表void DispList(LinkList *L){ //输出链表LinkList *p=L->next;while(p!=NULL){printf("%d",p->data);p=p->next;}printf("\n");}（6）查找链表中指定元素int GetElem(LinkList *L,int i){ //查找链表中指定元素LinkList *p=L;int j=0;while(j<i&&p!=NULL){j++;p=p->next;}if(p==NULL){return 0;}else{return p->data;}}（7）查找值是e的结点并返回该指针LinkList *LocateElem(LinkList *L,ElemType e){ //查找值是e的结点并返回该指针int i=1;LinkList *p=L;while(p!=NULL)if(p->data==e) return p;}if(p==NULL){return NULL;}}（8）删除元素int ListDelete(LinkList *L,int i,ElemType *e){ //删除元素LinkList *p=L,*q;int j=0;while(p!=NULL&&j<i-1){p=p->next;j++;} //找到要删除元素地址的前一个地址if(p==NULL){ return 0;} //不能删除else{q=p->next;*e=q->data;p->next=q->next;free(q); //删除成功return 1;}}（9）销毁链表void DestroyList(LinkList *L){//销毁链表LinkList *pre=L,*p=L->next;while(p!=NULL){free(pre);pre=p;p=pre->next;}free(pre);}main函数：int main(){LinkList *L;ElemType e;int i;L=InitList();CreateListF(L);DispList(L);printf("输入要查找的元素位置:\n");scanf("%d",&i);e=GetElem(L,i);printf("%d\n",e);printf("单链表长度为:%d\n",ListLength(L));printf("输入要删除元素的位置:");scanf("%d",&i);if (i>ListLength(L)){printf("超出范围重新输入");scanf("%d",&i);}if(ListDelete(L,i,&e)==0){printf("未找到元素\n");}else DispList(L);printf("输入插入元素的位置和值:");scanf("%d%d",&i,&e);InsertList(L,i,e);DispList(L);return 0;}4、测试数据及测试结果输入：23 56 12 28 45输出：四、注意事项1、存储结构定义和基本操作尽可能用头文件实现。

连连看思路算法及实现连连看是一款经典的益智游戏，其玩法简单，规则清晰，深受广大玩家喜爱。

在这个游戏中，我们需要通过消除相同的图案来获得高分。

而要想在游戏中取得好成绩，则需要掌握一定的思路算法和实现方法。

一、思路算法1.寻找相同图案在连连看游戏中，最基本的操作就是寻找相同的图案。

因此，在进行游戏时，我们需要将所有可消除的图案都找出来，并建立起它们之间的关联关系。

2.建立关联关系建立图案之间的关联关系是为了方便后续操作。

我们可以使用二维数组或者链表等数据结构来存储每个图案以及它们之间的连接情况。

对于每一个图案，我们可以将其坐标作为数组下标，并将其与周围相邻的图案进行连接。

3.寻找可消除路径在建立好每个图案之间的连接关系后，我们就可以开始寻找可消除路径了。

通常情况下，可消除路径有两种：直线型和弯曲型。

对于直线型路径，我们只需要判断两个图案之间是否存在直线连接即可；而对于弯曲型路径，则需要考虑路径中是否存在转折点。

4.消除图案当我们找到了可消除路径后，就可以进行图案的消除操作了。

在消除时，我们需要将所有经过的图案都从数据结构中删除，并将得分累加到总分中。

此外，在进行消除操作时，我们还需要考虑一些特殊情况，如图案之间存在障碍物等。

5.判断游戏结束当所有的图案都被消除或者无法再进行消除操作时，游戏就结束了。

在判断游戏是否结束时，我们可以检查当前数据结构中是否还有未被消除的图案。

如果存在未被消除的图案，则说明游戏还未结束；否则，游戏就已经结束了。

二、实现方法1.数据结构在实现连连看游戏时，我们通常使用二维数组或链表等数据结构来存储每个图案以及它们之间的连接关系。

对于二维数组来说，其优点是存储简单、操作方便；而链表则更加灵活，可以动态地添加和删除元素。

2.算法实现在实现连连看游戏时，我们需要编写一些算法来完成相应的功能。

例如，在寻找可消除路径时，我们可以使用广度优先搜索算法（BFS）或深度优先搜索算法（DFS）来遍历所有可能的路径，并找到其中符合要求的路径。

专业基础实践任务书学生姓名专业班级:指导教师:工作单位: 信息工程学院题目: 专业基础实践第套综合题初始条件:（）提供实验室机房及其以上版本软件；（）《教程》学习。

要求完成的主要任务:(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求):（）选择一本《教程》，认真学习该教程的全部内容，包括基本使用方法、数组运算、矩阵运算、数学运算、程序设计、符号计算、图形绘制、设计等内容；（）对该套综合题的道题，进行理论分析，针对具体设计部分的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码（含注释），上机调试运行程序，记录实验结果（含计算结果和图表）。

（）对实验结果进行分析和总结；（）要求阅读相关参考文献不少于篇；（）根据课程设计有关规范，按时、独立完成专业基础实践说明书。

时间安排:（）布置课程设计任务,查阅资料,学习《教程》天；（）进行编程设计天；（）完成专业基础实践报告书天；（）答辩天；指导教师签名: 年月日系主任(或责任教师)签名: 年月日目录摘要 (Ⅰ)第1章关于的简介的功能的典型应用第2章设计题目第3章设计内容题一题二题三题四题五题六题七题八题九题十第4章心得体会参考文献摘要（矩阵实验室）是的缩写，是一款由美国公司出品的商业数学软件。

是一种用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境。

除了矩阵运算、绘制函数数据图像等常用功能外，还可以用来创建用户界面及与调用其它语言（包括，和）编写的程序。

尽管主要用于数值运算，但利用为数众多的附加工具箱（）它也适合不同领域的应用，例如控制系统设计与分析、图像处理、信号处理与通讯、金融建模和分析等。

另外还有一个配套软件包，提供了一个可视化开发环境，常用于系统模拟、动态嵌入式系统开发等方面。

是一个包含大量计算算法的集合。

其拥有多个工程中要用到的数学运算函数，可以方便的实现用户所需的各种计算功能。

函数中所使用的算法都是科研和工程计算中的最新研究成果，而前经过了各种优化和容错处理。

《数据结构》实验1《数据结构与算法》第1次实验题目及要求实验一：线性表、队列与栈及其操作算法一、实验内容1．建立包括头结点和3个结点（4，2，1）的单链表，实现单链表建立、插入、删除和顺序查找等基本操作。

2．编程用一维数组来模拟一个栈，实现入栈和出栈操作，解决括号匹配问题。

3．编程用一维数组来模拟一个队列，实现入队列和出队列操作，解决杨辉三角问题。

二、实验要求1．掌握单链表的各种运算（表内结点的插入﹑删除，输出单链表等）。

2．掌握栈的结构和算法应用。

3．掌握队列的结构和算法应用。

三、实验报告要求实验报告使用教务处统一印制的《武汉理工大学学生实验报告书》，主要包括：1) 实验预习报告：主要包括下列内容：[1] 实验目的和意义。

[2] 问题描述：包括目标、任务、条件和约束的描述。

[3] 实验原理与方法：阐述所使用的方案的工作原理。

[4] 实验方案和技术路线，包括：数据结构设计和核心算法设计描述、主模块及功能模块层次结构、主要功能模块的输入、输出和算法框架描述、功能模块之间的调用与被调用关系等内容。

2) 实验过程记录：主要包括下列内容：[1] 上机实验的调试过程，包括编译时出现的错误信息、错误分析、解决方法和解决过程。

[2] 上机实验的测试过程，包括测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。

[3] 软件使用说明：主要描述如何使用你的程序以及使用时的主要事项。

[4] 实验输出结果。

3) 结果与讨论：主要包括下列内容：[1] 实验结果分析：对本次实验进行分析和评价。

[2] 小结、建议和体会：说明程序的改进思想、经验和体会。

[3] 思考题：回答教师布置的讨论题。

[4] 程序清单：根据教师的要求，以电子文档形式或者打印附件形式提交所设计的程序清单。

要求：1、用Visual C++ 上机编程，请预习VC++软件；2、本要求适用后面两个实验；3、请同学们做实验时把课本带来，需要借助书上的例子；4、不能在课堂上完成的，自己课后完成，然后将课后完成的结果运行给老师看。

2022年武昌理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A.快速排序B.堆排序C.归并排序D.直接插入排序3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、设X是树T中的一个非根结点，B是T所对应的二叉树。

算法设计综合实训题目0．逆序数字（借助栈）编写一个函数，接收一个4位整数值，返回这个数中数字逆序后的结果值。

例如，给定数7631，函数返回1367.输入：第一行一个正整数T（T<=10），表示有T组测试数据; 以下T行，每行一个非负的整数N。

输出：共T行，对于每组输入数据输出一行，即数字逆序后的结果值。

样本输入：3763110185158样本输出：1367810185151．人见人爱A+B这个题目的A和B不是简单的整数，而是两个时间，A和B 都是由3个整数组成，分别表示时分秒，比如，假设A为34 45 56，就表示A所表示的时间是34小时 45分钟 56秒。

输入：输入数据有多行组成，首先是一个整数N，表示测试实例的个数，然后是N行数据，每行有6个整数AH,AM,AS,BH,BM,BS，分别表示时间A和B所对应的时分秒。

题目保证所有的数据合法。

输出：对于每个测试实例，输出A+B，每个输出结果也是由时分秒3部分组成，同时也要满足时间的规则（即：分和秒的取值范围在0-59），每个输出占一行，并且所有的部分都可以用32位整数表示。

样本输入：21 2 3 4 5 634 45 56 12 23 34样本输出：5 7 947 9 302．敲七【问题描述】输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【要求】【数据输入】一个整数N。

(N不大于30000)【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。

【样例输入】20【样例输出】714173．统计同成绩学生人数问题【问题描述】读入N名学生的成绩，将获得某一给定分数的学生人数输出。

【要求】【数据输入】测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。

第3行：给定分数当读到N=0时输入结束。

其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

学号：课程设计题目链式简单选择排序学院计算机科学与技术学院专业班级姓名LDSD指导教师耿枫2013 年7 月 2 日课程设计任务书学生姓名： LDSD 专业班级：指导教师：耿枫工作单位：计算机科学与技术学院题目:链式简单选择排序初始条件：试写一个程序，以单链表作为存储结构，实现简单选择排序。

1、课程设计报告中应有你的算法的时间复杂度分析；2、测试用例自己设计。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1、问题描述简述题目要解决的问题是什么。

2、设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4、经验和体会（包括对算法改进的设想）5、附源程序清单和运行结果。

源程序要加注释。

如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

时间安排：1、第20周（6月29日至7月3日）完成。

2、7月3 日8：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。

指导教师签名：年月日系主任（或责任教师）签名：年月日目录1．课程设计问题描述及开发工具........................................... - 4 -1.1 课程设计问题描述................................................ - 4 -1.2 开发工具........................................................ - 4 - 2．程序设计............................................................. - 4 -2.1思想描述......................................................... - 4 -2.2存储结构设计..................................................... - 6 -2.3 主要算法设计.................................................... - 6 -2.3.1 链表的创建................................................. - 6 -2.3.2随机数据产生函数........................................... - 7 -2.3.3链式简单排序............................................... - 8 -2.3.4词法分析................................................... - 9 - 3．程序调试过程问题与改正............................................... - 9 - 4．运行结果及说明...................................................... - 10 -4.1以随机方式创建链表.............................................. - 10 -4.2 用户自己写入数据............................................... - 11 -4.3 比较三组不同输入数据的排序..................................... - 11 - 5．时间复杂度分析...................................................... - 13 - 6．经验与体会.......................................................... - 14 - 7．课程设计源程序...................................................... - 14 -链式简单选择排序链式简单选择排序主要涉及到数据结构中链表和排序两个知识点，其中，链表的知识又涉及创建、插入、遍历等。

实验2 栈和队列的基本操作和应用1实验目的(1)熟练掌握顺序栈的基本操作。

(2)掌握顺序栈的应用。

(3)掌握顺序循环队列的基本操作。

(4)掌握链式队列的基本操作。

2实验内容(1)设计一个顺序栈的基本操作的演示程序；(2)利用顺序栈，进行整数的不同进制之间的转换；(3)设计一个顺序循环队列的基本操作演示程序；(4)设计一个链式队列的基本操作演示程序。

【基本要求】I.实验内容(1)的基本要求：编写一个程序，将一个顺序栈的元素依次取出，并打印其元素值。

II.实验内容(2)的基本要求：编写一个程序，将一个非负的十进制整数转换成二进制。

III.实验内容(3)的基本要求：编写一个程序，将一个顺序队列的元素依次取出，并打印其元素值。

IV.实验内容(4)的基本要求：编写一个程序，将一个链式队列的元素依次取出，并打印其元素值。

【测试数据】自定3实验结果按照学校实验格式要求撰写实验报告，内容主要包括1）实验目的；2）实验内容；3）实验环境和方法；4）实验过程描述；5）实验心得体会参考程序如下：实验内容（1）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;//typedef char ElemType;typedef struct SqStack {ElemType *base;ElemType *top;int stacksize;}SqStack;enum Status{OK,ERROR,OVERFLOW};/*sqStackOp.h文件*/#include "sqStack.h"Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"Status InitStack(SqStack &S) {//构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(! S.base) exit(OVERFLOW); //存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;return OK;} //InitStackStatus GetTop(SqStack S,ElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top==S.base) return ERROR;e=*(S.top-1);return OK;} //GetTopStatus Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*S.top++=e;return OK;} //PushStatus Pop(SqStack &S,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(--S.top);return OK;} //Push//判断栈是否为空bool StackEmpty(SqStack &S){if(S.top == S.base)return true;elsereturn false;}/*main.cpp文件*/#include <stdio.h>#include <stdlib.h>#include "sqStackOp.h"void main(){printf("Hellow stack \n");SqStack S; //定义顺序栈Sif(OK != InitStack(S)) {printf("顺序栈初始化出错，退出....\n");exit(-1);}Push(S, 1);Push(S,2);Push(S,3);int e;Pop(S, e);printf("出栈元素= %d \n",e);Push(S,4);Push(S,5);while(!StackEmpty(S)){Pop(S, e);printf("出栈元素= %d \n",e);}/*SqStack S; char x,y;InitStack(S); x='c';y='k';Push(S,x); Push(S,'a'); Push(S,y);Pop(S,x); Push(S,'t'); Push(S,x);Pop(S,x); Push(S,'s');while(!StackEmpty(S)){ Pop(S,y);printf("%c ",y); };printf("%c ",x);*/getchar();}实验内容（2）参考程序/*sqStack.h文件*/#define INIT_SIZE 100#define INCREMENT 10typedef int ElemType;typedef struct SqStack {ElemType *base;ElemType *top;int stacksize;}SqStack;enum Status{OK,ERROR,OVERFLOW};/*sqStackOp.h文件*/#include "sqStack.h"Status InitStack(SqStack &S) ;Status GetTop(SqStack S,ElemType &e);Status Push(SqStack &S,ElemType e);Status Pop(SqStack &S,ElemType &e);bool StackEmpty(SqStack &S);/*sqStackOp.cpp文件*/#include <malloc.h>#include <stdlib.h>#include "sqStackOp.h"Status InitStack(SqStack &S) {//构造一个空的栈S.base=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(! S.base) exit(OVERFLOW); //存储分配失败S.top=S.base;S.stacksize=INIT_SIZE;return OK;} //InitStackStatus GetTop(SqStack S,ElemType &e){//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(S.top-1);return OK;} //GetTopStatus Push(SqStack &S,ElemType e){//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间S.base=(ElemType *)realloc(S.base,(S.stacksize+INCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW); //存储分配失败S.top=S.base+S.stacksize;S.stacksize+=INCREMENT;}*S.top++=e;return OK;} //PushStatus Pop(SqStack &S,ElemType &e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base) return ERROR;e=*(--S.top);return OK;} //Push//判断栈是否为空bool StackEmpty(SqStack &S){if(S.top == S.base)return true;elsereturn false;}/*main.cpp文件*/#include <stdio.h>#include <stdlib.h>#include "sqStackOp.h"void main(){SqStack s;int x;InitStack(s);scanf("%d",&x); //%d--十进制输入；%O--八进制输入；%x--十六进制输入//修改这里输入进制和下面整除和余数计算，就可以获得其他进制的转换while(x!=0){Push(s,x%8);x=x/8;}while(!StackEmpty(s)){Pop(s,x);printf("%d ",x);}printf("\n");getchar();}实验内容（3）参考程序/*sqQueue.h 文件*/#define MAXQSIZE 100typedef int QElemType;typedef struct SqQueue {QElemType *base;int front;int rear;}SqQueue;enum Status{OK,ERROR,OVERFLOW};/*sqQueueOp.h 文件*/#include "sqQueue.h"Status InitQueue (SqQueue &Q) ;Status EnQueue (SqQueue &Q, QElemType e);Status DeQueue (SqQueue &Q, QElemType &e) ;bool QueueEmpty(SqQueue &Q);int QueueLength(SqQueue Q);/*sqQueueOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "sqQueueOp.h"Status InitQueue (SqQueue &Q) {// 构造一个空队列QQ.base = (QElemType *) malloc(MAXQSIZE *sizeof (QElemType));if (!Q.base) exit (OVERFLOW);// 存储分配失败Q.front = Q.rear = 0;return OK;}Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素if ((Q.rear+1) % MAXQSIZE == Q.front)return ERROR; //队列满Q.base[Q.rear] = e;Q.rear = (Q.rear+1) % MAXQSIZE;return OK;}Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，// 用e返回其值，并返回OK; 否则返回ERRORif (Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front+1) % MAXQSIZE;return OK;}//判断队列是否为空bool QueueEmpty(SqQueue &Q){if(Q.front== Q.rear)return true;elsereturn false;}//计算循环队列长度int QueueLength(SqQueue Q){return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;}/*main.cpp 文件*/#include <stdio.h>#include <stdlib.h>#include "sqQueueOp.h"void main(){printf("Hello Queue \n");SqQueue Q; //定义顺序队列QQElemType e;if(OK != InitQueue(Q)) {printf("顺序队列初始化出错，退出....\n");exit(-1);}EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);printf("当前队列长度= %d \n",QueueLength(Q));DeQueue(Q,e);printf("队首元素%d出队，当前队列长度=%d\n",e,QueueLength(Q));EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)){DeQueue(Q,e);printf("队首元素%d出队，当前队列长度=%d\n",e,QueueLength(Q));}getchar();}实验内容（4）参考程序/*linkQueue.h 文件*/typedef int QElemType;typedef struct QNode {// 结点类型QElemType data;struct QNode *next;} QNode, *QueuePtr;typedef struct { // 链队列类型QueuePtr front; // 队头指针QueuePtr rear; // 队尾指针} LinkQueue;enum Status{OK,ERROR,OVERFLOW};/*linkQueueOp.h 文件*/#include "linkQueue.h"Status InitQueue (LinkQueue &Q) ;Status EnQueue (LinkQueue &Q, QElemType e); Status DeQueue (LinkQueue &Q, QElemType &e) ; bool QueueEmpty(LinkQueue &Q);/*linkQueueOp.cpp 文件*/#include <malloc.h>#include <stdlib.h>#include "linkQueueOp.h"Status InitQueue (LinkQueue &Q) {// 构造一个空队列QQ.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));if (!Q.front) exit (OVERFLOW);//存储分配失败Q.front->next = NULL;return OK;}Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素QueuePtr p = (QueuePtr) malloc (sizeof (QNode));if (!p) exit (OVERFLOW); //存储分配失败p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;}Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素，//用e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR;QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if (Q.rear == p) Q.rear = Q.front;free (p);return OK;}//判断队列是否为空bool QueueEmpty(LinkQueue &Q){if(Q.front == Q.rear)return true;elsereturn false;}/*main.cpp 文件*/#include <stdio.h>#include <stdlib.h>#include "linkQueueOp.h"void main(){printf("Hello LinkQueue \n");LinkQueue Q; //定义顺序队列QQElemType e;if(OK != InitQueue(Q)) {printf("顺序队列初始化出错，退出....\n");exit(-1);}EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);DeQueue(Q,e);printf("队首元素%d出队，\n",e);EnQueue(Q,9);EnQueue(Q,11);while(!QueueEmpty(Q)){DeQueue(Q,e);printf("队首元素%d出队，\n",e);}getchar();}。

一、判断(共计40分,每题2.5分)1、层次遍历初始堆可以得到一个有序的序列。

（）A. 正确B. 错误错误:【B】2、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（）A. 正确B. 错误错误:【A】3、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误错误:【B】4、快速排序是排序算法中平均性能最好的一种排序。

（）A. 正确B. 错误错误:【A】5、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（）A. 正确B. 错误错误:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误错误:【A】7、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误错误:【A】8、线性表的顺序存储结构比链式存储结构更好。

（）A. 正确B. 错误错误:【B】9、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确错误:【A】10、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误错误:【B】11、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误错误:【B】12、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）A. 正确B. 错误错误:【B】13、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（）A. 正确B. 错误错误:【A】14、非空的双向循环链表中任何结点的前驱指针均不为空。

（）A. 正确B. 错误错误:【A】15、对连通图进行深度优先遍历可以访问到该图中的所有顶点。

（）A. 正确B. 错误错误:【A】16、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误错误:【A】二、单选(共计60分,每题2.5分)17、设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。

武汉理工大学华夏学院2011～2012学年第二学期公共选修课课程介绍1、汽车文化与人类文明（32学时/2.0学分）开课单位：汽车工程系开课对象： 08、09级本科、10级本专科课程简介：本课程主要讲解世界汽车发展史、中国汽车发展史、汽车的总体结构、发动机结构、汽车性能、汽车新技术概况、汽车的选购，汽车驾驶等方面的知识。

教师简介：余晨光武汉理工大学汽车学院博士研究生，讲师。

参与省科技攻关项目《湖北省电动汽车发展规划》、武汉市《WG6120HEV混合动力电动汽车的研制》及其他横向科研课题。

2、化学.人类.社会（32学时/2.0学分）开课单位：化学与制药工程系开课对象：08、09级本科、10级本专科课程简介：化学是一门与人类生活有着密切关系的基础学科。

它所涉及的范围可以说是无所不包，以至于在人类的生活、生产过程中无处不在。

教师简介：魏登贵武汉理工大学应用化学系化学实验中心主任副教授长期从事本科生的教学及研究工作，先后讲授6门化学类课程。

主持和参与了多项教学研究项目和科学研究项目，发表论文二十余篇。

3、现代环境意识（32学时/2.0学分）开课单位：化学与制药工程系开课对象：08、09、10级本科课程简介：本课程以环境学的基本原理为依据，介绍环境学的基础知识和基本概念、可持续发展的事项和原则，探讨环境问题的发生、发展以及在人类活动影响下引起的环境各个要素的变化，阐述了人口、能源、资源、城市和人类工程建设与环境的相互作用。

教师简介：李德忠华中科技大学化学与化工学院副教授，硕士导师，湖北省物理化学专业委员会副主任会员，先后十五次获得湖北省及华科大的各类教学质量优秀奖和教学研究成果奖。

主编高校教材二本，主审高校教材三本，发表科研和教学论文三十六篇。

4、中华诗词欣赏（32学时/2.0学分）开课单位：人文与艺术系开课对象：09级本科、10级本专科课程简介：本课程通过讲解中华诗词是中华民族几千年灿烂文化的重要组成部分，是中华民族智慧的结晶。

计算机科学与技术专业“卓越工程师培养计划”试点方案二○一一年十二月目录1. 专业基本情况 (2)2. 实施卓越工程师培养计划的基础 (5)3. 合作培养依托单位 (6)4. 培养方案 (7)4.1 本科阶段 (7)5. 质量保障与监控体系 (17)5.1 校内学习阶段 (18)5.2 企业学习阶段 (20)5.3 学生校外学习期间相关要求及注意事项 (18)6. 工程教育改革理论研究 (18)6.1 工程教育思想和教学规律研究 (19)6.2 工程教育理论提升 (19)附件1：武汉理工大学“卓越工程师培养计划”计算机科学与技术专业校企联合培养协议书 (21)附件2：计算机科学与技术卓越工程师培养专业标准 (22)附件3：计算机科学与技术专业卓越工程师培养计划 (29)附件4：武汉理工大学计算机工程师企业培养方案 (36)附件5：武汉理工大学计算机科学与技术专业“卓越工程师培养计划”师资队伍建设方案 (39)1. 专业基本情况发展历史：武汉理工大学是教育部直属的全国重点大学、国家“211工程”的重点建设高校。

计算机科学与技术专业是我校恢复高考制度以来开办的最早专业院系之一，我校计算科学与技术专业的创办和建设可以追溯到1979年，是国内较早创办计算机专业的院校之一，迄今已有30年的办学历史。

1984年开始招收计算机应用专业本科生，1986年开始招收计算机应用方向研究生，1992年获计算机应用硕士学位授予权，1997年被评为湖北省重点学科，2002年获计算机应用博士学位授予权，2007年获计算机科学与技术一级学科硕士学位授予权，正在申报计算机科学与技术一级学科博士学位授予权，目前已通过第一轮评审。

2010年计算机科学与技术专业被授予武汉理工大学本科品牌专业。

经过30年的发展与建设，武汉理工大学计算机科学与技术专业目前已具备“计算机应用技术”博士学位授予权、“计算机应用技术”和“计算机软件与理论”硕士学位授予权、“计算机科学与技术”和“计算机软件工程”学士学位授予权，“计算机应用技术”为湖北省重点学科，形成了从本科到博士的培养体系。

数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。

（）A. 正确B. 错误答案:【A】2、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误答案:【B】3、对连通图进行深度优先遍历可以访问到该图中的所有顶点。

（）A. 正确B. 错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误答案:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误答案:【A】7、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误答案:【A】8、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（）B. 错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确B. 错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。

（）A. 正确B. 错误答案:【A】11、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（）A. 正确B. 错误答案:【A】12、线性表的顺序存储结构比链式存储结构更好。

（）A. 正确B. 错误答案:【B】13、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）A. 正确B. 错误答案:【B】14、层次遍历初始堆可以得到一个有序的序列。

（）A. 正确B. 错误答案:【B】15、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误答案:【A】16、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（）B. 错误答案:【B】二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。