《数据结构》结业试卷A

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

1、------------------------------------------作者xxxx------------------------------------------日期xxxx《数据结构》结业试卷A【精品文档】题号一二三总分分数阅卷人《数据结构》试卷A一、单项选择题（本大题共10个小题，2分/题，共20分）1．计算机算法必须具备输入、输出、（）等5个特性。A）可行性、可移值性和可扩展性B）可行性、确定性和有穷性C）确定性、有穷性和稳定性D）易读性、安全性和稳定性2．栈的特点是（）A）先进先出B）后进先出C）后进后出D）不进

2、不出3．在数据结构中，与所使用的计算机无关的是数据的（）结构。A）逻辑B）存储C）逻辑和存储D）物理4．单链表的存储密度为（）A）大于1B）等于5C）小于1D）不能确定5．数据结构在计算机中的表示是指（）A）数据的逻辑结构B）数据结构C）数据的存储结构D）数据元素之间的关系6．在一个顺序表的表尾插入一个元素的时间复杂度的量级为（）A）O(n)B）O(1)C）O(n2)D）O(logn)7.下面程序段的时间复杂度的量级为（）For(inti=0;i

3、O(n2)C)O(m*n)D)O(m+n)【精品文档】【精品文档】8．已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）A）acbedB）decabC）deabcD）cedba9．按照二叉树的定义，具有三个结点的二叉树有（）种。A）3B）4C）5D）610．任意一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）不发生改变B）发生改变C）不能确定D）以上都不对二、简答题（本大题共4个小题，5分/个，共20分）1．数据的逻辑结构有哪几种？常用的存储结构有哪些？2．简述栈与队列的相同点与不同点

4、？3．什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？4．什么叫平均查找长度？写出平均查找长度的定义。【精品文档】【精品文档】三、设计题（本大题共6个小题，10分/个，共60分）1．编写一个算法判断S2是否是S1的子串。2．给定二叉树的先序序列和中序序列，能否重构出该二叉树？给定二叉树的先序序列和后序序列呢？若不能，给出反例。3．已知一个个数为12的数据元素序列为{Dec，Feb，Nov，Oct，June，Sept，Aug，Apr，May，July，Jan，Mar}，按各数据元素的顺序构造一棵二叉排序树。【精品文档】【精品文档

5、】4．设有两个栈s1和s2都采用顺序表示，并且共享一个存储区。请分别编写s1和s2进栈操作push和出栈操作pop函数。5．写一个堆删除算法：HeapDelete(R,i)，将R[i]从堆中删去。6．对下面所示的连通有向网，用迪杰斯特拉算法求从顶点A到图中其他顶点的最短路径，并写出执行算法过程中距离向量D的变化情况。AECFGB402320181528481233139BADECGF1512553864BADECGF151255386443339【精品文档】【精品文档】D410【精品文档】