2012考研专业课自测试题及答案计算机组成原理

顺序存储结构,线性表(List),部分操作的实现,逻辑结构和主要操作,小结和作业,逻辑结构,Da1, a2, , ai ,an,S |ai-1 ,ai D, i=2,.,n ,主要操作,InitList(&L)DestroyList(&L)ClearList(&L),ListInsert(&L, i, e)ListDelete(&L, i, &e),LocateElem(L, e, Compare()GetElem(L, i, &e)PriorElem(L, cur_e, &pre_e)NextElem(L, cur_e, &next_e),ListEmpty(L)ListLength(L),顺序存储结构,用一组地址连续的存储单元依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址(基地址),定义数据类型 SqList,#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize; SqList;,使用 SqList,SqListL;,elem,length,listsize,int a;,elem,length=6,listsize= 100,L,使用 SqList,部分操作的实现,InitList(&L),DestroyList(&L),ListInsert(&L, i, e),ListDelete(&L, i, &e),GetItem(L, i, &e),ListMerge(&La, Lb),ListMerge(La, Lb, &Lc),InitList功能,过程：1、申请存储空间，首地址存放到elem2、length=03、listsize= LIST_INIT_SIZE,原型：Status InitList( SqList &L),作用：给elem，length和listsize赋值,InitList功能,0,100,elem,length,listsize,InitList-申请内存,elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType),#include ,0,elem,1100,elem,没有获得内存，出错,InitList,Status InitList(SqList &L),L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);,if(!L.elem) return(OVERFLOW);,L.length=0;,L.listsize=LIST_INIT_SIZE;,return(OK);,DestroyList功能,过程：1、释放elem指示的连续存储单元2、L.length=03、L.listsize=0,原型：Status DestroyList( SqList &L),作用：释放L以前申请的内存,DestroyList功能,6,100,0,0,DestroyList,Status DestroyList(SqList &L),free(L.elem);,L.length=0;,L.listsize=0;,return(OK);,GetIem功能,过程：1、判断i的合法性2、e=ai,原型：Status GetItem( SqList L, int i, ElemType &e),作用：取出ai的值,GetItem功能,GetItem(L, 6, e),e,GetIem合法性判断,线性表中L有length个元素 a1 a2 a3 . alength,数据元素的下标为1， 2，length,1ilength,GetItemai的位置,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,数据元素,elem,a1 elem + 0a2 elem + 1a3 elem + 2,ai elem + i - 1,e=*(elem + i 1),GetItemai的位置,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,数据元素,elem0,a1 elem0a2 elem1a3 elem2,ai elem i 1,e=elem i 1,elem1,elem9,GetItem,Status GetItem(SqList L, int i, ElemType / e=*(L.elem + i 1) return (OK),ListInsert功能,原型：Status ListInsert( SqList &L, int i, ElemType e),作用：把e插入线性表，作为第i个数据元素,ListInsert功能,逻辑结构的变化, , ,(a1, , ai-1, ai, , an) (a1, , ai-1, e, ai, , an),ListInsert功能,存储结构的变化,ListInsert(L, 3, e),6,length,7,length,ListInsert功能,过程：1、判断i的合法性2、移动3、赋值4、length+,ListInserti的合法性,1i8,一般的 1ilength+1,ListInsert移动,6,length,7,length,a7a6a6a5a5a4a4a3,ak+1=ak,k=length i,ListInsert移动,方法一：数组元素,j=L.length-1;,L.elemi-1=e;,ak+1 = ak,k=length i,While( j=i-1) L.elemj+1=L.elemj; j-;,for(int j=L.length;j=i;j+) L.elemj= L.elemj-1;L.elemi-1=e;,ListInsert移动,q=L.elem + (i-1); p=L.elem + L.length-1while(p=q) *(p+1)=*p;p-;,方法二：移动指针,q指向了ai,P开始时指向了alength,*q=e;,ak+1=ak,k=length i,ListInsert移动,q=L.elem + (i-1); for(p=L.elem + L.length-1; p=q; p-) *(p+1)=*p;*q=e;,ListInsert(L, 5, 66),L.length-1,0,87,56,42,66,42,56,87,ListInsert移动,7,7,表满的条件？,length=listsize,10,ListInsert移动,if(L.length = L.listsize) newbase = realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) return(OVERFLOW); L.elem=newbase; L.listsize +=LISTINCREMENT;,ListInsert,Status ListInsert(SqList &L, int i, ElemType e),if( i L.length+1) return(ERROR);,if( L.length = = L.listsize) newbase = realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) return(OVERFLOW); L.elem=newbase; L.listsize +=LISTINCREMENT;,ListInsert,q=L.elem + (i-1); p=L.elem + L.length-1;while( p=q) *(p+1)=*p; p-,*q=e; L.length+;,return(OK);,移动,赋值,长度增加,for(int j=L.length-1;j=i-1;j+) L.elemj+1= L.elemj;L.elemi-1=e;+L.length;,ListInsert,1、在什么情况下，移动次数最少，最少移动次数是多少？,2、在什么情况下，移动次数最多，最多移动次数是多少？,3、在插入每个位置的概率相同的情况下，移动次数的期望值是多少？,List Delete功能,原型：Status ListDelete( SqList &L, int i, ElemType &e),作用：取出线性表L的第i个数据元素的值，并删除,ListDelete功能,逻辑结构的变化, ,(a1, , ai-1, ai, ai+1, an) (a1, , ai-1, ai+1, , an),ListDelete功能,存储结构的变化,ListDelete(L, 3, e),6,length,5,length,List Delete功能,过程：1、判断i的合法性2、取值3、移动4、length-,ListDeletei的合法性,1i7,一般的 1ilength,ListDelete移动,a3a4a4a5a5a6,ak-1=ak,k=i+1 length,6,length,5,length,ListDelete移动,p=L.elem + (i-1); e=*p;q=L.elem + L.length-1;for(+p; p=q; p+) *(p-1) =*p;,方法一：移动指针,p指向了ai,q开始时指向了alength,p指向了ai+1,ListDelete移动,方法二：数组元素,j=i;while(j=L.length-1) L.elemj-1=L.elemj; j+;,ak-1=ak,k=i+1 length,ListDelete,Status ListDelete(SqList &L, int i, ElemType &e),if( i L.length) return(ERROR);,p=L.elem + i 1;,e=*p;,q=L.elem + L.length 1;,for(+p; p=q; p+) *(p-1) =*p;,L.length-;,return(OK);,e= L.elemi-1; for(int j=i;j=L.length-1;j+) L.elemj-1= L.elemj;-L.length;,ListDelete,1、在什么情况下，移动次数最少，最少移动次数是多少？,2、在什么情况下，移动次数最多，最多移动次数是多少？,3、在删除每个位置的概率相同的情况下，移动次数的期望值是多少？,ListMerge功能,原型：Status ListMerge( SqList &La, SqList Lb),作用：把Lb中的数据元素添加到La的表尾,注意：不破坏Lb表,ListMerge功能,a1 a2 a3 a4 a5 a6,b1 b2 b3,La,Lb,b1,b2,b3,ListMerge功能,过程：1、取出Lb的一个数据元素bi2、把bi插入到La的表尾3、重复1-2，使得i=1, 2, Lb.length,ListMerge,Status ListMerge(SqList &La, SqList Lb),for(int i=1; i=Lb.length; i+),GetItem(Lb, i, e);,code=ListInsert(La, La.length+1, e);,return(OK);,if(code != OK) return(ERROR);,ListMerge,Status ListMerge(SqList &La, SqList Lb),For (int i=1; i=Lb.length; i+),La.elemLa.length=Lb.elemi-1; La.length+;,return(OK);,if( La.listsize La.length+Lb.length) newbase = realloc(L.elem, (La.length+Lb.length)*sizeof(ElemType); if(!newbase) return(OVERFLOW); L.elem=newbase; L.listsize = La.length+Lb.length; ,ListMerge功能,原型：Status ListMerge( SqList La, SqList Lb, SqList &Lc),作用：把有序表La和Lb合并得到一个新的有序表,La: a1 a2 a3 am,Lb: b1 b2 b3 bn,Lc: c1 c2 c3 cm+nci=aj or ci=bk,ListMerge功能,1 3 6 10,2 8 9,La,Lb,1 2 3 6 8 9 10,Lc,ListMerge分析,1 3 6 10 11,2 8 9,La,Lb,La,1,2,3,6,8,9,10,11,ListMerge分析,分析：,1、首先建立空表Lc,2、从La和Lb中余下未处理的数据元素中选取最小的一个e,3、把e插入表尾,4、重复 n+m次2和3,ListMerge 分析,1、首先建立空表Lc,InitList(Lc);,2、pa和pb分别表示La和Lb中余下未处理的第一个数据元素（初始时pa=1, pb=1）,GetItem(La, pa, Ea); GetItem(Lb, pb, Eb);,if(EaEb) e=Ea; pa+;elsee=Eb;pb+;,ListMerge 分析,3、向Lc的表尾插入一个La和Lb中最小的数据元素