设指针 p指向单向链表中的某个结点,指针 s指向一个要插入链表的新结点,现要把 s所指结点插入 p 所指结点之后,某学生采用以下语句: p->next=s; s->next=p->next; 这样做正确吗?若正确则回答正确,若不正确则说明应如何改写答: 不对, s ->next = p->next ; p->next =s; 2. (1) 以2,3,4,7,8,9作为叶结点的权,构造一棵哈夫曼树( 要求每个结点的左子树根结点的权小于等于右子树根结点的权),给出相应权重值叶结点的哈夫曼编码。 gf abde c 10 5284 963 10 7 1 (1) 2: 1110 3: 1111 4: 110 7: 00 8: 01 9: 10 (2) 一棵哈夫曼树有 n个叶结点,它一共有多少个结点?简述理由? 答: 2n-1 个,因为非叶结点数比叶结点数少一个。 3.( 1)画出对长度为 10的有序表进行折半查找的判定树(以序号 1, 2,…… 10表示树结点) (2)对上述序列进行折半查找,求等概率条件下,成功查找的平均查找长度答: ASL= ( 1x1+2x2+3x4+4x3 ) /10=29/10 4.一组记录的关键字序列为( 46, 79, 56, 38, 40, 84) (1)利用快速排序的方法,给出以第一个记录为基准得到的一次划分结果(给出逐次交换元素的过程,要求以升序排列) 初始序列 46, 79, 56, 38, 40, 84 40, 79, 56, 38, 40, 84 40, 79, 56, 38, 79, 84 40, 38, 56, 38, 79, 84 40, 38, 56, 56, 79, 84 40, 38, 46, 56, 79, 84 (2)对上述序列用堆排序的方法建立大根堆,要求以二叉树逐次描述建堆过程。 895 9 72 43 18 15 33
全文预览