北工大(数据结构)11-DSch8sort

理发馆学号_____110703xx___ 姓名_____xxx______ 指导教师______xx______2013年10月目录1 需求分析3 1.1程序功能介绍 3 1.2程序数据要求 3 1.3 开发与运行环境需求 41.4 用户界面设计 52 数据结构设计7 2.1 主要数据结构7 2.2 程序整体结构112.3 模块功能描述113 详细设计124 测试22 4.1 正确运行示例224.2 错误运行示例245 总结提高251需求分析1.1程序功能介绍本程序模拟理发馆一天的经营状况，理发馆的环境如下：1．理发馆有N把理发椅，可同时为N位顾客进行理发(2<N<9)；2．理发师按技术水平分为三个等级（一级最高，三级最低），对应不同的服务收费。

理发馆一天的工作过程如下：1．顾客进门时，需要选择某级别的理发师，只要该级别的理发师有空椅，则可立即坐下理发，否则需排队等候；2．一旦该级别的理发师有顾客理发完离去，排在该位理发师队列队头的顾客便可以开始理发。

理发馆老板统计每天不同级别理发师的营业时间、创收和每天理发馆总创收，并写入文本文件中，可作为理发师工资与奖金的发放依据。

1.2程序数据要求1.2.1输入数据（由文本文件输入）：7 ：3061 12 13 24 35 26 30.6数据说明：第一行的09：30表示理发馆将于九点半开门；第二行的6表示理发馆有6理发椅(此处可输入3~9的任意值)；随后的N行：表示第i椅子的理发师的级别（如：第1理发椅是1级理发师，第2理发椅是1级理发师…）。

最后一行的0.6代表折扣（可选）1.2.2随机数据需求：每个顾客进门时将负责生成三个随机数：1）理发时间durtime：进门顾客理发所需服务时间；2）间隔时间intertime：该顾客与下一位顾客到达的时间间隔；3）服务选项select：该顾客选择理发师的级别。

由随机数函数产生。

1.2.3输出数据（输出到文本文件中）：本日账目清单===============================按理发师===============================理发师编号：1 级别：1 工作时长：17 本日盈收：17理发师编号：2 级别：1 工作时长：29 本日盈收：29理发师编号：3 级别：2 工作时长：28 本日盈收：14理发师编号：4 级别：3 工作时长：73 本日盈收：23理发师编号：5 级别：2 工作时长：24 本日盈收：12理发师编号：6 级别：3 工作时长：27 本日盈收：9理发师编号：7 级别：3 工作时长：20 本日盈收：6理发师编号：8 级别：1 工作时长：30 本日盈收：30================================按级别===============================1级别理发师总工时：76 总收入：762级别理发师总工时：52 总收入：263级别理发师总工时：120 总收入：38=================================总汇=============================== 本日总创收：1401.3开发与运行环境需求1.3.1开发环境：Visual studio 20101.3.2运行环境：Win xp/Win 7/Win 81.4用户界面设计1.4.1初始化界面（例：6个队列）8队列界面1.4.2顾客到达、理发及等待界面1.4.3顾客离开界面1.4.4 DOS/GUI同步演示程序过程1.4.5折扣选择界面2数据结构设计2.1 主要数据结构2.1.1事件类（Event）//事件类：包含事件发生时间，事件类型，和下一个事件（指针）三个数据成员class Event {public:int occurtime;int event_type;Event* next_event;Event() {}Event(int occurtime, int event_type): occurtime(occurtime),event_type(event_type), next_event(NULL) {}~Event() {}};2.1.2事件表（EventList）//事件表类:数据成员：头指针，两个用于插入删除事件结点的指针，和事件表长度class EventList {public:Event *head, *ptr_before, *ptr_after;int length; //事件表长度EventList(){head = new Event(-1, -1);length=1;}~EventList() {}void OrderIn(Event* new_in);int ListEmpty();int Cmp(Event* new_in, Event* t1) ;};2.1.3顾客类（Customer）class Customer {public:int durtime;int select;Customer* next;Customer(): select(-1) {}Customer(int durtime, int select): durtime(durtime), select(select), next(NULL) {}~Customer() {}};2.1.4顾客队列类（CustomerQueue）class CustomerQueue {public:Customer *front, *rear;int select;int length;int worktime;int money;CustomerQueue(): front(NULL), rear(NULL), select(-1), length(0), money(0), worktime(0) {}~CustomerQueue() {}void EnQueue(Customer* add);void DelQueue();};2.1.5随机函数类（Random）：class Random {public:int durtime;int intertime;int select;Random() {srand((int)time(NULL));}~Random() {}int Durtime();int Intertime();int Select();};2.1.6文件操作类（FileOperation）：class FileOperation {public:int input_time[2];//接收输入时间小时、分钟char maohao;//接收中间的冒号int number[11];//用于接收理发师编号信息int chairs;//理发师人数float discount;//折扣（可选）char zhekou;FileOperation(): discount(1.0) {}~FileOperation() {}void FileInput(ifstream &from_file, int &opentime, CustomerQueue cq[], int&closetime);void FileOutput(ofstream &to_file, CustomerQueue cq[], int& total_money); };2.1.7绘图类（barbergraph）：class barbergraph {public:IMAGE background_img;//顾客去背景图片IMAGE baber_desk;//理发师桌子背景IMAGE my_clock;//时钟背景IMAGE door;//门char now_time[10];//时钟信息存储char barber_info[20];//理发师信息char graphic_symbol[15];//图例信息Customer* p;//获取当前动作顾客int chairs;//获取理发师人数barbergraph() {//读取背景图片集loadimage(&background_img, _T("背景1.jpg"));loadimage(&baber_desk, _T("六桌子.jpg"));loadimage(&my_clock, _T("时钟.jpg"));loadimage(&door, _T("门.jpg"));}void set_chairs (int chairs);//初始化理发师人数void CommonGraph(CustomerQueue cq[], int opentime);//通用绘图界面void BarberGraph(CustomerQueue cq[],int opentime);//无事件状态界面void ArriveBarberGraph(CustomerQueue cq[], int arrival, int nowtime);//顾客到来界面void DepartBarberGraph(CustomerQueue cq[], int departure, int nowtime);//顾客离开界面~barbergraph() {}};2.1.8理发馆类（Barbershop）：class BarberShop {public:EventList ev;//事件表CustomerQueue cq[11];//六个顾客队列1~10可选int opentime;//开门时间Event* cur_event;//当前事件Event* new_event;//初始事件Customer* new_customer;//新顾客指针int closetime;//TODO：目前为调试数据（22:00理想，未实现）int total_money;//理发馆一天总收入int chairs;//接收理发师人数BarberShop(): cur_event(NULL), new_customer(NULL), total_money(0) {}void OpenForDay(barbergraph &bg, int chairs);//开门初始化函数int Minimum(int select);//求同级别最短队列函数void CustomerArrived(Random &ran, barbergraph &bg);//顾客到来void CustomerDeparture(barbergraph &bg);//顾客离开void BarberSimulation(Random &ran, barbergraph &bg, int chairs);//事件驱动模型~BarberShop() {}};2.2 程序整体结构2.3 模块功能描述2.3.1 Event ：作为EventList 的结点元素，数据：事件类型、事件发生的时间2.3.2 EventList ：事件表，为有序表。

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

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

A.NB.2N-1C.2ND.N-13、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、设X是树T中的一个非根结点，B是T所对应的二叉树。

在B中，X是其双亲的右孩子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。

2019年北京工业大学896《数据结构》考试大纲一、考试要求数据结构考试大纲适用于北京工业大学信息学部（085211）计算机技术（专业学位）领域的硕士研究生招生考试。

数据结构课程是计算机技术领域（专业学位）的重要基础课。

考试内容主要包括基本数据结构、排序、索引、检索、高级数据结构等内容，从逻辑结构的角度包括线性表、栈、队列、二叉树、树和图等各种基本数据结构；从算法的角度包括各类排序、检索和索引算法。

要求考生对其中的基本概念有很深入的理解，掌握数据结构与算法的基本概念、合理组织数据的基本方法、高效处理数据的基本算法、并具备面对实际问题选择恰当数据结构与相应算法的能力。

二、考试内容1．数据结构的相关概念、算法概念、算法性质及算法分析（时间复杂度与空间复杂度）；2．线性表逻辑结构定义、存储结构的表示，以及在特定存储结构下线性表基本运算的算法实现；3．栈与队列的逻辑结构定义、存储结构的表示，基本操作特点，栈与队列的基本应用；4．串的逻辑结构定义，基本操作的含义与实现；5．数组定义及其顺序存储，矩阵的压缩存储，广义表定义及存储结构；6．树的定义与存储结构，二叉树的定义与性质、存储结构，二叉树遍历算法（三序遍历与按层遍历），赫夫曼树与赫夫曼编码以及二叉树基本算法的实现与应用；7．图的定义与术语，图的存储结构，图的遍历（深度优先搜索与广度优先搜索），最小生成树、拓扑排序以及最短路径的求解；8．查找的相关概念，静态查找表（顺序表的查找与有序表的查找），动态查找表（二叉排序树），B-树，B+树，AVL 树，哈希表的相关概念；9．排序的相关概念，掌握插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的执行过程、时空复杂度、稳定性以及使用场合。

三、参考书目1.严蔚敏吴伟民.《数据结构》(C 语言版)，清华大学出版社，2011。

北京工业大学计算机学院896数据结构[专业硕士]
历年考研真题汇编
最新资料，WORD格式，可编辑修改！
目录
2012年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 2011年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 2010年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 2001年北京工业大学计算机学院896数据结构[专业硕士]考研真题及详解................. 2000年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 1999年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 1998年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 1997年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 1996年北京工业大学计算机学院896数据结构[专业硕士]考研真题....................... 1995年北京工业大学计算机学院896数据结构[专业硕士]考研真题.......................
2012年北京工业大学计算机学院896数据结构[专业硕士]考研真题
2001年北京工业大学计算机学院896数据结构[专业硕士]考研真题及详解
1995年北京工业大学计算机学院896数据结构[专业硕士]考研真题。

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

A.5B.6C.8D.92、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、连续存储设计时，存储单元的地址（）。

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

A.0123B.1123C.1231D.12116、循环队列放在一维数组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）7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。