数据结构：练习题二 原创

数据结构：练习题二

练习题二

一、    判断题（每小题1分，共10分）

1．有向图的邻接表和逆邻接表中表结点的个数不一定相等。

2．对链表进行插入和删除操作时不必移动链表中结点。

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

4．若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。

5．希尔排序算法的时间复杂度为O(n²)。

6．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。

7．中序遍历一棵二叉查找树可以得到一个有序的序列。

8．入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。

9．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。

10.   堆是完全二叉树，完全二叉树不一定是堆。

二、    选择题（每小题2分，共20分）

1.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（  ）。

     (A) front->next=s；front=s； (B) s->next=rear；rear=s；

     (C) rear->next=s；rear=s；    (D) s->next=front；front=s；

2．执行一趟快速排序能够得到的序列是（  ）。

     (A) [41，12，34，45，27] 55 [72，63]

     (B) [45，34，12，41] 55 [72，63，27]

     (C) [63，12，34，45，27] 55 [41，72]

     (D) [12，27，45，41] 55 [34，63，72]

3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（  ）。

   (A) head==0                    (B) head->next==0

   (C) head->next==head         (D) head!=0

4．时间复杂度不受数据初始状态影响而恒为O(nlog₂n)的是（  ）。

     (A) 堆排序      (B) 冒泡排序   (C) 希尔排序    (D) 快速排序

5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（  ）。

     (A) 空或只有一个结点      (B) 高度等于其结点数

     (C) 任一结点无左孩子      (D) 任一结点无右孩子

6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（  ）。

     (A) 堆排序      (B) 冒泡排序   (C) 快速排序    (D) 希尔排序

7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（  ）。

     (A) 3         (B) 4             (C) 5          (D) 6

8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（  ）。

     (A) O(n)       (B) O(n²)      (C) O(n³)       (D) O(1og₂n)

9．二路归并排序的时间复杂度为（  ）。

     (A) O(n)       (B) O(n²)             (C) O(nlog₂n)     (D) O(1og₂n)

10.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（  ）次比较。

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

三、    应用题（每小题10分，共50分）

1.         已知顺序栈s，简述func函数的功能，当输入80时，输出结果是多少？

func( )

{  initstack(s);

scanf(“%d”，&n);

while(n)

     { push(s, n%8);  n=n/8; }

while(!Emptystack (s))

{ pop(s,x); printf(“%d”,x); }

}

2.         已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0…6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

           0         1         2         3         4         5         6

    （2）求出在查找每一个元素概率相等情况下的平均查找长度。

3.         下图所示的森林：　　

（1）      求树（a）的先根序列和后根序列；

（2）      将此森林转换为相应的二叉树；

       （a）                 （b）  

4.   设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。

5.   已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};

        E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

   用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

四、 算法题（每小题10分，共20分）

1．请补充完整下列二叉搜索树中查找的递归算法:

   bool Find(BTreeNode* BST,ElemType& item)

{

  if (        （1）         )

     return       （2）      ; //查找失败

  else {

        if (item==BST->data){

               item=BST->data;//查找成功

               return        （3）        ;}

       else if(item<BST->data)

               return  Find(      （4）         ,item);

       else  return Find(         （5）        ,item);

        }

}

2．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

   其中结点的存储结构如下图所示:

结点的结构类型定义如下:

    typedef char datatype;

    typedef struct node

   {

     datatype data;

     struct node *next;

}lklist;

三类不同的元素分别存入到三个不同的链表中，请补充完整下列函数：

void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)

{

}