习题一(第一章到第三章)答案.pdf

《习题一(第一章到第三章)答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.一线性表存储在带头结点的双向循环链表中，L为头指针。将双向循环链表结点的数据域按值自小到大排序，成为非递减有序双向循环链表,如下算法：voidunknown(BNODETP*L){…p=L->next;q=p->next;r=q->next；while(q!=L){while(p!=L)&&(p->data>q->data)p=p->prior；q->prior->next=r；(1)______；q->next=p->next；q->prior=p；(2)______；(3)______；q=r；p=q->prior；(4)______；}}(1)r->prior=q->prior;∥将

2、q结点摘下，以便插入到适当位置。(2)p->next->prior=q;∥（2）（3）将q结点插入(3)p->next=q;(4)r=r->next;或r=q->next;∥后移指针，再将新结点插入到适当位置。2、栈和队列的共同特点是只允许在端点插入和删除元素。3、向一个栈顶指针为HS的链中插入一个s所指结点时，则执行：s->next=HS;HS=s;4、向一个栈顶指针为HS的链中删除一个s所指结点时，用x保存被删除结点的值，则执行：x=HS->data;HS=HS->next;5、判定一个队列QU（最多元素为MaxSize）为空的条件是:QU->front==QU->rear。6、判定一个队

3、列QU（最多元素为MaxSize）为满队列的条件是:QU->rear-QU->front==MaxSize。7、判定一个循环队列QU（最多元素为MaxSize）为空的条件是:QU->front==QU->rear。8、判定一个循环队列QU（最多元素为MaxSize）为满队列的条件是:QU->front==(QU->rear+1)%MaxSize。9、循环队列用数组A[0,m-1]存放其元素，已知其头为指针分别是front和rear，则当前队列元素个数是：(rear-front+m)%m。10、在一个链队列中，假设f和r分别指向对头和队尾指针，则插入s所指结点的操作是：r->next=s;r=s

4、11、栈的静态顺序存储结构为#defineMAXSTACK500;typedefstructseqstack{ElemTypedata[MAXSTACK];inttop;}SQSTACK;SQSTACKss;这时设置栈底位置固定在数组最低段，即top=-1表示栈空，栈中存放元素的位置是事实ss.data[0],…,ss.data[MAXSTACK-1]共MAXSTACK个元素，元素进栈ss.top加1，出栈减1，问：栈空的条件是：ss.top=-1，栈满的条件是：ss.top=MAXSTACK-1，栈顶元素的表达式是：ss.data[ss.top]，栈底元素的表达式是：ss.data[0]。1

5、2、在一个具有n个结点的有序单链表中，插入一个新结点并仍然有序的时间复杂度为O(n)。13、给定有n个元素的向量，建立一个有序单链表的时间复杂度是O(n2)。14、数据的逻辑结构只抽象反映数据元素的逻辑关系；数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。15．计算机执行下面的语句时，语句s的执行次数为(n+3)(n-2)/2。FOR(i=l；i=i;j--)s;16.对于给定的n个元素,可以构造出的逻辑结构有集合线性结构树形结构图状结构四种17.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度18.一个算法具有5个特性:（1）

6、有穷性（2）确定性（3）可行性。，有零个或多个输入、有一个或多个输出。19.线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2。20.带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L21.在单链表L中，指针p所指结点有后继结点的条件是：p->next!=null22.带头结点的双循环链表L为空表的条件是：L->next==L&&L->prior==L23.下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。voi

7、dreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q->next=p；p=q；(2)___;}(3)_____;}(1)L=L->next;∥暂存后继(2)q=L;∥待逆置结点(3)L=p;∥头指针仍为L24.对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedefstruct