线性表习题
第二章线性表
一、判断题
(l）线性表的链式存储结构优于顺序存储。
(2）链表的每个结点都恰好包含一个指针域。
(3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数
据对象。
(4）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
(5）在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个
元素。
(6）在线性表的顺序结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。(7）顺序存储方式的优点是存储密度大，插入、删除效率高。
(8）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。
(9）顺序存储的线性表可以实现随机存取。
(10）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
二、填空题
(1)有一单链表结构如下：
若要删除值为 c 的结点，应做的操作是。
(2)线性表 L = ( a1, a2 ，…，an）用数组存储。假定删除表中任一元素的概率相同，则删除一个元素平均需要移动的元素个数是。
(3)建立单链表的算法时间复杂度；建立有序单链表的算法时间复杂度。
(4)设有结点定义：
struct node
{ int data ;
struct node * next ; };
且已建立如下图所示的带有头结点的单向链表：
函数 sum 的功能是：计算链表中各结点数据域之和，作为函数值返回。请填空。
int sum (struct node * head )
{ int s = 0 ;
struct node * p ;
p = head 一＞ next ;
do
{ s= s＋；
p = p 一＞ next ; }
while ( p ! ＝ )；
return s; }
(5)以下算法用以统计链表中元素的个数，其中 first 指向链表中的第一个结点； count 用来统计结点个数。请填空。
struct link
{ char data ;
struct link * next ; } ;
struct link * p , * first ;
┆
int count = 0 ;
p ＝first ;
while （）
{ ；
p ＝；}
(6)己知 head 指向一个带有头结点的单向链表，链表中每个结点包含整型数据域（ data ) 和指针域（ next ）。以下算法用来查找链表所有结点中数据域值最大的结点的位置，由指针 s 传回调用程序。请填空。
struct link
{ char data ;
struct link *next;};
main ( )
{ struct link * head , * q ;
┆
findmax ( head , & q ) ;
printf ( " max = % d \ n " , q 一＞ data ) ;
┆
}
findmax ( struct link * head , struct link * * s )
{ struct link * p ;
p = h ead 一＞ next ;
* s = p ;
while （）
{ p ＝ ;
if ( p 一＞ data ＞ ) * s=p ; } }
(7)设线性表顺序存储结构定义如下：
# define MAXSIZE 20
typedef int datatype
type struct
{ datatype data [ MAXSIZE + l ] ;
int last ;
}sequenlist ;
函数 int 1ocate2 ( sequenlist * L , int x ) ；利用在表头设立监视哨的算法，实现在顺序表 L 中查找值为 x 的元素的位置。请填空。
int locate2 ( sequenlist * L , int x )
{ int i = ；
L 一＞ data [0] = x ;
while ( L 一＞ data[i]! = x ）
;
return i ; }
(8)设有两个由尾指针表示的带有头结点的单向环形链表 ra 和 rb ，以下算法实现将rb
所指的链表连接到 ra 所指链表之后。请填空。
LinkList * Connect (LinkList * ra , LinkList * rb )
{ LinkList * p ;
p = ra 一＞ next ;
ra 一＞ next ＝；
free ( rb 一＞ next ) ;
rb一＞ next = ；
return rb; }
(9)顺序表中逻辑上相邻的元素在物理位置上___________相邻。
(10)在链表中逻辑上相邻的元素的物理位置___________相邻。
(11)顺序表相对于链表的优点有____________和____________。
(12)链表相对于顺序表的优点有__________和____________操作方便；缺点是存储密度
_______________。
(13)在 n 个结点的顺序表中插入一个结点，平均需要移动________个结点，具体的移动次数取
决于__________________。
(14)在 n 个结点的顺序表中删除一个结点，平均需要移动_____________个结点，具体的移动
次数取决于___________________。
(15)在顺序表中访问任意一个结点的时间复杂度均为 ______________。
(16)在单链表中除首结点外，任意结点的存储位置都由_________结点中的指针指示。
(17)在 n 个结点的单链表中要删除已知结点*p ，需要找到_______________.其时间复杂度为
_______________。
(18)在双链表中要删除已知结点*p ，其时间复杂度为______________。
(19)在单链表中要在已知结点*p 之前插入一个新结点，需找到_____________，其时间复杂度
为________；而在双链表中，完成同样操作时其时间复杂度为_______。
(20)在循环链表中，可根据一个结点的地址访问整个链表，而单链表中需知道_________才能访
问整个链表。
(21)在单链表中设置头结点的作用是。
(22)循环单链表与非循环单链表的主要不同是，循环单链表尾结点的指针，而非循环
单链表的尾结点指针。
三、选择题
(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 个结点 B．在地址为 P 的结点之后插入一个结点
C．删除开始结点 D．删除地址为 P 的结点的后继结点(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)单链表的存储密度（）。
A．大于 1 B．等于1 C．小于1 D．不能确定(10)己知一个顺序存储的线性表，设每个结点需占 m 个存储单元，若第一个结点的地址al ，
则第i个结点的地址为（）。
A. al+(i-1)*m
B. al+i*m
C. al-i*m
D. al+(i+1)*m
(11)在 n 个结点的顺序表中，算法的时间复杂度是 O(l）的操作是（）。
A．访问第i个结点（1 ≤ i ≤ n）和求第 i 个结点的直接前驱（2 ≤ i ≤ n)
B．在第 i 个结点之后插入一个新结点（1 ≤ i ≤ n-1）
C．删除第 i 个结点（ 1 ≤ i ≤ n )
D．将 n 个结点从小到大排序
(12)在线性表中（）只有一个直接前驱和一个直接后继。
A．首元素 B．中间元素 C．尾元素 D．所有元素
(13)对具有 n 个结点的线性表进行查找运算，所需的算法时间复杂度为（）。
A. 0 ( n2 )
B. 0 ( nlog2n )
C. O ( log2n )
D. O ( n )
(14)线性表采用顺序存储的缺点是（）。
A．存储密度降低 B．只能顺序访问
C．元素的逻辑顺序与物理顺序不一致 D．插入、删除操作效率低
(15)以下链表结构中，从当前结点出发能够访问到任一结点的是（）。
A．单向链表和双向链表 B．双向链表和循环链表
C．单向链表和循环链表 D．单向链表、双向链表和循环链表(16)线性表是具有 n 个（）的有限序列。
A．数据项 B．数据元素 C．表元素 D．字符
(17)若长度为 n 的线性表采用链式存储结构，访问其第 i 个元素的算法时间复杂度为（）。
A. 0 ( l )
B. 0 ( n )
C. 0 ( n2 )
D. 0 ( log2n )
(18)指针 P 指向循环链表 L 的首元素的条件是（）。
A. P＝＝L
B. L->next＝＝P
C.P->next= =NULL
D. P->next＝＝L
(19)指针 P 所指的元素是双循环链表 L 的尾元素的条件是（）。
A. P＝＝L
B. P->prior＝＝L
C. P＝＝NULL
D. P->next＝＝L
(20)不带头结点的单链表L为空的条件是( )
A. L!＝NULL
B. L＝＝NULL
C. L->next＝＝NULL
D. L->next＝＝
L
(21)带头结点的单链表L为空的条件是( )
A. L!＝NULL
B. L＝＝NULL
C. L->next＝＝NULL
D. L->next＝＝
L
(22)两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件
是（）。
A. P->next＝＝Q->next
B. P->next＝＝Q
C. Q->next＝＝P
D. P＝＝Q
(23)在长度为 n 的顺序表中，若要删除第 i (1≤i≤n ）个元素，则需要向前移动元素的
次数为（）。
A. 1
B. n 一 i
C. n 一 i + 1
D. n 一 i 一
l
(24)在长度为 n 的顺序表中第 i (1≤i≤n）个位置上插入一个元素时，为留出插入位置所
需移动元素的次数为（）。
A. n - i
B. i
C. n – i + 1
D. n - i - l
(25)假定己建立以下动态链表结构，且指针 Pl 和 P2 已指向如图所示的结点：则以下可以
将 P2 所指结点从链表中删除并释放该结点的语句组是( )
A. pl -> next = p2 -> next ; free ( pl ) ;
B. pl = p2 ; free ( p2 ) ;
C. pl -> next = p2 -> next ；free ( p2 ) ;
D. pl = p2 -> next ; free ( p2) ;
(26)若已建立如图所示的单向链表：
则以下不能将 s 所指的结点插入到链表尾部，构成新的单向链表的语句组是（）。
A. s一＞next = a - > next 一＞next ; a - > next - > next = s ;
B. a = a - > next; a 一＞next =s ; s 一＞next = NULL ;
C. s 一＞next = NULL ; a = a一＞ next; a一＞ next = s ;
D. a = a 一＞next ; s 一＞next = a 一＞next ; a - > next = s 一> next ;
(27)有如下函数：
Void fun( struct node * hl , struct node * h2 )
{ struct node * t ;
t = hl ;
while ( t - > n ext ! ＝’\0’ )
t = t 一＞ next ; t - > next = h2 ; }
其中形参 hl 和 h2 分别指向 2 个不同链表的第一个结点，此函数的功能是（）。
A．将链表 h2 接到链表 h1 后 B．将链表 h1 接到链表 h2 后
C．找到链表 hl 的最后一个结点由指针返回 D．将链表 hl 拆分成两个链表
四、简答题
(l）分别描述线性表、单链表、双链表、循环链表的概念。
(2)在处理某个问题时，需要存储的数据总量不能确定，并经常需要进行数据的添加和删除操作，此时应选用哪种存储结构？为什么？
(3)有哪些链表可仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上的任何一个结点。
(4)在单链表、双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点P从相应地链表中删除？若可以，其时间复杂度分别为多少？
(5) 简述头指针、头结点和开始结点的区别，以及头指针和头结点的作用。
(6)带有头结点的链表的操作一定比不带头结点的链表操作简单么？试举例说明。
(7) 简述线性表的存储结构及各自的长处。
(8) 为什么在单循环链表中设置尾指针比设置头指针更好？
(9)描述下列算法的功能
五、算法设计题
(1)若已建立一个带有头结点的单向链表，且链表结点 data 成员中的数据按由小到大的顺
序排列，编写函数实现算法：把 x 值插入到链表中，插入后链表中结点数据仍保持有序。其中 h 为指向头结点的指针。
(2)试编写算法实现在顺序表 L 中查找值为 x 的元素位置的简单顺序查找算法。
(3)试编写算法实现从顺序表 L 中删除第 i 个位置上的元素。
(4)试编写算法实现删除表 L 中值为 y 的元素的算法，函数返回 y 在线性表中的位置，若
y 不存在返回 0 值。
(5)试编写算法在顺序存储的线性表 L 的第 i 个位置上插入值为 x 的元素。
(6)试编写算法利用头插法建立带有头结点的单向链表。
(7)试编写算法利用尾插法建立不带头结点的单向链表。
(8)试编写算法输出带有头结点的单向链表中各结点的值。
(9)试编写算法在带有头结点的单向链表中查找值为 k 的结点，找到后返回其位置；否则返
回 NULL 。
(10)设有带头结点的单向链表， head 为指向头结点的指针。设计算法：实现在值为 x 的
结点前插入值为 y 的结点。若值为 x 的结点不存在，则将值为 y 的结点插在链表的最后，作为尾结点。
(11)已知A、B、C为三个元素值递增有序的线性表，现要求对表A做如下运算：删去那些既
在表B中出现又在表C中出现的元素，要求使用两种存储结构。
(12)已知线性表的元素是无序的，且以带头结点的单链表作为存储结构，试编写算法实现，
删除表中所有值大于min且小于max的元素的算法。
(13)假设在长度大于1的单循环链表中，既无头结点也无头指针，p为指向该链表中某个结
点的指针，编写算法实现删除该结点的前驱结点。
(14)设单向链表中结点按有序链接，设计算法：删除链表中值相同的结点，使之只保留一个。
(15)写一个对单循环链表进行遍历（打印每个结点的值）的算法，已知链表中任意结点的地址
为 P。
(16)对给定的带头结点的单链表 L ，编写一个删除 L 中值为 X 的结点的直接前驱结点的算
法。
(17)有两个循环单链表，链头指针分别为 head1 和 head2 ，编写一个函数将链表 head1 链接
到链表 head2 ，链接后的链表仍是循环链表。
(18)有一个由整数构成的单链表长度为n，试编写算法，将单链表分解成两个，一个只由奇数
构成，另一个只由偶数构成。
部分参考答案
第一章绪论
一、判断题
(1）√ (2）× (3）√ (4）× (5）√ (6）√
三、选择题
(1） A (2） A (3） C (4） C (5） D
(6） D (7) B (8) A (9) D (10) A
(11) A (12) A (13) A (14) A (15) B
(16) C (17) C (18) C
第二章线性表
一、判断题
(1）× (2）× (3）√ (4）× (5）√
(6）× (7) × (8) × (9) √ (10) √
三、选择题
(1） A (2） B (3） B (4） B (5） A
(6） B (7) C (8) B (9) C (10) A
(11) B (12) B (13) D (14) D (15) B
(16) B (17) B (18) A (19) D (20) B
(21) C (22) B (23) B (24) C (25) C
(26) D (27) A
第三章栈
一、判断题
(1）√ (2）√ (3）× (4）× (5）×
(6）× (7) ×
三、选择题
(1） A (2） B (3） C (4） B (5） C
(6） D (7) D (8) C (9) B (10) C
(11) A (12) C (13) D (14) B (15) A
(16) A
第四章队列
一、判断题
(1）√ (2）√ (3）√ (4）× (5）× (6）×三、选择题
(1） B (2） D (3） A (4） C (5） B
(6） D (7) A (8) A (9) C (10) D
(11) B (12) A (13) C (14) C (15) D
(16) A (17) A (18) B (19) A (20) A
第五章串
一、判断题
(1）√ (2）√ (3）× (4）× (5）×
(6）× (7) × (8) √ (9) × (10) ×
三、选择题
(1） C (2） B (3） C (4） D (5） D
(6） A (7) B (8) D (9) D (10) A
(11) D (12) A (13) B (14) A
第六章树和二叉树
一、判断题
(1）√ (2）√ (3）√ (4）× (5）√
(6）√ (7) √ (8) × (9) × (10) √
(11) × (12) × (13) √ (14) √ (15) √
(16) √ (17) √ (18) × (19) √ (20) ×
(21) √(22) √(23) √
三、选择题
(1） B (2） C (3） C (4） C (5） D
(6） B (7) B (8) A (9) B (10) D
(11) D (12) B (13) A (14) C (15) A
(16) D (17) D (18) A (19) D (20) C
(21) D (22) D (23) D (24) B (25) A
(26) C (27) C (28) A (29) D (30) A
(31) B (32) C (33) C (34) B (35) ① B ② B ③ B (36) C (37) A
第七章图
一、判断题
(1）√ (2）√ (3）× (4）√ (5）√
(6）× (7) √ (8) √
三、选择题
(1） C (2） B (3） B (4） C (5） C
(6） B (7) A (8) A (9) D (10) B
(11) B (12) B (13) B (14) A (15) D
(16) C (17) D (18) C (19) B (20) C
(21) A (22) B
第八章查找
一、判断题
(1）√ (2）√ (3）× (4）√ (5）×
(6）√ (7) √ (8) × (9) × (10) √
(11) √ (12) × (13) √ (14) × (15) ×
三、选择题
(1） A (2） B (3） D (4） C (5） D
(6） C (7) D (8) B (9) (10)
(11) C (12) B (13) B (14) B (15) ① D ② C
(16) D (17) B (18) D (19) B
第九章排序
一、判断题
(1）√ (2）× (3）√ (4）× (5）√
(6）× (7) × (8) × (9) √
三、选择题
(1） C (2） A (3） C (4） C (5） D
(6） B (7) C (8) C (9) C (10) B
(11) A (12) C (13) D (14) C (15) D
(16) A (17) D (18) A (19) B (20) C
(21) C (22) D (23) A (24) C (25) D
(26) C B (27) D (28) C (29) A (30) C (31) D (32) A (33) A
第2章线性表习题解析(答)
第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关； （2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是。 A、（1）、（2） B、（1） C、（1）、（2）、（3） D、（2） 6.在双向链表存储结构中，删除p所指的结点时须修改指针。 A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next; B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p; C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior; D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;
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.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。 A、 n b、2n－1 c、2n d、n－1 9.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动个元素。 A、n－i B、n－i+1 C、n－i－1 D、i 10.线性表L=(a1，a2,……an)，下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法，以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针，它不指向任何结点只起标志作用
线性表练习题(答案)
第2章线性表 一选择题 下列程序段的时间复杂度为（ C ）。 for( int i=1;i<=n;i++) for( int j=1;j<= m; j++) A[i][j] = i*j ; A. O(m2) B. O(n2) C. O(m*n) D. (m+n) 下面关于线性表的叙述中，错误的是哪一个？（B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素B．字符C．数据元素D．数据项 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表B．仅有头指针的单循环链表 C．双链表D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 下面的叙述不正确的是（B,C ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）A．O（i）B．O（1）C．O（n）D．O（i-1） 循环链表H的尾结点P的特点是（A ）。 A．P->next=H B．P->next= H->next C．P=H D．P=H->next 完成在双循环链表结点p之后插入s的操作是（D ）；
第2章 线性表习题参考答案
习题二参考答案 一、选择题 1. 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2. 假设在顺序表{a 0,a 1,……,a n －1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地 址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i 个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方 式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表 5. 在一个单链表中的p 和q 两个结点之间插入一个新结点，假设新结点为S,则修改链的java 语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n 个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。 A. O (1) B. O (log 2n) C. O (n) D. O (n2) 7. 要将一个顺序表{a 0,a 1,……,a n-1}中第i 个数据元素a i (0≤i ≤n-1)删除，需要移动（ B ）个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p 结点之后插入一个新结点s ，其修改链的java 语句序列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s); D. s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s); 9. 顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。 A ．小于1 B. 等于1 C. 大于1 D. 不能确定 10. 对于图2.29所示的单链表，下列表达式值为真的是（ D ）。 图2.29 单链表head 的存储结构图 A. head.getNext().getData()=='C' B. head.getData()=='B' C. P 1.getData()==’D ’ D. P 2.getNext()==null 二、填空题 1. 线性表是由n （n ≥0）个数据元素所构成的 有限序列 ，其中n 为数据元素的个数，称为线性表的 长度 ，
线性规划典型例题
例1：生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如下表。若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费O.2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立模型。 解： 法1 设每个季度分别生产x1,x2,x3,x4 则要满足每个季度的需求x4≥26 x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 考虑到每个季度的生产能力 0≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10 每个季度的费用为：此季度生产费用+上季度储存费用 第一季度15.0x1 第二季度14 x2 0.2(x1-20) 第三季度15.3x3+0.2(x1+ x2-40) 第四季度14.8x4+0.2(x1+ x2+ x3-70)
工厂一年的费用即为这四个季度费用之和, 得目标函数；minf=15.6 x1+14.4 x2+15.5 x3+14.8 x4-26 s.t．x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 20≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10。 法2：设第i季度生产而用于第j季度末交货的产品数量为xij吨 根据合同要求有： xll=20 x12+x22=20 x13+x23+x33=30 x14+x24+x34+x44=10 又根据每季度的生产能力有： xll+x12+x13+x14≤30 x22+x23+x24≤40 x33+x34≤20 x44≤10 第i季度生产的用于第j季度交货的每吨产品的费用cij=dj+0.2(j-i)，于是，有线性规划模型。 minf=15.Oxll+15.2x12+15.4xl3+15.6xl4+14x22+14.2x23+14.4x24+15.3 x33+15.5x34+14.8x44 s．t． xll=20， x12+x22=20， x13+x23+x13=30， x14+x24+x34+x44=10， x1l+x12+x13+x14≤30， x22+x23+x24≤40， x33+x34≤20，
线性表练习题答案
一、判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2．顺序存储的线性表可以按序号随机存取。(TRUE) 3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。（TRUE） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE）7．线性表的链式存储结构优于顺序存储结构。（FALSE） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE） 二、单选题、(请从下列A，B，C，D选项中选择一项) 11．线性表是( ) 。 (A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。 答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 答：A 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的；(B) 部分地址必须是连续的； (C) 一定是不连续的；(D) 连续与否均可以。 答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表
第2章线性表习题解答
第2章线性表习题解答
第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S)
{ https://www.wendangku.net/doc/dd18093046.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/dd18093046.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/dd18093046.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/dd18093046.html,st+1之间 return false; else { x=S.data[i-1];
return true; } } //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/dd18093046.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)
128499-管理运筹学-第二章线性规划-习题
11（2），12,14,18 习题 2-1 判断下列说法是否正确： （1） 任何线性规划问题存在并具有惟一的对偶问题； T （2） 对偶问题的对偶问题一定是原问题；T （3） 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之， 当对偶问题无可行解时，其原问题具有无界解；F （4） 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优 解； （5） 若线性规划问题中的b i ，c j 值同时发生变化，反映到最终单纯形表中，不会出 现原问题与对偶问题均为非可行解的情况； （6） 应用对偶单纯形法计算时，若单纯形表中某一基变量x i <0，又x i 所在行的元素全 部大于或等于零，则可以判断其对偶问题具有无界解。 （7） 若某种资源的影子价格等于k ，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大5k ； （8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优生产计划中第 i 种资源已经完全耗尽；若y i =0，说明在最优生产计划中的第i 种资源一定有剩余。 2-2将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题： 5 43212520202410max x x x x x z ++++=
第2章线性表习题参考答案
第2章线性表习题参考答案 习题二 一、选择题 1. 链式存储结构的最大优点是（ D ）。 A.便于随机存取 B.存储密度高 C.无需预分配空间 D.便于进行插入和删除操作 2. 假设在顺序表{a0,a1,……,an－1}中，每一个数据元素所占的存储单元的数目为4，且第0 个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 A. 106 B. 107 C.124 D.128 3. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表 B. 带头结点的单链表 C.不带头结点的单链表 D. 循环单链表 4. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜 采用（ C ）存储方式。 A. 顺序表 B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表 D. 双向链表
5. 在一个单链表中的p和q两个结点之间插入一个新结点， 假设新结点为S,则修改链的 java语句序列是（ D ）。 A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 6. 在一个含有n个结点的有序单链表中插入一个 新结点，使单链表仍然保持有序的算法的 时间复杂度是（ C ）。 A. O(1) B. O(log2n) C. O(n) D. O(n2) 7. 要将一个顺序表{a0,a1,……,an-1}中第i个数据元素 ai(0≤i≤n-1)删除，需要移动（ B ） 个数据元素。 A. i B. n-i-1 C. n-i D. n-i+1 8. 在带头结点的双向循环链表中的p结点之后插入一个新结 点s，其修改链的java语句序 列是（ D ）。 A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior()); B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext()); C. s.setPrior(p); s.setNext(p.getNext()); p.setNext(s); p.getNext().setPrior(s);
2.线性表习题答案
1、基于单链表写出向线性表的末尾添加一个元素的算法。 Status Insert(LinkList L,ElemType e) { LinkList p,q; q=L; p=(LinkList)malloc(sizeof(LNode));//为元素开辟空间 if(p==null) return error; p->data=e； while(q->next) q=q->next;//使p指向最后一个节点 p->next=q->next;//插入p节点 q->next=p; return ok； } 2、若L为有序表，基于单链表写出算法，使得向L中插入一个元素e后依然有序。 Status InsertInOrder_L(LinkList &L,ElemType e) { LinkList p,q,s; q=L; p=L->next s=(LinkList)malloc(sizeof(LNode));//为元素开辟空间 if(s==null) return error; s->data=e； while( p != NULL ) { if( s->value >= p->value ) // 找到了s该插入的位置,并且此时p,q已记录下要插入的位置 break else q = p; p = p->next; } // 将s节点插入到q,p节点之间 s->next = p; q->next = s; return ok； } 3、基于单链表写出删除线性表尾元素的算法。 Status DeleteRear_L(LinkList &L,ElemType &e) { LinkList p,q, P=L; Q=L->next;
(完整版)简单的线性规划问题(附答案)
简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一线性规划中的基本概念 知识点二线性规划问题 1．目标函数的最值 线性目标函数 z＝ax＋by (b≠0)对应的斜截式直线方程是 y＝－a x＋z，在 y 轴上的 截距是z， b b b 当 z 变化时，方程表示一组互相平行的直线． 当 b>0，截距最大时， z 取得最大值，截距最小时， z 取得最小值； 当 b<0，截距最大时， z 取得最小值，截距最小时， z 取得最大值． 2．解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域．(2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点 (或边界 )便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案．
知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小．常见问题有： ①物资调动问题例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C 三种 材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解． (3)模型应用：将求解出来的结论反馈到具体的实例中，设计出最佳的方案． 题型一求线性目标函数的最值 y≤2， 例 1 已知变量 x，y 满足约束条件 x＋y≥1，则 z＝3x＋y 的最大值为 ( ) x－y≤1， A ． 12 B ．11 C ．3 D ．－ 1 答案 B 解析首先画出可行域，建立在可行域的基础上，分析最值点，然后通过解方程组得最值点 的坐标，代入即可．如图中的阴影部分，即为约束条件对应的可行域，当直线y＝－3x＋z 经 y＝2，x＝ 3，
第2章线性表习题解答
第2章习题 (1) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last，在实现各基本运算时需要做那些修改？ 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S) { https://www.wendangku.net/doc/dd18093046.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/dd18093046.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/dd18093046.html,st+1) //i为元素编号，有效范围在https://www.wendangku.net/doc/dd18093046.html,st+1之间 return false; else { x=S.data[i-1]; return true; }
} //查找元素x，成功：返回元素编号；失败：返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/dd18093046.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出} return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) { int k; if(https://www.wendangku.net/doc/dd18093046.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.wendangku.net/doc/dd18093046.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.wendangku.net/doc/dd18093046.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.wendangku.net/doc/dd18093046.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.wendangku.net/doc/dd18093046.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.wendangku.net/doc/dd18093046.html,st+1) return 1; //删除元素编号超出范围，返回1 else
线性表练习题
一、火车出栈序列 （train.pas） 【题目描述】 输入n（n列火车),输出火车出栈的所有可能顺序。 【输入样例】 3 【输出样例】 3 2 1 2 3 1 2 1 3 1 3 2 1 2 3 【数据规模】 3<=n<=12 二、括号匹配 （LongestRegularBracketsSequence.pas） 【题目描述】 对一个由(，)，[，]括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串称为括号匹配的字符串：1．（），[]是括号匹配的字符串 2．若A是括号匹配的串,则(A),[A]是括号匹配的字符串 3．若A,B是括号匹配的字符串，则AB也是括号匹配的字符串。例如，(),[],([]),()()都是括号匹配的字符串，而][,[()],(]则不是。 字符串A的子串是指由A中连续若干个字符组成的字符串。 例如：A,B,C,ABC,CAB,ABCABC都是ABCABC的子串空串是任何字符串的子串。 【输入格式】 输入一行，为一个仅由()[]组成的非空字符串。 【输出格式】 输入也仅有一行，为最长的括号匹配子串。若有相同长度的子串，
输出位置靠前的子串。 【数据规模】 对20%的数据，字符串长度<=100； 对50%的数据，字符串长度<=10,000； 对100%的数据，字符串长度<=1,000,000； 三、马的最短步数 （horse.pas） 【题目描述】 求马在棋盘上从某个起点到某个终点的最少步数。 【输入格式】 第一行，n，m，表示棋盘有n行m列；(2 第2章线性表练习题答案 一、填空 1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 3. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 4. 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 5．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误 （×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针 域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。（×）9. 顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于 非线性结构，但其最佳存储方式是顺序存储方式。 （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。 三、单项选择题 （C）1．数据在计算机存储器内表示时，物理地址连续，数据间的逻辑关系依靠其物理地址间的连续性来表达，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（ B ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 （A）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个结点从小到大排序 （ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素（A）8 （B）63.5 （C）63 （D）7 一、判断题 1. 线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2. 顺序存储的线性表可以按序号随机存取。(TRUE) 3.顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。TRUE) 4.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。(TRUE) 5，在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。(FALSE ) 6.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。(TRUE) 7.线性表的链式存储结构优于顺序存储结构。(FALSE ) 8. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。(TRUE) 9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。(TRUE) 10.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(FALSE ) 二．选择题 11．线性表是()。 (A)一个有限序列，可以为空； (B)一个有限序列，不能为空； (C)一个无限序列，可以为空； (D)一个无序序列，不能为空。答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（）个元素。 (A)n/2(B)(n+1)/2(C)(n–1)/2(D)n答：A 13．线性表采用链式存储时，其地址()。 (A)必须是连续的；(B)部分地址必须是连续的；(C)一定是不连续的；(D)连续与否均可以。答：D 14．用链表表示线性表的优点是（）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同答：C 15.单链表中，增加一个头结点的目的是为了（）。 第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少? 答：我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; 线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、 若x 、y 满足约束条件222x y x y ≤?? ≤??+≥? ，则z=x+2y 的取值范围是 （ ） A 、[2,6] B 、[2,5] C 、[3,6] D 、（3,5] 解：如图，作出可行域，作直线l ：x+2y ＝0，将 l 向右上方平移，过点A （2,0）时，有最小值 2，过点B （2,2）时，有最大值6，故选A 二、求可行域的面积 例2、不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A 、4 B 、1 C 、5 D 、无穷大 解：如图，作出可行域，△ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的面积即可，选B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x ，y ）中整点（横纵坐标都是整数）有（ ） A 、9个 B 、10个 C 、13个 D 、14个 x y O 2 2 x=2 y =2 x + y =2 B A 2x + y – 6= 0 = 5 x ＋y – 3 = 0 O y x A B C M y =2 解：|x|＋|y|≤2等价于2(0,0)2(0,0)2(0,0) 2 (0,0)x y x y x y x y x y x y x y x y +≤≥≥??-≤≥? ? -+≤≥??--≤? 作出可行域如右图，是正方形内部（包括边界），容易得到整 点个数为13个，选D 四、求线性目标函数中参数的取值范围 例4、已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ，使z=x+ay(a>0) 取得最小值的最优解有无数个，则a 的值为 （ ） A 、－3 B 、3 C 、－1 D 、1 解：如图，作出可行域，作直线l ：x+ay ＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解 有无数个，则将l 向右上方平移后与直线x+y ＝5重合，故a=1，选D 五、求非线性目标函数的最值 例5、已知x 、y 满足以下约束条件220240330x y x y x y +-≥?? -+≥??--≤? ，则z=x 2+y 2的最大值和最小值分别是（ ） A 、13，1 B 、13，2 C 、13，4 5 D 、 5 解：如图，作出可行域,x 2+y 2是点（x ，y ）到原点的距离的平方，故最大值为点A （2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x ＋y －2=0的距离的平方，即为 4 5 ，选C 六、求约束条件中参数的取值范围 例6、已知|2x －y ＋m|＜3表示的平面区域包含点 （0,0）和（－ 1,1），则m 的取值范围是 （ ） A 、（-3,6） B 、（0,6） C 、（0,3） D 、（-3,3） 第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’;线性表练习题答案
数据结构_线性表练习题
第二章线性表习题及答案
线性规划经典例题
栈和队列练习题答案