_数据结构_期中测验试卷

《_数据结构_期中测验试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级学号姓名“数据结构”期中测验试卷一．（58分）填空（本题末尾附有部分参考答案）：1．一个完整的算法应该具有输入、输出、，和　等五个特性。衡量一个算法的性能主要有时间复杂度和空间复杂度。时间复杂度表示__________________________________________________________;空间复杂度表示____________________________________________________________。2．数据的主要存储结构包括___和___。3.ADT代表

2、,其定义是____________________________________________________________。ADT在C++中可以用___________来实现。4．栈(stacks)的逻辑结构是；栈的存储结构可以是和。当栈的规模可以预先确定时，使用____________较适宜，当栈的规模不可预先确定时，使用__________较适宜。　栈的主要操作有入栈(push)和出栈(pop)，入栈的一端叫，出栈的一端叫。入栈可能失败的原因是，出栈可能失败的原因是。栈的特点是_________

3、。5．队列(queues)的逻辑结构是；队列的存储结构可以是____和；入队(enqueue)操作的一端叫，出对（dequeue）操作的一端叫。队列的特点是____。6．线性表（Lists）可用来描述性同类型的数据元素构成的线性序列，故其逻辑结构是，它的存储结构可以是、和。当表的长度是已知的，且插入和删除不是很平凡时，采用实现较合适。当表的长度不确定时，宜采用。7．线性表(Lists)的插入和删除函数可分别用以下函数表示：Error_codeList::insert(intposition,constLis

4、t_entry&x);/*Post:IftheListisnot___and____position_____,wherenisthenumberofentriesintheList,thefunctionsucceeds:Anyentryformerlyatpositionandalllaterentrieshavetheirpositionnumbersincreasedby1,andxisinsertedatpositionintheList.Else:thefunctionfailswitha6班级

5、学号姓名diagnosticerrorcode.*/Error_codeList::remove(intposition,List_entry&x)/*Post:If____position______,wherenisthenumberofentriesintheList,thefunctionsucceeds:TheentryatpositionisremovedfromtheList,andalllaterentrieshavetheirpositionnumbersdecreasedby1.Thep

6、arameterxrecordsacopyoftheentryformerlyat_________.*/8．面是C++表示线性表(Lists)中的一种方法：Error_condeList::retrieve(intposition,List_entry&x)const;其中的const表示____________________________。9．长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素需要_______次移动元素的操作，在所有可能的位置插入的平均移动次数为__________

7、_,用大O表示法为_________.。10．一个算法的时间复杂度表示为问题规模n的函数为T(n)=3n2+5nlgn–10000n。用大O表示法为_______，因为_____________________;用大Q表示法为_________,因为_______________________;用大W表示法为____________,因为________________。11.递归算法的复杂度可以通过其递归树来分析，其时间复杂度与_______________成正比，空间复杂度与____________

8、_____成正比。12.基于比较的查找算法的工作量可以用比较次数来衡量。分析比较次数的工具是算法的比较树(comparisontrees)。假设比较树的每个分支结点表示一次比较，所有的不成功查找在叶结点结束，则树的高度h表示_______________________________________,树的外部路径长度(Externalpathlength)E表示_________________________