发布时间 : 星期六 文章数据结构习题更新完毕开始阅读
typedef struct node { file://链表结点定义 ElemType data； file://数据
struct node * Link； file://结点后继指针 } ListNode；
（1）已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ A. s->link = p； p->link = s； B. s->link = p->link； p->link = s； C. s->link = p->link； p = s；
D. p->link = s； s->link = p；
（2）非空的循环单链表first的尾结点（由p所指向）满足： A. p->link == NULL； B. p == NULL； C. p->link == first； D. p == first；
14．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可
C．必须是连续的 D．和头结点的存储地址相连续
15．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） A．O（1） B．O（n） C．O（m） D．O（m+n）
16．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 17.下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 18．线性表是具有n个（ ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 19．下面的叙述不正确的是（ ）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
20．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
5
21．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 22．下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 23．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
24．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 25．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 26．循环链表h的尾结点p的特点是（ ）
A．p→next=h B．p→next=h->next C．p=h D．p=h->next 27．完成在双循环链表结点p之后插入s的操作是（ ）
A． p->next=s ; s->priou=p; p->next->priou:=s ; s->next=p->next; B． p->next->priou=s; p->next=s; s->priou=p; s->next:=p->next; C．s->priou=p; s->next:=p->next; p->next=s; p->next->priou=s ; D．s->priou=p; s->next:=p->next; p->next->priou=s ; p->next=s;
28．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点） A．p->llink->rlink=p->llink; p->llink->rlink=p->rlink; dispose(p); B．dispose(p); p->llink->rlink=p->llink; p->llink->rlink=p->rlink; C．p->llink->rlink=p->llink; dispose(p); p->llink->rlink=p->rlink; D．以上A，B，C都不对。
二、填空题
1．向一个长度为n的向量的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动 ________个元素。 2．线性表（a1,a2，……，an）以链接方式存储时，在第i个位置删除一个元素的时间复杂度是____ __。 3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。 4.链表适用于 查找。
6
5.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。 6.在一个链式栈中，若栈顶指针等于NULL则为________。
7.在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。 8.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。
9．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_____。
10. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 11．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
12．在单链表中设置头结点的作用是________。
13．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定值为x的结点后插入一个新结点的时间复杂度为________。
14．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。
15. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s->next=p； s->prior= ________；p->prior=s；________=s；
16.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
17. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 18. 循环单链表的最大优点是：________。
19. 带头结点的双循环链表L中只有一个元素结点的条件是：________ 20. 在单链表L中，指针p所指结点有后继结点的条件是： 21. 带头结点的双循环链表L为空表的条件是：________。
三、判断题
1.顺序存储方式只能用于存储线性结构。
2.顺序表和一维数组一样，都可以按下标随机（或直接）访问。 3.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 4.通常使用两个类来协同表示单链表，即链表的结点类和链表类。
5.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 6.线性表采用顺序存储表示时，必须占用一片连续的存储单元。
7
7.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 8．线性表的逻辑顺序与物理顺序总是一致的。 9．线性表的顺序存储表示优于链式存储表示。
10．线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
四、应用题
1．线性表的顺序存储表示和链式存储表示的特点比较。
2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。
int count ( ListNode * Ha, ElemType x ) { // Ha为不带头结点的单链表的头指针 int n = 0;
while ( Ha->link != NULL )
{ Ha = Ha->link; if ( Ha->data == x ) n++; return n; }
}
五、算法设计题
1．设带表头结点的双向链表的定义为 typedef int ElemType；
typedef struct dnode { file://双向链表结点定义 ElemType data； file://数据
struct dnode * lLink， * rLink； file://结点前驱与后继指针 DblNode；
typedef DblNode * DblList； file://双向链表
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。
2．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 3. 已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
8