自学考试_数据结构历年考题综合(答案).doc

《自学考试_数据结构历年考题综合(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2006.101.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为()A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为()A.n-i+1B.n-iC.iD.i-13.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为()A.4B.5C.

2、6D.75．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（　　　）A．2，14B．2，15C．3，14D．3，156．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（　　　）A．116B．118C．120D．1227．一个带权的无向连通图的最小生成树（　　　）A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在8．下列有关

3、图遍历的说法中不正确的是（　　　）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次9．某算法的空间花费s(n)=2n+n100+nlog2n+n101，则其空间复杂度为（）。A．O(nlog2n)B.O(n100)C.O(n101)D.O(2n)10.单链表中的存储密度一定（）。A．小于0.5B.等于1C.大于0.1D.小于111．在顺序栈中删除一个元素，至少要移动（）元素。A．0B.1C.n/2D.n12．

4、空串是（）。A．只包含空格符的串B.长度为0的串C.只包含一个空格符的串D.不含字母的串13．采用三元组表存储稀疏矩阵，是为了（）。A．节省存取时间B.节省存储空间C.提高对矩阵元素的访问速度D.提高对矩阵运算的可靠性14．高度为h的二叉树最多有（）个节点。A．2h-1B.2hC.2h-1D.2h-1+115．N个顶点，e条边的无权有向图的邻接矩阵中非零元素有（）个。A．nB.n-eC.eD.e+n16．直接选择排序在最好情况下的时间复杂度是（）。A．O(n)B.O(nlog2n)C.O(1)D.O(n2)17．N个结点

5、的m阶B树至少包含（）个关键字。A．(m-1)*nB.nC.(「m/2」-1)*(n-1)+1D.n*「m/2」-1)18．在散列文件中，同一个桶内的所有记录应当具有（）。A．相同的关键字B.相同的散列值C.相同的某个属性值D.相同的存取频率19．在最坏的情况下，查找成功时二叉排序树的平均查找长度（　　　）A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较20．散列表中由于散列到同一个地址而引起的“堆积”现象，是由（　　　）A．同义词之间发生冲突引起的

6、B．非同义词之间发生冲突引起的C．同义词之间或非同义词之间发生冲突引起的D．散列表“溢出”引起的二、填空题（每空1.5分，计15分）21．ALV树是一种平衡的二叉排序树，树中任一结点的()22．在VSAM文件的控制区间中，记录的存储方式为()23．单链表的存储密度（）顺序表的存储密度。24．设SQ是循环队列，存储在数组D[M]中，则SQ入队操作对其队尾指针rear的修改是（）。25．长度为n的串s1与长度为2n的串s2的比较运算的时间复杂度是（）。26．广义表(((a,b,c),d,e,f))的长度是（）。27．N（n>

7、0）个节点的哈夫曼树恰含（）个度为1的节点。28．深度为n的二叉树最少有（）个结点。29．N（n>0）个顶点的连通有向图至少有（）条边。30．对N（n>0）个记录进行冒泡排序，最少要交换（）记录。三、简答题（每小题5分，计30分）31．给出下面森林对应的二叉树及二叉树的后续序列。（图1）32．一棵树有3度节点100个，2度节点200个，该树有叶子节点多少个，该树可以有多少个度为1的节点？33．设有广义表A,A=(((a,b),x),((a),(b)),(c,(d,(y))))，写出由A得到y的对广义表A的操作序列。34．

8、画出用普里姆算法构造下面所示带权无向图的最小生成树的示意图。35．写出下列用快排序对下列序列进行两次划分的过程及结果。372651487769822117132139551836．画出对下面的5阶B树插入关键字37后的结果。四、理解设计题（每小题5分，计15分）37．设某带头结头的单链表的结点结构说明如下：typed