一、选择题

1. 下面说法错误的是  C   。

  （1）算法原地工作的含义是指不需要任何额外的辅助空间。

  （2）在相同的规模n下，复杂度O（n）的撒在时间上总是优于复杂度O(2ⁿ)的算法。

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。

（4）同一个算法，实现语言的级别越高，执行效率越低。

A、（1）     B、（1）（2）     C、（1）（4）     D、（3）

2. 一个递归算法必须包括   B   。

A、递归部分               B、终止条件和递归部分

C、迭代部分               D、终止条件和迭代部分

3. 数据的   C  包括查找、插入、删除、更新、排序等操作类型。

A、存储结构               B、逻辑结构

C、基本运算               D、算法描述

4. 在数据结构中，从逻辑上可以把数据结构分成   C  。

A、动态结构和静态结构    B、紧凑结构和非紧凑结构

C、线性结构和非线性结构  D、内部结构和外部结构

5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的  C   。

A、存储结构               B、存储实现

C、逻辑结构               D、运算实现

6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着   B  。

      A、数据具有同一特点

B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致

C、每个数据元素都一样

D、数据元素所包含的数据项的个数要相等

7. 以下说法正确的是   D  。

A、数据元素是数据的最小单位

B、数据项是数据的基本单位

C、数据结构是带有结构的各数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构

8. 以下说法错误的是   A  。

      A、程序设计的实质是数据处理

B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式

C、运算实现是完成运算功能的算法或这些算法的设计

D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然

9. 下列程序段的时间复杂度为   B  。

         x=n; 

         y=0;

         while (x>=(y+1)*(y+1))

         y=y+1;

A、O(n)    B、O(n^1/2)    C、O(1)    D、O(n²)

10. 下列叙述中有关好的编程风格的正确描述是   C  。

      A、程序中的注释是可有可无的

B、对递归定义的数据结构不要使用递归过程

C、过程应是自封闭的，尽量少使用全程变量

D、多采用一些技巧以提高程序的运行效率

 

二、填空题

1. 一个算法有5个特性： 有穷性 、 确定性 、 可行性、有零个或多个输入、有一个或多个输出。

2. 算法的时间复杂度是指该算法所求解问题  规模（或频度）的函数。

3. 算法的可行性是指每一条  指令都应在有限的时间内完成  。

4、线性结构的特征：逻辑上满足有且仅有一个开始结点和一个终端结点，且其余结点有  且仅有唯一的一个直接前趋和一个直接后继  。

5. 数据的存储结构被分为  顺序 、 链接 、  索引  和  散列 4种。

6. 存储结构是逻辑结构的 存储 实现，其基本目标是建立数据的  机内表示  。

7.数据表示任务是逐步完成的，即数据表示形式的变化过程是：  机外表示   →

    逻辑结构    →   存储结构   。

8. 数据处理任务也是逐步完成的，即转化过程是：  处理要求  →    基本运算  →         →  算法  。

9. 从逻辑关系上讲数据结构主要分为两大类，它们是  线性结构  和  非线性结构  。

10. 数据结构的基本任务是数据结构的  设计  和  实现  。

 

三、给出下列算法的时间复杂度。

    1、Sum(int n)

      {

         int sum=0,i,j;

           for (i=1;i<=n;i++)

              {

                 p=1;

                 for(j=1;j<=i;j++)

                   p=p*j;

                 sum=sum+p;

               }

              return (sum);

        }

       T（n）=O（n²）

   2、j=1;

   while(j<=n)

  {j=j*2;

      }

      O(log₂n)

习题二

一、选择题

1.线性表是具有n个   C   的有限序列。

A、表元素         B、字符       C、数据元素 

D、数据项         E、信息项

2.线性表的静态链表存储结构与顺序存储结构相比优点是  C    。

A、所有的操作算法实现简单   B、便于随机存储

C、便于插入和删除      D、便于利用零散的存储器空间

3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为   C   。

   A、O(log₂n)             B、O(1)

C、O(n)                 D、O(n²)

4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关；

（2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；

（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是   B      。

   A、（1）、（2）      B、（1）     C、（1）、（2）、（3）      D、（2）

5.将图2-6所示的s所指结点加到p所指结点之后，其语句应为   D    。

A、s－＞next=p+1;p－＞next=s;

B、(*p).next=s;(*s).next=(*p).next;

C、s－＞next=p－＞next;p－＞next=s－＞next;

D、s－＞next=p－＞next;p－＞next=s;

p               

 

s

   

 

       

图2-6  插入结点示意

6.在双向链表存储结构中，删除p所指的结点时须修改指针  A    。

A、p－＞next－＞prior=p－＞prior;p－＞prior－＞next=p－＞next;

B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p;

C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior;

D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;

7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是   C   。

A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q;

B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next;

C、q－＞prior=p;q－＞next=p－＞next;

p－＞next－＞prior=q;p－＞next=q;

D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q;

8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是   A   。

A、 n  b.2n－1  c.2n  d.n－1

9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动   B   个元素。

A、n－i  B、n－i+1  C、n－i－1  D、i

10.线性表L=(a₁，a₂,……a_n)，下列说法正确的是  D    。

A、每个元素有有一个直接前驱和一个直接后继

B、线性表中至少有一个元素

C、表中诸元素的排列必须是由小到大或由大到小。

D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

11.对单链表表示法，以下说法错误的是   C   。

A、数据域用于存储线性表的一个数据元素

B、指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

C、所有数据通过指针的链接而组织成单链表

D、NULL称为空指针，它不指向任何结点只起标志作用

12.若指定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是  C    。

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

13.以下说法正确的是   D   。

A、顺序存储方式的优点是存储密度大且插入、删除运算率高

B、链表的每个结点中都恰好包含一个指针

C、线性表的顺序存储结构优于链式存储结构

D、顺序存储结构属于静态结构而链式结构属于动态结构

14.以下说法错误的是   A   。

A、对循环链表来说，从表中任一结点出发都能通过前后移操作扫描整个循环链表

B、对单链表来说，只有从头结点开始才能扫描表中全部结点

C、双链表的特点是找结点的前趋和后继都很容易

D、对双链中来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针中

15.以下说法错误的是   D   。

A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B、序存储的线性表可以随机存取

C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D、线性表的链式存储结构优于顺序存储结构

 

二、判断题

 

1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ 错  ）

2.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（  错   ）

3.顺序存储的线性表可以随机存取。（  对   ）

4.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存储结构。（   错    ）

5.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（  对   ）

6.顺序存储结构属于静态结构，链式结构属于动态结构。（对   ）