线性表作业
学号姓名分数
一选择题（14分）
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．非空的循环单链表head的尾结点p满足（）。
A．p－＞next=head B．p－＞next =NULL C．p=NULL D．p= head 11．循环链表H的尾结点P的特点是（）。
A．P－＞NEXT=H B．P－＞NEXT= H－＞NEXT C．P=H D．P=H－＞NEXT 12．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）
A. p－＞next=h
B. p－＞next=NULL
C. p－＞next. －＞next=h
D. p－＞data=-1
13．在单链表指针为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;
14．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL
二、判断（10分）
1. 链表中的头结点仅起到标识的作用。( )
2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )
3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )
4. 对任何数据结构链式存储结构一定优于顺序存储结构。( )
5. 线性表的特点是每个元素都有一个前驱和一个后继。( )
6. 取线性表的第i个元素的时间同i的大小有关. ( )
7. 线性表只能用顺序存储结构实现。( )
8. 线性表就是顺序存储的表。( )
9. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
10. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。( )
三、填空(25分)
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______; 4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。5．在单链表中设置头结点的作用是________。
6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。
7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。
8．链接存储的特点是利用________来表示数据元素之间的逻辑关系。
9.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
10. 对于单链表链表,在两个结点之间插入一个新结点需修改的指针共 ______个。
11. 循环单链表的最大优点是：________。
12. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________
13. 在单链表L中，指针p所指结点有后继结点的条件是：__
14. 在单链表p结点之后插入s结点的操作是：_______。
15．线性结构包括______、______、_______和_______。线性表的存储结构分成______和______
四/程序填空（10分）
．对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。
typedef struct node
{int data; struct node *next;
}linknode,*link;
void Insertsort(link L)
{ link p,q,r,u;
p=L->next; (1)______;
while((2)________)
{ r=L; q=L->next;
while((3)________&& q->data<=p->data) {r=q; q=q->next;}
u=p->next; (4)______; (5)______; p=u;
}
}
五应用题(51分)
1．线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？
5．线性表（a 1，a 2，…，a n ）用顺序映射表示时，a i 和a i+1（1<=i 6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 7. 试述头结点,首元结点,头指针这三个概念的区别. 10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？ 11. 设单链表结点指针域为next ，试写出删除链表中指针p 所指结点的直接后继的C 语言语句。 12. 设单链表中某指针p 所指结点（即p 结点）的数据域为data ，链指针域为next ，请写出在p 结点之前插入s 结点的操作 一．选择题 1. 已知在单链表中指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？（ B ） 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； 2. 非空的循环单链表first的尾结点（由p所指向）满足：（ C ） A、 p->next == NULL； B、 p == NULL； C、 p->next == first； D、 p == first； 3. 在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，需要从后向前依次后移___C___个元素。 A、n-i B、n-i-1 C、n-i+1 D、i 4. 线性表是具有n个__C____的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 5. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较___B___个结点。 A、 n B、n/2 C、(n-1)/2 D、(n+1)/2 6. 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___A___存储方式最节省运算时间。 A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表 7. 已知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; 二．填空题 1．在顺序表中插入或删除一个元素，需要平均移动________元素，具体移动的元素个数与_______有关。 2．在顺序表中，逻辑上相邻的元素，其物理位置________相邻。在单链表中，逻辑上相邻的元素，其物理位置__________相邻。 3．在带头结点的非空单链表中，头结点的存储位置由___________指示，首元素结点的存储位置由_________指示，除首元素结点外，其它任一元素结点的存储位置由_______指示。4.当对一个基本线性表进行的插入和删除操作较频繁时，基本线性表应采用存储结构；当对基本线性表的操作不会引起它的变化时，基本线性表应采用存储结构。 5.设某有一双链表，若要在指针q所指结点（中间结点）的后面插入一个新结点s，则需要执行下述语句段： s->prior=q；s->next=q->next；；q->next=s; 第二章线性表练习题 一、选择题 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称为空指针，它不指向任何结点只起标志作用 第二章线性表作业 一、选择题 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．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。 A．单链表B．双链表C．单循环链表D．带头结点的双循环链表 8. 静态链表中指针表示的是（）. A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址 9. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（） 第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是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。 习题二参考答案 一、选择题 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 为数据元素的个数，称为线性表的 长度 ， 第2章线性表 班级学号__________-姓名 一、判断正误 （×）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 （ A ）5. 链式存储的存储结构所占存储空间： 例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， 第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.doczj.com/doc/cf1534745.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.doczj.com/doc/cf1534745.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.doczj.com/doc/cf1534745.html,st+1) //i为元素编号，有效范围在https://www.doczj.com/doc/cf1534745.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.doczj.com/doc/cf1534745.html,st;i++) { if(S.data[i]==x) return i+1; //找到，转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i) 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章线性表 一选择题 下列程序段的时间复杂度为（ 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 ）； 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; 第2章线性表 1．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2．线性表是具有n个（）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 3.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置 元素的时间复杂性为（） A．O（i） B．O（1） C．O（n） D．O（i-1） 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插 入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表，访问结点和增加、删除结点的时间 复杂度为（）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6．对于一个头指针为head的带头结点的单链表，判定该表为空 表的条件是（） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 7.链表不具有的特点是（） A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是（）。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点，正确的 操作是：（）。 A． s->next=p->next;p->next=s; B． p->next=s;s->next=p->next; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10．对于一个头指针为head的带头结点的单链表，判定该表为 简单的线性规划问题 [ 学习目标 ] 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， 一、判断题 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章习题 (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.doczj.com/doc/cf1534745.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.doczj.com/doc/cf1534745.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.doczj.com/doc/cf1534745.html,st+1) //i为元素编号，有效范围在https://www.doczj.com/doc/cf1534745.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.doczj.com/doc/cf1534745.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.doczj.com/doc/cf1534745.html,st>MAXLEN-1) return 0; //表满，返回0 else if(i<1 || i>https://www.doczj.com/doc/cf1534745.html,st+2) return 1; //插入位置查处范围，返回1 else { for(k=https://www.doczj.com/doc/cf1534745.html,st;k>=i-1;k--) S.data[k+1]=S.data[k]; S.data[i-1]=x; https://www.doczj.com/doc/cf1534745.html,st++; return 2; } } //删除元素 int listDelete(seqList &S,int i) { int k; if(https://www.doczj.com/doc/cf1534745.html,st==-1) return 0; //空表，返回0 else if(i<1 || i>https://www.doczj.com/doc/cf1534745.html,st+1) return 1; //删除元素编号超出范围，返回1 else 例1说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 答：在线性表的链式存储结构中，头指针是指指向链表的指针，若链表有头指针则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一数据元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用作监视哨，等等），有了头结点后，对在第一数据元素结点前插入结点和删除第一结点，其操作与对其它结点的操作就统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一数据元素结点，它是头结点后边的第一个结点。 例2 为什么在单循环链表中设置尾指针比设置头指针更好？ 答：尾指针是指指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一个带头结点的单循环链表，其尾指针是rear，则开始结点和终端结点分别为指针rear所指结点的后继结点的后继结点和指针rear所指结点（利用C语言分别描述为rear->next->next和rear，利用标准Pascal语言分别描述为rear↑.next↑.next和rear），查找时间均为O(1)。若用头指针来表示该链表，则查找时间均为O(n)。 例3请分析含有n个结点的顺序表，在进行插入和删除操作时的时间复杂度，并对计算的结果进行分析，由此可得到线性表的适用范围的什么结论。 解：值得注意的是，插入操作是指在某个元素前面或后面插入，是针对位置的，因此可插入的位置为n+1个，而删除操作是删除线性表中某个位置上的元素，是针对元素的，因此可删除的元素为n个。 设p i为在第i个元素之前插入一个元素的概率，在等概率的条件下，其值为1/(n+1)。在第i个元素之前插入一个元素需要移动的元素的个数为：n-i+1。所以，在长度为n的线性表中插入一个元素所需要移动的元素次数的数学期望值（平均次数）为： E in=∑+ = + - 1 1 )1 ( n i i i n p=n/2 同理，设q i为删除第i个元素的概率，在等概率的条件下，其值为1/n。删除第i 个元素需要移动的元素的个数为：n-i。所以，在长度为n的线性表中删除一个元素所需要移动的元素次数的数学期望值（平均次数）为： E del=∑ =- n i i i n q 1 ) (=(n-1)/2 由于这两个操作的时间主要消耗在数据元素的移动上，所以插入算法和删除算法的时间复杂度均为：O(n)。 从上述分析可知，在顺序存储结构下，在线性表上插入或删除一个元素时需要平均移动线性表长度一半的元素个数，因此当n的值较大时，在顺序结构下，不宜对它频繁 第二章线性表习题及答案 一、基础知识题 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;数据结构习题二线性表
第2章线性表习题解析(答)
第二章 考研试题精选
有关线性表的题目及答案
第2章 线性表习题参考答案
数据结构第2章作业 线性表(答案)
线性规划典型例题
第2章线性表习题解答
128499-管理运筹学-第二章线性规划-习题
线性表练习题(答案)
2.线性表习题答案
第2章线性表(课堂作业)
(完整版)简单的线性规划问题(附答案)
线性表练习题答案
第2章线性表习题解答
线性表例题
第二章线性表习题及答案
相关主题
文本预览