《数据结构(第二版)习题答案第3章[学习]》由会员分享，可在线阅读，更多相关《数据结构(第二版)习题答案第3章[学习]（11页珍藏版）》请在金锄头文库上搜索。
1、3.1 选择题 第 3 章 线性表的链式存储 （1）两个有序线性表分别具有n 个元素与m 个元素且n m，现将其归并成一个有序表， 其最少的比较次数是（A ）。 AnBmCn - 1Dm + n （2）非空的循环单链表head 的尾结点（由p 所指向）满足（C ）。 Ap-next=NULL Bp=NULL C p-next=head Dp=head （3）在带头结点的单链表中查找x 应选择的程序体是（C ）。 Anode *p=head-next; while (p if (p-info=x) return p else return NULL; Bnode *p=head; while (
2、p return p; Cnode *p=head-next; while (p return p; Dnode *p=head; while (p-info!=x) p=p-next ; return p; （4）线性表若采用链式存储结构时，要求存中可用存储单元的地址（D ）。 A必须是连续的 C一定是不连续的 B部分地址必须是连续的 D连续不连续都可以 （5）在一个具有n 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间 复杂度是（B ）。 AO(1) BO(n) CO(n 2) DO(nlog2n) （6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向
3、队 尾结点，则在进行删除操作时（ D ）。 A仅修改队头指针 C队头、队尾指针都要修改 B仅修改队尾指针 D队头 ,队尾指针都可能要修改 （7）若从键盘输入n 个元素，则建立一个有序单向链表的时间复杂度为（B ）。 AO(n) BO(n 2) CO(n 3) DO(n log2 n) （8）下面哪个术语与数据的存储结构无关（D）。 A顺序表B链表C散列表 D队列 （9）在一个单链表中，若删除p 所指结点的后续结点，则执行（A ）。 Ap-next=p-next-next; B p=p-next; p-next=p-next-next; Cp-next=p-next; D p =p-next-n
4、ext; （10）在一个单链表中，若p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行 （ B ）。 As-next=p;p-next=s; B s-next=p-next;p-next=s; Cs-next=p-next;p=s; D p-next=s;s-next=p; 3.2 设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下（相关文件：linklist.h ） #include 11 #include typedef struct node int data; struct node *next; linknode; typedef linknode *
5、linklist; /*尾插法创建带头结点的单链表*/ linklist creatlinklist() linklist head,r,x,s; head=r=(linklist)malloc(sizeof(linknode); printf(n 请输入一组以0 结束的整数序列：n); scanf(%d, while (x) s=(linklist)malloc(sizeof(linknode); s-data=x; r-next=s; r=s; scanf(%d, r-next=NULL; return head; /*输出带头结点的单链表*/ void print(linklist he
6、ad) linklist p; p=head-next; printf(List is:n); while(p) printf(%5d,p-data); p=p-next; printf(n); 基于上述结构定义，求单链表中的结点个数的算法程序如下： int count(linklist head) int c=0; linklist p=head; while (p) c+; 12 p=p-next; return c; 3.3 设计一个算法，求一个带头结点单链表中的结点个数。 【答】：带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c） #include li
7、nklist.h int count(linklist head) int c=0; linklist p=head-next; while (p) c+; p=p-next; return c; main() /* 测试函数 */ linklist head; head=creatlinklist(); print(head); printf(nLength of head is:%d,count(head); getch(); 当输入5 个数据时，产生的输出结果如下图所示： 3.4 设计一个算法，在一个单链表中值为y 的结点前面插入一个值为x 的结点。即使值为x 的 新结点成为值为y 的结
8、点的前驱结点。 【答】： #include linklist.h void insert(linklist head,int y,int x) /* 在值为y 的结点前插入一个值为x 的结点 */ linklist pre,p,s; pre=head; p=head-next; 13 while (p p=p-next; if (p)/* 找到了值为y 的结点 */ s=(linklist)malloc(sizeof(linknode); s-data=x; s-next=p; pre-next=s; void main() linklist head; int y,x; /* 测试程序 */
9、 head=creatlinklist(); /*创建单链表 */ print(head); /* 输出单链表 */ printf(n 请输入y 与 x 的值 :n); scanf(%d %d, insert(head,y,x); print(head); 程序的一种运行结果如下图所示： 3.5 设计一个算法，判断一个单链表中各个结点值是否有序。 【答】： #include linklist.h int issorted(linklist head,char c) /*当参数c=a时判断链表是否为升序，当参数c=d是判断链表是否为降序*/ int flag=1; linklist p=head
10、-next; switch (c) case a:/* 判断带头结点的单链表head 是否为升序 */ 14 while (p else flag=0; break; case d:/*判断带头结点的单链表head 是否为降序 */ while (p else flag=0; break; return flag; int main() /* 测试程序 */ linklist head; head=creatlinklist(); print(head); if (issorted(head,a) printf( 单链表head 是升序排列的！ n); else if (issorted(he
11、ad,d) printf( 单链表head 是降序排列的！ n); else printf( 单链表head 是无序的！ n); 程序运行时的三种输出结果如下图所示： 3.6 设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。 【答】： #include linklist.h void verge(linklist head) /* 本函数的功能是就地倒置带头结点的单链表*/ 15 linklist p,q; p=head-next; head-next=NULL; while (p) q=p; p=p-next; /*每次从原表取一个结点插入到新表的最前面*/ q-next=hea
12、d-next; head-next=q; int main() linklist head; /*测试函数 */ head=creatlinklist(); /*创建单链表 */ print(head); /* 输出原单链表 */ verge(head); /*就地倒置单链表 */ print(head); /* 输出倒置后的单链表*/ 3.7 设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的 结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。 【答】： #include linklist.h linklist sprit(linklist hea
13、d) /* 将带头结点的单链表head 中的奇数值结点删除生成新的单链表并返回*/ linklist L,pre,p,r; L=r=(linklist)malloc(sizeof(linknode); r-next=NULL; pre=head; p=head-next; while (p) if (p-data%2=1) pre-next=p-next; r-next=p; r=p; p=pre-next; else pre=p; p=p-next; /* 删除奇数值结点 */ /* 保留偶数值结点 */ 16 r-next=NULL; return L; /* 置链表结束标记 */ int
14、 main() linklist head,L; /* 测试函数 */ head=creatlinklist(); /* 创建单链表 */ print(head); /* 输出原单链表 */ L=sprit(head); /* 分裂单链表head*/ printf(n 原单链表为 :n); print(head); /* 输出倒置后的单链表*/ printf(n 分裂所得奇数单链表为:n); print(L); 本程序的一组测试情况如下图所示。 3.8 设计一个算法，对一个有序的单链表，删除所有值大于x 而不大于y 的结点。 【答】： #include linklist.h void dele
15、tedata(linklist head,datatype x,datatype y) /* 删除带头结点单链表中所有结点值大于x 而不大于y 的结点 */ linklist pre=head,p,q; p=head-next; 初始化 */ while (p while (p q=pre-next; pre-next=p; pre=q-next; /* 删除大于x 而小于y 的结点 */ 17 while (pre!=p) free(q); q=pre; pre=pre-next; /*释放被删除结点所占用的空间*/ void main() linklist head,L; datatypex,y; /* 测试函数 */ head=creatlinklist(); /*创建单链表 */ print(head); /* 输出原单链表 */ printf(n 请输入要删除的数据区间:n); scanf(%d%d, deletedata(head,x,y); print(head); /* 输出删除后的单链表*/ 3.9 设计一个算法，在双链表中值为y 的结点前面插入一个值为x 的新结点。即使值为x 的新 结点成为值为y 的结点的前驱结点。 【答】： 首先定义双链表的数据结构，相关文件dlin
