资源描述：
《数据结构本科教学资料-试题一》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、简答问题：(每小题4分，共16分)四类数据结构2.3.4.线性结构与非线性结构有何差别？简述算法的定义与特性。设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中(归并排序、基数排序、快速排序、堆排序、插入排序)哪一种方法最好，为什么？二、判断正误：(每小题1分，共5分〉正确在()内打V,否则打Xo)二叉排序树或是一棵空树，或是具有下列性质的二叉1.(树:2.3・4.若它的左子树非空，则根结点的值大于其左孩子的值,若它的右子树非空，则根结点的值大于其右孩壬的值。)))if表存放。
2、5.三、快速排序的枢轴元素可以任意选定O()单项选择题：(每小题1分，共4分)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、99C、50D、483・对下列关键字序列用快速排序法进行排序时
3、，速度最快的情形是:A){21、25、5、17、9、23、30}9}B){21、9、17、30、25、23、5}B){25、23、30、17、21、5、D){5、9、17、21、23、25、30}4.设森林F中有三棵树，第一.第二和第三棵树的结点个数分别为Ml、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是:A)MlB)M1+M2C)M3D)M2+M3填空题:(每小题2分，共20分)1.H2.设一哈希表表长M为100,用除留余数法构造哈希函数，即(K)=KMODP(P<=M),为使函数
4、具有较好性能，P应选N个结点的二叉树采用二叉链表存放，共有空链域个数为—1.单链表与多重链表的区别是2.在各种查找方法中，平均查找长度与结点个数无关的是3.深度为6(根层次为1)的二叉树至多有个结点。4.已知二维数组A[20][10]采用行序为主方式存储，每个元素占2个存储7.单元并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是在一个单链表中P所指结点之后插入s所指结点时,应执行8.s->next=和p->next=的操作.广义表(Q,b),c,d)的表头是，表尾是9.循环单
5、链表LA中，指针P所指结点为表尾结点的条件是10.在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。五、构造题：(每小题5分，共25分〉1.已知一棵二叉树，其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。2.设哈希表长度为11,哈希函数H(K)=(K的第一字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成
6、功平均查找长度。3.有一组关键字{50,52,85,22,96,17,36,55},请用快速排序，写出第一趟排序结果。4.已知叶子结点值2,3,5,6,9,11,构造哈夫曼树，计算其带权路径长度。5.画出8个结点的折半判定树。六、算法设计题：《每小题15分，共30分〉（仅要求给出子程序》1.编写算法，判断带头结点的双向循环链表L是否对称。（15分）对称是指：设各元素值aba2,...,an,则有即指：ai=&2=结点结构为:priordatanext2.二叉排序树T用二叉链表表示，其中各元素均不相同
7、。（1）写出递归算法，按递减顺序打印各元素的值。（10分）（2）写出完成上述要求的非递归算法。（5分）
