数据结构课后答案(高等教育出版社唐策善版)VIP免费

第一章绪论（参考答案） 1.3 (1) O(n ) (2) (2) O(n ) (3) (3) O(n ) (4) (4) O(n 1/2) (5) (5) 执行程序段的过程中，x ,y 值变化如下： 循环次数 x y 0（初始） 91 100 1 92 100 2 93 100 „„ „„ „„ 9 100 100 10 101 100 11 91 99 12 92 100 „„ „„ „„ 20 101 99 21 91 98 „„ „„ „„ 30 101 98 31 91 97 到y =0 时，要执行10*100 次，可记为O（10*y ）=O（n ） 1.5 2100 , (2/3)n , lo g2n , n 1/2 , n 3/2 , (3/2)n , n lo g2n , 2 n , n ! , n n 第二章 线性表(参考答案) 在以下习题解答中，假定使用如下类型定义： （1）顺序存储结构： #define MAXSIZE 1024 typedef int ElemType;// 实际上，ElemType可以是任意类型 typedef struct { ElemType data[MAXSIZE]; int last; // last表示终端结点在向量中的位置 }sequenlist; （2）链式存储结构（单链表） typedef struct node {ElemType data; struct node *next； }linklist; （3）链式存储结构（双链表） typedef struct node {ElemType data; struct node *prior,*next； }dlinklist; （4）静态链表 typedef struct {ElemType data; int next; }node; node sa[MAXSIZE]; 2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。 头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。 开始结点：即上面所讲第一个元素的结点。 2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。 2·3 void insert(ElemType A[],int elenum,ElemType x) // 向量 A目前有 elenum个元素，且递增有序，本算法将 x插入到向量 A中，并保持向量的递增有序。 { int i=0,j; while (i=i;j--) A[j+1]=A[j];// 向后移动元素 A[i]=x; // 插入元素 } // 算法结束 2·4 void rightrotate(ElemType A[],int ...