江苏省白蒲高级中学2020—2021学年信息技术竞赛数据结构与算法全套练习（含答案）

绪论

作业1 

一、单项选择题

1．数据结构在计算机中的表示称为数据的（　A　）。

A）存储结构      B）抽象结构               

C）顺序结构      D）逻辑结构

2．对于下面程序段的时间复杂度为（　B　）。

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

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

    x=x+1;

A）O(n)   B）O(n2)   C）O(n*i)                             D）O(n+i)

3．数据结构是（　A　）。

A）相互之间存在一种或多种特定关系的数据元素的集合

B）相互之间存在一种特定关系的数据元素的集合

C）数据元素的集合    D）前面都不正确

4．数据结构可形式地定义为(D,S)，其中S是D上（　C　）的有限集。

A）操作   B）存储映象  C）关系   D）数据元素

5．数据结构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（　B　）。

   A）逻辑结构      B）顺序存储结构

     C）链式存储结构     D）以上都对

二、综合题

1．下面程序段用于求两个n*n矩阵相乘的算法，试求其时间复杂度。

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

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

    c[i][j]=0;

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

      c[i][j]=c[i][j]+a[i][k]*b[k][j];

  }

【解答】

问题规模n，基本操作为乘法“*”，

三层for循环，每层循环n次，基本操作的执行次数为f(n)= ，则时间复杂度T(n)=O(f(n))=O().

2．试编写一算法，实现将输入的三个整数x，y，z按从小到大的顺序排列起来。

【解答】：

线性表

作业2

一、单项选择题

1．在下列序列中，不是线性表的是（　C　）。

A）('a','b','c')   B）('AB','CD')   

C）('a',true,'c')   D）("a","b","c","d")

2．线性链表中各链结点之间的地址（　D　）。

A）必须连续       B）部分地址必须连续

C）不一定连续      D）连续与否无所谓

3．如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则（　D　）存储方式最节省运行时间。

A）单链表       B）带头结点的单链表

C）单循环链表      D）带头结点的双循环链表

4． 在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行动作（　B　）。

A）q->next=p;p->next=q;     B）q->next=p->next;p->next=q

C）q->next=p->next;p=q;    D）p->next=q;q->next=p;

5．线性表的顺序存储结构具有的特点是（  A  ）。

A）可直接随机访问任一元素   B）插入删除不需要移动元素

C）不必事先估计元素个数    D）所需空间与线性表长度成正比

二、综合题

1．设A是一个线性表（al，a2，…,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？

解：

共有n+1个插入位置，若元素插入第m (1≤m≤n+1)个位置，则需要移动n-(m-1)个元素，在等概率的前提下，平均每插入一个元素需要移动的元素个数为(0+1+2+…+n)/(n+1)=n/2.

则：在等概率的前提下，平均每插入一个元素需要移动的元素个数为n/2.

2．在单链表和双向链表中，能否从当前结点出发访问到任一结点？