数据结构期中笔试题答案.docx

《数据结构期中笔试题答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》期中考试题答案一、填空题（20分，每题2分）1.逻辑结构、存储结构2.便于插入和删除操作3.方便运算的实现4.算法执行过程中所需要的基本运算次数5.存储结构6.q.next=p.next；p.next=q7．递归算法8.抽象类或接口二、选择题（30分，每题2分）AACBBBDDCBAACAC三、问答题（50分，每题10分）1.什么是栈和队列？两者有何异同？答：栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。2.采用顺序存储结构的栈

2、和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？答：采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。3.什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？答：顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。解决的办法是将顺序

3、队列设计成循环结构。链式存储结构队列不会出现假溢出。因为每次元素入队，都要申请新结点，数据不会溢出。4.答案：(1)(a2,a4,…,)(2)将单链表中偶数结点位置的元素值写入顺序表list5.数据的存储结构有哪两种，各有什么特点？答：数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。顺序存储结构使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序与它们的逻辑次序相同。链式存储结构使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素间的关系需要采用附加信息特别指定。