《数据结构(第二版)习题答案第3章》由会员分享，可在线阅读，更多相关《数据结构(第二版)习题答案第3章（11页珍藏版）》请在金锄头文库上搜索。
1、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; if (p-info=x) return p else return NULL;Bnode *p
2、=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 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B ）。AO(1) BO(n)CO(n2)DO
3、(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-next=p-next-next; Bp=p-next; p-next=p-next-next; C
4、p-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 struct node int data; struct node *next;linknode;
5、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; scanf(%d,&x); r-next=NULL; return head;/*输出带头结点的单链表*
6、/ 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 设计一个算法，求一个带头结点单链表中的结点个数。【答】：带头结点的单链表的存储结构定义同题 3.2，实现本题功能的算法程序
7、如下（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 个数据时，产生的输出结果如下图所示：3.4 设计一个算法，在一个单链表中值为 y 的结点前面插入一个值为 x 的结点。即使值
8、为 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); s-data=x; s-next=p; pre-next=s; void main()lin
9、klist 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 head,char c)/*当参数 c=a时判断链表是否为升序，当参数 c=d是判断链表是否为降序
10、*/ 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; else flag=0; break; return flag;int main() /*测试程序
11、*/ 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 linklist.h void verge(linklist head)/*本函数的功能是就地倒置带头结点的单链表*/ 15 linklist p,q; p=head-next;
