2009级《数据结构》期末考试(闭卷)试卷 a(2)

《2009级《数据结构》期末考试(闭卷)试卷 a(2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、填空题（每空1分，10分）（1）在一个长度为n的顺序表中，删除第i个元素（1≤i≤n+1）时,需要移动少n-i个元素。（2）稀疏矩阵的三元组存储方式有三列，第一列存储是矩阵非零元素所在的行。（3）单链表P所指节点后插入*S时，应执行S->next=P->next和P->next=S。hao（4）长度是n的单链表链接在长度m的单链表之后，算法的时间复杂度是多少O(m)。（5）在一棵二叉树中，假定度为2的结点数为5个，度为1的结点数为6个，则叶子结点数为6个。（6）目标串的长度为n，模式匹配的长度为[n/3]，则

2、算法在最坏情况下时间复杂度为n^2。（7）假定一组记录为｛46，79，56，25，76，38，40，80｝，对其进行快速排序的第一次划分后，右区间内元素的个数为4。（8）在图的邻接表的表示中，每个顶点的邻接表所有的结点数，对无向图来说是该顶点的度数，对于有向图来说是该顶点的出度数。2、单选题（每题2分，共20分）（1）以下图中，其邻接矩阵是对称矩阵的是（B）。A．有向图B.无向图C.AOV网D.AOE网（2）在一课平衡二叉排序树中，每个结点的平衡因子的取值范围是（A）。A.-1~1B.-2~2C.1~2D.0~1

3、（3）把数列｛56，23，78，92，88，67，19，34｝，增量等于3，进行一趟希尔排序的结果是（D）。A.｛19，23，56，34，78，67，88，92｝B.｛23，56，78，66，88，92，19，34｝C.｛19，23，34，56，67，78，88，92｝D.｛19，23，67，56，34，78，92，88｝仅供学弟学妹们参考，不得另行他用，谢谢（回想出来，可能有错，谨慎使用）（4）若100个结点的完全二叉树从根这一层开始，每层从左至右依次对其编号，根的编号为1，则编号为47的双亲是C号。A.24B

4、.25C.23D.无法确定（5）10阶B_树中，其中含有关键码个数最多是（C）。A.1B.2C.9D.10（6）顺序搜索算法适于存储结构为B链接表。A.哈希存储B.顺序存储或线性存储C.压缩存储D.索引存储（7）采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（C）。A.O（n²）B.O（nlog2n）C.O（log2n）D.O（n）（8）广义表A(a)，则表尾是（d）。A.()B.(())C.aD.(a)（9）若有循环队列Q，以下那个是判断队列已经满了的条件：(D)A.Q.front==Q.rear

5、B.Q.front-Q.rear==MaxsizeC.Q.front-Q.rear==MaxsizeD.Q.front==(Q.rear+1)%Maxsize（10）用线性探测法在哈希表中查找关键字，可能要探测多个哈希地址，这些位置上的键值B。A.一定都是同义词B.不一定都是同义词C.都相同D.一定都不是同义词3、简答题（每题5分，共20分）（1）什么是数据结构？通常有哪4类基本结构？（5分）相互之间存在一种或多种特定关系的数据元素的集合集合、线性结构、树形结构、图形结构或网状结构（1）冒泡排序，快速排序，选择排

6、序，归并排序，希尔排序，堆排序，插入排序这些排序中那些排序是不稳定的，为什么？（5分）不稳定的是快速排序、堆排序、希尔排序因为在这两种排序中可能存在两个或两个以上的关键字（设用R记录关键字，并假设Ri=Rj）排序后的序列中Rj领先于Ri详情看书263页仅供学弟学妹们参考，不得另行他用，谢谢（回想出来，可能有错，谨慎使用）（1）如果输入的序列为1、2、3、4、5、6，试问能否通过栈得到以下两个序列：4、3、5、6、1、2和1、3、5、4、2、6，为什么？（5分）前面不行，后面可以前面那个必须先弹出2才能弹出1（2）

7、试比较顺序存储结构和链式存储结构的优缺点。（5分）链式存储结构:(1)占用额外的空间以存储指针(浪费空间)(2)存取某个元素速度慢(3)插入元素和删除元素速度快(4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关.顺序存储结构:(1)空间利用率高(2)存取某个元素速度快(3)插入元素和删除元素存在元素移动,速度慢,耗时(4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现"溢出"问题.当元素个数远少于预先分配的空间时,空间浪费巨大.在存取元素频繁,但删除或插入操作较少的情况宜用顺序

8、表.堆排序,二分查找适宜用顺序表.4、采用哈希函数H（key）=keyMOD7。用开放定址法处理冲突，Hi=（H（key）+di）MOD10（di=1²，2²，3²，………）。试在表长为10的散列地址空间中对关键字序列（9，01，23，14，55，23，84，27）造哈希表，并求等概率元素查询情况下查找成功时的平均查找长度。（10分）仅供学弟学妹们参考，不得另行他用，谢谢