数据结构课后习题第二章

《数据结构课后习题第二章》由会员分享，可在线阅读，更多相关《数据结构课后习题第二章（6页珍藏版）》请在装配图网上搜索。

1、一、 选择题1. 线性表是具有n个（ ）的有限序列。 A数据项 B. 数据元素 C. 数据对象 D.表记录2. 以下关于线性表的说法不正确的是（ ）。 A. 线性表中的数据元素可以是数字、字符、记录等不同类型 B. 线性表中包含的数据元素个数不是任意的 C. 线性表中的每个结点都有且只有一个直接前趋和直接后继 D. 存在这样的线性表：表中各结点都没有直接前趋和直接后继3. 线性表的顺序存储结构是一种（ ）的存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取4. 在顺序表中，只要知道（ ），就可在相同时间内求出任一结点的存储地址。 A基地址 B. 结点大小 C. 线性表大

2、小 D. 基地址和结点大小5. 下面关于线性表的叙述中，错误的是（ ）。 A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链式存储，不必占用一片连续的存储单元 D. 线性表采用链式存储，便于插入和删除操作6. 线性表采用链表存储时其存储地址要求（ ）。 A. 必须是连续的 B. 部分地址必须是连续的 C. 必须是不连续的D. 连续和不连续都可以7. 一个长度为n的线性表顺序存储，向第i个元素（1=i=n+1）之前插入一个新元素时，需要从后向前依次后移（ ）个元素。An-i B. n-i+1 C. n-i-1 D. i8.（

3、 ）运算，使用顺序表比链式表好。 A. 插入 B. 删除 C. 根据序号查找 D. 根据元素值查找9.向具有n个结点的有序单链表中插入一个新的结点并仍然有序的时间复杂度是（ ）。A.O(1) B.O(n) C.O(n2) D.O(2n)10.在一个长度为n的顺序存储的线性表中，删除第i个元素（1=inext=HL;B. p- next=HL;HL=p;C. . p- next=HL;p=HL;D. . p- next=HL-next;HL-next=p;13.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指的结点，则执行的语句是（ ）。A.q-next=p-next;p-ne

4、xt=q;B. p-next=q-next;q=p;C. q-next=p-next;p-next=q;D. p-next=q-next;q-next=p;14.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ ）。A.p=q-next;p-next=q-next;B. p=q-next;q-next=p;C.p=-next;q-next=p-next;D.q-next=q-next-next;q-next=q;15.在双向链表中，在指针p所指的结点前插入一个指针q所指的结点，操作是（）。A.p-prior=q;q-next=p;p-prior-next=q;q-prior=

5、q;B.p-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior;C.q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q;D.q-prior=p-prior;q-next=q;p-prior=q;p-next=q;16.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。.顺序表 B.双链表C.带头结点的双循环链表 D.单循环链表二、 填空题1. 对于一个具有n个节点的单链表，在已知结点p之后插入一个新结点的时间复杂度为（ ），在给定值为x的结点之后插入

6、一个新结点的时间复杂度为（ ）。2.根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成（ ）和（ ）。3.顺序存储结构是通过（ ）表示元素之间的关系的。4.对于双向链表，在两个结点之间插入一个新结点需修改（ ）个指针，而单链表插入需要修改（ ）个指针。5.循环单链表的最大优点是（ ）。6.在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在（ ）结点的next域中。7.带头结点的双循环链表L为空表的条件是（ ）。8.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（ ）存储结构。9.求顺序表和单链表的

7、长度算法，其时间复杂度分别是（ ）和（ ）。10. 顺序表存储结构的优点是（）、（）、（）；缺点是（）。11. 单链表存储结构的优点是（）、（）；缺点是（）。12. 在单链表中，设置头结点的作用是（）。13. 单链表存储的特点是利用（）表示数据元素之间的逻辑关系。14. 不带头结点的双循环链表DL为空表的条件是（）。15. 以下算法的功能是：在一个非递减的顺序表中，删除所有值相等的多余元素。画线处填上适当的语句，将程序补充完整。#define maxlen 100tepedef struct elemtype a maxlen int length; sqlist;void delequil

8、( sqlist &s) int j=1.i=2;while (_) if ( s.ai!=s.aj )_;_;i+;_;16. 设双链表的结点存储结构如图2.39所示。删除链表中指针p所指结点的两步主要操作是：（）、（）。 LlinkRlinkData p三、 问答题1.是描述头指针、头结点、首结点的区别。并说明头指针和头结点的作用。2.何时选用顺序表、何时选用链表作为线性表的存储结构为宜？3. 为什么在单循环链表中设置尾指针比设置头指针更好？4. 下述算法的功能是什么？LinkList ABC(LinkList L) /L是无头结点单链表 If( L&L next) Q=L; L=L ne

9、xt; p=L;While(p next) p=p next;P next=Q; Q next=NULL; return L;5. 写出图2.40所示双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。 p 10 23 15 30 图 2.40 问答题 5 图结点结构为 : ( prior,data,next )6. Void AA(SqList &,int i ,int x ) if (i=1 & i=i;j) Aj+1=Aj; Ai=x; Else exit(ERROR);假定调用该算法时线性表L的内容为（15,26,37,48,55），i为3，x为51，则调用返回后该单链表

10、的内容变为什么？四、算法设计题1. 重写建立单链表的算法CreatList._L(Linklist &L,int n)要求顺序输入 n 个元素的值（即先输入a1，a2，） CreatList_L(LinkList &L;int n)2. 设顺序表L是一个递减有序表，试写一算法，插入元素x，插入后仍保持L的有序性。Void sinsert (Sqlist &S,int x)3. 写一算法，在带头结点的单链表上实现线性表的求表长 ListLength(L)的运算。Int ListLength(LinkList L)4. 写出从一个带头结点的单链表中删除其值等于给定值x的结点的算法函数。Int delete(LinkList &L, int x)5. 已知递增有序的两个带头结点的单链表La和Lb分表存储了一个非空集合A,B。设计算法实现求两个集合的并集运算 A=AB。void mergelist(linklist &La, linklist Lb)6. 设计算法将不带表头结点的单向链表就地逆转。7. 设计算法，删除整数数组中值相等的多余整数（只保留第一次出现的那个整数）。Void delDuplicate(int A ,int & n)