1482: 算法基础(哈夫曼树及链表)

1. 由权值为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 (       )。

A．23       B．37       C．44       D．46

2. 下表为某文件中字符的出现频率，采用哈夫曼编码对下列字符编码，则字符序列“bed”的编码以及编码为 “110001001101”的对应的字符序列为（     ）。 (选对应的答案)

   A.100010101 bee      B.  10010100 face      C.  10001101 add      D.  10011000 bace

3. 判别以下叙述，其中不正确的是（     ）。

   A. 哈夫曼算法以自底向上的方式构造最优二叉树。

   B. 哈夫曼树的构造算法是一个贪心算法。

   C. 哈夫曼树中结点个数一定是奇数。

   D.哈夫曼树是二叉树，因而存在度为 1 的结点。

4. 带头结点的单链表L为空的判断条件是(       )。

  A. L==NULL                      B. L->next==NULL    

  C. L->next==L                   D. L!=NULL

5. 在一个单链表中 若q所指结点是p所指结点的前驱结点 若在q与p之间插入一个s所指的结点 则执行(      )。

   A.  s→link=p→link; p→link=s;          B.  p→link=s; s→link=q;

   C.  p→link=s→link; s→link=p;          D.  q →link=s; s→link =p;

6. 非空的头结点为head的循环单链表的尾结点（由p所指向）满足 (   ) 。

  A．p－＞next ＝＝ NULL    B．p ＝＝ NULL

  C．p－＞next ＝＝head        D．p ＝＝ head

7. 非空的头结点为head的循环单链表的尾结点（由p所指向）满足 (   ) 。

  A．p－＞next ＝＝ NULL    B．p ＝＝ NULL

  C．p－＞next ＝＝head        D．p ＝＝ head

8. 有以下结构体说明和变量定义 如右图如示，指针pqr分别指向一个链表中连续的三个结点。

struct node {

int data;

struct node *next;

} *p*q*r;

现要将q和r所指结点的先后位置交换，同时保持链表的连续，以下程序段中错误的是(        )。

   A. q->next=r->next; p->next=r; r->next=q;          

   B. p->next=r; q->next=r->next; r->next=q;

   C. q->next=r->next; r->next=q; p->next=r;

   D. r->next=q; q->next=r->next; p->next=r;