《数据结构》实验指导
第一章实验0 C/C++程序设计
一、实验基础知识
二、实验案例
1 学生成绩统计系统
[问题描述]
一个班同学的学号为1-n，输入n位同学的学号、姓名、语文、数学、英语等3门课程成绩，统计每位同学的总分后按成绩从高到低的次序输出。
[基本要求]
实现成绩表的录入、总分统计、总分排序和输出。
[测试数据]
对于10个同学的学号、姓名、语文、数学、英语等3门课程成绩设计实例数据
[实现提示]
1）用结构体设计同学记录，学号、各课程成绩和总分数据域用整型，姓名域采用字符数组；学生成绩表用数组模拟，数组大小根据实际学生数动态申请；学生成绩统计系统通过主菜单形式提供成绩表初始化、学生成绩录入、学生总分统计和排名、成绩表输出等功能。[提高部分]
1）实现成绩表的文件录入和文件保存
2）实现成绩键盘录入的有效数据限制
2复数计算器
[问题描述]
设计一个能进行复数运算的演示程序。
[基本要求]
实现复数的基本运算：1）由输入的实部和虚部生成一个复数；2）求两个复数的和；3）求两个复数的差；4）求两个复数的乘积；5）求复数的实部；6）求复数的虚部
[测试数据]
0+0=0
3.1,0;
4.22,8.9;输出7.32+i8.9
9,8;-9,8;输出i16
9,-8;-9,-8;输出-i16
-9,8;-9,-8;输出-18
9,-7;-9,8;输出i
9,-9;-9,8;输出-i
[实现提示]
将复数的实部和虚部组成结构体数据类型，利用实数的操作实现复数的操作。
[提高部分]
1）实现复数的除法运算；2）求共轭复数
3有理数计算器
[问题描述]
设计一个能进行有理数运算的演示程序。
[基本要求]
实现有理数的基本运算：1）由输入的分子和分母生成一个有理数；2）求两个有理数的和；3）求两个有理数的差；4）求两个有理数的乘积；5）求有理数的分子；6）求有理数的分母
[实现提示]
将有理数的分子和分母组成结构体数据类型，利用整数的操作实现有理数的操作。[提高部分]
1）实现有理数的除法运算；
第二章线性表
一、实验基础知识
二、实验案例
4顺序表基本操作演示系统
[问题描述]
设计一个能进行顺序表基本运算的演示程序。
[基本要求]
实现顺序表的基本运算：1）顺序表的初始化；2）置空顺序表；3）求表长；4）在指定位置插入新元素；5）查找指定位置元素；6）查找给定值元素；7）删除指定位置元素；8）删除指定值元素
[测试数据]
[实现提示]
[提高部分]
1）实现顺序表中重复元素的删除；2）实现有序顺序表的指定元素的保序插入；3）实现有序顺序表中重复元素的删除；
5单链表基本操作演示系统
[问题描述]
设计一个能进行单链表基本运算的演示程序。
[基本要求]
实现带头结点单链表的基本运算：1）单链表的初始化；2）置空单链表；3）求表长；4）在指定位置插入新元素；5）查找指定位置元素；6）查找给定值元素；7）删除指定位置元素；8）删除指定值元素
[测试数据]
[实现提示]
[提高部分]
1）实现无序单链表中重复元素的删除；2）有序单链表的指定元素的保序插入；2）实现有序顺序表中重复元素的删除；
6集合运算演示系统
[问题描述]
设计一个能进行集合基本运算的演示程序。
[基本要求]
1）限制集合基本元素为小写字母a-z；2）实现集合建立：a）集合的并；b）集合的交；c）集合的差；
1)Set1=”magzine”,set2=”paper”
set1∪set2=”aeimnprz”,set1∩set2=”ae”,set1-set2=”gimnz”
2)set1=”012per4a6tion89”,set2=”error data”
set1∪set2=”adeinoprt”,set1∩set2=”aeort”,set1-set2=”inp”
[实现提示]
以有序单链表表示集合
[提高部分]
1）集合元素判定和子集判定；2）求集合的补集；
7约瑟夫环问题
[问题描述]
编号为1~n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向从1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。试设计一个程序求出列顺序。[基本要求]
利用无头结点循环链表存储模拟此过程；每个结点中包含序号、密码和指针域。
[测试数据]
当m初始值为20；n=7,7个人的密码依次为：3，1，7，2，4，8，4；正确的输出序列为6，1，4，7，2，3，5；当m初始值为2；n=1;密码为3；正确的输出序列为1。
[实现提示]
1）扫描指针应指向报数结点的前驱结点以方便出列；2）当表中只有一个结点时，无须报数了，直接出列即行。
[提高部分]
1）采用带头结点单链表实现；2）采用顺序表实现；
8一元稀疏多项式计算器
[问题描述]
设计一个一元稀疏多项式计算器。
[基本要求]
实现一元稀疏多项式的基本运算：1）输入并建立一元稀疏多项式；2）输出多项式（以指数降序方式输出非零系数项的系数和指数）；3）实现一元稀疏多项式的相加；
[测试数据]
[实现提示]
用带头结点的单链表存储多项式，每个结点中包含指数、系数和指针；单链表中结点按指数降序排列。
[提高部分]
1）实现一元稀疏多项式的相减；2）实现一元稀疏多项式求导；
9仓储管理系统
[问题描述]
设计一个能对商厦商品进行管理的系统。
实现：1）商品的入库；2）商品的出库；3）商品查询；4）营业前的商品数据恢复；5）营业结束的商品数据保存
[测试数据]
[实现提示]
用有序单链表模拟商品数据表。
[提高部分]
第三章栈和队列
一、实验基础知识
二、实验案例
10顺序栈模拟器
[问题描述]
设计一个实现顺序栈的基本运算的演示程序。
[基本要求]
实现顺序栈的基本运算：1）顺序栈的初始化；2）置空栈；3）元素入栈；4）元素出栈；5）打印栈中元素
[测试数据]
[实现提示]
注意栈的溢出。
[提高部分]
1）实现两栈共享一连续存储空间的基本运算；2）使用链栈实现栈的基本运算
11队列模拟器
[问题描述]
设计一个实现循环队列的基本运算的演示程序。
[基本要求]
实现循环队列的基本运算：1）循环队列的初始化；2）置空队列；3）元素入队；4）元素出队；5）打印队列中元素
[测试数据]
[实现提示]
1）通过设置队尾指针指向队尾元素，队首指针指向队首前一位置以及模运算方法实现循环队列；2）注意循环队列的溢出。
[提高部分]
1）用队尾指针指向真正队尾、队首指针指向真正队首和附加队列曼/空标记实现循环队列和循环队列的基本操作；2）用队尾指针加表长方式实现循环队列和循环队列的基本操作；3）用循环链表实现队列和队列的基本操作
12表达式括号匹配判断器
[问题描述]
设计一个判断一个表达式中的括号匹配是否配对的演示程序。
实现判断一个表达式中圆括号是否配对
[测试数据]
1）（A+B）+（B-D）
2）（（A+B）*（C-D）））
3）（（A+B））*（（C-D）
[实现提示]
将算术表达式输入并保存在数组中，通过顺序栈实现括号配对。当读入的字符为左括号时入栈，为右括号时出栈。出栈时，若栈顶元素为对应左括号，则出栈；若栈空则说明括不匹配，算法结束；若表达式结束时，栈为空，则说明表示式括号配对，否则说明表示式括号不配对。
[提高部分]
1）实现含3种括号配对
13舞伴问题
[问题描述]
在周末舞会上，男士们和女士们进入舞厅时，各排成一队。跳舞开始时，依次从男队和女队的对头上各出一人配成舞伴。若两队初始人数不同，则较长的那队中未配对者等待下一轮舞曲。写一程序模拟舞伴配对问题。
[基本要求]
输入跳舞者人数、姓名、性别后，建立男士和女士队列；输出配对成功的男士和女士姓名，以及未配对队伍中剩余元素的个数和队头元素的姓名。
[测试数据]
（A，M），（B，F），（C，F），（D，M），（E，M），（F，M），（G，F）
[实现提示]
使用两个循环队列分别模拟男士队列和女士队列（队列的大小根据人数确定）。根据输入的姓名和性别分别入到男队或女队；舞曲开始后，将男士和女士从队列出队，直到一队为空。
[提高部分]
1）实现多轮舞曲的配对
14数制转换
[问题描述]
实现一个将十进制整数转化为n（n<10）进制的数的程序。
[基本要求]
将输入的十进制整数用“除n取余法”求出其n进制表示。
[测试数据]
[实现提示]
将非零正整数除n后的余数保存在栈中，当商为0时，才将栈中数出栈，出栈序列即为转换成功的序列。
[提高部分]
1）实现将十进制整数转化为n（n>10）进制的数的程序
15八皇后问题
[问题描述]
在一个8*8的棋盘里放置8个皇后，要求每个皇后两两之间互不相冲（每一行、列和斜线上都只能有一个皇后）。
[基本要求]
求出无冲突八皇后问题的一组解。
[测试数据]
[实现提示]
利用递归和回溯的方法，在8*8的棋盘从一行一列开始逐行尝试放置皇后，若冲突，则回到上一行下一列尝试，若无冲突，则继续下一行放置，直到放上所有8个皇后。
[提高部分]
1）求出所有可行的八皇后方案。
16背包问题
[问题描述]
设一个背包能放入的物品的重量为s，现有n件物品，重量分别是w[1],w[2]，…，w[n]。判断能否从着n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s；若可以，求出其具体方案。
[基本要求]
求出满足背包问题的一组解。
[测试数据]
s=10,w={1,8,4,3,5,2}
结果：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2）
[实现提示]
利用递归回溯的方法，设置栈模拟背包，将物品放入背包模拟为入栈，若能放入且剩余空间为0，则栈中序列即为一组合法解；若物品放入背包后，剩余空间为>0，则继续选择物品放入；若剩余空间为<0,则取出栈部分物品，继续其他物品的尝试。
[提高部分]
1）设置用户栈求解背包问题；2）求出背包问题的所有解。
17迷宫问题
[问题描述]
迷宫是一个矩形区域，它有一个入口和一个出口。在迷宫内包含不能穿越的墙或障碍。障碍沿着行和列放置，它们与迷宫的矩形边界平行。
[基本要求]
用二维数组模拟迷宫，其中为0处表示通路，为1处表示墙或障碍。求出从入口（0，0）到出口（m,n）的一条通路（通路路径由一组位置构成）。
[测试数据]
[实现提示]
1）把一个m*n的迷宫设置为一个（m+2）*(n+2)的二维数组表示；2）。
[提高部分]
1）求出从入口（0，0）到出口（m,n）的所有通路。
18马踏棋盘演示
[问题描述]
设计一个国际象棋的马踏棋盘的演示程序。
[基本要求]
将马放在国际象棋的8*8棋盘board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵并输出方阵。
[测试数据]
[实现提示]
1）下图显示了马位于方格（2，3）时的8个可移动位置。一般来说，当马位于（i,j）时，能走到下列8个位置之一：
（i-2,j+1），(i-1,j+2)，(i+1,j+2)，(i+2,j+1)，(i+2,j-1)，(+1,j-2)，(i-1,j-2)，(i-2,j-1)
1
2
3
4
5
6
7
但是，如果（i,j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。0个可能位置用两个一维数组Htry1[0..7]和Htry2[0..7]来表示：
Htry1
Htry2
位于（i,j）的马能走到的新位置是棋盘范围内的（i+Htry1[h],j+Htry2[h]），其中h=0,1, (7)
每次在多个可走位置中选择其中一个进行试探，其余未曾测试过的可走位置必须用适当结构妥善管理，以备试探失败时回溯使用。
[提高部分]
求出从某一起点出发的多条行走线路。
19表达式求值演示
[问题描述]
设计一个实现四则运算表达式转换和求值的演示程序。
[基本要求]
以字符序列的形式输入语法正确、操作数为个位数的四则运算中缀表达式；利用算符优先级关系，实现后缀表达式的转换，；然后对表达式的求值。
[测试数据]
3*（7-2）；8；1+2+3+4；88-1*5；1024/4*8；1024/（4*8）；（20+2）*（6/2）；3-3-3；[实现提示]
1）设置字符串数组存放转换成功的后缀表达式；2）设置运算符栈辅助中缀表达式转化为后缀表达式；3）当读入的表达式字符为操作数时读入的表达式字符为运算符时，直接输出到后缀表达式数组中；若读入的是运算符，则将该运算符与运算符栈栈顶的比较优先级：若与比栈顶运算符优先级高则入栈；若相等，则出栈；若小于，则将栈顶运算符输出到后缀表达式数组中；
[提高部分]
1）运算量是变量的四则运算表达式的转换和求值。
20银行业务模拟
[问题描述]
客户业务分为两种。第一种是取款或贷款；第二种是存款或还款。客户到达银行后先排一个队。处理每个业务时，如果属于第一种业务且申请额度超出银行现款而得不到满足，则立即排入第二个队等候，直到取到款后离开银行；否则业务处理完后立即离开银行。每接待完第二种业务的客户，则顺序检查和处理第二个队列中的客户，对能满足的申请者予以满足，不能满足的重新排到第二个队列的队尾。一旦银行资金少于或等于第一个队列中最后一个客户（第二种业务）被接待前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查转而接待第一个队列的客户。任何时刻只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立刻离开银行。
写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间
[基本要求]
[测试数据]
一天营业开始时银行拥有10000元，营业时间为600分钟。其他模拟参数自定，注意极端情况：1）两个到达事件之间的间隔时间很短，而客户交易时间很长；2）设置两个到达事件的间隔时间很长，而客户的交易时间很短。
[实现提示]
两类事件：1）到达银行2）离开银行。初始时银行资金总额为total，开始营业后的第一个事件是客户的到达，营业时间从0到closetime。到达时间发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负数和正数分别表示第一类和第二类业务。变量total、closetime和上述两个随机变量的上下界均交互地从终端读入，作为模拟参数。
21停车场管理
[问题描述]
设停车场是一个可停放N辆车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车辆到达时间的先后依次从北到南排列（大门在最南端，最先到达的车停放在最北端）。若车场停满了N辆车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该车辆开出大门外，其他车辆再按原来次序进入车场，每辆停放在车场内的车在它离开车场时按停留时间的长短交付费用。试为停车场编制按上述要求进行管理的模拟程序。
[基本要求]
以栈模拟停车场，以队列模拟场外的便道，按照从终端读入的输入数据序列进行模拟管理。每组输入数据包括：汽车的到达或离开的信息、汽车牌号和汽车的到达或离开的时刻。每组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的
位置；若是车辆离开，则输出汽车在停车场内停留的时间和交的费用（便道上停留时间不收费）。
[测试数据]
设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’表示到达，D表示离开，E表示结束
[实现提示]
需要另设一个栈，临时停放为要离开汽车让路而从停车场退出的汽车。输入数据按到达或离开的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车牌号和进入停车场的时刻。
22实验室管理
[问题描述]
某高校物理实验室实行全天开放，学生可以根据自己的学习进度自行安排实验时间，但是每个实验有一个限定的时间，例如某实验要在近两周内完成。假设近期将要做的实验可以有周一下午、周三下午、周五下午三个时间（可以根据实际情况进行调整），不妨称为时间一、时间二、时间三，模拟多个实验室的管理和做实验的情况。
[基本要求]
能模拟学生的实验预约、修改预约、做实验、查看预约等过程。
[测试数据]
[实现提示]
这三个时间做实验的学生可以用队列来存储，要求完成如下功能：1）插入：将预约做实验的学生插入到合适的时间队列中；
2）删除：时间队列中前5位学生可以在该时间做实验；
3）查询：教师可以随时查询某个时间队列中学生的预约情况；
4）修改：在没做实验之前，学生可以对预约的时间进行修改；
5）输出：输出每个时间队列中预约的学生名单。
23打印杨辉三角
[问题描述]
（x+y）n二项式展开式的系数表即为杨辉三角，要求打印杨辉三角：
1 1
1 2 1
1 3 3 1
1 4 6 4 1
………………
[基本要求]
计算并输出杨辉三角的前n(n>=7)行的值。
[测试数据]
[实现提示]
用队列存放第i行的的系数，由第i行系数生成下一行系数。
24运动会的日程安排
[问题描述]
某运动会有N个比赛项目，每个运动员可参加1-3个项目。对运动会的比赛项目进行时间安排。
[基本要求]
输入比赛的项目数和项目名称（可用0~n）表示，输入运动员的人数和参加的项目名，构造项目时间冲突数组，将无冲突的项目安排在同一时间进行（以一行的形式输出）并保证总的赛程时间最短。
[测试数据]
项目：A={0，1，2，3，4，5，6，7，8}
7名运动员报名：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）和（6，4）[实现提示]
1）用二维数组a存放项目之间的时间冲突关系，如某运动员报了第1、2、3三个项目，则a[1][2]、a[2][1]、a[1][3]、a[3][1]、a[2][3]和a[3][2]都设置为1表示冲突。
2）将第一个项目放入第一个时间段。其他项目要么与第一个段项目无冲突放入第一个时间段，要么与第一个时间段的其他项目有冲突，放入一个队列中，直到所有项目处理完毕。
3）如果队列中还有项目，则取队首项目为第2时间段的第一项目，然后按照构造第一时间段项目的方法构造第二时间段和其他时间段的项目
25最佳任务分配方案求解
[问题描述]
设有N个人，准备承担M项课题任务，每个人只能承担其中一项（一般N）=M）。假设个人完成课题的经费不同，求最佳方案。
[基本要求]
输入人数和项目数，并输入第i个人承担第j项课题任务的经费消耗COST（i,j）。总体经费消耗由N*M的COST矩阵给定。设计算法解决任务分配，安排每项课题任务只能一人承担，且使完成这M项课题任务的总经费最小。具体任务分配结果由序号形式输出，如最佳方案中第i个人被分配承担第j项任务，则输出（i，j）。
[测试数据]
[实现提示]
1）同背包问题
三、
第四章串
一、实验基础知识
二、实验案例
26串的加密解密
[问题描述]
利用恺撒密码设计进行文本串的加密和解密的演示程序。
[基本要求]
根据设置的字母映射表设置字母映射表：
abcdefghijklmnopqrstuvwxyz
ngzqtcobmuhelkpdawxfyivrsj
1）输入以回车作为结束符的文本串，进行加密并输出；
2）输入以回车作为结束符的文本串，进行解密并输出。
[测试数据]
[实现提示]
1）加密算法字母映射表（串1和串2）的两个串中的字符对应关系来实现，当输入一个字符时，由算法在串1中查找位置，然后用串2中相应位置的字符去替换原来的字符即可。解密算法刚好相反。
[提高部分]
27文本统计器
[问题描述]
编写一个程序，统计文章中指定字符、字符串和单词出现的次数。
[基本要求]
1）输入一以回车结束的字符串；2）求主串中指定单词出现的次数和位置。
[测试数据]
[实现提示]
[提高部分]
28串基本操作演示器
[问题描述]
编写一个程序，演示串的基本运算。
[基本要求]
采用串的定长顺序存储，实现串的基本运算：1）串的赋值；2）求串长；3）串的联接；4）求子串；5）串的比较；6）串的模式匹配
[测试数据]
[实现提示]
[提高部分]
1）采用串的堆存储实现串的基本操作；2）实现串的对称判别
第五章多维数组和广义表
一、实验基础知识
二、实验案例
1．二维数组运算器
2．魔方矩阵
3．稀疏矩阵运算器
4．广义表表头、表尾识别器
第六章树和二叉树
一、实验基础知识
二、实验案例
29二叉树运算演示器
[问题描述]
基于二叉树的二叉链表表示实现二叉树的基本操作。
[基本要求]
基于二叉树二叉链表表示实现：
1）创建二叉树的二叉链表表示
2）打印二叉树的不同遍历序列
3）求二叉树的高度
4）求二叉树的叶子数
[测试数据]
[实现提示]
1）二叉链表的建立可输入二叉树的层次遍历序列，利用队列建立，也可基于二叉树的中序遍历序列和先（或后）序遍历序列建立
[提高部分]
1）交换二叉树的左右子树
2）打印二叉树的树形结构
30树运算演示器
[问题描述]
基于树的不同存储结构表示实现树的基本操作。
[基本要求]
基于树孩子兄弟表示法实现：
1）创建树的孩子兄弟表示
2）打印树中的叶子
3）求树的高度
[测试数据]
[实现提示]
1）通过输入双亲、孩子关系建立树的孩子兄弟表示法
[提高部分]
1）用双亲表示法实现树的基本运算
2）用孩子表示法实现树的基本运算
3）实现输出从根到叶子的路径
31中序线索二叉树运算演示器
[问题描述]
基于中序线索二叉树的二叉链表表示实现基本操作。
[基本要求]
1）对二叉链表表示的二叉树进行中序线索化
2）输出指定结点的中序遍历直接后继
3）输出指定结点的中序遍历直接前驱
[测试数据]
[实现提示]
[提高部分]
1）对二叉树进行先序线索化
2）对二叉树进行后序线索化
32哈夫曼树的构造和应用
[问题描述]
根据给出的字符和字符使用频率（权值）构造哈夫曼树，并获得哈夫曼编码，从而利用哈夫曼编码对文本进行编码和译码，减少文本的编码长度，缩短文本的传输时间。
[基本要求]
1）从终端读入字符集大小n、n个字符和n个权值，建立哈夫曼树
2）打印每个字符的哈夫曼编码
[测试数据]
1）字符（权值）：A（7），B（18），C（3），D（32），E（5），F（26），G（12），H（8）2）字符（权值）：A（7），B（19），C（2），D（6），E（32），F（3），G（21），H（10）[实现提示]
1)由于Huffman树中没有度为1的结点，则一棵有n个叶子结点的Huffman树中共
有2n-1个结点，可设计一个结构数组存储2n-1个结点的值。每个结点中包含权
值、父结点、左孩子和右孩子。
2)Huffman编码可通过走一条从叶子到根结点的路径并记录路径的方法求得（该过
程可通过结点找双亲的方法实现），路径可记录在一个数组中。若走的是左孩子
到双亲的边，则记录0，否则记录1。
[提高部分]
1）实现文本的编码和译码
2）打印哈夫曼树的树形结构
33二叉排序树基本操作演示器
[问题描述]
基于二叉排序树的二叉链表表示实现二叉排序树的基本操作。
[基本要求]
基于二叉排序树二叉链表表示实现：
1）创建二叉排序树的二叉链表表示
2）打印二叉排序树的中序遍历序列
3）二叉排序树的查找
[测试数据]
1）88，43，14，31，78，8，62，49，35，71，22，83，18，52
2）88，43，14，31，52，8，62，49，88
[实现提示]
1）二叉排序树的建立可往空的二叉排序树不断插入结点实现。
2）为了保证二叉排序树的无重复结点的特点，每次插入前都要先进行查找要插入的结点的关键字是否存在，在不存在的前提下才能申请新的结点并放入关键字的值插入到二叉排序树中。
3）每次要插入的结点都作为叶子进行插入。因此，在查找算法中要设置一个全局变量p 指针用来指示q比较结点的双亲（初始时指示根结点的双亲，即为空）；若最后查找失败，则p指针就指向要插入叶子结点的双亲结点，根据值的大小将叶子结点来连接为p 结点的左孩子或右孩子。
[提高部分]
3）二叉排序树的结点删除
4）打印二叉树的树形结构
第七章图
一、实验基础知识
二、实验案例
34图的基本操作演示
[问题描述]
实现图深度优先遍历和广度优先遍历，并得到DFS遍历序列和DFS生成树、BFS遍历序列和BFS生成树。
[基本要求]
基于无向图的邻接矩阵表示实现：
1）创建无向图的邻接表表示
4）进行DFS搜索得到DFS遍历序列
5）进行BFS搜索得到BFS遍历序列
[测试数据]
1）顶点：{V1，V2，V3，V4，V5，V6，V7，V8}
边集：{（V1,V2）,(V1,V3),(V2,V4),(V2,V5),(V3,V6),(V3,V7),(V6,V7),(V4,V8),(V5,V8)} [实现提示]
[提高部分]
5）基于邻接表表示实现DFS遍历和DFS生成树的边集合
6）基于邻接表表示实现BFS遍历和BFS生成树的边集合
35图的拓扑排序
1．教学计划编制问题
36最小生成树问题
2．
第八章查找
一、实验基础知识
二、实验案例
1．学生成绩查询系统
2．图书馆管理系统
37哈希表查找
第九章排序
一、实验基础知识
二、实验案例
38内部排序演示器
[问题描述]
通过计算不同排序算法的关键字比较次数和关键字移动次数，评价内部排序方法的执行效率。
[基本要求]
针对正序、反序和随机序列实现：
1）起泡排序
2）直接插入排序
3）简单排序
4）快速排序
[测试数据]
10000个数据的正序、反序和随机序列
[实现提示]
1)在对应排序算法的关键字比较和移动的地方进行计数
2)随机数的产生方法：
#include
#include
#include
#define max 10
void main(){
int j,temp[max];
srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子
for(j=0;j temp[j]=rand()%max;//产生一个0~max-1的整数 printf("%d ",temp[j]);//打印 } } 39 实现堆排序 实现归并排序 40文件操作基础 学会从文件中读取数据，并将处理结果数据输出到指定文件中。 #include #include void main(){ int x; int i; FILE *fp1,*fp2;//定义两个文件指针，注意文件类型FILE一定要大写 fp1=fopen("input.txt","r");//以只读方式打开当前目录下的文件input.txt fp2=fopen("output.txt","w");//以写方式打开当前目录下的文件output.txt for(i=1;i<=10;i++){ fscanf(fp1,"%d",&x);//从文件指针fp1所指文件input.txt中读入一个整数给变量x; fprintf(fp2,"%d\n",x);//将变量x的值写入文件指针fp2所指文件output.txt中 printf("x%d=%d\n",i,x); } fclose(fp1);//关闭文件 fclose(fp2); //关闭文件 } 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。 2.编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。 3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成 (an,…..a2,a1)。（单链表的数据域数据类型为一结构体，包括学生的部分信息：学号，姓名，年龄） 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 实验指导-数据结构B 附录综合实验 1、实验目的 本课程的目标之一是使得学生学会如何从问题出发，分析数据，构造求解问题的数据结构和算法，培养学生进行较复杂程序设计的能力。本课程实践性较强，为实现课程目标，要求学生完成一定数量的上机实验。从而一方面使得学生加深对课内所学的各种数据的逻辑结构、存储表示和运算的方法等基本内容的理解，学习如何运用所学的数据结构和算法知识解决应用问题的方法；另一方面，在程序设计方法、C语言编程环境以及程序的调试和测试等方面得到必要的训练。 2、实验基本要求： 1）学习使用自顶向下的分析方法，分析问题空间中存在哪些模块，明确这些模块之间的关系。 2）使用结构化的系统设计方法，将系统中存在的各个模块合理组织成层次结构，并明确定义各个结构体。确定模块的主要数据结构和接口。 3）熟练使用C语言环境来实现或重用模块，从而实现系统的层次结构。模块的实现包括结构体的定义和函数的实现。 4）学会利用数据结构所学知识设计结构清晰的算法和程序，并会分析所设计的算法的时间和空间复杂度。 5）所有的算法和实现均使用C语言进行描述，实验结束写出实验报告。 3、实验项目与内容： 1、线性表的基本运算及多项式的算术运算 内容：实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。 要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。 2、二叉树的基本操作及哈夫曼编码译码系统的实现 内容：创建一棵二叉树，实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。哈夫曼编码/译码系统。 要求：能成功演示二叉树的有关运算，实现哈夫曼编码/译码的功能，运算完毕后能成功释放二叉树所有结点占用的系统内存。 3、图的基本运算及智能交通中的最佳路径选择问题 内容：在邻接矩阵和邻接表两种不同存储结构上实现图的基本运算的算法，实现图的深度和宽度优先遍历算法，解决智能交通中的路径选择问题。设有n 个地点，编号为0~n-1，m条路径的起点、终点和代价由用户输入提供，寻找最佳路径方案（例如花费时间最少、路径长度最短、交通费用最小等，任选其一即可）。 要求：设计主函数，测试上述运算。 4、各种内排序算法的实现及性能比较 内容：验证教材的各种内排序算法。分析各种排序算法的时间复杂度。 要求：使用随机数产生器产生较大规模数据集合，运行上述各种排序算法，使用系统时钟测量各算法所需的实际时间，并进行比较。 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 实验报告 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 【题目五】连通OR 不连通 描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入 第一行两个数n,m（5<=n<=40000,1<=m<=100000） 接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found. 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 《数据结构》实验指导 (计算机信息大类适用) 实验报告至少包含以下内容： 实验名称 实验目的与要求: 实验内容与步骤（需要你进行细化）: 实验结果（若顺利完成，可简单说明；若实验过程中遇到问题，也请在此说明） 收获与体会（根据个人的实际情况进行说明，不得空缺） 实验1 大整数加法（8课时） 目的与要求： 1、线性表的链式存储结构及其基本运算、实现方法和技术的训练。 2、单链表的简单应用训练。 3、熟悉标准模版库STL中的链表相关的知识。 内容与步骤: 1、编程实现单链表的基本操作。 2、利用单链表存储大整数（大整数的位数不限）。 3、利用单链表实现两个大整数的相加运算。 4、进行测试，完成HLOJ(https://www.doczj.com/doc/8418375020.html,) 9515 02-线性表大整数A+B。 5、用STL之list完成上面的任务。 6、尝试完成HLOJ 9516 02-线性表大菲波数。 实验2 栈序列匹配（8课时） 目的与要求 1、栈的顺序存储结构及其基本运算、实现方法和技术的训练。 2、栈的简单应用训练。 3、熟悉标准模版库STL中的栈相关的知识。 内容与步骤: 1、编程实现顺序栈及其基本操作。 2、对于给出的入栈序列和出栈序列，判断2个序列是否相容。即：能否利用栈 将入栈序列转换为出栈序列。 3、进行测试，完成HLOJ 9525 03-栈与队列栈序列匹配。 4、用STL之stack完成上面的任务。 5、尝试完成HLOJ 9522 03-栈与队列胡同。 实验3 二叉排序树（8课时） 目的与要求 1、二叉树的链式存储结构及其基本运算、实现方法和技术的训练。 2、二叉树的遍历方法的训练。 3、二叉树的简单应用。 内容与步骤: 1、编程实现采用链式存储结构的二叉排序树。 2、实现插入节点的操作。 3、实现查找节点的操作（若查找失败，则将新节点插入二叉排序树）。 4、利用遍历算法对该二叉排序树中结点的关键字按递增和递减顺序输出，完成 HLOJ 9576 07-查找二叉排序树。 5、尝试利用二叉排序树完成HLOJ 9580 07-查找Let the Balloon Rise。 实验4 最小生成树（8课时） 目的与要求 1、图的邻接矩阵存储结构及其相关运算的训练。 2、掌握最小生成树的概念。 3、利用Prim算法求解最小生成树。 实验背景： 给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。要求显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 内容与步骤: 1、建立采用邻接矩阵的图。 2、编程实现Prim算法，求解最小生成树的代价。 3、尝试利用Prim算法完成：HLOJ 9561 06-图最小生成树。 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include 模拟试卷一 一、单选题（每题 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的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 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 D. 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)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 《数据结构》实验指导书 贵州大学 电子信息学院 通信工程 目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109) 实验一顺序表的操作 实验学时：2学时 实验类型：验证 实验要求：必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作（建立、插入、删除等）的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型，输入一组整型数据，建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数，调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程，上机调试、得出正确的运行程序。 2、编译运行程序，观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。 【附录----源程序】 #include 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/8418375020.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 洛阳理工学院实验报告 附：源程序： #include { InsertBST(&((*bst)->lchild),key); return OK; } else if(key>(*bst)->key) { InsertBST(&((*bst)->rchild),key); return OK; } } void CreateBST(BSTree *bst) { int key; *bst=NULL; scanf("%d", &key); while (key!=ENDKEY) { InsertBST(bst, key); scanf("%d", &key); } } BSTree SearchBST(BSTree bst, int key) { if(!bst) return NULL; else if(bst->key==key) return bst; //查找成功 else if(bst->key>key) return SearchBST(bst->lchild,key); else return SearchBST(bst->rchild,key); 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 《数据结构实验》实验指导书及答案 信电工程学院计算机科学和技术教研室编 2011.12 数据结构实验所有代码整理 作者郑涛 声明：在这里我整理了数据结构实验的所有代码，希望能对大家的数据结构实验的考试有所帮助，大家可以有选择地浏览，特别针对一些重点知识需要加强记忆（ps:重点知识最好让孙天凯给出），希望大家能够在数据结构实验的考试中取得令人满意的成绩，如果有做的 不好的地方请大家谅解并欢迎予以指正。 实验一熟悉编程环境 实验预备知识： 1．熟悉本课程的语言编译环境（TC或VC），能够用C语言编写完整的程序，并能够发现和改正错误。 2．能够灵活的编写C程序，并能够熟练输入C程序。 一、实验目的 1．熟悉C语言编译环境，掌握C程序的编写、编译、运行和调试过程。 2．能够熟练的将C程序存储到指定位置。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。 ⒉软件：Windows操作系统+Turbo C； 三、实验要求 1．将实验中每个功能用一个函数实现。 2．每个输入前要有输入提示（如：请输入2个整数当中用空格分割：），每个输出数据都要求有内容说明（如：280和100的和是：380。）。 3．函数名称和变量名称等用英文或英文简写（每个单词第一个字母大写）形式说明。 四、实验内容 1．在自己的U盘中建立“姓名+学号”文件夹，并在该文件夹中创建“实验1”文件夹（以后每次实验分别创建对应的文件夹），本次实验的所有程序和数据都要求存储到本文件夹中（以后实验都按照本次要求）。 2．编写一个输入某个学生10门课程成绩的函数（10门课程成绩放到结构体数组中，结构体包括：课程编号，课程名称，课程成绩）。 3．编写一个求10门成绩中最高成绩的函数，输出最高成绩和对应的课程名称，如果有多个最高成绩，则每个最高成绩均输出。 4．编写一个求10门成绩平均成绩的函数。 5．编写函数求出比平均成绩高的所有课程及成绩。 #include数据结构实验
数据结构模拟题(开卷)
数据结构课程实验指导书
数据结构实验答案1
数据结构模拟试题及答案
实验指导-数据结构B教案资料
数据结构实验报告
数据结构_实验六_报告
《数据结构C》模拟试题
《数据结构》实验指导
数据结构实验报告
《数据结构》模拟试卷一及答案
2017数据结构实验指导书
数据结构实验
数据结构实验六
数据结构模拟试卷(含答案)
数据结构实验指导书及答案(徐州工程学院)
相关主题
文本预览