软件技术基础 习题课ppt课件.ppt

《软件技术基础 习题课ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题课－1ok4.设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。(2)i=0;1k=0;1do{k=k+10i;ni++;n}while(ij)n+1j++jelsei++;i}T(n)=2n+4+i+j=3n+5=O(n)习题－数据结构概述1.试描述头指针、头结点及开始结点的区别，并说明头指针和头结点的作用。头指针是指针：头指针是结点类型的指针，由于开始结点没有前驱，即开始结点的地址需要

2、存放，故设头指针存放开始结点的地址。头结点是结点：头结点是在链表的开始结点的前面附加的一个结点。开始结点是结点：开始结点是存放线性表的第一个元素的结点。头指针的作用：唯一确定一个单链表，链表可以用头指针来命名。头结点的作用：(1)使开始结点和其它结点的处理一致;(2)使空表和非空表的处理一致。习题－线性表2.有哪些链表可由一个尾指针来惟一确定？（即从尾指针出发能访问到链表上任何一个结点）。单循环链表双向链表双循环链表习题－线性表4.试用顺序存储结构设计一个算法，仅用一个辅助结点，实现将线性表中的结点循环右移k位的运算，并分析算法的时间复杂度。循环右移一次：习题－线

3、性表a1a2a3a4…ai…anana1a2a3…ai-1…an-1③②①循环右移k次：习题－线性表an-k+1…ana1…ai…an-kan-k…ana1…ai-1…an-k-1③②①算法实现：intmove(sequenlistL){datatypex;inti,j;for(i=k-1;i>=0;i--)/循环右移k次/{x=L->data[L->last];/将当前终端结点数据存放入x/for(j=L->last;j>0;j--)/将所有元素右移一个单位/L->data[j]=L->data[j-1];L->data[0]=x;/将x存放到开始结点/}ret

4、urn(1);}算法时间复杂度O(kn)习题－线性表注意移动元素的起始位置5.已知带头结点的动态单链表的结点是按整数值递增排列的试编写一个算法将值为x的结点插入到表L中，使表仍然有序。这道题主要考察单链表的查找算法和插入算法。#∧L…xqsp①②③④⑤习题－线性表算法实现：linklistinsert(linklistL,datatypex){linklists,p,q;p=(linklist)malloc(sizeof(linklist));/生成新结点/p->data=x;q=L;s=L->next;/保证q是s的直接前驱/while(s!=NULL){if(

5、s->data>x)break;else{q=s;s=s->next;}}p->next=s;/将p插入到q和s之间/q->next=p;returnL;}习题－线性表要不要单独考虑空表和插入到单链表的表尾情况7.试编写在带头结点的动态单链表上实现线性表操作LENGTH(L)的算法，并将长度写入头结点的数据域中。这个问题主要考察查找或求长度时，计数器初值的设定：带头结点i=0;p=head;i=1;p=head->next;习题－线性表算法实现：intLENGTH(linklistL){linklists;inti=0;s=L;while(s->next!=NUL

6、L){s=s->next;i=i+1}L->data=i;returni;}习题－线性表8.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，试编写算法将A表和B表合并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表）的结点空间。习题－线性表实现思路：(1)先将线性表A和B和并，再将合并的结果链表逆置；(2)先将线性表A和B逆置，再将逆置的A和B合并；(3)以线性表A为合并的线性表，逐个读入A和B的结点，根据结点值的大小关系，依次插入到合并表的头指针或头结点之后。习题－线性表这里我们采用第一种方法实现,分两步：第一步：将两个递

7、增的单链表合并成一个递增单链表,不另开辟空间。第二步：将单链表逆置。其实这两个算法前面已进过。习题－线性表第一步：将两个递增的单链表合并成一个递增单链表,不另开辟空间。算法考虑：以第一个单链表表示合并后的单链表,step1:初始化:p和q分别指向两个单链表A和B的开始结点,r指向A的头结点;step2:若p和q不空,则循环若p->data>q->data,将结点q插入到结点p前;若p->data=>q->data,指针p指向p的后继;step3:循环结束,判断指针q是否为空,若非空,将q后的结点链接到结点p后。习题－线性表lalbpu①②r③q⑤要保证插入后下一次

8、能够回到初