《Ch2习题参考答案.docx》由会员分享，可在线阅读，更多相关《Ch2习题参考答案.docx（11页珍藏版）》请在三一办公上搜索。
1、Ch2习题参考答案第二章 习题参考答案 一、 判断题 1线性表的逻辑顺序与存储顺序总是一致的。(ERROR) 2顺序存储的线性表可以按序号随机存取。(OK) 3顺序表的插入和删除一个数据元素，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7线性表的链式存储结构优于顺序存储结构。 8在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
2、 9线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二、 单选题、 (请从下列A，B，C，D选项中选择一项) 11线性表是( A ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 12对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 (A) n/2 (B) (n+1)/2 (C) (n 1)/2 (D) n 13线性表采用链
3、式存储时，其地址( D ) 。 (A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 14用链表表示线性表的优点是 。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 1 16. 循环链表的主要优点是( D ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他
4、的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 17. 下面关于线性表的叙述错误的是( B )。 (A) 线性表采用顺序存储，必须占用一片地址连续的单元； (B) 线性表采用顺序存储，便于进行插入和删除操作； (C) 线性表采用链式存储，不必占用一片地址连续的单元； (D) 线性表采用链式存储，便于进行插入和删除操作； 18. 单链表中，增加一个头结点的目的是为了。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 方便运算的实现 (D) 说明单链表是线性表的链式存储 19. 若某线性表中最常用的操作是在最后一个元素
5、之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表 20. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用存储方式最节省运算时间。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 21. 一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是_。 A. 110 B. 108 C. 100 D. 120 答：B 第5个元素的地址=100+2*(5-1)=108 22. 不带头结点的单链表head为空的判定条
6、件是_。 A. head = = NULL; B. head-next = = NULL; C. head-next = = head; D. head! = NULL; 答：A 23. 带头结点的单链表head为空的判定条件是_。 A. head = = NULL; B. head-next = = NULL; C. head-next = = head; D. head! = NULL; 答：B 24. 在循环双链表的p所指结点之后插入s所指结点的操作是_。 A. p-right=s; s-left=p; p-right-left=s; s=-right=p-right; B. p-rig
7、ht=s; p-right-left=s; s-left=p; s-right=p-right; C. s-left=p; s-right= p-right; p-right=s; p-right-left=s; D. s-left=p; s-right=p-right; p-right-left=s; p-right=s; 答：D 25. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行_。 A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p; 2 C. q-next=s; s-next=p; D
8、. p-next=s; s-next=q; 答：C 26. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。(参见网上讲义：1.4.2例1_5) A. n; B. n/2; C. (n-1)/2; D. (n+1)/2; 答：D 27. 给定有n个结点的向量，建立一个有序单链表的时间复杂度_。 A. O(1); B. O(n); C. O(n2); D. O(nlog2n); 答：C 三、 填空题 28. 在一个长度为n的向量中的第i个元素(1in)之前插入一个元素时，需向后移动_个元素。 答：n-i+1 29. 在一个长度为n的向量中删除第i个元素(
9、1in)时，需向前移动_个元素。 答：n-i 30在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作： s-next=_p-next_; p-next=s; t=p-data; p-data=_s-data_; s-data=_t_; 四、算法设计题： 31. 有一个单链表，其头指针为head，编写一个函数计算数据域为x的结点个数。 解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下： int count (head, x) node *head; ElemType x; /*本题中head 为链头指针，不含头结点
10、*/ node *p; int n=0; p=head; while (p!=NULL) if (p-data= =x) n+; 3 p=p-next; return(n); 32. 有一个有序单链表，表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。 解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找出该结点的位置，最后插入该结点。实现本题功能的函数如下： node *insertorder(head, x) node *head; ElemType x; /*本题中head 为链头指针，不含头结点*/ node
11、 *s, *p, *q; s=(node *)malloc(sizeof(node); /* 建立一个待插入的结点*/ s-data=x; s-next=NULL; if (head= =NULL xdata) /* 若单链表为空或x小于第一个结点的data域*/ s-next=head; /* 则把s结点插入到表头后面*/ head=s; else q=head; /*为s结点寻找插入位置,p指向待比较的结点,q指向p的前驱结点*/ p=q-next; while (p!=NULL & xp-data) /* 若x小于p所指向的data域值*/ if (x p-data) q=p; p=p-
12、next; s-next = p; /* 将s结点插入到q和p之间*/ q-next=s; return(head); 33 编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B4 链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。 解：其函数是将单链表A中的所有偶数序号的结点删除，并在删除时把这些结点链接起来构成单链表B。实现本题功能的函数如下： void disa(a, b) node *a, *b; /*本题中a、b为链头指针，不含头结点*/ node *r, *p, *q; p=a; b=a-ne
13、xt; r=b; while (p!=NULL & p-next!=NULL) q = p-next; /* q指向偶数序号的结点*/ p-next=q-next; /* 将q从原A中删除掉*/ r-next=q; /* 将q结点链接到B链表的末尾*/ r=q /* r总是指向B链表的最后一个结点*/ p=p-next; /*p指向原链表A中的奇数序号的结点*/ r-next=NULL; /* 将生成B链表中的最后一个结点的next域置空*/ 34. 假设有两个已排序的单链表A和B，编写一个函数将它们合并成一个链表C而不改变其排序性。 解：这里采用链表合并的方法，设原两链表的头指针分别为p和q
14、，每次比较p-data和q-data的值，把值较小的结点作为新链表的结点，这一过程直到一个链表为空为止。当一个链表为空而另一个链表不为空时，只要将不空的链表指针赋给新链表中最后一个结点的指针即可。实现本题功能的函数如下： node *mergelink(p, q) node *p, *q; /*本题中p、q为链头指针，不含头结点。*/ /*但为操作方便，过程中要为链表C建立一个临时头结点。*/ node *h, *r; h=(node *)malloc(sizeof(node); /* 建立头结点*/ h-next=NULL; r=h; while (p!=NULL & q!=NULL) if
15、 (p-datadata) r-next=p; r=p; p=p-next; 5 else r-next=q; r=q; q=q-next; if (p= =NULL) /* 若A链表的结点已取完，则把B的所有余下的结点链接C中*/ r-next=q; if (q= =NULL) /*若A链表的结点已取完，则把B的所有余下的结点链接C中*/ r-next=p; /*下面三句要去掉链表C的头结点，如果不想去掉，则不要这三句*/ p=h-next; h=h-next; free(p); return h; 35设A=和B=均为顺序表，A和B分别为A和B中除去最大共同前缀后的子表，B=，则两者中最大
16、的共同前缀为，在A=B=空表，则A=B；若A=空表，而B空表，或者两者均不为空表，且A的首元小于B的首元，则AB。试写一个比较A，B大小的算法。 36. 设有一个用向量表示的线性表L，要求写出一个将该表逆置的过程，并允许在原表的存储空间外再增加一个附加的工作单元。(朱儒荣, C语言版数据结构考研例题) 解：用数据类型描述Seqlist顺序存储结构： vold converts(seqlist L) k=L.length; m = k/2; for(i = 0;im;i+) x = L.elementi; L.elementi = L.elementk-i-1; L.elementk-i-1 =
17、 x; / converts 讨论：这个算法过程只须进行数据元素的交换操作，其主要时间花费在for循环上，整个算法的时间复杂度为O(k)。 6 37. 已知两个整数集合A和B，它们的元素分别依元素值递增有序存放在两个单链表HA和HB中，编写一个函数求出这两个集合的并集C,并要求集合C的链表的结点仍依元素值递增有序存放。(提示：求并集不是归并!) 38 已知两个顺序表A和B分别表示两个集合，其元素递增排列，编写一个函数求出A和B的交集C，要求C同样以元素递增的顺序表形式存储。 void SqList_Intersect(SqList A,SqList B,SqList &C)/求元素递增排列的线性表A和B的元素的交集并存入C中 i=0;j=0;k=0; while(A.elemi&B.elemj) if(A.elemiB.elemj) j+; if(A.elemi=B.elemj) C.elemk+=A.elemi; /当发现了一个在A,B中都存在的元素, i+;j+; /就添加到C中 /while /SqList_Intersect 7
