写在开头

还有五天就考试了，这篇文章是复习数据结构与算法的第一篇，主要是为了预习巩固之前学习的内容。先看点选择题。

选择题

第一章 绪论

1.“数据结构”是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（   ）和操作等的学科。

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

2.算法的时间复杂度与(  )有关。

  • A.问题规模 √
  • B程序设计语言
  • C.计算机硬件性能
  • D.编译程序质量

3.计算机算法指的是（   ）。

  • A.计算方法
  • B.排序方法
  • C.解决问题的步骤序列 √
  • D.调度方法

4.计算机算法必须具备（  ）这三个特性

  • A.可执行性、可移植性、可扩充性
  • B.可执行性、确定性、有穷性
  • C.确定性、有穷性、可行性 √
  • D.易读性、稳定性、安全性

5.在数据结构中，从逻辑上可以把数据结构分为(  )两大类。

  • A内部结构和外部结构
  • B.线性结构和非线性结构 √
  • C.紧凑结构和非紧凑结构
  • D.静态结构和动态结构

6.数据的逻辑结构是指(  )的整体。

A数据项之间逻辑关系
B存储结构之间关系
C数据类型之间关系

  • D.数据元素之间逻辑关系 √

7.下面说法错误的是(   )。

  • A.数据项是数据中不可分制的最小单位
  • B.数据元素是数据的基本单位
  • C.数据项可由若干个数据元素构成 √
  • D.数据可由若干个数据元素构成

8.以下数据结构中，哪一个是线性结构(  )。

  • A.有向图 
  • B.二叉树
  • C.线索二叉树
  • D.栈 √

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

  • A.存储结构
  • B.逻辑结构 √
  • C.物理结构
  • D.逻辑结构和物理结构

10在下面的程序段中

for(i=l;i<=n;i++)
for(j=l;j<=n;j++)
         x=x+l;
对x的赋值语句的频度为(   )

  • A.O(2n) 
  • B.O(n)
  • C.O(n^2) √
  • D.2为底n的对数

11.下列语句的时间复杂度为（  ）。

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

  • A.O(1)
  • B.O(n^2) √
  • C.O(n)
  • D.O(n^3)

12.下列语句的时间复杂度为（   ）。

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

  • A.O(1)
  • B.O(n) √
  • C.O(n^2)
  • D.O(n^3)

13.在数据结构中，数据的基本单位是(   )。

  • A.数据项
  • B.数据元素 √
  • C.数据对象
  • D.数据文件

14.算法分析的目的是(   )。

  • A.研究算法中输人和输出的关系
  • B.分析算法的易读性和健壮性
  • C.找出数据结构的合理性
  • D.分析算法的效率以求改进 √

15.数据元素及其关系在计算机存储器内的表示,称为数据的(    )。

  • A.逻辑结构
  • B.存储结构 √
  • C.线性结构
  • D.非线性结构

16.数据的最小单位是（  ）。

  • A.数据项 √
  • B.数据类型
  • C.数据元素
  • D.数据变量

17.计算机算法指的是（  ）,它具有输入、输出、可行性、确定性和有穷性等五个特性。

  • A.计算方法
  • B.解决问题的优先运算序列 √
  • C.排序方法
  • D.调度方法

第二章 线性表

1.采用顺序存储结构存储的线性表，其第一个的地址为100，每个元素的长度为2，则第5个元素的地址为(  )。

  • A.110
  • B.108 √
  • C.100
  • D.120

2.不带头结点的单链表head为空的判定条件是(   )。

  • A.head == NULL √
  • B.head -> next == NULL
  • C.head -> next == head
  • D.head != NULL

3.带头结点的单链表head为空的判定条件是(   )。

  • A.head == NULL
  • B.head -> next == NULL √
  • C.head -> next == head
  • D.head != NULL

4.非空循环单链表head的尾结点(由p指向)满足( )。

  • A.p -> next == NULL
  • B.p == NULL
  • C.p -> next == head √
  • D.p = head

5.在一个单链表中,若p所指结点不是最后结点,在p之后插人s所指结点,则执行( )。

A s-> next = p; p->next = s

  • B.s-> next = p -> next; p -> next = s √
    C s-> next = p -> next; p = s
    D p-> next = s; s -> next = p

6.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需要平均比较( )个结点。

  • A.n
  • B.n/2
  • C.(n-1)/2
  • D.(n+1)/2 √

7.在一个具有n个结点的有序单链表中插人一个新结点并仍然有序的时间复杂度是( )。

  • A.O(1)
  • B.O($n^2$)
  • C.O(n) √
  • D.O(n&log_2&n)

8.在一个长度为n的顺序表中,向第i个元素(1<=i<=n+1)位置插人一个新元素时需要移动( )个元素。

  • A.n-i
  • B.n-i+1 √
  • C.n-i-1
  • D.i

9.线性表若采用链表存储结构时,要求内存中可用存储单元的地址( )。

  • A.必须是连续的
  • B.部分地址必须是连续的
  • C.一定是不连续的
  • D.连续不连续都可以 √

10.链表不具有的特点是（ ）。

  • A.可随机访问任一个元素 √
  • B.不必事先估计存储空间
  • C.插入删除不需要移动元素
  • D.所需空间及线性表长度成正比

11.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（     ）。

  • A.单链表
  • B.双链表
  • C.单循环链表
  • D.顺序表 √

12.对于一个线性表，若既要求能够进行较快地插人和删除，又要求存储结构能够反映出数据元素之间的关系，则应该以(   )。

  • A.顺序方式存储
  • B.链式存储 √
  • C.散列方式存储
  • D.散列方式存储

13.在一个长度为n的顺序表中删除第i个元素（0<=i<=n-1）时，需向前移动（ ）个元素。

  • A.n-i-1 √
  • B.n-i
  • C.n-i+1
  • D.i

14.在一个具有n个结点的单链表的p结点之后插入一个新结点s的算法时间复杂度为（   ）。

  • A.O(n)
  • B.O(1) √
  • C.O(n^2)
  • D.O(n^3)

第三章（栈和队列）

1.一个栈的输人序列为1，2，3，…，n，若输出序列的第1个元素为n，输出第i(1<=i<=n)个元素是(      )。

  • A.不确定
  • B.n-i+1 √
  • C.i
  • D.n-i

2.如果用数组A[1…100]来实现一个大小为100的栈，并且用变量top来指示栈顶，top的初值为0，表示栈空。请问在top为100时，再进行入栈操作，会产生( B  )。

  • A.正常动作
  • B.溢出 √
  • C.下溢
  • D.同步

3.栈可以在(    )中应用。

  • A.递归调用
  • B.子程序调用
  • C.表达式求值
  • D.A，B，C √

4.链式存储的队列，在进行删除运算时，(   )。

  • A.仅修改头指针
  • B.仅修改尾指针
  • C.头、尾指针都要修改
  • D.头、尾指针可能都要修改 √

5.循环队列A[0…m-1]存放其元素值，分别用front和rear表示队头和队尾，则当前队列中的元素个数是(  A  )。

  • A.(rear- front+ m) %m √
  • B.rear- front+ 1
  • C.rear- front- 1
  • D.rear- front

6.将一个递归算法改为对应的非递归算法时，通常需要使用（    ）。

  • A.栈 √
  • B.队列
  • C.循环队列
  • D.优先队列

7.循环队列sq的队满条件为（ ）。

A (sq.rear+1)%maxsize==(sq.front+1)%maxsize

  • B.sq.(rear+1)%maxsize==sq.front √
    C (sq.rear)%maxsize==sq.front+1
    D sq.rear==sq.front