数据结构综合题.doc

综合题1设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆（1）495983414347834741435949498341434783435949414347834959414759（2）4741835943494347415983495947414983434741438349595947414383492、设有一个不带头结点的单向链表，头指针为head，结点类型为NODE，每个结点包含一个数据域data和一个指针域next，该链表有两个结点，p指向第二个结点（尾结点），按以下要求写出相应语句（不要求完整程序，（1）、（2）、（3）、（4）是一个连续的过程）。（1）新开辟一个结点，使指针s指向该结点，结点的数据成员data赋值为1（2）把该结点插入链表的尾部，释放指针s的指向（3）删除链表的第一个结点（4）已知p1指向另一个新结点，把它插入到p所指结点和尾结点之间（1）s=（NODE*）malloc(sizeof(NODE);s-data=1;（2）p-next=s;s-next= NULL；free(s)（3）head = head -next；（4）p1-next= p-next；p-next=p1；3设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1,2,12。 （1）说出有哪几个元素需要经过4次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到(1)19，48，84，116，200471285211110639 （2）(3)3次4（1）设有序列10，12，15，19，22，25，100，130，150，200画出对上述序列进行折半查找的判定树（以序列中的元素作为树的结点）（2）为了成功查找到100需要进行多少次元素间的比较？为了查找9，经过多少次元素间的比较可知道查找失败？221213019150251520010010（1）（2）4次，3次5（1）对给定数列7,16,4,8,20,9,6,18,5，依次取数列中的数据，构造一棵二叉排序树。 (2 )对一个给定的查找值,简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?468957162018（1）（2）先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。6 (1) 设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二叉排序树。（2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。246167318514 （1）(2)中序遍历 中序 2，3，4，5，6，7，14，16，181（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树 （2）若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系 （3）给出该树的前序遍历序列abced（1）（2）dbeanext=s; s-next=p-next;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写（1）p1-next= head2；p2-next= head1；（2）不对，s-next= p-next；p-next=s；2（1）一组记录的关键字序列为45，40，65，43，35，95写出利用快速排序的方法，以第一个记录为基准得到的一趟划分的结果（要求给出一趟划分中每次扫描和交换的结果） （2）同样对序列45，40，65，43，35，95利用直接插入排序，写出逐次插入过程（从第一个元素一直到第六个元素）。（1） 45 40 65 43 35 95 35 40 65 43 35 95 35 40 65 43 65 95 35 40 43 43 65 95 35 40 43 45 65 95（2） 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 953（1）画出对长度为10的有序表进行折半查找的判定树（以序号1，2，10表示树结点） （2）对上述序列进行折半查找，求等概率条件下，成功查找的平均查找长度52849631071（1）（2）ASL=（1x1+2x2+3x4+4x3）/10=29/104（1）利用筛选过程把序列42，82，67，102，16，32，57，52建成堆（小根堆），画出相应的完全二叉树（不要求中间过程） （2）写出对上述堆对应的完全二叉树进行中序遍历得到的序列1642325257678242826752573216102102初始树 堆（2）102，52，42，82，16，67，32，575（1）利用筛选法把序列37，77，62，97，11，27，52，47建成堆（小根堆），画出相应的完全二叉树 （2）写出对上述堆所对应的二叉树进行前序遍历得到的序列37776247522711 971137274752627797（1）初始树 堆（2）11，37，47，97，77，27，62，526（1）设有一个整数序列50，38，16，82，110，13，64，依次取出序列中的数，构造一棵二叉排序树50388213131106416 （2）利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找15，经多少次元素间的比较可知道查找失败(1)（2）三次；四次1设一组记录的关键字序列为（49，83，59，41，43，47），采用堆排序算法完成以下操作：（要求小根堆，并画出中间过程）（1）以二叉树描述6个元素的初始堆（2）以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆495983414347834741435949498341434783435949414347834959414759（1）594741498343474183594349434741598349（2）4741438349595947414383492一组记录的关键字序列为（46，79，56，38，40，84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。(1)初始序列 46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，8456793840844684793840465665679384046793840848456463设有序表为（13，19，25，36，48，51，63，84，91，116，135，200），元素的下标依次为1,2,12。 （1）说出有哪几个元素需要经过4次元素间的比较才能成功查到（2）画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）（3）设查找元素5，需要进行多少次元素间的比较才能确定不能查到(1)19，48，84，116，200471285211110639（2）(3)3次4设查找表为(16,15,20,53,64,7), (1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结点)(3)求在等概率条件下,对上述有序表成功查找的平均查找长度.(1)原序列16 15 20 53 64 7 15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 6471520641653（2）(3)平均查找长度=（1*1+2*2+3*3）/6=14/65（1）对给定数列7,16,4,8,20,9,6,18,5，依次取数列中的数据，构造一棵二叉排序树。 (2 )对一个给定的查找值,简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20共要进行多少次元素的比较?468957162018（1）(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。6(1)“一棵二叉树若它的根结点的值大于左