判断
1-1
对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 T
1-4
线性表采用链式存储表示时，所有结点之间的存储单元地址可以连续也可以不连续。 T
1-22
将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。 F
1-24
在具有头结点的链式存储结构中，头指针指向链表中的第一个元素结点。 F
1-2
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。 T
1-3
(neuDS)线性表的唯一存储形式是链表。 F
1-6
对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。 F
1-7
在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 F
1-8
若用链表来表示一个线性表，则表中元素的地址一定是连续的。 F
1-18
(neuDS)所谓随机存取，就是通过首地址和元素的位序号值可以在O(1)的时间内找到指定的元素。 T
1-19
(neuDS)在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。 F
1-20
(neuDS)在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行顺序存取。 T
1-21
(neuDS)线性表的长度是指线性表所占用的存储空间的大小。 F
1-23
线性表中每个元素都有一个直接前趋和一个直接后继。 F
1-25
循环链表不是线性表。 F
1-27
下列函数试图求链式存储的线性表的表长，是否正确？F
int Length ( List *PtrL )
{ List *p = PtrL;
int j = 0;
while ( p ) {
p++;
j++;
}
return j;
}
选择
2-15
带头结点的单链表h为空的判定条件是： ( B )
A.h == NULL;
B.h->next == NULL;
C.h->next == h;
D.h != NULL;
2-18
在双向链表存储结构中，删除p所指的结点，相应语句为：( C )
A.p->prior=p->prior->prior; p->prior->next=p;
B.p->next->prior=p; p->next=p->next->next;
C.p->prior->next=p->next; p->next->prior=p->prior;
D.p->next=p->prior->prior; p->prior=p->next->next;
2-20
已知L是带头结点的单链表，则摘除首元结点的语句是（ B ）。
A.L=L->link;
B.L->link=L->link->link;
C.L=L->link->link;
D.L->link = L；
2-25
如果最常用的操作是取第i个结点及前驱，最节省时间的存储方式是（ D ）。
A.单链表
B.双向链表
C.单循环链表
D.顺序表
2-26
阅读下列程序，该算法的功能是（ B ）。
typedef struct node{
ElemType data;
struct node *next;
}LNode;
void fun2(LNode *&h){
LNode *p, *q, *r;
if (h==NULL) return;
p=h;
q=h->next;
while (q!=h )
{
r=q->next;
q->next=p;
p=q;
q=r;
}
h->next=p;
h=p;
}
A.将单链表逆置
B.将单循环链表逆置
C.从头到尾遍历单链表
D.头到尾遍历单循环链表
2-1
数组A[1…5,1…6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为：( C )
A.1120
B.1125
C.1140
D.1145
2-2
在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：( A )
A.访问第i个结点（1≤i≤N）和求第i个结点的直接前驱（2≤i≤N）
B.在第i个结点后插入一个新结点（1≤i≤N）
C.删除第i个结点（1≤i≤N）
D.将N个结点从小到大排序
2-3
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？ ( D )
A.双链表
B.单循环链表
C.带头结点的双循环链表
D.顺序表
2-4
链表不具有的特点是： ( B )
A.插入、删除不需要移动元素
B.方便随机访问任一元素
C.不必事先估计存储空间
D.所需空间与线性长度成正比
2-5
已知表头元素为c的单链表在内存中的存储状态如下表所示：
现将f存放于1014H处，并插入到单链表中，若f在逻辑上位于a和e之间，则a、e、f的“链接地址”依次是：( D )
A.1010H, 1014H, 1004H
B.1010H, 1004H, 1014H
C.1014H, 1010H, 1004H
D.1014H, 1004H, 1010H
2-6
数据结构反映了数据元素之间的结构关系。单链表是一种（ D ）。
A.顺序存储线性表
B.非顺序存储非线性表
C.顺序存储非线性表
D.非顺序存储线性表
2-7
在具有N个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(N)？ ( C )
A.在地址为p的结点之后插入一个结点
B.删除开始结点
C.遍历链表和求链表的第i个结点
D.删除地址为p的结点的后继结点
2-8
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？ ( B )
A.单链表
B.仅有尾指针的单循环链表
C.仅有头指针的单循环链表
D.双链表
2-9
将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？( C )
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
2-10
对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为 ( C )
A.O(1)
B.O(N/2)
C.O(N)
D.O(N2)
2-23
与单链表相比，双链表的优点之一是（ D ）。
A.插入、删除操作更加简单
B.可随机访问
C.可以省略表头指针或表尾指针
D.顺序访问相邻结点更加灵活
2-24
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ C ）。
A.O(1)
B.O(n)
C.O(m)
D.O(m+n)
2-27
单链表的每个结点中包括一个指针next，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中（ C ）是正确的。
A.q=p->next; p->next =q->next;
B.p->next =q->next; q=p->next;
C.q->next =p->next; p->next=q;
D.p->next =q; q-> next=p->next;
2-28
以下说法错误的是 ( C )。
A.对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n）
B.插入、删除操作在顺序表上的实现，平均时间复杂度为O（n）
C.在链表上实现读表元运算的平均时间复杂度为O（1）
D.插入、删除操作在链表上的实现可在O（1）时间内完成
2-29
链表 - 存储密度
链表的存储密度 ▁▁C▁▁ 。
A.大于 1
B.等于 1
C.小于 1
D.不能确定
程序填空题
本题目要求以头插法建立单链表。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
LinkList Create();
void print( LinkList L);
int main()
{
LinkList L = Create();
print(L);
return 0;
}
LinkList Create()
{
LinkList L,s;
ElemType e;
L = (LinkList)malloc(sizeof(LNode));
L->next=NULL;
scanf("%d",&e);
while(e!=-1)
{
s = (LinkList)malloc(sizeof(LNode));
s->data=e;
s->next = L->next;
L->next=s;
scanf("%d",&e);
}
return L;
}
void print(LinkList L)
{
LinkList p;
p=L->next;
while (p)
{
printf("%d ", p->data);
p =p->next;
}
}
输入格式：
输入数据为若干正整数，最后以-1表示结尾（-1不算在序列内，不要处理）。所有数据之间用空格分隔。
输入样例：
1 2 3 4 5 6 7 8 9 -1
输出样例：
9 8 7 6 5 4 3 2 1
5-2
已知单链表LA和LB的元素按值非递减排列 归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列
#include<iostream>
using namespace std;
#define ERROR 0
typedef struct LNode
{
int data;
struct LNode *next;
} LNode, *LinkList;
void InitList_L(LinkList &L)
{
L = new LNode;
L->next = NULL;
}
void input(LinkList &L, int n)
{
int i=0;
LNode *p, *r;
r = L;
while (i<n) {
p = new LNode;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
i++;
}
}
void output(LinkList L)
{
int i = 0;
LNode *p;
p = L->next;
while (p) {
if (i)
cout << ",";
cout << p->data;
p = p->next;
i = 1;
}
}
void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC)
{
LinkList pa, pb, pc;
pa = LA->next;
pb = LB->next;
LC = LA;
pc = LC;
while(pa && pb)
{
if (pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
} else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
delete LB;
}
int main() {
LinkList La, Lb, Lc;
int num_a, num_b;
cin >> num_a >> num_b;
InitList_L(La);
input(La, num_a);
InitList_L(Lb);
input(Lb, num_b);
InitList_L(Lc);
MergeList_L(La, Lb, Lc);
output(Lc);
return 0;
}