《数据结构(第二版)习题答案第3章.doc》由会员分享，可在线阅读，更多相关《数据结构(第二版)习题答案第3章.doc（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构(第二版)习题答案第3章.精品文档.3.1 选择题第 3 章线性表的链式存储（1）两个有序线性表分别具有 n 个元素与 m 个元素且 nm，现将其归并成一个有序表，其最少的比较次数是（A ）。AnBmCn 1Dm + n（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（C）。Ap-next=NULL Bp=NULL Cp-next=head Dp=head（3）在带头结点的单链表中查找 x 应选择的程序体是（C ）。Anode *p=head-next; while (p & p-info!=x) p=p-next;
2、if (p-info=x) return p else return NULL;Bnode *p=head; while (p& p-info!=x) p=p-next; return p;Cnode *p=head-next; while (p&p-info!=x) p=p-next; return p;Dnode *p=head; while (p-info!=x) p=p-next ; return p; （4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D ）。A必须是连续的C一定是不连续的B部分地址必须是连续的D连续不连续都可以（5）在一个具有 n 个结点的有序单链表中
3、插入一个新结点并保持单链表仍然有序的时间复杂度是（B ）。AO(1) BO(n)CO(n2)DO(nlog2n)（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D ）。A仅修改队头指针C队头、队尾指针都要修改B仅修改队尾指针D队头,队尾指针都可能要修改（7）若从键盘输入 n 个元素，则建立一个有序单向链表的时间复杂度为（B ）。AO(n)BO(n2)CO(n3)DO(n log2n)（8）下面哪个术语与数据的存储结构无关（D ）。A顺序表B链表C散列表D队列（9）在一个单链表中，若删除 p 所指结点的后续结点，则执行（A ）。Ap-ne
4、xt=p-next-next; Bp=p-next; p-next=p-next-next; Cp-next=p-next; Dp =p-next-next;（10）在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（ B ）。As-next=p;p-next=s; Bs-next=p-next;p-next=s;Cs-next=p-next;p=s; Dp-next=s;s-next=p;3.2 设计一个算法，求一个单链表中的结点个数。【答】：单链表存储结构定义如下（相关文件：linklist.h）#include 11 #include typedef s
5、truct node int data; struct node *next;linknode;typedef linknode *linklist;/*尾插法创建带头结点的单链表*/linklist creatlinklist() linklist head,r,x,s; head=r=(linklist)malloc(sizeof(linknode); printf(n 请输入一组以 0 结束的整数序列：n); scanf(%d,&x); while (x) s=(linklist)malloc(sizeof(linknode); s-data=x; r-next=s; r=s; scan
6、f(%d,&x); r-next=NULL; return head;/*输出带头结点的单链表*/ void print(linklist head) 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 设计一个算法，求一个带头结
7、点单链表中的结点个数。【答】：带头结点的单链表的存储结构定义同题 3.2，实现本题功能的算法程序如下（3_3.c）#include linklist.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 个数据时，产生的输出结果如下
8、图所示：3.4 设计一个算法，在一个单链表中值为 y 的结点前面插入一个值为 x 的结点。即使值为 x 的新结点成为值为 y 的结点的前驱结点。【答】：#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-data!=y) pre=p; p=p-next; if (p)/*找到了值为 y 的结点*/ s=(linklist)malloc(sizeof(linknode)
9、; s-data=x; s-next=p; pre-next=s; void main()linklist head; int y,x;/*测试程序*/ head=creatlinklist(); /*创建单链表*/ print(head); /*输出单链表*/ printf(n 请输入 y 与 x 的值:n); scanf(%d %d,&y,&x); insert(head,y,x); print(head); 程序的一种运行结果如下图所示：3.5 设计一个算法，判断一个单链表中各个结点值是否有序。【答】：#include linklist.h int issorted(linklist h
10、ead,char c)/*当参数 c=a时判断链表是否为升序，当参数 c=d是判断链表是否为降序*/ int flag=1; linklist p=head-next; switch (c) case a:/*判断带头结点的单链表 head 是否为升序*/14 while (p &p-next & flag) if (p-datanext-data) p=p-next; else flag=0; break; case d:/*判断带头结点的单链表 head 是否为降序*/ while (p &p-next & flag) if (p-data=p-next-data) p=p-next; e
11、lse flag=0; break; return flag;int main() /*测试程序*/ linklist head; head=creatlinklist(); print(head); if (issorted(head,a) printf(单链表 head 是升序排列的！n); else if (issorted(head,d) printf(单链表 head 是降序排列的！n); else printf(单链表 head 是无序的！n);程序运行时的三种输出结果如下图所示：3.6 设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。【答】：#include link
12、list.h void verge(linklist head)/*本函数的功能是就地倒置带头结点的单链表*/ 15 linklist p,q; p=head-next; head-next=NULL; while (p) q=p; p=p-next; /*每次从原表取一个结点插入到新表的最前面*/ q-next=head-next; head-next=q;int main()linklist head; /*测试函数*/ head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ verge(head); /*就地倒置单链表*/ prin
13、t(head); /*输出倒置后的单链表*/3.7 设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。【答】：#include linklist.h linklist sprit(linklist head)/*将带头结点的单链表 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
14、=1)pre-next=p-next;r-next=p; r=p; p=pre-next;else pre=p;p=p-next;/*删除奇数值结点*/*保留偶数值结点*/16r-next=NULL; return L;/*置链表结束标记*/int main()linklist head,L;/*测试函数*/ head=creatlinklist(); /*创建单链表*/ print(head); /*输出原单链表*/ L=sprit(head); /*分裂单链表 head*/ printf(n 原单链表为:n); print(head); /*输出倒置后的单链表*/ printf(n 分裂所
15、得奇数单链表为:n); print(L);本程序的一组测试情况如下图所示。3.8 设计一个算法，对一个有序的单链表，删除所有值大于 x 而不大于 y 的结点。【答】：#include linklist.h void deletedata(linklist head,datatype x,datatype y) /*删除带头结点单链表中所有结点值大于 x 而不大于 y 的结点*/linklist pre=head,p,q;p=head-next;初始化*/ while (p & p-datanext;while (p & p-datanext;q=pre-next;pre-next=p;pre=
16、q-next;/*删除大于 x 而小于 y 的结点*/17while (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,&x,&y);deletedata(head,x,y);print(head); /*输出删除后的单链表*/3.9 设计一个算法，在双链表中值为 y 的结点
17、前面插入一个值为 x 的新结点。即使值为 x 的新结点成为值为 y 的结点的前驱结点。【答】：首先定义双链表的数据结构，相关文件 dlink.h，内容如下：typedef int datatype; /*预定义的数据类型*/typedef struct dlink_node /*双链表结点定义*/ datatype data; struct dlink_node *llink,*rlink; dnode; typedef dnode* dlinklist; /*双链表结点指针类型定义*/*尾插法创建带头结点的双链表*/dlinklist creatdlinklist(void) dlinkli
18、st head,r,s; datatype x; head=r=(dlinklist) malloc(sizeof(dnode); /*建立双链表的头结点*/ head-llink=head-rlink=NULL; printf(n 请输入双链表的内容：（整数序列，以 0 结束）n); scanf(%d,&x); while (x) /*输入结点值信息，以 0 结束*/ s=(dlinklist ) malloc(sizeof(dnode); s-data=x; s-rlink=r-rlink; /*将新结点 s 插入到双链表链尾*/ 18 s-llink=r; r-rlink=s; r=s;
19、 scanf(%d,&x); return head;/*输出双链表的内容*/void print(dlinklist head) dlinklist p; p=head-rlink; printf(n 双链表的内容是：n); while (p) printf(%5d,p-data); p=p-rlink; 本题的求解程序如下：#include #include dlink.h void insertxaty(dlinklist head,datatype y,datatype x) dlinklist s,p; /*首先在双链表中找 y 所在的结点，然后在 y 前面插入新结点*/ p=hea
20、d-rlink; while (p & p-data!=y) p=p-rlink; if (!p) printf(n 双链表中不存在值为 y 的结点,无法插入新结点!n); else /*插入值为 x 的新结点*/ s=(dlinklist)malloc(sizeof(dnode); s-data=x; s-rlink=p; s-llink=p-llink; p-llink-rlink=s; p-llink=s;void main() dlinklist head; datatype x,y;/*测试函数*/19 head=creatdlinklist(); print(head); prin
21、tf(n 请输入要输入的位置结点值 y:n); scanf(%d,&y); printf(n 请输入要输入的结点值 x:n); scanf(%d,&x); insertxaty(head,y,x);/*在值为 y 的结点前插入值为 x 的新结点*/ print(head);/*输出新的双链表*/ getch(); 本程序的一组测试情况如下图所示。3.10 设计一个算法，从右向左打印一个双链表中各个结点的值。【答】：本题的双链表定义同题 3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实现如下：#include #include dlink.h void vprint(dlinklis
22、t head) /*递归方法从右向左打印双链表的值*/ if (head-rlink) vprint(head-rlink); printf(%5d,head-rlink-data); void main() dlinklist head;/*测试函数*/ head=creatdlinklist(); print(head); printf(n 从右向左打印的双链表的内容是:n);20 vprint(head); getch(); 本程序的一组测试情况如下图所示。3.11 设计一个算法，将一个双链表改建成一个循环双链表。【答】：#include #include dlink.h /*将一个双链
23、表改成循环双链表*/void dlinktocdlink(dlinklist head) dlinklist r; r=head; while (r-rlink) r=r-rlink; head-llink=r; r-rlink=head; /*寻找尾结点*/void printcdlink(dlinklist head) /*打印双链表*/ dlinklist p; p=head-rlink; while (p!=head) printf(%5d,p-data); p=p-rlink;int main() dlinklist head;/*测试函数*/ head=creatdlinklist(); dlinktocdlink(head); printf(n 循环双链表的内容是：n); printcdlink(head);21