【以练促学】（数据结构）1.绪论篇

（持续刷题 持续更新…）

1. 数据结构的三要素：逻辑结构、物理结构、数据运算

 eg. 以下属于逻辑结构的（  ）

A. 顺序表     B. 哈希表     C. 有序表    D. 单链表

// A顺序表表示是按照顺序存储的方式存储，B哈希表使用散列存储，D单链表表明是链式存储。这三个选项都是根据它的物理存储方式命名的，都属于存储结构/物理结构。（有序表指有序的线性表）C有序表可用顺序/链式 存储，只表示逻辑结构

 eg. 以下属于逻辑结构的（  ）

A. 循环队列     B. 链表     C. 哈希表    D. 栈

// 回顾一下存储结构是啥？顺序、链式、索引、散列。A循环队列是顺序存储，B链表是链式存储，C哈希表使用散列存储，D栈是一种抽象数据类型，可用顺序/链式 存储，只表示逻辑结构

2. 在存储数据时，不仅要存储数据元素的值，且要存储数据元素间的关系

eg. 在存储数据时，不仅要存储数据元素的值，而且要存储（  ）

A. 数据的操作方法    B. 数据元素的类型    C. 数据元素之间的关系    D. 数据的存取方法

// 数据元素是数据的基本单位。根据数据元素之间的关系的不同特征，可以分成集合、线性结构、树状结构、图状或者网状结构4类基本结构。在存储数据时，不仅要存储数据元素的值，且要存储数据元素间的关系

3. 链式存储：存储空间可以不连续，存储单元地址必须连续

eg. 链式存储设计时，结点内的存储单元地址（  ）

A. 一定连续    B. 一定不连续    C. 不一定连续    D. 部分连续，部分不连续

// 看清题意，问的是存储单元地址

4. 算法：是对特定问题求解步骤的一种描述

eg. 一个算法应该是（  ）

A. 程序    B. 问题求解步骤的描述    C. 要满足5个基本特性    D. A和C

// 此题网上好像有争议，A程序会有特殊情况（死循环等），建议选B

5.时间复杂度（多动笔计算）

eg. 已知两个长度分别为m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是（  ）
A.O(n)    B.O(m*n)    C.O(min(m,n))    D.O(max(m,n))

// 留个坑，看解析也没看懂

eg. 下列程序段的时间复杂度（  ）

count = 0
for (k=1; k<=n; k*=2)
     for(j=1; j<=n; j++)
          count++;

A. O(log₂n)    B. O(n)    C. O(nlog₂n)    D. O(n²)

// 内层是O(n)，外层是O(log₂n)，嵌套循环相乘为O(nlog₂n) 

eg. 下列函数的时间复杂度（  ）

int func(int n){
     int i=0, sum=0;
     while (sum<n) sum += ++i;
     return i;
}

A. O(logn)    B. O(n^1/2)    C. O(n)   D. O(nlogn) 

// 大不了就穷举，sum是个等差求和sum=0+1+2+…+i，套公式就是sum=i² , 循环次数满足sum<n，O(n^1/2) 

 eg. 以下算法中加下划线的语句的执行次数是（  ）

int m=0, i, j;
for(i=1; i<=n; i++)
     for(j=1; j<=2*i; j++)
          m++;

A. n(n+1)    B. n    C. n+1    D.n²

 // 注意是语句的执行次数，不能一看到代码就以为是求复杂度。穷举找规律：n=1时，执行2次；n=2时，执行2+4次；n=3时，执行2+4+6次；n=4时，执行2+4+6+8次；所以是n(n+1) 

eg. 设n是描述问题规模的非负整数，下列程序段的时间复杂度是（  ）

x=0;
while (n>=(x+1)*(x+1))
x+=1;

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

 // 留个坑，看解析也没看懂

 未完待续…

涉及的后面一点知识点：

① 哈希表：散列存储；

② 栈是一种抽象数据类型；

原文地址：http://www.cnblogs.com/ZWJ-zwj/p/16796473.html