2001a数据结构
南师大计算机系《数据结构》试题2001.6.30
班级姓名学号
一、填空题（每小题2分，共20分）
1．当时，快速排序算法的时间复杂性为0（n2），此时算法的空间复杂性为。
2．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为。
3．假设以一维数组S[n(n+1)/2]作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A[3][5]的值存储在S[ ]中。
4．树的先根遍历序列与其对应二叉树的遍历序列相同。5．设用邻接矩阵A存储一个含有N个顶点的有向图，
则顶点i的入度ID（i）= ，出度OD（i）= 。
6．图中的关键路径是指。
7．设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而S5≠P4时，S5应与比较。
8．设有一个长度为n的Hash表，用线性探测法解决冲突，向Hash表中插入一个关键字，在插入成功的情况下，至多探测次。
9．设用权6，10，13，14，20，37构造Huffman树，则该Huffman树的根结点的权值为。
10．假定参数n是2的正整数幂，即n=2，4，8……则下列函数的返回值为，该函数的时间复杂性为。
int mystery(int n)
{ int x, count=0; x=2;
while (x { x=2*x; count++; } return (count); } 二、根据要求解答下列问题。（每小题4分，共20分） 2．画出广义表D=(()，(e)，(a，(b，c，d)))的存储结构。 3．画出下列二叉树对应的中序线索二叉树存储结构。 4．判断循环队列是否“满”，有哪两种方法？请说明。 5．向下列平衡二叉排序树中插入字母Y后，得到的结果是什么？请写出具体步骤。 三、已知一棵5阶B树如下： 试分别画出依次删除41，152之后的B树。（10分） 四、设L为有序顺序表，试编写一个算法删除L中的重复元素。 要求不要另开辟数据存储空间。（10分） 例如：L=（1，1，2，4，4，9，9，9），执行算法后L=（1，2，4，9） 试编写一算法求树T中各结点的度数。（12分） 六、试编写图的广度优先搜索算法，并写出该算法中图的存储结构类型定义。（算法12分，类型定义4分，共16分） 七、设数组a存储了N个整数，试完善下列对数组a进行堆排序的算法。（12分） void HeapAdjust(int a[ ], int h, int s) { temp=a[h]; for (j= ; j<=s; j*=2) { if ((j if (temp<=a[j]) break; ; h=j; } ; } void HeapSort(int a[ ], int n) // 对a[1]，a[2]，…，a[n]进行堆排序// { for (i= ; i>0; --i) HeapAdjust (a，i，n)； for (i= ; i>1; --i) { t=a[1]; a[1]=a[i]; a[i]=t; ; } } 数据结构和软件工程简介 数据结构的基本概念 ?数据是描述客观事物并能为计算机加工处理的符号的集合。数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。数据项是有独立含义的数据最小单位，有时也把数据项称为域、字段等。 ?数据结构（Data Structure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容。 1、数据的逻辑结构 ?数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。 因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ?数据的逻辑结构有两大类： ?线性结构——线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。 ?非线性结构——非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等 2、数据的物理结构 ?数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。 ?数据的存储结构可用以下四种基本存储方法体现： ?顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构。 ?链式存储方法——不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。由此得到的存储结构称为链式存储结构。 ?索引存储方法——在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。索引项由关键字和地址组成，关键字是能惟一标识一个结点的那些数据项，而地址一般是指示结点所在存储位置的记录号。 ?散列存储方法——根据结点的关键字直接计算出该结点的存储地址。 ?用不同的存储方法对同一种逻辑结构进行存储映像，可以得到不同的存储结构。四种基本的存储方法也可以组合起来对数据逻辑结构进行存储映像。 3、数据的运算 ?数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等 线性表： 1．顺序表 ?当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。在高级语言中，可以直接用数组实现。 2. 单链表 ?采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。 ?在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。 3. 栈与队列 栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 第1章绪论习题参考答案 1、试述数据、数据库、数据库管理系统、数据库系统的概念。（参见P3、4、5页） 参考答案： 描述事物的符号记录称为数据；数据库是长期储存在计算机内的、有组织的、可共享的数据集合；数据库管理系统是位于用户与操作系统之间的一层数据管理软件; 数据库系统是指在计算机系统中引入数据库后的系统，一般由数据库、数据库管理系统(及其开发工具)、应用系统、数据库管理员和用户构成。 2．使用数据库系统有什么好处?（参见P12页） 参考答案： 数据库系统使信息系统从以加工数据的程序为中心转向围绕共享的数据库为中心的阶段，这样既便于数据的集中管理，又有利于应用程序的研制和维护，提高了数据的利用率和相容性，提高了决策的可靠性。 3．试述文件系统与数据库系统的区别和联系。（8、9、10页） 参考答案： 1）数据结构化是数据库与文件系统的根本区别。 在文件系统中，相互独立的文件的记录内部是有结构的，管其记录内部已有了某些结构，但记录之间没有联系。数据库系统实现整体数据的结构化，是数据库的主要特征之一。 2）在文件系统中，数据的最小存取单位是记录，粒度不能细到数据项。而在数据库系统中，存取数据的方式也很灵活，可以存取数据库中的某一个数据项、一组数据项一个记录或或一组记录。 3）文件系统中的文件是为某一特定应用服务的，文件的逻辑结构对该应用程序来说是优化的，因此要想对现有的数据再增加一些新的应用会很困难，系统不容易扩充。而在数据库系统中数据不再针对某一应用，而是面向全组织，具有整体的结构化。5．试述数据库系统的特点。（9、10、11页） 参考答案： 数据结构化；数据的共享性高、冗余度低、易扩充；数据独立性高；数据由DBMS统一管理和控制。 6．数据库管理系统的主要功能有哪些? （4页） 《数据结构课程设计》指导书 软件学院软件工程（娱乐软件） 2015年06月 《数据结构课程设计》指导书 一、课程设计题目与要求 根据课程设计题目规模，要求每个题目可分组完成(不超过3个人)。一经确定不得随意调换，题目由各组选派代表抽签确定，设计题目不得更换。 1. 运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分， 3) 可以按学校编号或名称、学校总分、男女团体总分排序输出； 4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5) 数据存入文件并能随时查询 6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。请在最后的上交资料中指明用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 2. 飞机订票系统 任务：通过此系统可以实现如下功能： 录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息：当航班信息改变可以修改航班数据文件 要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 3．宿舍管理查询系统 1) 任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求： A. 采用交互工作方式 B. 建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选两种方法实现) 2) 查询菜单: (用二分查找实现以下操作) A. 按姓名查询 B. 按学号查询 C. 按房号查询 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 K 1373—2 20139730236 余玲 数据结构与程序构建第十三十四章笔记在阅读完数据结构与程序构建的第十三章后，了解了许多查找程序设计。同时也了解到查找技术在编程中作用很大，是重要的操作基础之一。 顺序查找就是线性表遍历查找法。从表的一端开始，向另一端逐个按给定值与关键码进行比较，若找到。查找成功。，并给出数据元素在表中的位置；若整个表检测完，未找到相同的关键码，则查找失败。给出失败信息。 从数据结构的逻辑关系层面考虑，顺序查找的方向是可以从左到右，也可以是从右到左。但是如果进一步考虑存储结构，该结论就不一定正确，比如单链表只能从左到右，如果决定使用链表，又要考虑从右到左的查找，显然必须启用双向链表，为了操作方便性而付出空间代价。 主要源码（顺序查找） Int seqsearching::ltorsearching(int*data,int length,int seekdata) { Int i=1; While(i<=length && data[i]!=seekdata) I++; If(i<=length) Return i; Else Return 0; } Int seqsearching::rtorsearching(int*data,int length,int seekdata) { Int i=length; While(i>0 && data[i]!=seekdata) I--; If(i>=1) Return i; Else Return 0; } Int seqsearching::gtorsearching(int*data,int length,int seekdata) { Data[0]=seekdata; Int i=length; While(data[i]!=seekdata) I--; Return i; } Int seqsearching::displaydata(int*data,int length) { Int i; Count<<“坐标” For(i=1;i<=length;i++) Count< 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 数据库表结构设计参考 表名外部单位表（DeptOut） 列名数据类型（精度范围）空/非空约束条件 外部单位ID 变长字符串(50) N 主键 类型变长字符串(50) N 单位名称变长字符串(255) N 单位简称变长字符串(50) 单位全称变长字符串(255) 交换类型变长字符串(50) N 交换、市机、直送、邮局单位邮编变长字符串(6) 单位标识(英文) 变长字符串(50) 排序号整型(4) 交换号变长字符串(50) 单位领导变长字符串(50) 单位电话变长字符串(50) 所属城市变长字符串(50) 单位地址变长字符串(255) 备注变长字符串(255) 补充说明该表记录数约3000条左右，一般不做修改。初始化记录。 表名外部单位子表（DeptOutSub） 列名数据类型（精度范围）空/非空约束条件 外部子单位ID 变长字符串(50) N 父ID 变长字符串(50) N 外键 单位名称变长字符串(255) N 单位编码变长字符串(50) 补充说明该表记录数一般很少 表名内部单位表（DeptIn） 列名数据类型（精度范围）空/非空约束条件 内部单位ID 变长字符串(50) N 主键 类型变长字符串(50) N 单位名称变长字符串(255) N 单位简称变长字符串(50) 单位全称变长字符串(255) 工作职责 排序号整型(4) 单位领导变长字符串(50) 单位电话（分机）变长字符串(50) 备注变长字符串(255) 补充说明该表记录数较小（100条以内），一般不做修改。维护一次后很少修改 表名内部单位子表（DeptInSub） 列名数据类型（精度范围）空/非空约束条件内部子单位ID 变长字符串(50) N 父ID 变长字符串(50) N 外键 单位名称变长字符串(255) N 单位编码变长字符串(50) 单位类型变长字符串(50) 领导、部门 排序号Int 补充说明该表记录数一般很少 表名省、直辖市表（Province） 列名数据类型（精度范围）空/非空约束条件ID 变长字符串(50) N 名称变长字符串(50) N 外键 投递号变长字符串(255) N 补充说明该表记录数固定 表名急件电话语音记录表（TelCall） 列名数据类型（精度范围）空/非空约束条件ID 变长字符串(50) N 发送部门变长字符串(50) N 接收部门变长字符串(50) N 拨打电话号码变长字符串(50) 拨打内容变长字符串(50) 呼叫次数Int 呼叫时间Datetime 补充说明该表对应功能不完善，最后考虑此表 表名摄像头图像记录表（ScreenShot） 列名数据类型（精度范围）空/非空约束条件ID 变长字符串(50) N 拍照时间Datetime N 取件人所属部门变长字符串(50) N 取件人用户名变长字符串(50) 取件人卡号变长字符串(50) 图片文件BLOB/Image 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 数据库基础 （ 视频讲解：25分钟） 本章主要介绍数据库的相关概念，包括数据库系统的简介、数据库的体系结构、数据模型、常见关系数据库。通过本章的学习，读者应该掌握数据库系统、数据模型、数据库三级模式结构以及数据库规范化等概念，掌握常见的关系数据库。 通过阅读本章，您可以： 了解数据库技术的发展 掌握数据库系统的组成 掌握数据库的体系结构 熟悉数据模型 掌握常见的关系数据库 1 第 章 1.1 数据库系统简介 视频讲解：光盘\TM\lx\1\数据库系统简介.exe 数据库系统（DataBase System，DBS）是由数据库及其管理软件组成的系统，人们常把与数据库有关的硬件和软件系统称为数据库系统。 1.1.1 数据库技术的发展 数据库技术是应数据管理任务的需求而产生的，随着计算机技术的发展，对数据管理技术也不断地提出更高的要求，其先后经历了人工管理、文件系统、数据库系统等3个阶段，这3个阶段的特点分别如下所述。 （1）人工管理阶段 20世纪50年代中期以前，计算机主要用于科学计算。当时硬件和软件设备都很落后，数据基本依赖于人工管理，人工管理数据具有如下特点： ?数据不保存。 ?使用应用程序管理数据。 ?数据不共享。 ?数据不具有独立性。 （2）文件系统阶段 20世纪50年代后期到60年代中期，硬件和软件技术都有了进一步发展，出现了磁盘等存储设备和专门的数据管理软件即文件系统，文件系统具有如下特点： ?数据可以长期保存。 ?由文件系统管理数据。 ?共享性差，数据冗余大。 ?数据独立性差。 （3）数据库系统阶段 20世纪60年代后期以来，计算机应用于管理系统，而且规模越来越大，应用越来越广泛，数据量急剧增长，对共享功能的要求越来越强烈。这样使用文件系统管理数据已经不能满足要求，于是为了解决一系列问题，出现了数据库系统来统一管理数据。数据库系统满足了多用户、多应用共享数据的需求，它比文件系统具有明显的优点，标志着管理技术的飞跃。 1.1.2 数据库系统的组成 数据库系统是采用数据库技术的计算机系统，是由数据库（数据）、数据库管理系统（软件）、数 4.1数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； 华南农业大学期末考试试卷（A卷） 2004学年第1学期考试科目：数据结构（04软件工程） 考试类型：（闭卷）考试时间：120分钟 学号姓名年级专业 说明：1 本试卷的答案必须写在答题卡上，答题卡同时写上专业、班级、学号、姓名； 一、选择题（每题2分，共30分） 1.hh设子串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返 回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则 con( subs (s1,2,len(s2), subs(s1,len(s2),2) )的结果串是（） A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF 2.某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列。 A．a，c，b，d B．b，c，d，a C．c，d，b，a D．d，c，a，b 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为_________. A．0（1）B．0（n） C．0（m）D．0（m+n） 4.长度为n（1…n）的顺序循环队列中，front和rear分别指示队首和队尾。判断队列满的条件 为_________. A．rear%n=front B．front%n+1=rear C．rear%n-1=front D．rear%n+1=front 5.设二叉树有2n个结点，则对于m 数据库结构设计说 1引言 (2) 1.1编写目的 (2) 1.2背景 (2) 1.3定义 (2) 1.4参考资料 (2) 2外部设计 (2) 2.1标识符和状态 (2) 2.2使用它的程序 (3) 2.3约定 (3) 2.4专门指导 (3) 2.5支持软件 (3) 3结构设计 (3) 3.1概念结构设计 (3) 3.2逻辑结构设计 (3) 3.3物理结构设计 (4) 4运用设计 (4) 4.1数据字典设计 (4) 4.2安全保密设计 (4) 数据库设计说明书(GB8567―― 88) 1 引言 1.1 编写目的 说明编写这份数据库设计说明书的目的, 指出预期的读者。 1.2 背景 说明: a．说明待开发的数据库的名称和使用此数据库的软件系统的名称; b．列出该软件系统开发项目的任务提出者、用户以及将安装该软件和这个数据库的计算站（中心）。 1.3 定义 列出本文件中用到的专门术语的定义、外文首字母组词的原词组。 1.4 参考资料 列出有关的参考资料: a．本项目的经核准的计划任务书或合同、上级机关批文; b．属于本项目的其它已发表的文件; C.本文件中各处引用到的文件资料，包括所要用到的软件开发 标准。 列出这些文件的标题、文件编号、发表日期和出版单位, 说明能够 取得这些文件的来源。 2 外部设计 2.1 标识符和状态 联系用途, 详细说明用于唯一地标识该数据库的代码、名称或标识符, 附加的描述性信息亦要给出。如果该数据库属于尚在实验中、尚在测试中或是暂时使用的, 则要说明这一特点及其有效时间范围。 2.2 使用它的程序 列出将要使用或访问此数据库的所有应用程序, 对于这些应用程序的每一个, 给出它的名称和版本号。 2.3 约定 陈述一个程序员或一个系统分析员为了能使用此数据库而需要了解的建立标号、标识的约定, 例如用于标识数据库的不同版本的约定和用于标识库内各个文卷、、记录、数据项的命名约定等。 2.4 专门指导 向准备从事此数据库的生成、从事此数据库的测试、维护人员提供专门的指导, 例如将被送入数据库的数据的格式和标准、送入数据库的操作规程和步骤, 用于产生、修改、更新或使用这些数据 文卷的操作指导。如果这些指导的内容篇幅很长, 列出可参阅的文件资料的名称和章条。 第2章标准版数据库结构说明 2.1表名: DSAcctForecast 描述: 科目预算2.1.1结构: 字段名类型大小描述 FSchemeID 长整型 4 预算方案 FAcctID 文本15 科目代码 FY ear 整型 2 年度 FPeriod 整型 2 期间 FActual 货币8 实际数 FForecast 货币8 预测数 FBudget 货币8 预算数 2.1.2索引: 索引名字段 PrimaryKey FSchemeID FAcctID FY ear FPeriod 2.2表名: DSAcctModel 描述: 科目预算模型2.2.1结构: 字段名类型大小描述 FSchemeID 长整型 2 预算方案 FAcctID 文本15 科目代码 FModel 整型 2 预测方法 FMovingTimes 整型 2 移动次数 FSmoothCoeff 双精度8 平滑系数,以1%为单位FWeightID 长整型 4 权FCalculated 是/否 1 是否已预算 2.2.2索引: 索引名字段 PrimaryKey FSchemeID FAcctID 2.3表名: DSProdForecast 描述: 产品销售预算 2.3.1结构: 字段名类型大小描述 FSchemeID 长整型 4 预算方案 FProdID 文本15 产品代码 FY ear 整型 2 年度 FPeriod 整型 2 期间 FActualQty 双精度8 实际销量 FActualSale 货币8 实际销售额 FActualCost 货币8 实际成本 FForecastQty 双精度8 预测数量FForecastSale 货币8 预测销售额FForecastCost 货币8 预测成本 FBudgetQty 双精度8 预算数量 FBudgetSale 货币8 预算销售额 FBudgetCost 货币8 预算成本 2.3.2索引: 索引名字段 PrimaryKey FSchemeID FProdID FY ear FPeriod 2.4表名: DSProdModel 描述: 产品销售预算模型2.4.1结构: 字段名类型大小描述 FSchemeID 长整型 4 预算方案 FProdID 文本16 产品代码 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 试述数据模型的概念，数据模型的作用和数据模型的三个要素: 答案： 模型是对现实世界的抽象。在数据库技术中，表示实体类型及实体类型间联系的模型称为“数据模型”。 数据模型是数据库管理的教学形式框架，是用来描述一组数据的概念和定义，包括三个方面： 1、概念数据模型（Conceptual Data Model）：这是面向数据库用户的实现世界的数据模型，主要用来描述世界的概念化结构，它使数据库的设计人员在设计的初始阶段，摆脱计算机系统及DBMS的具体技术问题，集中精力分析数据以及数据之间的联系等，与具体的DBMS 无关。概念数据模型必须换成逻辑数据模型，才能在DBMS中实现。 2、逻辑数据模型（Logixal Data Model）:这是用户从数据库所看到的数据模型，是具体的DBMS所支持的数据模型，如网状数据模型、层次数据模型等等。此模型既要面向拥护，又要面向系统。 3、物理数据模型（Physical Data Model）:这是描述数据在储存介质上的组织结构的数据模型，它不但与具体的DBMS有关，而且还与操作系统和硬件有关。每一种逻辑数据模型在实现时都有起对应的物理数据模型。DBMS为了保证其独立性与可移植性，大部分物理数据模型的实现工作又系统自动完成，而设计者只设计索引、聚集等特殊结构。 数据模型的三要素： 一般而言，数据模型是严格定义的一组概念的集合，这些概念精确地描述了系统的静态特征（数据结构）、动态特征（数据操作）和完整性约束条件，这就是数据模型的三要素。 1。数据结构 数据结构是所研究的对象类型的集合。这些对象是数据库的组成成分，数据结构指对象和对象间联系的表达和实现，是对系统静态特征的描述，包括两个方面： （1）数据本身：类型、内容、性质。例如关系模型中的域、属性、关系等。 （2）数据之间的联系：数据之间是如何相互关联的，例如关系模型中的主码、外码联系等。 2 。数据操作 对数据库中对象的实例允许执行的操作集合，主要指检索和更新（插入、删除、修改）两类操作。数据模型必须定义这些操作的确切含义、操作符号、操作规则（如优先级）以及实现操作的语言。数据操作是对系统动态特性的描述。 3 。数据完整性约束 数据完整性约束是一组完整性规则的集合，规定数据库状态及状态变化所应满足的条件，以保证数据的正确性、有效性和相容性。 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }数据结构和软件工程简介
数据结构实验报告
数据库概论 习题参考答案
数据结构课程设计(软件工程)
数据结构实验十一：图实验
数据结构与程序
数据结构实验---图的储存与遍历
数据库表结构设计参考
数据结构实验报告图实验
数据结构实验
数据库的体系结构
软件技术基础(包含数据结构、软件工程、数据库基础知识和基本内容)
软件工程数据结构期末试卷
数据库结构设计说明
金蝶标准版数据库结构说明.
数据结构实验报告图实验
试述数据模型的概念
数据结构图实验报告