1. 选择
1. 一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（B）。
A. 98? ? ? ? ? ? ?B. 100? ? ? ? ? ? ? ?C. 102? ? ? ? ? ? ?D. 106
2. 线性表的顺序存储结构是一种（A）的存储结构，而链式存储结构是一种（C）的存储结构。
A. 随机存储? ? ? ? ? B. 索引存储? ? ? ? ? C. 顺序存储? ? ? ? ? ? D. 散列存储?
3. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素算法的时间复杂度为（C）。
A. O(logn)? ? ? ? ? ? ?B. O(1)? ? ? ? ? ? ? ?? C. O(n)? ? ? ? ? ? ?D. O(n*n)
4. 线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）。
A. 必须是连续的? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B. 部分地址必须是连续的
C. 一定是不连续的? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D. 连续或不连续都可以?
5. 从表中任一结点出发都能扫描整个表的是（C）。
A. 单链表? ? ? ? B. 顺序表? ? ? ? ? C. 循环链表? ? ? ? D. 静态链表?
6. 线性表是 n 个（C）的有限序列。
A. 表元素? ? ? ? B. 字符? ? ? ? ? ? C. 数据元素? ? ? ? ?D. 数据项
7. 在线性表的下列存储结构中，读取元素花费的时间最少的是（D）。?
A. 单链表? ? ? ? ?B.双链表? ? ? ? ?C. 循环链表? ? ? ? ?D. 顺序表?
8. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（A）。
A. n? ? ? ? ? ? ?B. 2n-1? ? ? ? ? ?C. 2n? ? ? ? ? ? ?D. n-1?
9. 非空循环单链表head的尾结点（由p所指向）满足（C）。
A. p->next==NULL? ? ? ? ? ? ? ? B. p==NULL
C. p->next==head? ? ? ? ? ? ? ? ?D. p==head?
10. 在双向循环链表中，在p指针所指的结点后插入一个指针 q 所指向的新结点，修改指针的操作是（C）。
A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D. q->next=p->next;q->prior=p;p->next=q;p->next=q;?
11. 在一个单链表中，若删除p所指结点的后续节点，则执行（A）。
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->p->next;
C. p=p->next;
D. p=p->next->next;?
12. 将长度为n的单链表连接在长度为m的单链表之后，算法的时间复杂度为（C）。
A. O(1)? ? ? ? ? ? B. O(n)? ? ? ? ? ?C. O(m)? ? ? ? ? ? D. O(m+n)?
13. 在一个具有 n 个结点的有序单链表中插入一个新结点，并继续保持有序的时间复杂度是（B）。
A. O(1)? ? ? ? ? ?B. O(n)? ? ? ? ? C. O(n*n)? ? ? ? ? D. O(nlogn)?
14. 静态链表中，某个元素中的指针（游标）指示的是（C）。
A. 内存地址? ? ? ? ? ? ? ? ? ? ? ? ? ? ? B. 数组下标
C. 下一个元素存放的位置? ? ? ? D. 左右孩子的地址?
15. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）方式最节省运算时间。
A. 单链表? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B. 仅有头指针的循环单链表
C. 双链表? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D. 仅有尾指针的循环单链表?
16. 对于线性表，以下（C）情况应采用链表表示。
A. 需要经常随机存取元素
B. 表中的元素个数不变
C. 需要经常插入和删除元素
D. 表中元素需要占用连续的存储空间?
2. 填空?
1. 在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置决定的；而链式存储结构中，元素之间的逻辑关系是通过链指针决定的。
2. 表长为 n 的顺序存储的线性表，当在任何位置上删除元素的概率相等时，删除一个元素所需移动的元素平均数为(n-1)/2。
3. 若一线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用顺序表存储方式最节省空间。
4. 表长为0的线性表称为空表。?
3. 判断?
1. 线性表采用链式存储时，结点和结点内部的存储空间可以是不连续的。? ? ? ? ? （×）?
2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。? ? ? ? ? ? ? ? ? ? ?（×）?
3. 线性表的逻辑顺序与存储顺序总是一致的。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（×）?
4. 双向链表的特点是找结点的前趋和后继都方便。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （√）?
5. 对单链表来说，只有从头结点开始才能访问表中的所有结点。? ? ? ? ? ? ? ? ? ? ? ? ?（√）?
|