第1次作业（线性结构）1
需积分: 0 75 浏览量
2022-08-08
20:42:00
上传
评论
收藏 610KB DOCX 举报
1 / 3
哈尔滨工业大学（深圳）2021 年春《数据结构》
第一次作业 线性结构
学号
姓名
成绩
1、简答题
1.1 简述线性链表头指针,头结点,首元结点(第一个结点) 三个概念的区别。
1.2 在什么情况下用顺序表比链表好?
1.3 简述队列和栈这两种数据类型的相同点和差异处
1.4 设有如下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向
均为从左至右，列车可驶入任意一条轨道。现有编号为 1～9 的 9 列列车，
驶入的次序依次是 8,4,2,5,3,9,1,6,7。若期望驶出的次序依次为 1 至 9，
则 n 至少是多少？
7 6 1 9 3 5 2 4 8
9 8 7 6 5 4 3 2 1
入口 出口
轨道
1.5 现有队列 Q 与栈 S，初始时队列 Q 中的元素依次是 1,2,3,4,5,6（1 在队头），
栈 S 为空。若仅允许下列 3 种操作：
① 出队并输出出队元素；
② 出队并将出队元素入栈；
③ 出栈并输出出栈元素。
请分析是否能得到 1,2,5,6,4,3 和 3,4,5,6,1,2 两个输出序列,为什么？
1.6 假设按低下标优先存储整数数组 A(-3:8,3:5,-4:0,0:7)时，第一个元素的字
节存储地址是 100，每个整数占 4 个字节。问：A(0,4,-2,5)的存储地址是什
么？请简要说明计算方法。
2、数据结构设计及算法描述
给出一个停车场需求如下：
设停车场是一个可以停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进
出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最
南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆车，那
么后来的车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车
即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为
它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场
评论0