数据结构-综合题

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

1、综合题1.设一组记录的关键字序列为(49,83,59,41,43,47),采用堆排序算法完成以下操作：(要求小根堆，并画出中间过程)(1)以二叉树描述6个元素的初始堆(2)以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆。3.设有序表为(13,19,25,36,48,51,63,84,91,116,135,200),元素的下标依次为1,2,,12o(1)说出有哪几个元素需要经过4次元素间的比较才能成功查到(2)画出对上述有序表进行折半査找所对应的判定树(树结点用下标表示)(3)设查找元素5,需要进行多少次元素间的比较才能确定不能查到(1)164$.S4,116,

2、2002.设有一个不带头结点的单向链表，头指针为head,结点类型为NODE,每个结点包含一个数据域data和一个指针域next,该链表有两个结点，p指向第二个结点(尾结点)，按以下要求写出相应语句(不要求完整程序，(1)、(2)、(3)、(4)是一个连续的过程)。(1)新开辟一个结点，使指针s指向该结点，结点的数据成员data赋值为1(2)把该结点插入链表的尾部，释放指针s的指向(3)删除链表的第一个结点(4)已知pl指向另一个新结点，把它插入到p所指结点和尾结点Z间(1)s=(NODE*)malloc(sizeof(NODE));s->data=1;(2)p->next=s;

3、s->next=NULL；free(s)(3)head=head->next：(4)pr>next=p->next；p->next=pi；4.(1)设有序列｛10,12,15,19,22,25,100,130,150,200｝画出对上述序列进行折半査找的判定树(以序列中的元素作为树的结点)(2)为了成功查找到100需要进行多少次元素间的比较？为了查找9,经过多少次元素间的比较可知道查找失败？5.(1)对给定数列｛7,16,4,&20,9,6,1&5｝,依次取数列中的数据，构造一棵二叉排序树。(2)对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查找元素20

4、共要进行多少次元素的比较？(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。6.(1)设有查找表｛5,14,2,6,18,7,4,16,3｝,依次取表中数据，构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。6(2)中序遍历中序2,3,4,5,6,7,14,16,181.(1)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该

5、树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系(3)给出该树的前序遍历序列4・(1)给定数列｛8,17,5,9,21,10,7,19,6｝,依次取序列中的数构造一棵二叉排序树(2)对上述二叉树给出中序遍历得到的序列(2)5,6,7,8,9,10,17,18,19,215.(1)利用筛选过程把序列｛42,82,67,102,16,32,57,52｝建成堆(小根堆)，画岀相应的完全二叉树(不要求中间过程)(2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列(2)d

6、试画出该二叉树(2)给出上述二叉树的后序遍历序列(3)若上述二叉树的各个结点的字符分别是1,2,3,4,5,并恰好使该树成为一棵二叉排序树，试问冬bxC.d.C的值各为多少？2.(1)(2)edbca(3)e=1,a=2,d=3,c=4,b=5(2)102,52,42,82,16,67,32,576.(1)以给定权重值1,2,12,13,20,25为叶结点，建立一棵哈夫曼树(2)若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一3.(1)设有一个整数序列｛40,28,6,72,100,3,54｝依次取出序列中的数，构造一棵二叉排序树(2

7、)对上述二叉排序树，在等概率条件下，求成功査找的平均査找长度(2)2n-l不一定唯一(2)ASL=(1x1+2x2+3x34-4)/7=18/7(1)(2)1.(1)设headt和pi分别是不带头结点的单向链表A的头指针和尾指针，head,和P2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以head】为头指针的单向循环链表，写出其中两个关键的赋值语句(不用完整程序，结点的链域为next)o(2)单向链表的链域为next,设指针p指向单向链表中