第PAGE\*Arabic\*MERGEFORMAT15页共NUMPAGES\*Arabic\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页第PAGE\*MERGEFORMAT15页共NUMPAGES\*MERGEFORMAT15页2022大学数据结构课后习题答案高校数据结构课后习题答案参考答案第一章、绪论一、选择题1B；2A；3B；4C；5C；6B；7C；8C；9D；10B。二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，随意多个；4、一对一，一对多，多对多；5、时间困难度，空间困难度；6、集合，线性结构，树形结构，图形结构；7、依次结构，链式结构，索引结构，散列结构；8、依次。三、问答题与算法题1、3；2、T1(n)=5n2-O(n);T2(n)=3n2+O(n);T3(n)=8n2+O(logn);T4(n)=1.5n2+O(n)。T4(n)较优，T3(n)较劣。3、见课本。其次章线性表一、选择题1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O(1),O(n)；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next==L且L->prior==L；8、依次。三、问答题与算法题1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指针动身可以找到链表中全部结点的信息。头结点：是附加在链表的第一个结点之前的一个特别结点，其数据域一般不存放信息。其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。首结点：是链表的第一个结点。2、(1)基于空间的考虑。当要求存储的线性表长度改变不大，易于事先确定其大小时，为了节约存储空间，宜采纳依次表；反之，当线性表长度改变大，难以估计其存储规模时，采纳动态链表作为存储结构为好。(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采纳依次表做存储结构为宜；反之，若须要对线性表进行频繁地插入或删除等的操作时，宜采纳链表做存储结构。并且，若链表的`插入和删除主要发生在表的首尾两端，则采纳尾指针表示的单循环链表为宜。3、尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的起先结点和终端结点都很便利，设一带头结点的单循环链表，其尾指针为rear，则起先结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)4、S=P->Prior;P->Prior=S->Prior;S->Prior->Next=P;S->Prior=P;S->Next=P->Next;P->Next=S;S->Next->Prior=S;5、:将起先结点摘下链接到终端结点之后成为新的终端结点，而原来的其次个结点成为新的起先结点，返回新链表的头指针6、15，26，51，37，48，,55。7、CreatList_L(LinkList&Lintn){L=(LinkList)molloc(sizeof(Lnode));//头结点L->next==NULL;q=L;For(i=1;i<=n;++i)41{P=(LinkList)molloc(sizeof(Lnode));Scanf(&(p->data));p->next=NULL;q->next=p;q=p