《《数据结构》期末复习题及参考答案-第2章线性表【HSH2013级】给学生---.docx》由会员分享，可在线阅读，更多相关《《数据结构》期末复习题及参考答案-第2章线性表【HSH2013级】给学生---.docx（7页珍藏版）》请在三一文库上搜索。
1、数据结构期末复习题及参考答案- 第 2 章线性表一、选择题1、下面关于线性表的叙述中，错误的是哪一个？（） A 线性表采用顺序存储，必须占用一片连续的存储单元。B 线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D 线性表采用链接存储，便于插入和删除操作。2、线性表是具有n 个（）的有限序列（n0）。A 表元素B字符C数据元素D数据项E信息项3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A 顺序表B双链表C带头结点的双循环链表D单循环链表4、设一个链表最常用的操作是在末尾插入结点和删除尾
2、结点，则选用()最节省时间。A. 单链表B. 单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表5、静态链表中指针表示的是（） .A 内存地址B 数组下标C下一元素地址D 左、右孩子地址6、链表不具有的特点是（）A 插入、删除不需要移动元素B 可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比7、长度为 N 的线性表， 如果是顺序存储，则访问、 删除某个结点的时间复杂度分别是（） 和（）；如果是链式存储，则访问、删除某个结点的时间复杂度分别是（）和（）。 A. O(N) , O(1), O(1) , O(N)B. O(N) , O(1), O(N) , O(1)C.
3、O(1) , O(1), O(N) , O(1)D. O(1) , O(N), O(N) , O(1)8、若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（） (1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;7C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-
4、Llink=q;12、在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是：（）。A p-next=s;s-next=p-next;B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next;D p-next=s-next;p-next=s;13、对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（）A head=NULLBhead next=NULLChead next=headDhead!=NULL14、设指针变量p 指向单链表中结点A ，若删除单链表中结点A ，则需要修改指针的操作序列为（）。(A) q=p-next； p
5、-data=q-data； p-next=q-next；free(q)；(B) q=p-next；q-data=p-data； p-next=q-next； free(q)；(C) q=p-next；p-next=q-next； free(q)；(D) q=p-next； p-data=q-data； free(q)；二、填空题1、对于一个长度为n 的顺序存储的线性表，在表头插入元素的时间复杂度为O(n)，在表尾插入元素的时间复杂度为O(1)。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 顺序 存储结构。1、长度为N 的线性表中插入一
6、个结点，对于顺序存储和链式存储的线性表，其插入操作的时间复杂度分别是O(N)和 O(1)。3、线性表L= （ a1,a2, ,a）n用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（ n-1） /2。3、顺序存储的线性表中已有n 个结点，插入一个新结点平均需要移动数据n/2次。4、设单链表的结点结构为(data,next)， next 为指针域，已知指针px 指向单链表中data 为 x 的结点， 指针 py 指向 data 为 y 的新结点, 若将结点y 插入结点x 之后， 则需要执行以下语句:py-next=px-next; px-next=py ；5、在
7、一个长度为n 的顺序表中第i 个元素（1=inext!=NULL13、线性表的存储结构分为顺序存储结构和 链式存储结构。14、采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。15、设单链表结点指针域为next，则删除链表中指针p 所指结点的直接后继的的操作是：q=p-next;p-next=q-next; free(q);16、设 单链表的头结点的头指针为head,且 pre=head，单链表中某指针p 所指结点 （即 p 结点）的数据域为data，链指针域为next，则在 p 结点之前插入s 结点的操作是：
8、while(pre-next!=p) pre=pre-next; s-next=p;pre-next=s;17、在单链表p 结点之后插入s结点的操作是：s-next=p-next; p-next=s;三、简答题1、已知顺序表 La 和 Lb 中数据元素按值非递减有序排列，归并 La 和 Lb 得到新的顺序表Lc，使 Lc 中的数据元素也按值非递减有序排列 -这种操作称为顺序表的归并操作。 请阅读下列顺序表的归并操作 算法 代码，分析该算法的时间复杂度，并作简要解释。void MergeList(SqList La, SqList Lb, SqList &Lc) pa = La.elem ; p
9、b = Lb.elem ;Lc.listsize =Lc.length =La.length +Lb.length;pc= Lc.elem = (ElemType*) malloc( Lc.listsize*sizeof ( ElemType ); if (! Lc.elem)exit(OVERFLOW);/存储分配失败pa_last = La.elem +La.length-1 ;pb_last = Lb.elem +Lb.length-1 ; while ( pa= pa_last & pb= pb_last ) if ( *pa= *pb )*pc+ = *pa+;else*pc+ =
10、*pb+;while ( pa= pa_last ) *pc+ = *pa+;/将 La 的剩余元素插入while ( pb= pb_last )*pc+ = *pb+;/将 Lb 的剩余元素插入参考答案 ：上述算法将归并后的数据元素存放在新的顺序表Lc 中，顺序表 La 和 Lb 不用变化， 只是把顺序表 La 和 Lb 中的数据元素一个个新插入到顺序表 Lc 的末尾，最多有 La.length +Lb.length 个数据元素要插入到顺序表 Lc 中，所以该算法的时间复杂度是 O(La.length+Lb.length) 。2、已知顺序表La 和 Lb，现在将存在于顺序表Lb 中而不存在于
11、顺序表La 中的数据元素插入到顺序表La 中去（如果发现顺序表La 的空间不够， 则需要扩大顺序表La）。具体做法是从顺序表Lb 中依次取得每个数据元素，并依值在顺序表La 中进行查访，若不存在，则插入之 -这种操作称为顺序表的合并操作。请阅读下列顺序表的合并操作算法代码，分析该算法的时间复杂度，并作简要解释。void union(List &La, List Lb)ElemType e;intLa_len, Lb_len, i;La_len = ListLength(La);/ 求顺序表的长度Lb_len = ListLength(Lb);for (i = 1;i = Lb_len;i+)G
12、etElem(Lb, i, e); / 依 次取Lb 中第 i 个数据元素赋给eif (!LocateElem(La, e, equal ) / 依值 e 在顺序表La 中进行查访ListInsert(La, +La_len, e);/La中不存在和e 相同的数据元素，则在La 的最后面插入参考答案 ：在顺序表La 中查访是否存在和Lb 中第 i 个数据元素（值为e）相同的数据元素的方法是: 令e 和 La 中的数据元素逐个比较。若La 中存在和e 相同的数据元素ai，则比较次数为i(1 i La.lengt否h),则为 La.length ，即算法LocateElem 的时间复杂度为O(La
13、.length) 。而最多有 Lb.length 个数据元素要插入到顺序表La 中，由此，算法union 的时间复杂度为:O(La.lengthLb.length)。3、线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素； 其二，由于难以估计， 必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三， 表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。参考答案 ：链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、 删除不需移动元素，只修改指针，时间复杂度为O(1) ；其次，不需要预先分配空间，可根据需要动态申请空间；其三，
14、 表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。四、算法分析题1、下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedef struct node int data;struct node *next; linklist; void linklistcreate(linklist _ * &head )for (i=1;i&d(pata);p-next= NULL ; if(i=1)head=q=p;else q-next=p;_ q=p;2、下面的结构体定义了双向链表的节点结构。请分析如下程序
15、代码，填写其中缺少的语句代码：typedef struct node int data； struct node *last;struct node *next; Node;void deleteOne (Node *head, int target) Node *p = headnext; while(p != NULL)if(pdata != target)p = pnext; else if(pnext != NULL)pnextlast =plast;plastnext= pnext; free(p);3、说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首结点的关系
16、。参考答案 ：在线性表的链式存储结构中，针，头指针具有标识作用，头指针指链表的指针，若链表有头结点则是链表的头结点的指故常用头指针冠以链表的名字。头结点是为了使插入和删除等操作的统一、 方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点， 其操作与对其它结点的操作统一了。后边的第一个结点。首结点也就是第一元素结点，它是头结点五、算法描述题设有一带头结点的单链表,编程将链表颠倒过来。要求不用另外的数组或结点完成。参考答案：要实现带头结点的单链表的逆置， 通常作法是： 将工作指针指向第一个
17、元素结点， 将头结点的指针域置空。 然后将链表各结点从第一结点开始直至最后一个结点， 依次前插至头结点后， 使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。typedefstructnode intdata；假定结点数据域为整型。structnode*next ；node,*LinkedList；LinkedList creat （）LinkedList head ， pintx；head=（ LinkedList ） malloc （sizeof（ node） ； head-next=null ；/* 设置头结点 */scanf（“ %d”， &x ）；while （
18、 x!=9999 ）/* 约定输入9999 时退出本函数*/p= （ LinkedList ） malloc （ sizeof（ node）； p-data=x ；p-next=head-next ； /*将新结点链入链表*/ head-next=p ；scanf（ “ %d”， &x ）；return （ head）； 结束 creat 函数。LinkedList invert1 （ LinkedList head ）/* 逆置单链表 */ LinkedList p=head-next; /*p为工作指针 */ head-next=null ；while （ p!=null ） r=p-next ；/* 暂存 p 的后继 */p-next=head-next ； head-next=p ； p=r；return （ head）；/* 结 束 invert1 函 数 */void main （） LinkedList la；la=creat( ）；/* 生成单链表 */ la=invert1 （ la）； /* 逆置单链表 */