《数据结构》试卷第4套

《《数据结构》试卷第4套》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》A卷（2003）一、简答问题：（16分）1.四类数据结构2.线性结构与非线性结构的差别3.简述算法的定义与特性4.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？堆排序二、判断正误，正确在（）内打否则打r（共5分）1.（）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值若它的右子树非空，则根结点的值大于其右孩子的值2.（）索引顺序表的特点是块内可无序，块间要有序。3.（）子串是

2、主串中任意个连续字符组成的序列。4.（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。5.（）快速排序的枢轴元素可以任意选定三、单项选择题（4分，每小题1分）1.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列？A.E、D>C>B>A^FB.B、C、E、F、A>DC.C、B、E、D、A、FD.A、D、F、E、B、C2.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为49的结点的左孩子的编号为。A.98B.99

3、C.50D.483.对下列关键字序列用快速排序法进行排序时，速度最快的情形是A.{21、25、5、17、9、23、30}B.{25、23、30、17、21、5、9}C.{21、9、17、30、25、23、5}D・{5、9、17、21、23、25、30}4.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为Ml、M2和M3o与森林F对应的二叉树根结点的右子树上的结点个数是A.MlB.M1+M2C.M3D.M2+M3四、填空题：（每小题2分，共20分）1.设一哈希表表长M为100,用除留余数法构造哈希函数，即H（K）=KMOD

4、P（P〈二M〉，为使函数具有较好性能，P应选2.N个结点的二叉树采用二叉链表存放，共有空链域个数为3.单链表与多重链表的区别是4.在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法5•深度为6（根层次为1）的二叉树至多有个结点。1.己知二维数组A[20][10]采用行序为主方式存储，每个元素占2个存储单元,并且A[10]⑸的存储地址是1000,则A[18]⑼的存储地址是2.在一个单链表中p所指结点之后插入s所指结点吋，应执行s_〉next=和p->next=的操作o8・广义表（（a,b）,c,d）的表头是,表尾是9.循环

5、单链表LA中，指针P所指结点为表尾结点的条件是10.在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，你认为应使用排序方法最好。五、构造题：（25分）1.已知一棵二叉树，其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。2.设哈希表长度为11,哈希函数H（K）=（K的第一字母在字母表屮的序号）MOD11,若输入顺序为（D,BA,TN,M,CI,I,K,X,TA）,处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。3.有一组关键字{5

6、0,52,85,22,96,17,36,55},请用快速排序，写出第一趟结果。4.已知叶子结点值2,3,5,6,9,11,构造哈夫曼树，计算其带权路径长度。5.构造8个结点的折半判定树。六、设计题：（30分）1.编写算法，判断带头结点的双循环链表L是否对称。（15分）对称是指：设各兀素值di,^2,,an,则有3i-an-i+i即指：ai=an?岂二cin-i………结点结构为：priordatanext2.二叉排序树T用二叉链表表示，其屮各元素均不相同。（1）写递归算法，按递减顺序打印各元素的值。（10分）（2）写出完成上述要求

7、的非递归算法。（5分）《数据结构》B卷（2003）（不含图结构）-、简答问题：（每小题4分，16分）1.四类基木数据结构的含义和特点。2.简述栈和队列的共同点和不同点。它们与线性表有什么关系?3.举例说明什么是抽象数据类型。1.算法的定义和特性。二、判断正误，正确在（）内打丁，否则打r（每小题1分，共5分）（）（1）由树的中序表示和前序表示可以导岀树的后序表示。（）（2）将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。（）（3）采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。（）（4）—

8、棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。（）（5）用一维数组存储二叉树时，是以先根遍历的次序存储结点。三、单项选择题（4分，每小题1分）1.对线性表，在下列哪种情况下应当采用链表表示？A.经常需要随机地存取元素B.经常需要进行插入