2.3 考研真题与典型题详解
一、选择题
1下述哪一条是顺序存储结构的优点？（ ）[江苏大学2006研]
A．插入运算方便
B．可方便地用于各种逻辑结构的存储表示
C．存储密度大
D．删除运算方便
【答案】C
【解析】顺序存储结构插入删除操作较麻烦，需要移动大量元素，顺序存储结构也不能用于各种逻辑结构的存储表示，只能表示线性的逻辑结构。
2线性表是具有n个（ ）的有限序列（n＞0）。
A．表元素
B．字符
C．数据元素
D．数据项
E．信息项
【答案】C
【解析】一个线性表是n个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。
3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。[哈尔滨工业大学2001研]
A．顺序表
B．双链表
C．带头结点的双循环链表
D．单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素（随机存取）；线性表采用链表，便于进行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
4设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。[江苏大学2006研]
A．带头结点的双循环链表
B．单循环链表
C．带尾指针的单循环链表
D．单链表
【答案】A
【解析】要快速地在末尾插入元素，需要能立马得到末尾元素结点，故最好是循环链表。要快速地在末尾删除元素，需要立马得到末尾元素结点的前继结点，故最好是双向链表。综上可见为双循环链表。
5静态链表中指针表示的是（ ）。[中南大学2003研]
A．下一元素的地址
B．内存储器的地址
C．下一元素在数组中的位置
D．左链或右链指向的元素的地址
【答案】C
【解析】静态链表是一种特殊的链表，不同于使用指针实现的链表，它采用数组进行数据的存储。静态链表的一般结构为：
struct static_list
{
ElemType data;
int next;
}
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要更改相关元素next的值就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
6在n个结点的线性表的数组实现中，算法的时间复杂性是O（1）的操作是（ ）。[哈尔滨工业大学2003研]
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．以上都不对
【答案】A
【解析】BC两项操作复杂性均为O（n），顺序存储结构具有随机存取的特点，则访问元素时间复杂度为O（1）。
7若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）（1≤i≤n＋1）。
A．O（0）
B．O（1）
C．O（n）
D．O（n2）
【答案】C
【解析】线性表采用顺序存储结构，插入和删除操作的时间复杂度均为O（n），需要移动大量元素。
8对于双向循环链表，在p指针所指的结点之后插入s指针所指结点的操作应为（ ）。[北京工业大学2004研]
A．p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B．p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C．s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D．s->left=p;s->right=p->right;p->right->left=s;p->right=s;
【答案】D
【解析】先建立好s指向p和p的后继结点的链接，即s->left=p;s->right=p->right;然后建立p的后继结点指向s的链接，即p->right->left=s;最后，断开p与后继结点的链接，将p指向s，即p->right=s。
9线性表的顺序存储结构是一种（ ）。[北京理工大学2006研]
A．随机存取的存储结构
B．顺序存取的存储结构
C．索引存取的存储结构
D．Hash存取的存储结构
【答案】A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
二、填空题
1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用______存储结构。[北方交通大学2001研]
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，时间复杂度为O（1），但插入和删除操作不如链式存储结构方便；而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
2在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动______个元素。[北京工商大学2001研]
【答案】n－i＋1
【解析】在第i个元素之前插入元素，需要移动第i个及以后的所有元素，因此需要向右移动n－i＋1个元素。
3在单链表中设置头结点的作用是______。[哈尔滨工业大学2000研]
【答案】保证处理第一个结点和后面的结点的时候设计的算法相同，实现程序的高效性。
4对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。[哈尔滨工业大学2001研]
【答案】O（1）；O（n）
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x的结点。
5在双向循环链表中，向P所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。[中国矿业大学2000研]
【答案】f->next=p->next;f->prior=p;p->next->prior=f;p->next=f;
【解析】考察双向循环链表的插入操作，详见2.1复习笔记图2-4。
6顺序存储结构是通过______表示元素之间的关系的；链式存储结构是通过______表示元素之间的关系的。[北京理工大学2001研]
【答案】物理位置；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
7对于双向链表，在两个结点之间插入一个新结点需修改的指针共______个，单链表为______个。[南京理工大学2000研]
【答案】4；2
【解析】双向链表插入新结点需要修改四个指针，单链表只需修改两个指针。
8在单链表L中，指针P所指结点有后继结点的条件是______。[合肥工业大学2001研]
【答案】P->next!=NULL
【解析】指针所指结点的指针域所指向的元素非空，说明该指针所指结点有后继结点。
三、综合题
1线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
答：（1）应选择链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。
（2）应选择顺序存储结构。顺序表可以随机存取，元素存取的时间复杂度为O（1）。
2说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。[厦门大学2000研]
答：（1）头结点是在链表的第一个结点之前附加一个结点（该结点可以不存储任何信息，也可以存储链表长度等信息），从而使得链表的第一个结点和其他结点在处理问题上的操作保持一致。
头指针是为了标识一个链表而产生的，当链表存在头结点时，则头指针指向头结点，当链表不存在头结点时，头指针指向链表的第一个元素（也可能为空）。
（2）首元结点也就是第一元素结点，它是头结点后边的第一个结点。
3写算法将单链表L1拆成二个链表，其中以L1为头的链表保持原来向后的链接，另一个链表的头为L2，其链接方向与L1相反，L1包含原链表的奇数序号的结点，L2包含原链表的偶数序号的结点。[东华大学2004研]
答：
LinkedList DisUnion(LinkedList* L1,LinkedList* L2)
{
//该算法将L1和L2表拆分成两个链表，其中L2链接方向与L1相反
int i=0;
L2=(LNode*)malloc(sizeof(LNode));
L2->next=null; //空链表
LNode* p=L1->next;
LNode* pre=L1;
while(p)
{
i++;
if(i%2)
{ //奇数序号结点存在L1中
pre->next=p;
pre=p;
p=p->next;
}
else
{ //偶数序号存放在L2中
s=p->next;
p->next=L2->next;
L2->next=p;
p=s;
}
}
}
4在数组A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。
答：
LinkedList create(ElemType A[],int n)
{
//由含有n个数据的数组A生成循环链表，要求链表有序并且无值重复结点
LinkedList h;
h=(LinkedList)malloc(sizeof(LNode)); //申请结点空间
h->next=h; //形成一个空循环链表
LNode* pre,p;
for(i=0;i<n;i++)
{
pre=h;
p=h->next;
while(p!=h&&p->data<A[i])
{ //查找及安排A[i]的插入位置
pre=p;
p=p->next;
}
if(p==h||p->data!=A[i])
{ //去掉重复数据
s=(LinkedList)malloc(sizeof(LNode));
s->data=A[i];
pre->next=s;
s->next=p;
}
} //for
return h;
} //create()