奥赛数据结构题汇总

1、数据结构练习一一、单项选择题 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

2、)所需空间与线性表长度成正比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，bbffha，gc (2)cd，eb，ax，daffha，gc

3、，bb (3)gc，ax，eb，cd，bbffda，ha (4)ax，bb，cd，daffeb，gc，ha9用n个键值构造一棵二叉排序树，最低高度为 。 (1)n/2 (2)n (3)log2n (4)log2n+110二分查找法要求查找表中各元素的键值必须是 排列。 (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所指结点前插入指

4、针S所指的结点，需执行下列语句：S.next：= P； Sprior：= Pprior；Pprior：= S； ：= S； A B C D E F H3.1.maxsize为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是 ，栈为满的条件是 。4具有100个结点的完全二叉树的深度为 。5有向图G用邻接矩阵A1n，1.n存储，其第i行的所有元素之和等于顶点i的 。6在顺序文件中，要存取第i个记录，必须先存取 。 7对于下面的二叉树，按中序遍历所得到的结点序列为 。8分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是 算法，最费时间的是 算

5、法。9.对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上括当的内容，以说明该算法的执行过程。顶点134UV（U，V）代价（2,1）（2,3） 4（2,4） 221,3,4（U，V）代价（2,3） 42,41,3（U，V）代价(3,1) 12,3,41（U，V）代价2,3,4,110.设散列函数为H（key），用拉链（链地址）法解决冲突，H的值域为0，n-1，构造的散列表类型如下：TYPE link = node； Node = RECORD key：keytype；next：link； END；Openhash = array0n-1 of link；请在下列算法划线处填

6、上适当内容，以完成在散列表HP中查找键值等于K的结点，若查找成功，返回该结点的指针，否则返回空指针。Function research(K：keytype；HP：openhash)：link； BEGINI：= H(K)；SUC：= false； ；while(P<>NIL)and(not suc)doif P.key<>Kthen else suc：= true； return(P)END 四、应用题1已知二叉树的后序和中序序列如下，构造出该二叉树。 后序序列: ABCDEFG 中序序列：ACBGEDF2有一组关键码序列(38，19，65，13，97，49，41，95

7、，1，73)，采用冒泡排序方法由小到大进行排序，请写出每趟的结果。3设图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)= K mod 7，闭散列表的地址空间为0，6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表。5对下面两棵二叉树，分别画出它们的顺序存储结构。 A B C D E F I J A B C D E F

8、 G I J K 6已知图G的邻接表如下，画出图G的所有连通分量。数据结构练习二一、 选择题1.在下列备选答案中选出一个正确的，将其号码填在“ ”上。 1若线性表最常用的操作是存取第i个元素及其前趋的值，则采用 存储方式节省时间。 a单链表 b双链我 c单循环链表 d顺序表 2对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用 次序的遍历实现编号。 a先序 b中序 c后序 d从根开始的层次遍历 3.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。 a空或只有一个结点 b高度等于其结点数 c任

9、一结点无左孩子 d任一结点无右孩子 4下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogzn)的是 。 a堆排序 b冒泡排序 c直接选择排序 d快速排序5下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 a堆排序 b.冒泡排序 c快速排序 dSHELL排序三、填空1 在单链表中，删除指针P所指结点的后继结点的语句是 。2 取出广义表A：(x，y，2)，(a，b，c，d)中原子b的函数是 。3 已知完全-y树的第八层有8个结点，则其叶子结点数是 。4 将下三角矩阵A18，L8的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元

10、，则A?，5的地址为 。5 有n个顶点的强连通有向图G至少有 条弧。6 求最短路径的DIJKSTRA算法的时间复杂度为 。7 高度为5的三阶B树至少有 个结点。8 在有序表A1.20中，采用二分查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为 。9 直接选择排序算法所执行的元素交换次数最多为 。10.下列排序算法中，稳定的排序算法是 (选择排序，堆排序，快速排序，直接插入排序)。四、解答下列各题(30分) 1一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。(5分) 先序序列ABCDEFGHIJ 中序序列CBEDAGHFJl 2对下面给出的数据序列，构造一棵哈夫曼树，并求出其

11、带权路径长度。(6分) 4， 5， 6， 7， 10， 12， 15， 18， 23 3图G的邻接表如下页，完成下列各题：(7分) (1)画出从顶点5出发进行广度遍历所生成的生成树。 (2)判断其中是否存在有向回路，若不存在，求出其拓扑序列。 4对下列数据表，写出采用快速排序算法排序的每一趟的结果。(6分) (60，20，3l，1，5，44，55，61，200，30，80，150，4，29) 5.已知哈希表地址空间为0.8，哈希函数为H(k)k mod 7，采用线性探查法处理冲突。将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。 (6分) 100，20，21，35，3，78，

12、99，45012345678A：五、算法设计(共30分)1.已知单循环链表L中至少有两个结点，每个结点的两个字段为data和next，其中字段data的类型为整型。设计算法以判断该链表中的每个元素的值是否小于其后续两个结点的值的和，若满足，返回true，否则返回false。(8分)2.设计算法按后序次序打印二叉树T中所有叶子结点的值，并返回其结点数。 (8分)3.写出在二叉排序树中查找值为x的元素的算法。(6分)4.设计算法按层次遍历二叉树T。(8分) 模拟试卷三一、选择题(每小题2分，共20分)，在下列备选答案中选出一个正确的，将其号码填在“ ”上。1.一个栈的输入序列为1 2 3 4 5，

13、则下列序列中不可能是栈的输出序列的是 。 a2 3 4 1 5 b5 4 1 3 2 c2 3 1 4 5 d.1 5 4 3 22设循环队列中数组的下标范围是ln，其头尾指针分别为f和r，则其元素个数为。 a.r-f b。r-f+1 c(r-f)mod n+l d(r-f+n) mod n3.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 存储方式最节省时间。 a单链表 b双链表 c带头结点的双循环链表 d单循环链表4一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足。 a其中任意一结点均无左孩子 b其中任意一结点均无右孩子 c其中只有一个叶子结

14、点 d是任意一棵-y树5一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为。 a0 b1 c2 d.不确定6数组Al.5，1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为lOOO的连续的内存单元中，则元素A5，5的地址为。 a1140 b1145 c1120 d11257求最短路径的DIJKSTRA算法的时间复杂度为。 aO(n) bO(n+e) cO(n2) dO(n*e)8对有18个元素的有序表作二分查找，则查找A3的比较序列的下标为 。 a1，2，3 b9，5，2，3 c9，5，3 d9，4，2，39快速排序算法在最好情况下的时间复杂度为。 aO(n) bO(nlogn

15、) cO(n) dO(1Ogn)10下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是。 a堆排序 b冒泡排序 c.快速排序 d直接插入排序二、判断题(每小题1分，共10分)判断下列各题是否正确，若正确，在()内打“”，否则打“×”。1. ( )线性表的长度是线性表所占用的存储空间的大小。2. ( )双循环链表中，任意一结点的后继指针均指向其逻辑后继。3. ( )在对链队列做出队操作时，不会改变front指针的值。4. ( )如果两个串含有相同的字符，则说它们相等。5. ( )如果二叉树中某结点的度为1，则说该结点只有一棵子树。6. ( )已知一棵树的先序序列和后序序

16、列，一定能构造出该树。7. ( )图G的一棵最小代价生成树的代价未必小于G的其他任何一棵生成树的代价。 8. ( )图G的拓扑序列唯一，则其弧数必为n一1(其中n为G的顶点数)。9. ( )对一个堆按层次遍历，不一定能得到一个有序序列。10. ( )直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。三、填空(每小题2分，共20分)1. 在双循环链表L中，指针P所指结点为尾结点的条件是 。2. 在单链表中，删除指针P所指结点的后继结点的语句是 。3. 队列的特性是 。4. 若某串的长度小于一个常数，则采用 存储方式最节省空间。5. 在有n个叶子结点的哈夫曼树中，总结点数是

17、。6. 一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足 。7. 高度为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)删除150

18、 3对下列数据表，写出采用SHELL排序算法排序的每一趟的结果。(5分)(100，12，20，31，1，5，44，66，61，200，30，80，150，4，8)4求出下面AOE网中的关键路径(要求标明每个顶点的最早和最迟发生时间，并画出关键路径)。(5分)五、算法设计(共30分)1设计算法求中序线索二叉树中指针P所指结点的后继结点的指针。(6分)2设计算法以判断二叉树T是否为二叉排序树(设T中任意两个结点的值均不相等)。(8分)3设计算法将一个带有头结点的单循环链表A分解为两个具有相同结构的链表B，C，其中B表中结点为A表中值为奇数的结点，而C表中结点为A表中值为偶数的结点(要求利用原表结点

19、)。(8分) 4.设计算法以判断无向图G是否是连通的，若连通则返回true，否则返回false。(注：可以使用以下几个函数调用； firstadj(G，v)返回图G中顶点v的第一个邻接点，若不存在则返回0；nextadj(G，v，w)返回图G中顶点v的邻接点中处于w之后的邻接点，若不存在则返回0； nodes(G)返回图G中的顶点数) (8分)模拟试卷四一、选择题(每小题2分，共16分)在下列备选答案中选出一个正确的，将其号码填在“ ”上。1一个栈的输入序列为1 2 3 4 5，则下列序列中是栈的输出序列的是 。 a 2 3 4 1 5 b 5 4 1 3 2 c 3 1 2 4 5 d 1

20、4 2 5 32若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用下列 存储方式最节省时间。 a单链表 b.双链表 c带头结点的双循环链表 d单循环链表3二叉树在线索化后，仍不能有效求解的问题是 。 a先序线索-二叉树中求先序后继 b.中序线索二叉树中求中序后继 c中序线索二叉树中求中序前趋 d后序线索二叉树中求后序后继4求最短路径的FLOYD算法的时间复杂度为 。 aO(n) bO(n+e) c.O(n2) dO(n3)5下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是 。 a快速排序 b希尔排序 c冒泡排序 d堆排序6下列排序算法中， 每一趟都

21、能选出一个元素放在其最终位置上，并且是不稳定的。 a冒泡排序 b希尔排序 c直接选择排序 d直接插入排序7在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为一1，右孩子的平衡因子为0，则应作 型调整以使其平衡。 aLL b. LR cRL dRR 8数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用 排序算法最节省时间。 a堆排序 b希尔排序 c快速排序 d直接选择排序二、判断题(每小题1分，共10分)判断下列各题是否正确，若正确，在()内打“”，否则打“X”。1( )线性表的唯一存储形式是链表。2( )已知指针P指向链表L中的

22、某结点，执行语句P：Pnext不会删除该链表中的结点。3( )在链队列中，即使不设置尾指针也能进行入队操作。4( )如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。5( )设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。6( )9阶B树中，除根以外的任何一个非叶子结点中的关键字数目均在59之间。7( )任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。8( )若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条(其中n为G的顶点数)。9( )给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序

23、树。10( )由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。三、填空(每空2分，共20分)1带头结点的双循环链表L为空表的条件是 。2在双链表中，在指针P所指结点前面插入一个结点S的语句序列是： S.next：= P；Sprior：= Pprior；Pprior = S； 。3对广义表A(x，(a，b)，c，d)的运算head(head(tail(A)的结果是 。4已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是 。 5有n个结点并且其高度为n的二叉树的数目是 。6循环队列采用数组dataln来存储元素的值，并用front和rear分别作为其头

24、尾指针。为区分队列的满和空，约定：队中能够存放的元素个数最大为n-1，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是 。入队时，可用语句 求出新元素在数组data中的下标。7高度为8的平衡二叉树的结点数至少是 。8.在有n个顶点的有向图中，每个顶点的度最大可达 。9数组Al10，110的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A5，6的地址为 。四、解答下列各题(26分)1已知二叉树的中序序列和后序序列如下，画出该二叉树。(5分) 中序序列为：DCEFBHGAKJLIM 后序序列为：DFECHGBKLJMIA2.以下面数

25、据作为叶子结点的权值构造一棵哈夫曼树，并计算出其带权路径长度。 (6分，) 5，6，7，8，9，10，15，18，223对下面数据表，写出采用快速排序算法排序的每一趟的结果，并标明第一趟排序过程中的数据移动情况。(5分) (50，12，20，31，1，5，44，166，61，100，30，80，150，4，8)4求出下图的所有拓扑序列，并指出哪一个是拓扑排序算法的运行结果(设算法中搜索顶点的邻接点均是按从小到大的次序进行的)。(5分)5画出在递增有序表A121中进行二分查找的判定树。(5分)五、算法设计(共28分) 1已知带头结点的单循环链表L中至少有一个元素，设计算法判断L中各元素的值是否均

26、是其序号的两倍，若满足，返回true，否则返回false，同时返回该链表中的结点数。(6分)2已知数组A1n的元素递增有序。设计算法以数组A中的元素构造一棵二叉排序树，并使其满足平衡二叉树的条件。(8分)3设计算法，打印连通图G中每个顶点一次且仅一次，并要求其打印次序满足条件：距顶点v0近的顶点先于距离远的顶点(以边数为单位)。(8分)4.在下面冒泡排序算法中填入适当内容，以使该算法在发现有序时能及时停止。(6分) procedure bubble(vara：array1n of integer)； begin i:=1； repeat exchanged：=false； for j:= n

27、downto do if aj<aj-1 then begin aj<=>aj-1； 交换 end； ； until ； end；模拟试卷五一、选择题(20分)在下列备选答案中选出一个正确的，将其号码填在“ ”上。1.设循环队列中数组的下标范围是1n，头尾指针分别为f和r,则其元素个数为 。 ar-f br-f+1 c(r - f+1)mod n d(r-f+n)mod n2一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是 。 a 2 3 4 1 5 b 5 4 2 3 1 c 2 3 1 4 5 d 1 5 4 3 23用十字链表表示一个有K个非。

28、元素的mXn的稀疏矩阵，则其总结点数为 。 am*n bm*n+m+n cK+max(m，n)+1 dK+m+n+14对矩阵压缩存储是为了 。 a方便运算 b节省空间 c方便存储 d提高运算速度5.一棵左右子树均不空的二叉树在先序前趋和后序后继线索化后，其空链域数为 。 a0 b1 c2 d不确定6判断线索二叉树中某结点P有左孩子的条件是 。 ap<>nil bp1child<>nil cP1tag= 0 d.P1tag17在图G用邻接矩阵存储时，求最短路径的DIJKSTRA算法的时间复杂度为 。 aO(n) bO(n+e) cO(n2) dO(n*e)8.设图G采用邻

29、接表存储，则拓扑徘序算法的时间夏杂度为 aO(n) bO(n+e) c.O(n2) dO(n*e)9快速排序算法在最好情况下的时间复杂度为 。 aO(n) b.O(n2) cO(nlog2n) dO(1og2n)10下列排序算法中，时间复杂度为O(n1og2n)且占用额外空间最少的是 。 a堆排序 b冒泡排序 c快速排序 dSHELL排序二、填空(10分)1双循环链表L中某结点P为尾结点的条件是 。2已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 。3高度为K的m阶B树至少有 个结点。4有n个顶点的连通图至少有 条边。5取出广义表A：(x，(a，b，c，d)中原子b的函数是

30、 。三、解答下列题(20分)1一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。(6分) 先序： B F ICEH G 中序：D KFIA EJC 后序： K FBHJ G A2已知哈希表地址空间为014，哈希函数为H(k)= k mod 13，采用线性探查法处理冲突。将下面各数依次存入该散列表中，并求出在等概率下的平均查找长度和失败的查找长度。(6分) 240，29，345，189，100，20，21，35，3，208，78，99，45，350012345678910111213143对下面的递归算法，要求：(8分) (1)写出调用p(4)

31、的执行结果。 (2)将其转换为等价的非递归算法。 procedure p(w：integer)； begin if w >O then begin write(W)； p(w-1)； p(w-1)； endend；四、算法设计(50分，每题10分)1设计算法将数组AlN按从大到小的次序进行排序，要求一旦发现有序即停止。2设计算法求两个带有头结点的递增单循环链表A，B的公共元素，并建成另一相同结构的链表C。要求时间尽可能少。3已知T为一棵二叉排序树。 (1)设计算法按递减次序打印各结点的值。 (2)设计算法以产生一个序列，要求该序列满足：依次将这些元素插入到初值为 空的二叉排序树中所得的结

32、果与原二叉排序树相同。4一棵树T采用二叉链表表示，其中指针及结点的类型说明如下： typetreelink =tnode； tnode = record data：datatype； firstson，nextbrother：treelink；第一个孩子和下一个兄弟 end；设计算法按层次遍历树t的各结点，并给出离根结点最远的一个结点的指针。5设计算法判断图G中是否存在从顶点Vi到Vj的长度为K简单路径。模拟试卷六一、选择题(每小题2分，共10分)在下列备选答案中选出一个正确的，将其号码填在“ ”上。1若某链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点， 则采用 存储方式最节

33、省时间。 a单链表 b双链表 c单循环链表 d.带尾指针的单循环链表2一棵左右子树均不空的二叉树在后序线索化后，其空指针域数为 。 a0 b1 c2 d不确定3数组Ao5，06的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A5，5的地址为 。 a1175 b1180 c1205 d12104下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是 。 a堆排序 b冒泡排序 c直接选择排序 d快速排序5下列排序算法中， 算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 a堆排序 b冒泡排序 c快速排序 d.插入排序二、判

34、断题(每小题1分，共重0分)判断下列各题是否正确，若正确，在()内打"”，否则打“×”。1.( )在对链队列作出队操作时，不会改变front指针的值。 2( )若一个栈的输入序列为123n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=ni+1。(I=1，2,.，n)3( )二叉树中的叶子结点就是二叉树中没有左右子树的结点。4( )一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。5( )有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。6( )有向图的邻接表和逆邻接表中的结点数一定相同。7( )删除二叉排序树中一个结点，再

35、重新插入上去，一定能得到原来的二叉排序树。8( )图G的拓扑序列唯一，则其弧数必为n一1(其中n为G的顶点数)。9( )快速排序是排序算法中最快的一种。10( )对一个堆，无论按二叉树层次遍历还是先序遍历，都不一定能得到有序序列。 三、填空(每小题2分，共20分)1.在双循环链表中，删除指针P所指结点的语句序列是 。2.取出广义表A(x，(a，b，c，d)中原子c的函数是 。3.已知完全二叉树的第七层有8个结点，则其叶子结点数是 。4.在有n个叶子结点的哈夫曼树中，总结点数是二 。5.有n个顶点的有向图G最多有 条弧。6.求最短路径的FLOYD算法的时间复杂度为 。7.高度为7的平衡二叉树至少

36、有 个结点。 8.在有序表Al18中，采用二分查找算法查找元素值等于A7的元素，所比较过的元素的下标依次为 。9.冒泡排序算法在最好情况下的元素交换次数为 。10已知一个待排序序列已基本有序(每个元素离其最终位置不远)，则采用下面几种算法中的 最省时间(直接选择排序，堆排序，快速排序，直接插入排序)。四、解答下列各题(20分)1一棵树的先序序列和后序序列分别如下，画出该树。(4分) 先序序列：ABCDEFGHIJKLMN 后序序列：CDEBHIGKMLNJFA2对下面数据表，写出采用快速排序算法排序的每一趟的结果。(4分) (70，12，20，31，1，5，44，66，61，200，30，80

37、，150，4，28)3求出下面图中顶点1到其余顶点的最短路径。(4分)4. 对下面的递归算法，要求：(8分) (1)写出调用P(4)的执行结果。 (2)将其转换为等价的非递归算法， procedure p(w：integer) begin if w>0 then begin p(w-1)； write(w)； p(w-1) end end；五、算法设计(共40分)1巳知一个单链表中每个结点存放一个整数，并且其结点数不少于2。设计算法以判断该链表中从第二项起的每个元素值是否等于其序号的平方减去其前趋的值，若满足，返回true，否则返回false。(8分) 2设计算法求先序线索二叉树中指针P

38、所指结点的先序后继结点的指针，并通过调用该算法来写出先序遍历先序线索二叉树的非递归算法。(8分)3设计算法以求出无向图G的连通分量的个数。(8分)4分别写出在递增有序表A1n中采用二分查找算法查找值为x的元素的递归和非递归算法。(8分)5设计算法打印出二叉树T的先序次序下的前K个结点的值。(8分)模拟试卷七一、选择题(每小属2分，共10分)在下列备选答案中选出一个正确的，将其号码填在“ ”上。1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用 存储方式最节省时间。 a顺序表 b双链表 c带头结点的双循环链表 d单循环链表 2在用邻接表表示图时，求最短路径的Di

39、jkstra算法的时间复杂度为 。 aO(n) b.O(n+e) cO(n2) d.O(n3) 3依次将待排序序列中的元素和有序子序列合并为一个新的有序子序列的算法是 。 a快速排序 b插入排序 c冒泡排序 d堆排序 4在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 型调整以使其平衡。 aLL bLR cRL dRR 5已知数据表A中每个元素距其最终位置不远，则采用 排序算法最节省时间。 a堆排序 b插入排序 c快速排序 d直接选择排序二、判断题(每小题1分，共10分) 判断下列各题是否正确，若正确，在( )内打“

40、”，否则打“×”。 1( )线性表就是顺序表。 2( )链表只能借助于指针和动态变量来实现。 3( )线性表的长度是指其中元素所占用的存储空间的字节数。 4( )对广义表A(a，(b，c)，d)的运算head(tail(A)的结果不是b。 5( )若一棵树中某结点的度为1，则该结点仅有一棵子树。 6( )所谓平衡二叉树是指左右子树的高度差的绝对值不大于l的二叉树。 7( )AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。 8( )若从某顶点开始对有向图G进行深度遍历，所得的遍历序列唯一，则可断定其弧数为n一1。 9( )理想情况下，在散列表中查找一个元素的时间复杂

41、度为O(1)。 10( )快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。三、填空(每空2分，共20分) 1在带头结点的双循环链表L中，最后一个结点的指针是 。 2在仅有尾指针R指示的单循环链表R中，在表尾插入一个结点S的语句序列是 。 3。已知栈的输入序列为l，2，3，n，输出序列为a1，a2，an，a2 = n的输出序列共有 种输出序列。 4已知循环队列用数组datal.n存储元素值，用f，r分别作为头尾指针，则当前元素个数为 。 5在左右子树均不空的先序线索二叉树中，空链域的数目是 。 6在二叉链表中，判断某指针P所指结点为叶子结点的条件是 。 7若某二叉树有20个叶子结点

42、，有30个结点仅有一个孩子，则该二叉树的总结点数是 。 8在有n个顶点的连通图中，其边数至少为 。 9已知数组A1.10，110为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5，6对应的地址为 。10直接选择排序算法在最好情况下所作的交换元素的次数为 。四、解答下列各题(每小题5分，共20分)1.已知一树的双亲表示如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。123456789101112131415DataABCDEFGHIJKLMNOparent0111223344566782一棵二叉排序树结构如下，各结点的值从小到大依次为18，请标出各结点的值。 3对下面数据表，写出采用冒泡排序算法排序的每一趟的结果。 (25 10 20 31 5 44 16 61 100 3)4求出下图的一棵最小生成树。五、算法设计(每题8分，共40分)1已知某类集合中的元素个数不超过maxnum，元素类型为integer，试选择合适的数据结构和约定，并写出在这种结构下求解两个集合的交集的算法(要求算法的时间复杂度为两表长之和的数量级)。 2设计出在递增有序的数组Aln)中查找值为x的元素的二分查找