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

第2章 线性表一、 选择题1. 表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ e ），删除一个元素需要移动的元素个数为（ a ）。【，】A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/22. 线性表是具有N 个（ ）的有限序列。【】A、表元素 B、字符 C、数据元素 D、数据项 E、信息3. “线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。【】A、正确的 B、错误的 C、不一定，与具体结构有关。4. 线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。【，】A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。5. 带头结点的单链表为空的判定条件是（ ）。【】A、head=NULL B、head->next=NULL C、head->next=head D、head!=NULL6. 不带头结点的单链表head 为空的判定条件是（ ）。【】A、head=NULL B、head->next=NULLC、head->next=head D、head!=NULL7. 非空的循环单链表head 的尾结点P 满足（ ）。【】A、P->NEXT=NULL B、p=NULL C、p->next=head D、p=head8. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。【，】A、O(1) B、O(n) C、O(n2) D、O(nlog2n)9. 在一个单链表中，若删除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;10. 在一个单链表中，若在所指结点之后插入所指结点，则执行（ ）。【，】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，则执行（ ）。【】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. 假设双链表结点的类型如下：【，】typedef struct linknodeint data; /数据域struct linknode *llink; /指向前趋结点的指针域struct linknode *rlink; /指向后继结点的指针域bnode;现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（ ）。A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;B、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 的操作序列是（ ）。（多项选择）【】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、删除单链表中的第一个元素 B、删除单链表中最后一个元素 C、在单链表第一个元素前插入一个新元素 D、在单链表最后一个元素后插入一个新元素15. 线性结构中的一个结点代表一个（ ）【】A、数据元素 B、数据项 C、数据 D、数据结构16. 非空线性表L=(a1,a2,ai,an)，下列说法正确的是（ ）【】A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17. 顺序表是线性表的（ ）【，】A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构18. 对于顺序表，以下说法错误的是（ ）【，】A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作。【】A、插入操作 B、结点移动 C、算术表达式 D、删除操作20. 对于顺序表的优缺点，以下说法错误的是（ ）【】A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)21. 若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（ ）存储方式最节省时间。【】A、顺序表 B、单链表 C、双链表 D、单循环链表22. 循环链表主要优点是（ ）【】A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23. 在线性表的下列存储结构中，读取元素花费时间最少的是（ ）【，】A、单链表 B、双链表 C、循环链表 D、顺序表二、 填空题1. 在线性结构中，第一个结点（ 没有 ）前趋结点，其余每个结点有且只有（ 一个 ）个前趋结点。【】2. 在顺序表中插入或删除一个元素，需要平均移动（ 表中一半的 ）元素，具体移动的元素个数与（ 表长 ）有关。【】3. 已知是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：【，】（）表首插入结点的语句序列是（C）。（）表尾插入结点的语句序列是（ B.I.A.G）。、->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）删除首元结点的语句序列是（ H,G,B,I ） ,（2）删除尾元结点的语句序列是（ H,F,D,B,J）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 结点的直接后继结点的语句序列是（ F,A,I ）, （2）删除P 结点的直接前趋结点的语句序列是（ E,G,D,F,A,I ）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. 单链表中设置头结点的作用是（插入和删除元素时不必进行特殊处理 ）。【】10. 在单链表中，除首元结点外，任一结点的存储位置由（ 其前驱结点的链域 ）指示。【】11. 在非空双向循环链表中，在结点q 的前面插入结点p 的过程如下：【】p->prior=q->prior; q->prior->next=p;p->next=q;(q->prior=p; );12. 在双向链表中，每个结点有两个指针域，一个指向（前驱结点 ），另一个指向（ 后继结点 ）。【】13. 顺序表中逻辑上相邻的元素的物理位置（ 必定 ）相邻。单链表中逻辑上相邻的元素的物理位置（ 不一定 ）相邻。【】14. 为了便于讨论，有时将含n(n0)个结点的线性结构表示成(a1，a2,an)，其中每个ai 代表一个_结点_。a1 称为_第一个_结点，an 称为_最后_结点，i 称为ai 在线性表中的_位置_。对任意一对相邻结点ai、ai1(1i<n),ai称为ai1 的直接_前驱结点_，ai1 称为ai 的直接_后继结点_。【】15. 线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接_前驱_外，其他结点有且仅有一个直接_前驱_；除终端结点没有直接_后继_外，其它结点有且仅有一个直接_后继_.【】16. 所有结点按1对1的邻接关系构成的整体就是_线性_结构。【】17. 线性表的逻辑结构是_线性_结构。其所含结点的个数称为线性表的_长度_。【】18. 在单链表中，指针p 所指结点为最后一个结点的条件是_p->next=NULL;_。【】三、 判断题1. 顺序存储的线性表可以随机存取。【】对2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。【】错3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。【】对4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。【】错5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。【】对6. 在单链表中，可以从头结点进行查找任何一个元素。【】对7. 线性表的链式存储结构优于顺序存储结构。【】错8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。【】对9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。【】错10. 顺序存储方式只能用于存储线性结构。【, 】错四、 简答题1. 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？【】采用链式存储结构，因为其复杂度为O（1）；2. 描述概念：头指针、头结点、首元结点的区别？【，】3. 设 A 是一个线性表（a1a2an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai 与ai+1 之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1)，则平均每插入一个元素所要移动的元素个数又是多少？【，】4. 为什么在单循环链表中设置尾指针比设置头指针更好？【，】5. 双链表和单循环链表中，若仅知道指针p 指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？【】6. 下列算法的功能是什么？【，】LinkedList test1(LinkedList L)/L 是无头结点的单链表ListNode *q,*p;if(L&&L->next)q=L ;L=L->next; p=L;while(p->next) p=p->next;p->next=q;q->next=NULL;return L;7. 如果有n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？【】8. 若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？【】9. 设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10（1） 用单链表给出a(x)、b(x)的存储表示；（2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。【，】五、 设计题1. 编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A 中大于0的元素存放在B 中，小于0 的元素存放在C 中。【】2. 设顺序表L 中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。【】3. A、B 为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表C，保存两个表的公共元素，要求C 的元素值各不相同且递增有序。【】4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：【】（1） 找出最小值结点，且显示该数值。（2） 若该数值为奇数，则将其与直接后继结点的数值交换。（3） 若为偶数，则将其直接后继结点删除。六、 编程附加题1. 试分别用顺序表和单链表作为存储结构，实现将线性表（a0,a1,a2,.an-1）就地逆置的操作，所谓“就地”指辅助空间为O(1)。【，】2. 设单链表 L 是一个非递减有序表，试写一个算法将x 插入其中后仍保持L 的有序性。【】3. 设 A、B 是两个线性表，其表中元素递增有序，长度分别为m 和n。试写一算法分别以顺序存储和链式存储将A 和B 归并成一个仍按元素值递增有序的线性表C，请分析算法的时间复杂度。【，】4. 单链表 L 是一个递减有序表，试写一高效算法，删除表中值大于mink 且小于maxk 的结点（若表中有这样的结点），同时释放被删结点空间，这里mink 和maxk 是两个给定的参数, 它们可以和表中元素相同，也可以不同。【】5. 假设以两个元素依值递增有序排列的线性表A,B 分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C 中的元素也依值递增有序排列。是对顺序表编写求C 的算法。【】6. 假设在长度大于 1 的单循环链表中，既无头结点也无头指针。S 为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前驱结点。【】7. 计算带头结点的单循环链表的结点个数。【】8. 给定一个不带头结点的单链表，编写计算此链表长度的算法。【】