数据结构习题二线性表

第2章线性表班级学号__________-姓名一、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

前一半正确，但后一半说法错误，那是链式存储的优点。

顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（×）7. 线性表在物理存储空间中也一定是连续的。

线性表有两种存储方式，顺序存储和链式存储。

后者不要求连续存放。

（×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

（×）9. 顺序存储方式只能用于存储线性结构。

顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。

（后一节介绍）（×）10. 线性表的逻辑顺序与存储顺序总是一致的。

理由同7。

链式存储就无需一致。

Ai
B n-i-1
C n-i
D n-i+1
单选题 1分
17. 要在一个顺序表 {a1,……,an}中第i个数据元素 ai(1≤i≤n)前插入一个数据元 素,需要移动( )个数据元素。
Ai
B n-i-1
C n-i
D n-i+1
单选题 1分
18. 在n个结点的顺序表中,算法 的时间复杂度是O(1)的操作是:
正常使用主观题需2.0以上版本雨课堂
单选题 1分
10. 对于一个头指针为head的 带头结点的单链表,判定该表 为空表的条件是( )
A head==NULL B head→next==NULL C head→next==head D head!=NULL
单选题 1分
11. 在一个单链表中,已知p的 后继是q,即p-〉next=q,若在 p,q之间插入s结点,则执行( ) 操作
单选题 1分
26.线性表( a1,a2,…,an)以链 接方式存储时,访问第i位置 元素的时间复杂性为( )
A O(i) B O(1) C O(n) D O(i-1)
单选题 1分
27. 链接存储的存储结构所占 存储空间:
分两部分,一部分存放结点值,另一 A 部分存放表示结点间关系的指针
B 只有一部分,存放结点值
C
只有一部分,存储表示结 点间关系的指针
分两部分,一部分存放结点值, D 另一部分存放结点所占单元数
单选题 1分
28.循环单链表头指针为head, 尾指针为rear,则下列条件成 立的是( )
A rear->next= =head
B
rear->next->next= =head

A．找不到
B．查找时间复杂度为O（1）
C．查找时间复杂度为O（n）
D．查找结点的次数约
为n
（14）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目
为（ ）。
A．n
B．(n-1)/2
C． n/2
D．(n+1)
/2
（15）在下列链表中不能从当前结点出发访问到其余各结点的是（
（11）L是线性表，已知LengthList（L）的值是5，经DelList（L，2）运算后，
LengthList（L）的值是（ ）。
A．2
B．3
C．4
D．5
（12）单链表的示意图如下：
L
ABCDΛ
指向链表Q结点的前趋的指针是（
）。
A．L
B．P
C．Q
D．R
（13）设p为指向单循环链表上某结点的指针，则*p的直接前驱（ ）。
结点。
（12） 在一个长度为n的顺序表中删除第i个元素，要移动
个元
素。
（13） 在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 个
元素。
（14） 在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储
地址存放在
结点的指针域中。
（15） 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度
）。
A．双向链表
B．单循环链表 C．单链表
D．双向循
环链表
（16）在顺序表中，只要知道（
），就可以求出任一结点的存储地址。
A．基地址
B．结点大小
C． 向量大小
D．基地址和结点大小
（17）在双链表中做插入运算的时间复杂度为（ ）。

2. 指针 P 指向不带头结点的线性链表 L 的首元素的条件是（ ）。
A.P= =L
C.P-﹥next==L
B.L-﹥Next==P
D.P-﹥next==NULL
3. 指针 p 指向带头结点的单循环链表 L 的首元素的条件是（ ）。
A.P= =L
C.P-﹥next==L
B.L-﹥Next==P
D.P-﹥next==NULL
网络工程 2011 级 1 班、计算机科学与技术 2011 级 2 班《算法与数据结构》课后习题（第 2 章）
2011 级 计科 (网工)
题号
得分
一
【课后习题】第 2 章 线性表
班 学号：
一、判断题（如果正确，在题号前打“”，否则打“”。每题 2 分，共 10 分)
二
( ) 1. 线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。 ( ) 2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 ( ) 3. 如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。 ( ) 4. 线性表的逻辑顺序与物理顺序总是一致的。 ( ) 5. 线性表的长度是指它所占存储空间的大小。
二、填空题（每空 1.5 分，共 21 分)
1. 从逻辑结构看，线性表是典型的
2. 在一个长度为 n 的向量中在第 i（1≤i≤n+1）个元素之前插入一个元素时，需向后移动
个元素，算法的时间复杂度为
3. 在一个长度为 n 的向量中删除第 i（1≤i≤n）个元素时，需向前移动
算法的时间复杂度为
。
。
4. 若长度为 n 的线性表采用链式存储结构，在其第 i 个结点前插入一个新的元素的算法的

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;（C）s->next=p->next;p=s; （D）p->next=s;s->next=p;参考答案：B5.在一个单链表中，若删除p所指结点的后续结点，则执行（）（A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next;（C）p->next=p->next; （D）p =p->next->next;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5. 链表不具有的特点是（）A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比6. 下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关7. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n2)8. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 9．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）A．O（i） B．O（1） C．O（n） D．O（i-1）10．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

数据结构练习第二章线性表一、选择题1. 下面关于线性表的叙述错误的是（）。

A.线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)；B. q=p->next；q->data=p->data；p->next=q->next；free(q)；C. q=p->next；p->next=q->next；free(q)；D. q=p->next；p->data=q->data；free(q)；3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

n) C. O(1) D. O(n2)A. O(n)B. O(nlog24．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。

A. O(logn) B. O(1) C. O(n2) D. O(n)25．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。

A. head==0B.head->next==0C. head->next==headD.head!=06．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。

A. head==0B. head->next==0C. head->next==headD. head!=07．建立一个长度为n的有序单链表的时间复杂度为（）A. O(n)B. O(1)C. O(n2)D. O(logn)28．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。

数据结构--线性表习题及答案第⼆章线性表⼀、选择题1、若长度为n的线性表采⽤顺序存储结构，在其第i个位置插⼊⼀个新元素算法的时间复杂度（）。

A. O(log2n)B.O(1)C. O(n)D.O(n2)2、若⼀个线性表中最常⽤的操作是取第i个元素和找第i个元素的前趋元素，则采⽤（）存储⽅式最节省时间。

A. 顺序表B. 单链表C. 双链表D. 单循环链表3、具有线性结构的数据结构是（）。

A. 图B. 树C. ⼴义表D.栈4、在⼀个长度为n的顺序表中，在第i个元素之前插⼊⼀个新元素时，需向后移动（）个元素。

A. n-iB. n-i+1C. n-i-1D. i5、⾮空的循环单链表head的尾结点p满⾜（）。

A. p->next==headB. p->next==NULLC. p==NULLD. p==head6、链表不具有的特点是（）。

A. 可随机访问任⼀元素B. 插⼊删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正⽐7、在双向循环链表中，在p指针所指的结点后插⼊⼀个指针q所指向的新结点，修改指针的操作是（）。

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;8、线性表采⽤链式存储时，结点的存储地址（）。

A. 必须是连续的B. 必须是不连续的C. 连续与否均可D. 和头结点的存储地址相连续9、在⼀个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。

第2章线性表一、回答题1. 线性表的两种存储结构各有哪些优缺点？2. 对于线性表的两种存储结构，如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应该选用哪种存储结构，为什么？3. 对于线性表的两种存储结构，如果线性表的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度存取线性表中的元素，那么应该选用哪种存储结构？试说明理由。

二、填空题1. 已知L是无头结点的单链表，且p结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选出合适的语句序列：(1) 在p结点之后插入s结点：(2) 在p结点之前插入s结点：(3) 在单链表L首插入s结点：(4) 在单链表L后插入s结点：提供的语句：①p->next = s;② p ->next = p ->next ->next; ③ p ->next = s ->next; ④ s ->next = p ->next; ⑤ s ->next = L; ⑥ s ->next = p; ⑦ s ->next = NULL; ⑧ q = p;⑨ while ( p ->next ! = q ) p = p ->next ; ⑩ while ( p ->next ! = NULL ) p = p ->next ; p = q; p = L; L = s; L = p;2. 已知p 结点是某双向链表的中间结点，试从下列提供的语句中选出合适的语句序列。

(1) 在p 结点之后插入s 结点： (2) 在p 结点之前插入s 结点： (3) 删除p 结点的直接后继结点： (4) 删除p 结点的直接前驱结点：提供的语句：① p ->next = p ->next ->next; ② p ->prior = p ->prior ->prior; ③ p ->next = s; ④ p ->prior = s;11 12 13 14⑤ s ->next = p; ⑥ s ->prior = p; ⑦ s ->next = p ->next; ⑧ s ->prior = p ->prior; ⑨ p ->prior ->next = p ->next; ⑩ p ->prior ->next = p; p ->next ->prior = p; p ->next ->prior = s; p ->prior ->next = s; p ->next ->prior = p ->prior; q = p ->next; q = p ->prior; delete p; delete q;3. 在顺序表中插入或删除一个数据元素，需要平均移动个元素，具体移动的元素个数与有关。

第二章线性表一、选择题1.线性表是（）A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.一维数组与线性表的特征是（）。

A．前者长度固定，后者长度可变B．两者长度均固定C．后者长度固定，前者长度可变D．两者长度均可变3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ).A．当前结点所在地址域B．指针域C．空指针域D．空闲域4.用链表表示线性表的优点是（）。

A．便于随机存取B．便于进行插入和删除操作C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。

A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点6.下面关于线性表的叙述中，错误的是（）。

A．线性表采用顺序存储必须占用一片连续的存储单元B．线性表采用顺序存储便于进行插入和删除操作C．线性表采用链式存储不必占用一片连续的存储单元D．线性表采用链式存储便于进行插入和删除操作7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。

现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。

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 ;8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（）。

A．链表B．单链表C．双向循环链表D．双向链表9.单链表的存储密度（）。

1.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构
2.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是
（A）110 （B）108
（C）100
（D）120
3.在 n 个结点的顺序表中，算法的时间复杂度是 O（1）的操作是： (A)访问第 i 个结点（1≤i≤n）和求第 i 个结点的直接前驱（2≤i≤n） (B)在第 i 个结点后插入一个新结点（1≤i≤n） (C)删除第 i 个结点（1≤i≤n） (D)将 n 个结点从小到大排序
五、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表
L={23，17，47，05，31}，若它以链接方式存储在下列 100～119 号地址空间中，每个结点
由数据（占 2 个字节）和指针（占 2 个字节）组成，如下所示：
05 U 17 X 23 V 31 Y 47 Z
^
^
100
情况下适用于使用链式结构实现。
（Ａ）需经常修改Ｌ中的结点值
（Ｂ）需不断对Ｌ进行删除插入
（Ｃ）Ｌ中含有大量的结点
（Ｄ）Ｌ中结点结构复杂
9.单链表的存储密度
（Ａ）大于 1； （Ｂ）等于 1； （Ｃ）小于 1； （Ｄ）不能确定
10.设 a1、a2、a3 为 3 个结点，整数 P0，3，4 代表地址，则如下的链式存储结构称为
。
二、判断题
（ ）1. 链表的每个结点中都恰好包含一个指针。
（ ）2. 链表的物理存储结构具有同链表一样的顺序。
（ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的

数据结构第二章习题第2章线性表一、单项选择题1．线性表就是具备n个_________的非常有限序列。

a．表元素b．字符c．数据元素d．数据项2．线性表是_________。

a．一个非常有限序列，可以为空b．一个非常有限序列，不可以为空c．一个无穷序列，可以为空d．一个无穷序列，不可以为空3．线性表使用链表存储时，其地址_________。

a．必须是连续的b．一定是不连续的c．部分地址必须是连续的d．连续与否均可以4．链表不具备的特点是_________。

a．可以随机出访任一结点b．填入删掉不须要移动元素c．不必事先估算存储空间d．所须要空间与其长度成正比5．设立线性表存有n个元素，以下操作方式中，_________在顺序单上同时实现比在链表上同时实现效率更高。

a．输出第i(1≤i≤n)个元素值b．互换第1个元素与第2个元素的值c．顺序输入这n个元素的值d．输出与给定值x相等的元素在线性表中的序号6．设立线性表中存有2n个元素，以下操作方式中，_________在单链单上同时实现Obrero在顺序单上同时实现效率更高。

a．删掉选定的元素b．在最后一个元素的后面插入一个新元素c．顺序输出前k个元素d．互换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7．如果最常用的操作是取第i个结点及其前驱，则采用_________存储方式最节省时间。

a．单链表中b．双链表中c．单循环链表d．顺序表8．与单链表相比，双链表的优点之一是_________。

a．填入和删掉操作方式更直观b．可以展开随机出访c．可以省略字段指针或表尾指针d．出访前后相连结点更有效率9．率先垂范结点的单链表中l为觑的认定条件就是_________。

a．l==nullb．l->next==nullc．l->next==ld．l!=null10．在一个具备n个结点的有序单链表填入一个崭新结点并仍然维持有序的时间复杂度就是_________。

数据结构部分习题一、问答题1、简述下列术语：线性表，顺序表，链表。

2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?二、单选题1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是( )。

A. 查找单链表中第i个结点B. 在p结点之后插入一个结点C. 删除表中第一个结点D. 删除p结点的直接后继结点2、在下列链表中不能从当前结点出发访问到其余各结点的是( )。

A. 单链表B. 单循环链表C. 双向链表D. 双向循环链表3、线性表采用顺序存储时，其地址( )A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续与否均可以4、线性表采用链式存储结构时，其地址( )A．必须是连续的B．部分地址必须是连续的C.一定是不连续的D．连续与否均可以5、在长度为n的顺序表的第i个数据元素(1≤i≤n)之前插入一个数据元素,元素的移动次数为( )。

A. n-i+1B. n-iC. iD. i-16、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。

A. 顺序表B. 用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表7、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A．单链表B．双向链表C．单循环链表D．循环链表8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行（）。

A．p = q->next ; p->next = q->next;B．p = q->next ; q->next = p;C．p = q->next ; q->next = p->next;D．q->next = q->next->next; q->next = q;9、9、链表不具有的特点是（）。

第二章线性表2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

并说明头指针和头结点的作用。

答：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。

如链表H，链表L等，表示链表中第一个结点的地址存放在H、L中。

头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。

当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。

开始结点指第一个元素结点。

头指针的作用是用来惟一标识一个单链表。

头结点的作用有两个：一是使得对空表和非空表的处理得以统一。

二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

2.2填空题1、在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（表长和该元素在表中的位置）有关。

2、顺序表中逻辑上相邻的元素的物理位置（必定）相邻。

单链表中逻辑上相邻的元素的物理位置（不一定）相邻。

3、在单链表中，除了首元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。

4、在单链表中设置头结点的作用是（插入和删除元素不必进行特殊处理）。

2.3何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。

并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

2.10 Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素{if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;return OK;}//DeleteK2.11设顺序表中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置上，以保持该表的有序性。

{ p=head;j=0;
while(________________)
{ p=p->next; j++; }
if(i==j) return(p);
else return(NULL);
}
26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。
int locate_lklist(lklist head,datatype x)
if(________)return(i);
else return(0);
}
15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为________。求表长和读表元算法的时间复杂性为________。
16.在顺序表上，求表长运算LENGTH（L）可通过输出________实现，读表元运算
36．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。
37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为______格式，另一种是每个单元存放多个字符，称为______格式。
2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。
3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.
① 数据元素 ② 数据项 ③ 数据 ④ 数据结构
4．顺序表是线性表的 （ ）
①链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构

1、与单链表相比，双链表的优点之一是（）。

A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.访问前后相邻节点更方便正确答案：D解析：在双链表中可以访问任一节点的前后相邻节点，而单链表中只能访问任一节点的下一个节点。

2、带头节点的双链表L为空表时应满足（）。

A.L==NULLB.L->prior==L->nextC.L->prior==NULLD.L->next==NULL正确答案：D3、在长度为n（n≥1）的双链表中插入一个节点（非尾节点）要修改（）个指针域。

A.1B.2C.3D.4正确答案：D解析：需要修改插入节点的prior、next域，前驱节点的next域和后继节点的prior域。

4、对于长度为n（n≥1）的双链表L，在p所指节点之前插入一个新节点的算法的时间复杂度为（）。

A. O(1)B. O(n)C. O(n2)D. O(nlog2n)正确答案：A解析：设新节点指针为q，操作是：p->prior->next=p; q->prior=p->prior; p->prior=q; q->next=p;5、在长度为n（n≥1）的双链表中删除一个节点（非尾节点）要修改（）个指针域。

A.1B.2C.3D.4正确答案：B解析：需要修改前驱节点的next域和后继节点的prior域。

6、与非循环单链表相比，循环单链表的主要优点是（）。

A.不再需要头指针B.已知某个节点的位置后，能够容易找到它的前驱节点C.在进行插入、删除操作时，能更好地保证链表不断开D.从表中任意节点出发都能扫描到整个链表正确答案：D解析：循环单链表中可以循环扫描，因此从表中任意节点出发都能扫描到整个链表。

7、设有带头节点的循环单链表L，当这种链表成为空链表时，有（）。

A.表头节点指针域next为空B.L的值为NULLC.表头节点的指针域next与L的值相等D.表头节点的指针域next与L的地址相等正确答案：C解析：带头节点的循环单链表L成为空链表时满足L->next==L，即表头节点*L的指针域next与L的值相等，而不是表头节点*L的指针域next与L的地址相等。

数据结构实验二线性表数据结构实验二线性表1. 实验目的1.1 理解线性表的概念和特性1.2 学习线性表的顺序存储结构和链式存储结构1.3 掌握线性表的基本操作：初始化、插入、删除、查找、修改、遍历等1.4 熟悉线性表的应用场景2. 实验内容2.1 线性表的顺序存储结构实现2.1.1 定义线性表结构体2.1.2 初始化线性表2.1.3 插入元素2.1.4 删除元素2.1.5 查找元素2.1.6 修改元素2.1.7 遍历线性表2.2 线性表的链式存储结构实现2.2.1 定义链表节点结构体2.2.2 初始化链表2.2.3 插入元素2.2.4 删除元素2.2.5 查找元素2.2.6 修改元素2.2.7 遍历链表3. 实验步骤3.1 实现顺序存储结构的线性表3.2 实现链式存储结构的线性表3.3 编写测试程序，验证线性表的各种操作是否正确3.4 进行性能测试，比较两种存储结构的效率差异4. 实验结果与分析4.1 执行测试程序，检查线性表的操作结果是否正确4.2 对比顺序存储结构和链式存储结构的性能差异4.3 分析线性表的应用场景，总结线性表的优缺点5. 实验总结5.1 总结线性表的定义和基本操作5.2 回顾实验中遇到的问题和解决方法5.3 提出对线性表实现的改进方向和思考附件：请参考附件中的源代码和实验报告模板。

法律名词及注释：1. 版权：指对某一作品享有的法律上的权利，包括复制权、发行权、改编权等。

2. 法律责任：指违反法律或合同规定所承担的责任。

3. 保密义务：指个人或组织根据法律、法规、合同等规定需要承担的保密责任。

4.知识产权：指人们在社会实践中所创造的智力劳动成果所享有的权利，包括专利权、著作权、商标权等。