奥赛数据结构题汇总

1A／＼BC／＼＼DEF／H数据结构练习一一、单项选择题1．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。(1)单链表(2)双链表(3)单循环链表(4)带头结点的双循环链表2．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是(1)A，B，C，D(2)D，C，B，A(3)A，C，D，B(4)D，A，B，C3．串是。(1)不少于一个字母的序列(2)任意个字母的序列(3)不少于一个字符的序列(4)有限个字符的序列4．链表不具有的特点是。(1)可随机访问任一元素(2)插入删除不需要移动元素(3)不必事先估计存储空间(4)所需空间与线性表长度成正比5．在有n个叶子结点的哈夫曼树中，其结点总数为。(1)不确定(2)2n(3)2n+1(4)2n-16．任何一个无向连通图的最小生成树(1)只有一棵(2)有一棵或多棵(3)一定有多棵(4)可能不存在7．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为。(1)98(2)99(3)50(4)488.下列序列中，是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。(1)[da，ax，eb，de，bb]ff[ha，gc](2)[cd，eb，ax，da]ff[ha，gc，bb](3)[gc，ax，eb，cd，bb]ff[da，ha](4)[ax，bb，cd，da]ff[eb，gc，ha]9．用n个键值构造一棵二叉排序树，最低高度为。(1)n/2(2)n(3)[log2n](4)[log2n+1]10．二分查找法要求查找表中各元素的键值必须是排列。(1)递增或递减(2)递增(3)递减(4)无序11.对于键值序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，必须从键值为的结点开始。(1)100(2)12(3)60(4)15三、填空题1．在带有头结点的单链表L中，第一个元素结点的指针是。2．在双循环链表中，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S↑.next：=P；S↑．prior：=P↑．prior；P↑．prior：=S；：=S；3.[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是，栈为满的条件是。4．具有100个结点的完全二叉树的深度为。5．有向图G用邻接矩阵A[1．．n，1..n]存储，其第i行的所有元素之和等于顶点i的。6．在顺序文件中，要存取第i个记录，必须先存取。27．对于下面的二叉树，按中序遍历所得到的结点序列为。8．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是算法，最费时间的是算法。9.对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上括当的内容，以说明该算法的执行过程。10.设散列函数为H（key），用拉链（链地址）法解决冲突，H的值域为0，…，n-1，构造的散列表类型如下：TYPElink=↑node；Node=RECORDkey：keytype；next：link；…END；Openhash=array[0．．n-1]oflink；请在下列算法划线处填上适当内容，以完成在散列表HP中查找键值等于K的结点，若查找成功，返回该结点的指针，否则返回空指针。Functionresearch(K：keytype；HP：openhash)：link；BEGINI：=H(K)；SUC：=false；；while(PNIL)and(notsuc)doifP↑.keyKthenelsesuc：=true；return(P)END四、应用题1．已知二叉树的后序和中序序列如下，构造出该二叉树。后序序列:ABCDEFG中序序列：ACBGEDF2．有一组关键码序列(38，19，65，13，97，49，41，95，1，73)，采用冒泡排序方法由小到大进行排序，请写出每趟的结果。顶点134UV（U，V）代价（2,1）∞（2,3）4（2,4）2{2}{1,3,4}（U，V）代价（2,3）4{2,4}{1,3}（U，V）代价(3,1)1{2,3,4}{1}（U，V）代价{2,3,4,1}3A／＼BC／＼／＼DEFG／＼／IJKA／＼BC／＼＼DEF／＼IJ3．设图G=(V，E)，V={1，2，3，4，5，6}，E={1，2，1，3，2，5，3，6，6，5，5，4，6，4}。请写出图G中顶点的所有拓扑序列。4．设散列函数为H(K)=Kmod7，闭散列表的地址空间为0，…，6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表。5．对下面两棵二叉树，分别画出它们的顺序存储结构。6．已知图G的邻接表如下，画出图G的所有连通分量。数据结构练习二一、选择题1.在下列备选答案中选出一个正确的，将其号码填在“”上。1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。a．单链表b．双链我c．单循环链表d．顺序表2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用次序的遍历实现编号。a．先序b．中序c．后序d．从根开始的层次遍历3.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。a．空或只有一个结点b．高度等于其结点数c．任一结点无左孩子d．任一结点无右孩子4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogzn)的是。a．堆排序b．冒泡排序c．直接选择排序d．快速排序45．下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。a．堆排序b.冒泡排序c．快速排序d．SHELL排序三、填空1．在单链表中，删除指针P所指结点的后继结点的语句是。2．取出广义表A：((x，y，2)，(a，b，c，d))中原子b的函数是。3．已知完全-y．树的第八层有8个结点，则其叶子结点数是。4．将下三角矩阵A[1．．8，L．8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[?，5]的地址为。5．有n个顶点的强连通有向图G至少有条弧。6．求最短路径的DIJKSTRA算法的时间复杂度为。7．高度为5的三阶B树至少有个结点。8．在有序表A[1．.20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为。9．直接选择排序算法所执行的元素交换次数最多为。10.下列排序算法中，稳定的排序算法是(选择排序，堆排序，快速排序，直接插入排序)。四、解答下列各题(30分)1．一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。(5分)先序序列ABCDEFGHIJ中序序列CBEDAGHFJl2．对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。(6分)4，5，6，7，10，12，15，18，233．图G的邻接表如下页，完成下列各题：(7分)(1)画出从顶点5出发进行广度遍历所生成的生成树。(2)判断其中是否存在有向回路，若不存在，求出其拓扑序列。4．对下列数据表，写出采用快速排序算法排序的每一趟的结果。(6分)(60，20，3l，1，5，44，55，61，200，30，80，150，4，29)55.已知哈希表地址空间为0..8，哈希函数为H(k)＝kmod7，采用线性探查法处理冲突。将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。(6分)100，20，21，35，3，78，99，45012345678A：五、算法设计(共30分)1.已知单循环链表L中至少有两个结点，每个结点的两个字段为data和next，其中字段data的类型为整型。设计算法以判断该链表中的每个元素的值是否小于其后续两个结点的值的和，若满足，返回true，否则返回false。(8分)2.设计算法按后序次序打印二叉树T中所有叶子结点的值，并返回其结点数。(8分)3.写出在二叉排序树中查找值为x的元素的算法。(6分)4.设计算法按层次遍历二叉树T。(8分)模拟试卷三一、选择题(每小题2分，共20分)，在下列备选答案中选出一个正确的，将其号码填在“”上。1.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是。a．23415b．54132c．23145d.1543262．设循环队列中数组的下标范围是l～n，其头尾指针分别为f和r，则其元素个数为。a.r-fb。r-f+1c．(r-f)modn+ld．(r-f+n)modn3.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省时间。a．单链表b．双链表c．带头结点的双循环链表d．单循环链表4．一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足。a．其中任意一结点均无左孩子b．其中任意一结点均无右孩子c．其中只有一个叶子结点d．是任意一棵-y．树5．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为。a．0b．1c．2d.不确定6．数组A［l..5，1..6］的每个元素占5个单元，将其按行优先次序存储在起始地址为lOOO的连续的内存单元中，则元素A[5，5]的地址为。a．1140b．1145c．1120d．11257．求最短路径的DIJKSTRA算法的时间复杂度为。a．O(n)b．O(n+e)c．O(n2)d．O(n*e)8．对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为。a．1，2，3b．9，5，2，3c．9，5，3d．9，4，2，39．快速排序算法在最好情况下的时间复杂度为。a．O(n)b．O(nlog２n)c．O(n２)d．O(1Og２n)10．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是。a．堆排序b．冒泡排序c.快速排序d．直接插入排序二、判断题(每小题1分，共10分)判断下列各题是否正确，若正确，在()内打“√”，否则打“×”。1.()线性表的长度是线性表所占用的存储空间的大小。2.()双循环链表中，任意一结点的后继指针均指向其逻辑后继。3.()在对链队列做出队操作时，不会改变front指针的值。4.()如果两个串含有相同的字符，则说它们相等。5.()如果二叉树中某结点的度为1，则说该结点只有一棵子树。6.()已知一棵树的先序序列和后序序列，一定能构造出该树。7.()图G的一棵最小代价生成树的代价未必小于G的其他任何一棵生成树的代价。8.()图G的拓扑序列唯一，则其弧数必为n一1(其中n为G的顶点数)。9.()对一个堆按层次遍历，不一定能得到一个有序序列。10.()直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。三、填空(每小题2分，共20分)1.在双循环链表L中，指针P所指结点为尾结点的条件是。2.在单链表中，删除指针P所指结点的后继结点的语句是。3.队列的特性是。4.若某串的长度小于一个常数，则采用存储方式最节省空间。5.在有n个叶子结点的哈夫曼树中，总结点数是。6.一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足。77.高度为K的2-3树的结点数至少是。8.在有n个结点的无向图中，其边数最多为。9.取出广义表A＝(x，(a，b，c，d))中原子b的函数是。10.对矩阵采用压缩存储是为了。四、解答下列各题(20分)1．分别画出满足下列条件的所有二叉树。(4分)(1)先序序列和中序序列均为ABCDE。(2)先序序列为ABCDE，并且与其相对应的树的高度为5。2．对下面3阶B树依次执行下列操作，画出每步的操作结果。(6分)(1)插入300(2)插入70(3)插入30(4)删除1503．对下列数据表，写出采用SHELL排序算法排序的每一趟的结果。(5分)(100，12，20，31