数据结构上机作业.docx

数据结构上机作业 《数据结构》上机作业 (黑色--必做；蓝色--选作) 线性表 1、 某软件公司大约有 30 名员工，每名员工有姓名、工号、职务等属性，每年都有员工离职和入职。 把所有员工按照顺序存储结构建立一个线性表，建立离职和入职函数，当有员工离职或入职时，修改线性表，并且打印必威体育精装版的员工名单。（动态分配存储，malloc，realoc） 2、 约瑟夫（Josephus）环问题：编号为 1,2,3,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数,报到 m 时停止。报 m 的人出列，将他的密码作为新 m 值，从他在顺时针方向上的下一人开始重新从 1 报数，如此下去，直到所有人全部 出列为止。 建立 n 个人的单循环链表存储结构，运行结束后，输出依次出队的人的序号。（必须用链表） 3、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于 mink 且小于 maxk 的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意： mink 和 maxk 是给定的两个参变量，他们的值可以和表中相同，也可以不同） 4、试写一个算法，对单链表实现就地逆置。 5、设有一个双向循环链表，每个结点中除有 prior, data 和 next 三个域外，还增设了一个访问频度域 freq。在链表被起用之前，频度域 freq 的值均初始化为零，而每当对链表进行一次 locate(L, x)的操作后，被访问的结点（即元素值等于 x 的结点）中的频度域 freq 的值便增 1，同时调整链表中结点之间的次序，使其按访问频度非递减的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 locate 操作的算法。 （注意：如果没有特别说明，链表均带头结点） 栈和队列 6、某商场有一个 100 个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时 1 元收费。汽车的输入信息格式可以是（进入/离开，车牌号，进入/离开时间），要求可以随时显示停车场内的车辆信息以及收费历史记录。（选作，用指针轮询数组，有空位就入，利用时间函数计时） 7、某银行营业厅共有 6 个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、银行卡、理财卡等三种。公积金业务指定 1 号窗口，银行卡业务指定 2、3、4 号窗口，理财卡业务指定 5、6 号窗口。但如果 5、6 号窗口全忙，而 2、3、4 号窗口有空闲时，理财卡业务也可以在空闲的 2、3、4 号窗口之一办理。客户领号、业务完成可以作为输入信息，要求可以随时显示 6 个营业窗口的状态。（复杂，选作） 8、4 阶斐波那契序列如下：f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4， 利用容量为 k=4 的循环队列，构造序列的前 n+1 项（f0, f1 , f2 ,… fn ），要求满足 fn ≤200 fn+1 200。 9、八皇后问题：设 8 皇后问题的解为 (x1, x2, x3, …,x8), 约束条件为：在 8x8 的棋盘上， 第 1 页第 1 页 数据结构上机作业 其中任意两个 xi 和 xj 不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。 10、迷宫求解：用二维矩阵表示迷宫，自动生成或者直接输入迷宫的格局，确定迷宫是否能 走通，如果能走通，输出行走路线。 11、英国人格思里于 1852 年提出四色问题(four colour problem，亦称四色猜想），即在为一平面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。现在给定一张地图，要求对这张地图上的国家用不超过四种的颜色进行染色。 要求建立地图的邻接矩阵存储结构，输入国家的个数和相邻情况，输出每个国家的颜色代码。 数组与广义表 12、鞍点问题： 若矩阵 A 中的某一元素 A[i,j]是第 i 行中的最小值，而又是第 j 列中的最 大值，则称 A[i,j]是矩阵 A 中的一个鞍点。写出一个可以确定鞍点位置的程序。 13、稀疏矩阵转置： 输入稀疏矩阵中每个元素的行号、列号、值，建立稀疏矩阵的三元组 存储结构，并将此矩阵转置，显示转置前后的三元组结构。 树和二叉树 以下问题要求统一在一个大程序里解决。 14、按先序遍历的扩展序列建立二叉树的存储结构 15、二叉树先序、中序、后序遍历的递归算法 16、二叉树中序遍历的非递归算