安徽工程大学数据结构各章作业和实验

实验一约瑟夫问题实现1、实验目的1）掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。

2）掌握在顺序结构中实现查找、插入、删除操作的基本方法。

3）掌握在各种链表结构中实现查找、插入、删除操作的基本方法2、实验内容设有n个人围坐在一圈，现从指定的第个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，如此重复，直到所有的人全部出列为止。

3、实验要求针对实验内容，认真设计算法，上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序，上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）顺序结构：#include "stdio.h"#include "stdlib.h"#define MAXSIZE 100typedef struct node{int data[MAXSIZE];int length;}SeqList,*PSeqList;int Delete(PSeqList PL,int i){int j;if(!PL){printf(" 表不存在");return (-1);}if(i<1||i>PL->length){printf(" 删除位置不合法");return(0);}for(j=i;j<PL->length;j++){PL->data[j-1]=PL->data[j];}PL->length--;return(1);}PSeqList Init(void){int n,i;PSeqList PL;PL=(PSeqList)malloc(sizeof(SeqList));if(PL) {PL->length=0;}printf(" 请输入圆桌人数:\n");scanf("%d",&n);if(n>MAXSIZE)printf(" 溢出");for(i=0;i<n;i++){PL->data[i]=i;PL->length++;}return PL;}int yuesefu(PSeqList yuesefu,int s,int m){int s1,i,w;if(!yuesefu->length){printf(" 表中无元素");return(0);}s1=s-1;printf(" 输出约瑟夫序列:\n");for(i=yuesefu->length;i>0;i--){s1=(s1+m-1)%i;w=yuesefu->data[s1];printf("%d\t",w);Delete(yuesefu,s1+1);}return(1);}void main(){PSeqList PL;int m,n;PL=Init();printf(" 请分别输入起始序号和计数值:\n");scanf("%d%d",&m,&n);yuesefu(PL,4,3);}链式结构：#include <stdio.h>#include <stdlib.h>#include <cstdlib>typedef struct node{int data;struct node* next;}Lnode,*Linklist;Linklist create(int n){int i;Linklist head;Linklist p1,p2;p1=p2=(Linklist)malloc(sizeof(Lnode));p1->data=0;head=p1;for(i=1;i<n;i++){p2=p1;p1=(Linklist)malloc(sizeof(Lnode));p1->data=i;p2->next=p1;}p1->next=head;return(head);}int yuesefu(Linklist yuesefu,int s,int m){Linklist p,pre;int count;if(!yuesefu){printf("表中无元素");return(0);}p=yuesefu;for(count=1;count<s;count++){p=p->next;}printf("输出约瑟夫序列:\n");while(p!=p->next){pre=p->next;while(pre->next!=p) {pre=pre->next;}for(count=1;count<m;count++){pre=p;p=p->next;}printf("%d\t",p->data);pre->next=p->next;free(p);p=pre->next;}printf("%d\t",p->data);free(p);return(1);}int main(){Linklist PL;int s,m,n;printf("请输入圆桌的人数,起始位置,间隔\n");scanf("%d%d%d",&s,&m,&n);PL=create(s);yuesefu(PL,m,n);return(1);}静态链表：(选做)实验二数制转换算法实现1、实验目的1）掌握栈、队列的两类存储结构（顺序存储结构和链式存储结构）的描述方法。

作业11、编写一个函数deleteV_seq( PSeqList palist , int x)，在palist所指的顺序表中，删除一个值为x的元素，返回成功与否的标志。

#include<iostream>#include<stdlib.h>using namespace std ;#define MAXSIZE 100typedef struct{int data[MAXSIZE] ;int length ;}SeqList ;typedef SeqList *PSeqList ;PSeqList Init_SeqList(){PSeqList palist = (PSeqList)malloc(sizeof(SeqList)) ;if(palist != NULL){palist-> length = 0 ;return (palist) ;}cout<<"Out of space!"<<endl ;return NULL ;}int isNullList_seq(PSeqList palist){return(palist->length == 0) ;}int insertPre_seq(PSeqList palist ,int p ,int x){int q ;if(palist->length >= MAXSIZE){cout<<"overflow!"<<endl ;return 0 ;}if(p<0 || p>palist->length){cout<<"Not exist!"<<endl ;return 0 ;}if(isNullList_seq(palist)){palist->data[0] = x ;palist->length = 1 ;return 1 ;}for(q = palist->length-1 ;q >=p ;q --)palist->data[q+1] = palist->data[q] ;palist->data[p] = x ;palist->length = palist->length+1 ;return 1 ;}PSeqList deleteV_Seq(PSeqList palist ,int x){int i ,j=0 ,k ,a[10] ;if(!palist){cout<<"表不存在！"<<endl ;return 0 ;}for(i = 0 ; i < palist->length ; i ++)if(palist->data[i] == x)a[j++] = i ;for(i = 0 ; i < j ;i ++){for(k = a[i]-i ; k < palist->length ; k ++)palist->data[k] = palist->data[k+1] ;palist->length -- ;}return palist ;}void main(){int i ,n ,x ,a ;PSeqList palist ;palist = Init_SeqList() ;cout<<"请输入数据个数：" ;cin>>n ;cout<<"请输入数据："<<endl ;for(i = 0 ; i < n ; i ++){cin>>a ;insertPre_seq(palist , i , a ) ;}cout<<"原始数据为："<<endl ;for(i=0;i<palist->length;i++)cout<<palist->data[i]<<" ";cout<<endl ;cout<<"请输入想要删除的数据：" ;cin>>x ;deleteV_Seq(palist,x) ;cout<<"删除后的数据:"<<endl ;for(i=0;i<palist->length;i++)cout<<palist->data[i]<<" ";cout<<endl ;}2、已知list是指向无头结点的单链表的指针变量，写出删除该链表中从第i个结点开始的连续k个结点的算法。

数据结构课外实践报告项目名称：迷宫所在班级： 2013级软件工程小组成员任课教师：起止时间：项目基本信息课外实践评定成绩记录一、问题描述及分析本实验的目的是设计一个程序，实现手动或者自动生成一个n×m矩阵的迷宫，寻找一条从入口点到出口点的通路。

我们将其简化成具体实验内容如下：选择手动或者自动生成一个n×m，的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。

假设从起点出发，目的为右下角终点，可向“上，下，左，右，左上，右上，左下，右下”8个方向行走。

如果迷宫可以走通，则用“▇”代表1，用“□”代表“0”，用“→”代表迷宫所走的路径，输出迷宫原型图、迷宫路线图以及迷宫行走路径。

如果迷宫为死迷宫，输出信息。

二、功能模块及数据结构描述本程序包含三个模块：（1）主程序模块：void main(){初始化；do{接收命令；处理命令；}while（命令！=退出）；}（2）栈模块——实现栈抽象数据类型；（3）迷宫模块——实现迷宫抽象数据类型；主程序模块↓迷宫模块↓栈模块三、主要算法流程描述及部分核心算法四、系统使用说明首先进入迷宫系统选择操作，输入行列数，迷宫形成，再输入起点坐标，终点坐标，系统将寻找路径。

标记所走的路径，结束程序；当迷宫无路径时，提示输入有误，程序结束。

五、问题及解决办法调试过程中遇到的主要问题有哪些？如何解决的。

有何结论？六、课外实践总结1. 本次实验核心算法明晰，思路明确，易于实现。

遇到的问题是，迷宫的外围若未设置障碍，用此程序采用的求解迷宫路径的算法无法获得正确结果。

2. 本程序的算法代码不够简洁，但不影响算法实现。

3. 本次实验由于时间问题和知识水平有限，还存在一些问题，比如：界面比较单调，整个程序的功能还不完善，还有界面做的有些简单，菜单没有做好，可进行的操作太少，这些都有待进一步改善。

4.本次实验使我对迷宫游戏的原理有了一定的了解，但做出的结果离真正的迷宫还有很大差距，还需要进一步完善，需要自己课下学习更多的知识。

浙江工商大学计算机与信息工程学院数据结构实验大作业报告专业：班级：学号：姓名：指导教师：年月一、大作业报告内容包括以下几个部分⒈问题描述：(题目)⒉设计：⑴数据结构设计和核心算法设计描述；⑵主控及功能模块层次结构；⑶主要功能模块的输入、处理(算法框架描述)和输出；⑷功能模块之间的调用与被调用关系等。

⒊测试：测试范例，测试结果，测试结果的分析与讨论，测试过程中遇到的主要问题及所采用的解决措施。

⒋使用说明和作业小结：⑴使用说明主要描述如何使用你的程序以及使用时的主要事项；⑵在小结中说明程序的改进思想、经验和体会；⒌整理一份程序清单及运行示例的结果。

将以上各项文字材料及程序清单等装订成册，形成一个完整的报告。

题目从以下题目中任选一个，每人1个题目。

（一）试设计一个航空客运定票系统。

基本要求如下：1、每条航线所涉及的信息有：终点站名、航班号、飞机号、飞机周日（星期几）、乘员定额、余票量、订定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需数量）。

2、系统能实现的操作和功能如下：1）查询航线：根据客户提出的终点站名输出如下信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；2）承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票少余订票额，则需重新询问客户要求。

若需要，可登记排队候补；3）承办退票业务：根据客户提出的情况（日期、航班号），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队候补的客户。

3、实现提示：两个客户名单可分别由线性表和队列实现。

为查找方便，已订票客户的线性表应按客户姓名有序，并且，为了插入和删除方便，应以链表作为存储结构。

由于预约人数无法预计，队列也应以链表作为存储结构。

1—7章作业参考答案第1章数据库技术基础参考答案二、选择题参考答案CDDCA、DACBD三、填空题1．数据库的三级模式体系结构是指__外模式___、___模式____和___内模式_。

2．数据库经历了_人工管理阶段__、__文件管理阶段_和_数据库管理阶段_三个阶段。

3．层次模型的上层和下层实体之间表现为___ _____联系。

4．当用E-R图表示数据库概念模型时,此E-R图能常按_局部E-R图__和_总体E—R图_两个步骤进行设计。

5．两个实体型联系分为_一对一_、_一对多_、_多对多_ 。

6．模式/内模式映象为数据库提供了_物理数据独立性_数据独立性。

7．在层次、网状模型中，数据之间联系用_ _实现。

8．结构数据模型是由数据结构、数据操纵和完整性约束三部分组成的。

9．按照数据结构的类型来命名，数据模型分为层次、网状和关系。

10．提供数据库定义、数据装入、数据操纵、数据控制和DB维护功能的软件称为_DBMS___。

第2章关系数据库一、单项选择题BBABB、ACDBD二、填空题1．“关系”这个术语来自数学中的_集合_概念，因此，关系中任意两个元组不能__重复__。

2．关系代数运算都是_关系_级的运算，即它们的每个运算分量是一个_关系_，运算的结果也是_关系_。

3．关系数据库中，实现表与表之间的联系是通过__外码__。

4．两个没有公共属性的关系作自然连接时等价于它们作_笛卡尔积_。

5．关系数据库中，实现主码标识元组的作用是通过_实体完整性实现的_。

6．在关系数据库中，实现“表中任意两行不能相同”的约束是_UNIQUE_。

7．传统的集合“并、交、差”运算施加于两个关系时，这两个关系的_目数_必须相等，_对应列_必须取自同一个域。

8．在关系代数中，对一个关系做投影操作后，新关系的元组个数_等于或小于_原来关系的元组个数。

9．设关系 R 和关系 S 的元数分别是 3 和 4 ，关系 T 是 R 与 S 的笛卡尔积，即：T=R×S 则关系 T 的元数是 12 。

2023年安徽工程大学计算机科学与技术专业《数据库原理》科目期末试卷B（有答案）一、填空题1、在SQL Server 2000中，数据页的大小是8KB。

某数据库表有1000行数据，每行需要5000字节空间，则此数据库表需要占用的数据页数为_____页。

2、在SQL Server 2000中，新建了一个SQL Server身份验证模式的登录账户LOG，现希望LOG在数据库服务器上具有全部的操作权限，下述语句是为LOG授权的语句，请补全该语句。

EXEC sp_addsrvrolemember‘LOG’，_____；3、数据库管理系统的主要功能有______________、______________、数据库的运行管理以及数据库的建立和维护等4个方面。

4、关系规范化的目的是______。

5、SQL Server中数据完整性包括______、______和______。

6、如果多个事务依次执行，则称事务是执行______；如果利用分时的方法，同时处理多个事务，则称事务是执行______。

7、数据仓库是______、______、______、______的数据集合，支持管理的决策过程。

8、关系代数运算中，基本的运算是______________、______________、______________、______________和______________。

9、采用关系模型的逻辑结构设计的任务是将E-R图转换成一组______，并进行______处理。

10、设有关系模式R（A，B，C）和S（E，A，F），若R.A是R的主码，S.A是S的外码，则S.A的值或者等于R中某个元组的主码值，或者______取空值，这是规则，它是通过______和______约束来实现的。

二、判断题11、文件系统的缺点是数据不能长期存储。

（）12、SQL语言有嵌入式和交互式两种使用方法。

（）13、视图是观察数据的一种方法，只能基于基本表建立。

2022年安徽工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-13、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、有n（n>0）个分支结点的满二叉树的深度是（）。

A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、在下述结论中，正确的有（）。

数据结构习题及解答第1章 概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;解：该程序段的时间复杂度为O (m*n )。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ① while(s<n) { i++; ② s+=i; ③ }解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。

语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。

假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。

其时间复杂度按线性累加规则为O (x )。

此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。

所以有：1+2+3+…+x ≥n ，可以推出：x=nn 241212811+±-=+±-x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ① while(i<=n) i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2。

log)得：T（n）=O(n2【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){ if(n<=1)return(1);①elsereturn(n*fact(n-1));②}解：设fact（n）的运行时间函数是T(n)。

该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1一、单项选择题1.数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

第一章•一、简答题1 设有数据逻辑结构为：•B=（K，R）；K={K1，K2…Kn};•R={<K1,K3>,<K1,K8>, <K2,K3>, <K2,K4>, <K2,K5>, <K3,K9>, <K5,K6>, <K8,K9>, <K9,K7>, <K4,K7>, <K4,K6>}•画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点2 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。

1)A=（K，R），其中K={a,b,c,d,e,f,g,h};R={r}，r={<a,b>,<b,c>, <c,d>, <d,e>, <e,f>, <f,g>, <g,h>}2)B=(K,R),其中K={a,b,c,d,e,f,g,h};R={r}，r={<d,b>,<d,g>, <d,a>, <b,c>, <g,e>, <g,h>, <e,f>}•二、求下列程序段的时间复杂度(1) for (I=0;I<n;I++) (4) fact(int n)for (j=0;j<m;j++) {if (n<=1)A[I][j]=0; return 1;(2) I=s=0; elseWhile (s<n) return(n*fact(n-1));{ I++; }s+=I; (5) s=0;} for(I=0;I<=n;I++)(3) I=1; for(j=0;j<=n;j++)While (I<=n) for(k=0;k<I+j;k++)I=I*3; s++;•第二章•一.选择、填空：• 1 不带头结点的单链表head为空的判定条件是_ ；带头结点的单链表head为空的判定条件是_• A. head==null B. head->next=null• C. Head->next=head D. Head!=null• 2 在循环双链表P所指接点之前插入S所指结点的操作是__• A. P->prior=S;S->next=P;p->next= S;S ->prior=P->prior• B. P->prior=S;P->prior->next=S;S->next= P;S ->prior=P->prior• C. S->next=P; S->prior=P->prior; P->prior=S;P->right->next=S• D. S->next=P; S->prior=P->prior; P->prior->next=S;P->prior=S• 3. 双向链表删除P结点，执行的主要语句是_______• 4. 在单链表中，在指针P所指结点后面插入一个结点S的语句是_________• 5. 在单链表中删除P指针所指结点的的后一个结点的语句是_________• 6. 向长度为n的向量第i个元素C（0≤i≤n-1 ）之前插入一个元素时，需后移____个元素；删除长度为n的向量第i个元素C（0≤i≤n-1 ）之前插入一个元素时，需前移____个元素•第三章作业一选择、填空题1 判定一个栈（最多n个元素）为空的条件是__;判定为满的条件是__A. S->top!=0B. S->top= =0C. S->top!=nD. S->top= =n2 一个栈序列：a,b,c,d,e,则栈不可能输出序列__A. abcdeB. decbaC. dceabD. Edcba3 判定一个队列Q（最多n个元素）为空的条件___是为满的条件是___A. Q->near-Q->front==nB. Q->near-Q->front+1==nC. Q->front=Q->rearD. Q->front=Q->rear+14 判定循环队列Q（最多n个元素）为空的条件是___;为满的条件是__A. Q->rear==Q->frontB. Q->rear==Q->front+1C. Q->front==(Q->rear+1)%nD. Q->front==(Q->rear-1)%n二综合题1 设有4个元素ABCD进栈，写出它们所有可能的出栈次序共几种2 设计一个算法，利用栈的基本运算将指定栈中的内容进行逆转•第四章作业•一填空、选择题• 1. ___是C语言中“abcd321ABCD”的子串。