《大数据结构与算法》课后习题问题详解.doc

。(×)。(√),因为每次操作平均只有近一半的元素需要移动。(×),但同一线性表中的数据元素具有相同的特性,因此属于同一数据对象。(√),逻辑上相邻的两个元素在物理位置上并不一定相邻。(×),逻辑上相邻的元素在物理位置上不一定相邻。(√)。(×),插入和删除时移动元素的个数与该元素的位置有关。(√)。(√),要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。(×),又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。(×)。(×)[arrsize]的前elenum个分量中,且递增有序。试写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性,并且分析算法的时间复杂度。【提示】直接用题目中所给定的数据结构(顺序存储的思想是用物理上的相邻表示逻辑上的相邻,不一定将向量和表示线性表长度的变量封装成一个结构体),因为是顺序存储,分配的存储空间是固定大小的,所以首先确定是否还有存储空间,若有,则根据原线性表中元素的有序性,来确定插入元素的插入位置,后面的元素为它让出位置,(也可以从高下标端开始一边比较,一边移位)然后插入x,最后修改表示表长的变量。intinsert(datatypeA[],int*elenum,datatypex) /*设elenum为表的最大下标*/{if(*elenum==arrsize-1)return0; /*表已满,无法插入*/else{i=*elenum;while(i>=0&&A[i]>x) /*边找位置边移动*/{A[i+1]=A[i];i--;}A[i+1]=x; /*找到的位置是插入位的下一位*/(*elenum)++;return1; /*插入成功*/}}时间复杂度为O(n)。,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素。【提示】对顺序表A,从第一个元素开始,查找其后与之值相同的所有元素,将它们删除;再对第二个元素做同样处理,依此类推。voiddelete(Seqlist*A){i=0;while(i<A->last) /*将第i个元素以后与其值相同的元素删除*/ {k=i+1; while(k<=A->last&&A->data[i]==A->data[k]) k++; /*使k指向第一个与A[i]不同的元素*/ n=k-i-1; /*n表示要删除元素的个数*/ for(j=k;j<=A->last;j++) A->data[j-n]=A->data[j]; /*删除多余元素*/ A->last=A->last-n;i++; }},从一个给定的顺序表A中删除值在x~y(x<=y)之间的所有元素,要求以较高的效率来实现。【提示】对顺序表A,从前向后依次判断当前元素A->data[i]是否介于x和y之间,若是,并不立即删除,而是用n记录删除时应前移元素的位移量;若不是,则将A->data[i]向前移动n位。n用来记录当前已删除元素的个数。voiddelete(Seqlist*A,intx,inty) {i=0;n=0;while(i<A->last) {if(A->data[i]>=x&&A->data[i]<=y)n++; /*若A->data[i]介于x和y之间,n自增*/ elseA->data[i-n]=A->data[i]; /*否则向前移动A->data[i]*/ i++; }A->last-=n; },每个元素是一个字符,现存于向量R[n]中,试写一算法,使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间,元素移动次数最小。【提示】对线性表进行两次扫描,第一次将所有的字母放在前面,第二次将所有的数字放在字母之后,其它字符之前。intfch(charc) /*判断c是否字母*/{if(c>='a'&&c<='z'||c>='A'&&c<='Z') return(1);elsereturn(0); }intfnum(charc) /*判断c是否数字*/{if(c>='0'&&c<='9') return(1); elseret