《数据结构》结业试卷A.doc

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

1、题号一二三总分分数阅卷人《数据结构》试卷A一、单项选择题（本大题共10个小题，2分/题，共20分）1．计算机算法必须具备输入、输出、（）等5个特性。A）可行性、可移值性和可扩展性B）可行性、确定性和有穷性C）确定性、有穷性和稳定性D）易读性、安全性和稳定性2．栈的特点是（）A）先进先出B）后进先出C）后进后出D）不进不出3．在数据结构中，与所使用的计算机无关的是数据的（）结构。A）逻辑B）存储C）逻辑和存储D）物理4．单链表的存储密度为（）A）大于1B）等于5C）小于1D）不能确定5．数据结构在计算机中的表示是指（）A）数据的逻辑结构

2、B）数据结构C）数据的存储结构D）数据元素之间的关系6．在一个顺序表的表尾插入一个元素的时间复杂度的量级为（）A）O(n)B）O(1)C）O(n2)D）O(logn)7.下面程序段的时间复杂度的量级为（）For(inti=0;i

3、个结点的二叉树有（）种。A）3B）4C）5D）610．任意一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）4A）不发生改变B）发生改变C）不能确定D）以上都不对二、简答题（本大题共4个小题，5分/个，共20分）1．数据的逻辑结构有哪几种？常用的存储结构有哪些？2．简述栈与队列的相同点与不同点？3．什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？4．什么叫平均查找长度？写出平均查找长度的定义。三、设计题（本大题共6个小题，10分/个，共60分）1．编写一个算法判断S2是否是S1的子串。42．给定二叉树的先序序列和

4、中序序列，能否重构出该二叉树？给定二叉树的先序序列和后序序列呢？若不能，给出反例。3．已知一个个数为12的数据元素序列为{Dec，Feb，Nov，Oct，June，Sept，Aug，Apr，May，July，Jan，Mar}，按各数据元素的顺序构造一棵二叉排序树。4．设有两个栈s1和s2都采用顺序表示，并且共享一个存储区。请分别编写s1和s2进栈操作push和出栈操作pop函数。45．写一个堆删除算法：HeapDelete(R,i)，将R[i]从堆中删去。6．对下面所示的连通有向网，用迪杰斯特拉算法求从顶点A到图中其他顶点的最短路径，

5、并写出执行算法过程中距离向量D的变化情况。AECFGB402320181528481233139BADECGF1512553864BADECGF151255386443339D4104