第一章知识点：1.基本概念：数据结构分类、特点等：如线性结构，是数据元素之间存在一种（一对一关系）数据元素的概念（数据项）2.时空复杂度1、设有数据结构（D，R），其中D={d1,d2,d3,d4,d5,d6},R=r,r={(d1,d2),(d2,d3),(d3,d4),(d2,d5),(d3,d5)}试按照图论中的画法画出其逻辑结构图。2、称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和_【1】_的数量级相同。3.计算下面程序段的时间复杂度。x=0;for(i=1;inext=qB.p->next=q->nextC.p=q->nextD.p->next=q->next->next2、在一个头指针为head的带头结点单链表中，要向表头插入一个由指针p指向的结点,则应执行【4】p->next=head->next;、【5】head->next=p。4.在双链表中，在指针P所指结点前面插入一个结点S时的语句序列是：S->next=P;S->prior=P->prior;P->prior=S;____S->prior->next=S___；3.在双向链表指针p的结点前插入一个指针q的结点操作是（C）。A.p->Prior=q;q->Next=p;p->Prior->Next=q;q->Prior=p->Prior;B.p->Prior=q;p->Prior->Next=q;q->Next=p;q->Prior=p->Prior;C.q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;D.q->Prior=p->Prior;q->Next=p;p->Prior=q;p->Prior->Next=q;4.已知p结点是某双向链表的中间结点，要删除p结点的直接后继结点的语句序列是：DA.p->next->next->prior=p;p->next=p->next->next;q=p->next;free(q);B.q=p->next;p->next=p->next->next;p->next->next->prior=p;free(q);C.q=p->next;p->next->prior=p;p->next=p->next->next;free(q);D.q=p->next;p->next=p->next->next;p->next->prior=p;free(q);5.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___P->next==NULL________；r=s;r->next=null;。6.在单链表中，指针p所指结点为最后一个结点的条件是_Ls==NULL、ls=ls->link。7对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1),在给定值为x的结点后插入一个新结点的时间复杂度为O(n)___。8.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此顺序表也称为随机存取的数据结构。（A）1.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（E）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（F）在第i个结点后插入一个新结点（1≤i≤n）（G）删除第i个结点（1≤i≤n）（H）将n个结点从小到大排序9、线性链表不具有的特点是（A）。A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比10.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用(C)存储方式最节省时间。A.单链表B.双链表C.带头结点的双循环链表D.单循环链表11.带头结点的双循环链表L为空表的条件是__L->next=L->prior或L->next=L_____。12.不带头结点的单链表head为空的判定条件是head=NULL。13．一个带表头结点的单循环链表，指针P指向链的某一个结点，若P->next->next->next==P，则此链表的长度可能是0或2。14.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移...
