数据结构：练习题一 原创

数据结构：练习题一

练习题一

一、    判断题

1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

2．当向二叉查找树中插入一个结点，则该结点一定成为叶子结点。

3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log₂n)。

4．完全二叉树中的叶子结点只可能在最后两层中出现。

5．哈夫曼树中没有度数为1的结点。

6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。

7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

8．由树转化成二叉树，该二叉树的右子树不一定为空。

9．线性表中的所有元素都有一个前驱元素和后继元素。

10.带权无向图的最小生成树是唯一的。

二、    单项选择题

1．数据的最小单位是（  ）。

     (A) 数据项      (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（   ）。

     (A) 40，50，20，95      (B) 15，40，60，20

     (C) 15，20，40，45       (D) 45，40，15，20

3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（   ）。

    (A) 15，25，35，50，20，40，80，85，36，70

    (B) 15，25，35，50，80，20，85，40，70，36

    (C) 15，25，35，50，80，85，20，36，40，70

    (D) 15，25，35，50，80，20，36，40，70，85

4．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是___。

    (A) 3 1 2        (B) 2 3 1        (C) 1 2 3        (D) 3 2 1

5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（  ）。

     (A) O(log₂n)    (B) O(1)    (C) O(n²)    (D) O(n)

6．设一棵m叉树中度数为0的结点数为N₀，度数为1的结点数为N_l，……，度数为m的结点数为N_m，则N₀=（  ）。

     (A) N_l+N₂+……+N_m                  (B) l+N₂+2N₃+3N₄+……+(m-1)N_m

     (C) N₂+2N₃+3N₄+……+(m-1)N_m   (D) 2N_l+3N₂+……+(m+1)N_m

7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（  ）次。

     (A) 25          (B) 10           (C) 7              (D) 1

8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（  ）。

     (A) abedfc     (B) acfebd      (C) aebdfc           (D) aedfcb

9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（  ）。

     (A) n-i         (B) n-1-i        (C) n+1-i             (D) 不能确定

10.设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（  ）。

     (A) 40，42，45，55，80，83        (B) 42，40，45，80，85，88

     (C) 42，40，45，55，80，85         (D) 42，40，45，85，55，80

三、    应用题

1.          假设某个不设头指针的无头结点单向循环链表的长度大于1，s为指向链表中某个结点的指针。算法f42的功能是，删除并返回链表中指针s所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。

  typedef struct node {

    DataType data；

      struct node  *next；

  }*LinkList；

  DataType f42(LinkList s) {

    LinkList pre，p；

    DataType e；

    pre=s；    ’

    p=s->next；

    while(    (1)    ){

pre=p;

____________(2)             ;

}

pre ->next=      (3)      ;

e=p->data;

free(p);

return e;

}

2.          设散列表的地址范围是[ 0..9 ]，散列函数为H（key）=（key² +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

3.          已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

4.          无向图G的邻接矩阵如下图所示，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。

5.          已知数据六个字母及在通信中出现频率如下表：

     把这些字母和频率作为叶子结点及权值，完成如下工作：

（1）       画出对应的Huffman树。

（2）       计算带权路径长度WPL。

（3）       求A、B、C、D、E、F的Huffman编码。

四、    算法题

1.    下面程序段的功能是使用递归的方法建立二叉链树的算法，请在下划线处填上正确的内容。

typedef struct node

{

       int data;

       struct node  *lchild;

               （1）            ；

}bitree;

void Createbitree(bitree *bt)

{

        scanf(“%c”,&ch);

        if(ch=='#')            （2）            ;

        else

          {

             bt=(bitree*)          （3）        ;

             bt->data=ch;

                       （4）                  ;

                       （5）                  ；

                        }

}

2.    编写完整的算法，原地逆置顺序表L 中的元素，顺序表的类型声明和算法的原型如下：                        

            typedef struct

            {     //  顺序表的类型声明

                   ElemType *elem;   //  存储空间基址

                   int length;                     //  顺序表当前长度

                   int listsize;                    //  当前分配的存储容量

            } SqList;

            void Reverse(SqList &L);             //  逆置函数原型