下载文档原格式
第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（）的有限序列（n>0）。
【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用（）存储方式最节省运算时间。
【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。
第二章线性表一、选择题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.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。
第二章习题1. 描述以下三个概念的区别：头指针，头结点，首元素结点。
2. 填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。
（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。
在单链表中，逻辑上相邻的元素，其物理位置相邻。
（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。
3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。
按要求从下列语句中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是：。
b. 在P结点前插入S结点的语句序列是：。
c. 在表首插入S结点的语句序列是：。
d. 在表尾插入S结点的语句序列是：。
供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。
试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。
5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。
6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。
试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。
第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．线性表的逻辑次序与储存次序老是一致的。
×2．次序储存的线性表能够按次号随机存取。
√3．次序表的插入和删除操作不需要付出很大的时间代价，由于每次操作均匀只有近一半的元素需要挪动。
×4．线性表中的元素能够是各种各种的，但同一线性表中的数据元素拥有同样的特征，所以是属于同一数据对象。
√5．在线性表的次序储存构造中，逻辑上相邻的两个元素在物理地点上其实不必定紧邻。
×6．在线性表的次序储存构造中，插入和删除时，挪动元素的个数与该元素的地点相关。
√二单项选择题 ( 请从以下 A，B，C，D 选项中选择一项 )1．线性表是 ( A )。
(A)一个有限序列，能够为空；(B)一个有限序列，不可认为空；(C)一个无穷序列，能够为空；(D)一个无序序列，不可认为空。
2．对次序储存的线性表，设其长度为n，在任何地点上插入或删除操作都是等概率的。
插入一个元素时均匀要挪动表中的（ A ）个元素。
(A) n/2(B) n+1/2(C) n -1/2(D) n三填空题1．在次序表中做插入操作时第一检查___表能否满了 ______________。
四算法设计题1．设线性表寄存在向量A[arrsize]的前elenum个重量中，且递加有序。
试写一算法，将x插入到线性表的适合地点上，以保持线性表的有序性。
而且剖析算法的时间复杂度。
2．已知一次序表A，其元素值非递减有序摆列，编写一个函数删除次序表中剩余的值同样的元素。
3．编写一个函数，从一给定的次序表A 中删除值在 x~y(x<=y) 之间的所有元素，要求以较高的效率来实现。
提示：能够先将序表中所有在 x~y 之的元素置成一个特别的，其实不立刻除它，而后从最后向前挨次描，拥有特别的元素后，移后来面的元素将其除去。
4．性表中有 n 个元素，每个元素是一个字符，存于向量R[n] 中，写一算法，使 R 中的字符按字母字符、数字字符和其余字符的序摆列。
第2章线性结构
一、选择题
1. 顺序存储结构的优点是（）
A．存储密度大 B．插入运算方便
C．删除运算方便 D．可用于各种逻辑结构的存储表示
2. 下面关于线性表的叙述中，错误的是（）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项
4．若某线性表最常用的操作是存取任一指定序号的元素和在线性表的最后进行插入和删除元素，则利用（）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则
采用（）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双向链表D．仅有尾指针的单循环链表
6. 对于一个头指针为head的带头结点的单链表，判定该链表为空表的条件是（）。
A．head==NULL B．head→next==NULL
C．head→next==head D．head!=NULL
7. 链表不具有的特点是（）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与链表长度成正比
8. 下面的叙述正确的是（）
A．线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i个元素的时间同该元素的大小有关
9. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度分别为（）。
A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1)
10．非空的循环单链表head的指向尾结点的指针变量p满足（）。
A．p->link=head B．p->link=NULL C．p=NULL D．p=head
11. 若长度为n的线性表采用顺序存储结构，在第i个位置插入一个元素的算法的时间复杂度为（）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
12．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。
A．p->next=s; s->next=p->next; B． s->next=p->next; p->next=s; C．p->next=s; p->next=s->next; D． p->next=s->next; p->next=s;
13. 利用双向链表作线性表的存储结构的优点是（）。
A. 便于插入和删除操作
B. 提高按关系查找数据元素的速度
C. 节省存储空间
D. 便于销毁结构，释放存储空间
14. 若长度为n的非空顺序表，在表的第i个位置插入一个新元素，i的合法值是（）。
A. 1≤i≤n
B.1≤i≤n+1
C. 0≤i≤n-1
D. 0≤i≤n
15.已知L是带头结点的单链表，则删除首元结点的语句是（）。
A. L=L->next;
B. L->next=L;
C. L=L->next->next;
D. L->next=L->next->next;
16. 已知单链表A的长度为m，单链表B的长度为n，若将B链接在A的末尾，在没有尾指针的情况下，算法的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(m)
D. O(m+n)
* 17．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表
B.单循环链表
C. 带尾指针的单循环链表
D.带头结点的双循环链表
二、填空题
1. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动_ ___个元素。
2. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用____ _存储结构。
3. 对于一个有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为__ ____。
4．根据链式存储结构中每一个结点包含的指针个数，可以将线性链表分成_ __和多重链表。
5．链接存储的特点是利用__ _来表示数据元素之间的逻辑关系。
6. 顺序存储结构是通过_ __表示元素之间的关系的;链式存储结构是通过_______表示元素之间的关系的。
7. 循环单链表的最大优点是：__ ___。
8. 带头结点的单循环链表L，L为空表的条件是：__ ___。
三、判断题
1. 对任何数据结构链式存储结构一定优于顺序存储结构。
( )
2. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
( )
3. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
( )
4. 所谓静态链表就是一直不发生变化的链表。
( )
5. 线性表的特点是每个元素都有一个前驱和一个后继。
( )
6. 取线性表的第i个元素的时间同i的大小有关。
( )
7. 线性表只能用顺序存储结构实现。
( )
8. 顺序存储结构的主要缺点是不利于插入或删除操作。
( )
四、简答题
1. 对于线性表中的插入操作，分别写出在顺序存储结构下和链式存储结构下的时间复杂度。
2. 线性结构的特点是什么？
3.说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。
4. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?
*5. 顺序表在插入或删除元素时一般需要移动元素，如果想不移动多个元素就实现插入和删除，应该如何处理？
五、算法题
1、利用线性表的基本操作(见教材P19)，实现在线性表A中删除在线性表B中出现的元素。
2、编写算法，将一个有n个非零元素的线性表A拆分成两个线性表，其中大于零的元素存放线性表B中，小于零的元素存放在线性表C中。
3、分别基于线性表的顺序存储结构和链式存储结构（带头结点），实现以下操作：
(1) 从线性表中删除具有给定值x的所有元素。
(2) 从线性表中删除其值在有给定值s与t之间的所有元素，其中要求s<=t ，若s或t 不合理，或线性表为空，则显示出错信息并退出程序。
(3) 假设线性表的元素按递增顺序排列，删除表中所有大于s且小于t的所有元素（若存在这样的元素），其中要求s<=t ，若s或t不合理，或线性表为空，则显示出错信息并退出程序。
(4) 假设线性表的元素按递增顺序排列，删除表中所有值重复的元素，即使表中无重复元素，例如：A={ 1, 3, 5, 5, 8, 9, 9, 12}，删除后A={ 1, 3, 5, 8, 9, 12}
*4、设有一个不带头结点的单链表，编写递归算法实现以下操作：
(1) 求链表中的结点个数
(2) 求链表中的最大整数（设链表结点的数据域中存放的是整型数据）。
