绪论

选择题

  1. 数据对象：具有相同性质的数据成员（数据元素）的集合，是数据的一个子集。

  2. 数据元素是数据的基本单位,其中数据元素可以由类型互不相同的数据项构成。

  3. 数据项是数据的最小单位。

  4. 数据元素相互之间的关系称为结构（Structure）。

  5. 计算算法的时间复杂度是属于一种事前分析估算的方法。

  6. 算法分析的目的是分析算法的效率以求改进。

  7. 算法的时间复杂度是与指执行时间成正比，例如:时间复杂度为O(n)表示算法的执行时间和n成正比。

  8. 下列数据结构不是多型数据类型的是（）

    A.堆

    B.栈

    C.字符串

    D.有向图

    题解: 多型就是数据元素的类型不确定，字符串的每个元素始终都是字符(char)，而不会是别的类型。

判断题

  1. 哈夫曼树和平衡二叉树都是数据的逻辑结构。
  2. 算法可以没有输入，但是必须有输出：一个算法有0个或多个输入 有一个或多个输出。
  3. 数据元素可以由数据类型互不相同的数据项构成。

线性表

选择题

1.(多选）在下列叙述中，（ABD）是错误的。

1
2
3
4
A.线性表的逻辑顺序与物理顺序总是一致的                          //链表的逻辑顺序和物理顺序是不一致的
B.二叉树的顺序存储结构比链式存储结构节省存储空问                 //链式存储相对于顺序存储更加节省空间
C.二叉树的度小于等于2
D.每种数据结构都具有两种基本运算（操作）：插人、删除元素（结点)    //通常都具有这两个操作，不是都具有

2.若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（A）存储方法最节省时间

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

解析：从本题目中的取第i个元素可以发现只有顺序表最节省时间。

3.若长度为n的线性表采用顺序存储结构，在其第i个位置之前插入一个新元素的算法的移动结点的平均次数为（B）

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

解析：因为需要移动的元素是(n(n+1))/2个，而此时插入一个元素的话，总的元素个数是n+1个，算法的移动结点的平均次数为(n(n+1))/（2*(n+1))，即是 n/2次。

4.在一个单链表中，已知指针p指向其中的某个结点，若该节点之前插入一个由指针s指向的节点，则需指行（D）?????

1
2
3
4
A.s->next=p->next=s;p->next=s;
B.p->next=s;s->next=p;   
C.r=p->next;p->next=s;s->next=r;
D.仅靠已知条件无法实现。

判断题

1.集合与线性表的区别在于是否按关键字排序(错)

1
2
3
线性表可以是有序的，也可以是无序的
集合与线性表的区别是是否允许元素重复
集合不允许元素重复，线性表允许元素重复

2.线性表中的所有数据类型必须相同

3.带头结点的单循环链表中，任一结点的后继结点的指针域均不空。

填空题

1.循环单链表的最大优点是：从任何一个元素出发，均可以访问到链表中的任何一个元素。

2.顺序存储结构是通过结点的物理顺序上相邻表示元素之间的关系的，链式存储结构是通过结点的指针来表示元素之间的关系的。

3.设单链表的结点的结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向单链表中data为y的结点，若将结点y插入结点x之后，则需要执行以下语句：

1
2
py->next=px->next;
px->next=py;