在一个单链表中,已知q所指结点是p所指结点的直接前趋,若在p,q之间插入s结点,则执行()操作。
A.s—>next=p—>next;p—>next=s;
B.q—>next=s;s—>next=p;
C.p—>next=s—>next;s—>next=p;
D.p—>next=s;s—>next=q;
A.q—>next=s—>next;s—>next=p;
B.s—>next=P;q—>next=s—>next;
C.p—>next=s—>next;s—>next=q;
D.s—>next=q;p—>next=s—>next;
非空的循环单链表head的尾结点(由指针p所指)满足()
A.p—>next=NULL
B.p=NULL
C.p—>next=head
D.p=head
A.p—>next==head
B.p—>next—>Next==head
C.p—>next==NULL
D.p==head
设采用实现如教材48页代码2.21所示的二分查找binSearch()算法版本A,针对独立均匀分布于[0,2n]内的整数目标,在固定的有序向量(1,3,5,...,2n-1)中查找。
a)若将平均的成功和失败查找长度分别记作S和F,试证明:(S+1)•n=F•(n+1);
b)上述结论,是否适用于binSearch()算法的其它版本?为什么?
c)上述结论,是否适用于fibSearch()算法的各个版本?为什么?
d)若待查找的整数按照其它的随机规律分布,以上结论又应如何调整?
a)试证明,在后一类树中,新成员的权重(频率)总是最大;
b)试利用以上性质设计一个算法,在O(n)时间内完成Huffman编码。