数据结构-综合题

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,12。(1) 说出有哪几个元素需要经过4次元素间的比较才能成功查到(2) 画出对上述有序表进行折半查找所对应的判定树(树结点用下标 表示)(3) 设查找元素5,需要进行多少次元素间的比较才能确定不能查到

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

3、ta=1;(2) p_>next=s;s->next= NULL ;free(s)(3) head = head ->next；(4) P1->next= p->next ；p->next=p 1；4. ( 1)设有序列10, 12, 15, 19, 22, 25, 100, 130, 150, 200画出 对上述序列进行折半查找的判定树(以序列中的元素作为树的结点)(2) 为了成功查找到100需要进行多少次元素间的比较？为了查找 9, 经过多少次元素间的比较可知道查找失败？lit3袂5.(1)对给定数列7,16,4,8,20,9,6,18,5，依次取数列中

4、的数据，构造一棵二叉排序树。(2 )对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤， 在上述二叉树中查找元素20共要进行多少次元素的比较？图5(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。6. (1)设有查找表5,14,2,6,18,7,4,16,3,依次取表中数据，构造一棵二 叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述 二叉排序给岀中序遍历的结果。(1)(2)中序遍历中序 2, 3, 4, 5, 6, 7, 14, 16, 181. (1)已知某二叉树的后序遍历序

5、列是debca,中序遍历序列是dbeac,试画出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没 有相等的)，并恰好使该树成为一棵二叉排序树，试给岀a、b、c、d、e的大小关系(3)给岀该树的前序遍历序列1.4. ( 1)给定数列8, 17, 5, 9, 21, 10,数构造一棵二叉排序树(2)对上述二叉树给岀中序遍历得到的序列7, 19, 6，依次取序列中的(2) 5, 6, 7, 8, 9, 10,17, 18, 19, 215. ( 1)利用筛选过程把序列 42, 82, 67, 102, 16, 32, 57, 52建成 堆(小根堆)，画岀相应的完全二叉树(不要求中

6、间过程)(2) d<b<evavc(3) abdec2.( 1)已知某二叉树的先序遍历序列是aecdb中序遍历序列是 eadcb,试画岀该二叉树(2)给岀上述二叉树的后序遍历序列3)若上述二叉树的各个结点的字符分别是1, 2, 3, 4, 5,并恰好使该树成为一棵二叉排序树，试问a、b c、d、e的值各为多少?(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个非叶子结点，则树中共有多少

7、结点。对给定 的一组权重值建立的棵哈夫曼树是否一定唯一3. ( 1)设有一个整数序列40, 28, 6, 72, 100, 3, 54依次取出序列 中的数，构造一棵二叉排序树(2)对上述二叉排序树，在等概率条件下，求成功查找的平均查找长 度(2) ASL= ( 1x1+2x2+3x3+4 ) /7=18/7(2) 2n-1 不一定唯(2)写岀对上述堆对应的完全二叉树进行中序遍历得到的序列1. (1)设head*!和Pi分别是不带头结点的单向链表A的头指针和尾指针，head2和P2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以 head*为头指针的单向循环

8、链表，写岀其中两个关键的赋值语句(不用完整程序，结点的链域为next)(2)单向链表的链域为 next，设指针p指向单向链表中的某个结点， 指针s指向一个要插入链表的新结点，现要把s所指结点插入 p所指结点之后，某学生采用以下语句：p->next=s; s->next=p->next;这样做正确吗？若正确则回答正确，若不正确则说明应如何改写(1) Pi->next= head2； P2->next= headi ；(2) 不对，s->next= p->next ； p->next=s ；2 . ( 1) 一组记录的关键字序列为 45，40, 65

9、, 43，35, 95写出利用 快速排序的方法，以第一个记录为基准得到的一趟划分的结果(要求给岀一趟划分中每次扫描和交换的结果)(2)同样对序列45，40，65, 43，35, 95利用直接插入排序，写 岀逐次插入过程(从第一个元素一直到第六个元素)。45 40 65 43535 40 65 43 35 9535钊卿3 £ 9?35 40 4>H3j55 235 40 43 45 65 9540 45 65 43 35 9540 43 45 65 35 P:35 40 43 45 65 9:3. (1)画岀对长度为10的有序表进行折半查找的判定树(以序号1,2, 10表示树结点)(2)对上述序列进行折半查找，求等概率条件下，成功查找的平均 查找长5. ( 1)利用筛选法，把序列37, 77, 62, 97, 11, 27, 52, 47建成 堆(小根堆)，画出相应的完全二叉树(2)写岀对上述堆所对应的二叉树进行前序遍历得到的序(2) 11, 37, 47, 97, 77, 27, 62, 52 6. ( 1)设有一个整数序列50, 38, 1