《数据结构》习题集第2章线性表

数据结构课后练习题第2章线性表1/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1第2章线性表一、选择题1.表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素个数为（A）。A.(N-1)/2B.NC.N+1D.N-1E.N/2F.(N+1)/2G.(N-2)/22.线性表是具有N个（C）的有限序列。A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（B）。A、正确的B、错误的C、不一定，与具体结构有关。4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。5.带头结点的单链表为空的判定条件是（B）。A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL6.不带头结点的单链表head为空的判定条件是（A）。A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL7.非空的循环单链表head的尾结点P满足（C）。A、P-NEXT=NULLB、p=NULLC、p-next==headD、p==head8.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）。A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P所指结点的后继结点，则执行（A）。A、p-next=p-next-nextB、p=p-next;p-next=p-next-nextC、p-next=p-next;D、p=p-next-next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（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;11.在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（C）。A、s-next=p-next;p-next=s;B、p-next=s-next;s-next=p;C、q-next=s;s-next=p;D、p-next=s;s-next=q;12.假设双链表结点的类型如下：typedefstructlinknode{intdata;／／数据域structlinknode*llink;／／指向前趋结点的指针域structlinknode*rlink;／／指向后继结点的指针域}bnode现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（D）。A、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;数据结构课后练习题第2章线性表2/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1B、p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llinkC、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-llink=q;D、以上都不对13.如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（D）。A、p-rlink=s;s-llink=p;p-rlink-llink=s;s-rlink=p-rlink;B、p-rlink-s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;C、s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;D、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;14.在一个长度为n的单链表上，设有头和尾两个指针，执行（A，C，D）操作与链表的长度无关。A、删除单链表中的第一个元素B、删除单链表中最后一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素15.线性结构中的一个结点代表一个（A）A、数据元素B、数据项C、数据D、数据结构16.非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（D）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17.顺序表是线性表的（B）A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构18.对于顺序表，以下说法错误的是（A）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B）为标准操作。A、插入操作B、结点移动C、算术表达式D、删除操作20.对于顺序表的优缺点，以下说法错误的是（C）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)21.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（A）存储方式最节省时间。A、顺序表B、单链表C、双链表D、单循环链表22.循环链表主要优点是（D）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A、单链表B、双链表C、循环链表D、顺序表数据结构课后练习题第2章线性表3/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1二、填空题1.在线性结构中，第一个结点（没有）前趋结点，其余每个结点有且只有（1）个前趋结点。2.在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（该元素的位置）有关。3.已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：（１）表首插入Ｓ结点的语句序列是（FC）。（２）表尾插入Ｓ结点的语句序列是（BIAG）。Ａ、Ｐ-next=S;Ｂ、P=L;Ｃ、L=S;Ｄ、P-next=S-next;Ｅ、S-next=P-next;Ｆ、S-next=L;Ｇ、S-next=NULL;Ｈ、while(P-next!=Q)p=p-next;Ｉ、while(P-next!=NULL)P=P-next;4.已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。（1）删除首元结点的语句序列是（HGBJ）,（2）删除尾元结点的语句序列是（HFDBJ）A、P=P-next;B、P-next=P-next-next;C、while(P!=NULL)p=p-next;D、while(Q-next!=NULL){P=Q;Q=Q-next;}E、while(P-next!=Q)P=P-next;F、Q=P;G、Q=P-next;H、P=L;I、L=L-next;J、free(Q);5.已知L是带表头结点的非空链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。（1）删除P结点的直接后继结点的语句序列是（FAI）,（2）删除P结点的直接前趋结点的语句序列是（EGDFAI）A、P-next=P-next-next;B、P=P-Pnext-next;C、while(P-next!=Q)P=P-next;D、while(P-next-next!=Q)P=P-next;E、Q=P;F、Q=P-next;G、P=L;H、L=L-next;I、free(Q);6.已知结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问（n/2）个结点，从n个结点的双链表中查找一个结点，平均要访问（n/4）个结点。（此题有误！另作说明）7.对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（O(1)）；在值域为给定值的结点后插入一个新结点的时间复杂度是（O(n)）。8.单链表是（线性表）的链接存储表示。9.单链表中设置头结点的作用是（插入和删除首元素时不必进行特殊处理）。数据结构课后练习题第2章线性表4/7北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-110.在单链表中，除首元结点外，任一结点的存储位置由（其直接前趋结点的链域）指示。11.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p-prior=q-prior;q-prior-next=p;p-next=q;(q-prior=p;);12.在双向链表中，每个结点有两个指针域，一个指向（前趋结点），另一个指向（后继结点）。13.顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻的元素的物理位置（不一定）相邻。14.为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,…,an)，其中每个ai代表一个_结点_。a1称为_第一个_结点，an称为_最后一个__结点，i称为ai在线性表中的__位置_。对任意一对相邻结点ai、ai┼1(1≤in),ai称为ai┼1的直接__前驱__，ai┼1称为ai的直接__后继__。15.线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__前驱__外，其他结点有且仅有一个直接_前驱__；除终端结点没有直接__后继__外，其它结点有且仅有一个直接__后继__.16.所有结点按1对1的邻接关系构成的整体就是__线性__结构。17.线性表的逻辑结构是__线性__结构。其所含结点的个数称为线性表的___长度___。18.在单链表中，指针p所指结点为最后一个结点的条件是___p→next=NULL;___。三、判断题1.顺序存储的线性表可以随机存取。√2.顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。X3.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。X5.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。√6.在单链表中，可以从头结点进行查找任何一个元素。√7.线性表的链式存储结构优于顺序存储结构。X8.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。√9.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。X10.顺序存储方式只能用于存储线性结构。X四、简答题1.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？答案：宜采用链式存储结构，因为它使线性表的插入和删除操作的时间复杂度为O（1），而顺序存储结构的为O（n）。2.描述概念：头指针、头结点、首元结点的区别？答案：首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存线性表的数据