第一章 绪论

一、单项选择题

1.数据结构是一门研究非数值计算的程序设计问题中计算机的   ①   以及它们之间的   ②   和运算等的学科。

①A. 数据元素        B. 计算方法            C. 逻辑存储            D. 数据映象

②A. 结构            B. 关系                C. 运算                D. 算法

2.数据结构被形式地定义为（K，R），其中K是   ①   的有限集，R是K上的   ②   有限集。

①A. 算法            B. 数据元素            C. 逻辑结构            D. 数据操作

②A. 操作            B. 存储                C. 映象                D. 关系

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

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

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

4.数据结构在计算机内存中的表示是指      。

A. 数据的存储结构                B. 数据结构

C. 数据的逻辑结构                D. 数据元素之间的关系

5.在数据结构中，与所使用的计算机无关的是数据的      结构。

A. 逻辑                B. 存储                C. 逻辑和存储        D. 物理

6.算法分析的目的是   ①   ，算法分析的两个主要方面是   ②   。

①A. 找出数据结构的合理性            B. 研究算法中的输入和输出的关系

C. 分析算法的效率以求改进            D. 分析算法的易懂性和文档性

②A. 空间复杂度和时间复杂度            B. 正确性和简明性

C. 可读性和文档性                    D. 数据复杂性和程序复杂性

7.计算机算法指的是   ①   ，它必须具备输入、输出和   ②   等5个特性。

①A. 计算方法                        B. 排序方法

C. 解决问题的有限运算序列            D. 调度方法

②A. 可行性、可移植性和可扩充性        B. 可行性、确定性和有穷性

C. 确定性、有穷性和稳定性            D. 易读性、稳定性和安全性

8.在以下叙述中，正确的是      。

A. 线性表的线性存储结构优于链表存储结构            B. 二维数组是其数据元素为线性表的线性表    

C. 栈的操作方式是先进先出                        D. 队列的操作方式是先进后出

9.在决定选取何种存储结构时，一般不考虑      。

A. 各结点的值如何                    B. 结点个数的多少

C. 对数据有哪些运算                    D. 所用编程语言实现这种结构是否方便

10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储      。

A. 数据的处理方法                    B. 数据元素的类型

C. 数据元素之间的关系                D. 数据的存储方法

11.下面说法错误的是      。

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

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

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

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

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

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

A. 数据元素具有同一特点

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

C. 每个数据元素都一样

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

13.以下说法正确的是      。

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

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

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

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

二、填空题

1.一个数据结构在计算机中的      称为存储结构。

2.数据逻辑结构包括   ①   、   ②   和   ③   三种结构，树形结构和图形结构合称为   ④   。

3.在线性结构中，第一个结点   ①   前驱结点，其余每个结点有且只有   ②   个前驱结点；最后一个结点   ③   后继结点，其余每个结点有且只有   ④   个前驱结点。

4.在树形结构中，树根结点没有   ①   结点，其余每个结点有且只有   ②   个前驱结点；叶子结点没有 ③   结点，其余每个结点的后继结点可以有   ④   个。

5.在图形结构中，每个结点的前驱结点数和后继结点数都可以有      个。

6.线性结构中元素之间存在   ①   关系，树形结构中元素之间存在   ②   关系，图形结构中元素之间存在   ③   关系。

7.算法的五个重要特性是      、      、      、输入和输出。

8.算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这个断言是      （正确的或错误的）。

三、简答题

1.设有数据逻辑结构为：

B=(K,R)  K={k1,k2,...,k9}

R={,,,,,,,

,,,}

画出这个逻辑结构的图示，并确定相对关系R，哪些结点是开始结点，哪些结点是终端结点。

2.设有如图1所示的逻辑结构图示，给出它的逻辑结构。

3.有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。

（1）A=(K,R)，其中：K={a,b,c,d,e,f,g,h}  R={r}

   r={,,,,,,}

（2）B=(K,R)，其中：K={a,b,c,d,e,f,g,h}  R={r}

   r={,,,,,,}

（3）C=(K,R)，其中：K={1,2,3,4,5,6}  R={r}

      r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

    这里的圆括号对表示两结点是双向的。

（4）D=(K,R)，其中：K={48,25,,57,82,36,75}  R={r1,r2}

   r1={<25,36>,<36,48>,<48,57>,<57,>,<,75>,<75,82>}

   r2={<48,25>,<48,>,<,57>,<,82>,<25,36>,<82,75>}

4.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？

四、算法设计题

1.下面程序段的时间复杂度是      。

for(i=0;i for(j=0;j  A[i][j]=0;

2.下面程序段的时间复杂度是      。

i=s=0;

while(s i++; s+=i;

}

3.下面程序段的时间复杂度是      。

s=0;

for(i=0;i for(j=0;j  s+=B[i][j];

sum=s;

4.下面程序段的时间复杂度是      。

i=1;

while(i<=n)

 i=i*3;

5.有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){

if(n<=1) return 1;

 else return (n*fact(n-1));

}

6.指出下列个算法的时间复杂度。

（1）prime(int n){ //n为一个正整数

        int i=2;

     while(n%i!=0&&i     if(i*1.0>sqrt(n)) printf(“%d 是一素数\\n”,n);

        else printf(“%d 不是一个素数\\n”,n);

    }

（2）sum1(int n){ //n为一个正整数

        int p=1,sum=0,i;

     for(i=1;i<=n;i++){p*=i; sum+=p;}

        return sum;

    }

（3）sum2(int n){ //n为一个正整数

        int sum=0,i,j;

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

            p=1;

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

            sum+=p;

        }

        return sum;

    }

7.求两个n阶矩阵的乘法C=A×B，其算法如下：

#define MAX 100

void MaxtrixMult(int n,float a[MAX][MAX], float b[MAX][MAX],

                    float c[MAX][MAX]){

    int i,j,k;

    float x;

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

     for(j=1;j<=n;j++){

            x=0;

         for(k=1;k<=n;k++) x+=a[i][k]*b[k][j];

            c[i][j]+=x;

        }

    }

}

分析该算法的时间复杂度。

8.设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。

m=0;

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

for(j=2*i;j<=n;j++)

        m++;

9.给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写一个算法，将数组a和b归并为递增有序数组c[1..m+n]，要求算法的时间复杂度为O(m+n)。

10.求解盘片为n的汉诺塔问题的算法如下，分析其算法时间复杂度。

void hanoi(int n,char x,char y,char z){

    if(n==1) printf(“Move disk %d from %c to %c.\\n”,n,x,z);

    else{

        hanoi(n-1,x,z,y);

        printf(“Move disk %d from %c to %c.\\n”,n,x,z);

        hanoi(n-1,y,x,z);

    }

}

11.分析以下程序段的时间复杂度。

s=0;

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

for(j=0;j<=n;j++)

     for(k=0;k            s++;下载本文