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

《考研专业课自测试题及答案计算机组成原理.ppt》由会员分享，可在线阅读，更多相关《考研专业课自测试题及答案计算机组成原理.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、顺序存储结构顺序存储结构线性表线性表(List)部分操作的实现部分操作的实现逻辑结构和主要操作逻辑结构和主要操作小结和作业小结和作业逻辑结构逻辑结构Da1,a2,ai,anS|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)ListLeng

2、th(L)顺序存储结构顺序存储结构 用一组地址连续地址连续的存储单元依次存放依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的起始地址(基地址)定义数据类型定义数据类型 SqList#defineLIST_INIT_SIZE 100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize;SqList;使用使用 SqListSqListL;Lelemlengthlistsizeint a;elemlength=6listsize=100L使用使用 SqList部分操作的实现部分操作的实现Ini

3、tList(&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赋值LInitList功能功能 0100elemlengthlistsizeInitList-申请内存申请内存elem=(ElemT

4、ype*)malloc(LIST_INIT_SIZE*sizeof(ElemType)#include 0elem1100elem没有获得内存，出错InitListStatus 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=

5、0原型：Status DestroyList(SqList&L)作用：释放L以前申请的内存LDestroyList功能功能 610000DestroyListStatus 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功能功能L10100a1a2a3a4a5a6a7a8a9a10GetItem(L,6,e)eGetIem合法性判断

6、合法性判断线性表中L有length个元素 a1 a2 a3 .alength数据元素的下标为1，2，length1ilengthGetItemai的位置的位置a1a2a3a4a5a6a7a8a9a10数据元素elema1 elem+0a2 elem+1a3 elem+2ai elem+i-1e=*(elem+i 1)GetItemai的位置的位置a1a2a3a4a5a6a7a8a9a10数据元素elem0a1 elem0a2 elem1a3 elem2ai elem i 1e=elem i 1elem1elem9GetItemStatus GetItem(SqList L,int i,Elem

7、Type&e)if(iL.length)return(ERROR);e=L.elemi-1;/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功能功能存储结构的变化a1 a2 e a3 a4 a5 a6a1 a2 a3 a4 a5 a6 ListInsert(L,3,e)6length7lengthLis

8、tInsert功能功能过程：1、判断i的合法性2、移动3、赋值4、length+ListInserti的合法性的合法性L7100a1a2a3a4a5a6a71i8一般的 1ilength+1ListInsert移动移动a1 a2 e a3 a4 a5 a6a1 a2 a3 a4 a5 a6 6length7lengtha7a6a6a5a5a4a4a3ak+1=akk=length iListInsert移动移动方法一：数组元素j=L.length-1;L.elemi-1=e;ak+1=akk=length iWhile(j=i-1)L.elemj+1=L.elemj;j-;for(int j=

9、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指向了aiP开始时指向了alength*q=e;ak+1=akk=length iListInsert移动移动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-10pppq87564266p21 18 30 75 42 5

10、6 87ListInsert移动移动L77a1a2a3a4a5a6a7a1a2a3a4a5a6a7表满的条件？length=listsize10ListInsert移动移动if(L.length=L.listsize)newbase =realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;ListInsertStatus ListInsert(SqList&L,int i,ElemType e

11、)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;ListInsertq=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

12、 j=L.length-1;j=i-1;j+)L.elemj+1=L.elemj;L.elemi-1=e;+L.length;ListInsert1、在什么情况下，移动次数最少，最少移动次数是、在什么情况下，移动次数最少，最少移动次数是多少？多少？2、在什么情况下，移动次数最多，最多移动次数是、在什么情况下，移动次数最多，最多移动次数是多少？多少？3、在插入每个位置的概率相同的情况下，移动次数、在插入每个位置的概率相同的情况下，移动次数的期望值是多少？的期望值是多少？List Delete功能功能原型：Status ListDelete(SqList&L,int i,ElemType&e)作用

13、：取出线性表L的第i个数据元素的值，并删除ListDelete功能功能逻辑结构的变化 (a1,ai-1,ai,ai+1,an)(a1,ai-1,ai+1,an)ListDelete功能功能存储结构的变化a1 a2 a4 a5 a6a1 a2 a3 a4 a5 a6 ListDelete(L,3,e)6length5lengtheList Delete功能功能过程：1、判断i的合法性2、取值3、移动4、length-ListDeletei的合法性的合法性L7100a1a2a3a4a5a6a71i7一般的 1ilengthListDelete移动移动a3a4a4a5a5a6ak-1=akk=i+1

14、 lengtha1 a2 a4 a5 a6a1 a2 a3 a4 a5 a6 6length5lengthListDelete移动移动p=L.elem+(i-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;p+)*(p-1)=*p;方法一：移动指针方法一：移动指针p指向了aiq开始时指向了alengthp指向了ai+1ListDelete移动移动方法二：数组元素j=i;while(j=L.length-1)L.elemj-1=L.elemj;j+;ak-1=akk=i+1 lengthListDeleteStatus ListDelete(SqList&L,int

15、 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;ListDelete1、在什么情况下，移动次数最少，最少移动次数是、在什么情况下，移动次数最少，最少移动次数是多少？多少？2、在什么情况下，移动次数最多，最多移动次数是、在什么情况下，移动次数最多，最多移动次数是多

16、少？多少？3、在删除每个位置的概率相同的情况下，移动次数、在删除每个位置的概率相同的情况下，移动次数的期望值是多少？的期望值是多少？ListMerge功能功能原型：Status ListMerge(SqList&La,SqList Lb)作用：把Lb中的数据元素添加到La的表尾注意：不破坏Lb表ListMerge功能功能a1 a2 a3 a4 a5 a6b1 b2 b3 LaLbb1b2b3ListMerge功能功能过程：1、取出Lb的一个数据元素bi2、把bi插入到La的表尾3、重复1-2，使得i=1,2,Lb.lengthListMergeStatus ListMerge(SqList&L

17、a,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);ListMergeStatus 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

18、(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 amLb:b1 b2 b3 bnLc:c1 c2 c3 cm+nci=aj or ci=bkListMerge功能功能1 3 6 10 2 8 9 LaLb 1

19、 2 3 6 8 9 10LcListMerge分析分析 1 3 6 10 11 2 8 9 LaLb Lapapb12368910papapapbpbpb11papaListMerge分析分析分析：1、首先建立空表Lc2、从La和Lb中余下未处理的数据元素中选取最小的一个e3、把e插入表尾4、重复 n+m次2和3ListMerge 分析分析1、首先建立空表LcInitList(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

20、;pb+;ListMerge 分析分析3、向Lc的表尾插入一个La和Lb中最小的数据元素ListInsert(Lc,Lc.length+1,e)4、如果paLa.length 并且pbLb.length 重复2-35、把La余下的插入Lc(把Lb余下的插入到Lc)ListMergeInitList(Lc);Status ListMerge(SqList La,SqList Lb,SqList&Lc)pa=1;pb=1;m=La.length;n=Lb.length;GetItem(La,pa,Ea);GetItem(Lb,pb,Eb);while(pa=m&pb=n)if(Ea=Eb)e=Ea

21、;pa+;else e=Eb;pb+;ListInsert(Lc,Lc.length+1,e);ListMergewhile(pa=m)GetItem(La,pa+,Ea);ListInsert(Lc,Lc.length+1,Ea)while(pb=n)GetItem(Lb,pb+,Eb);ListInsert(Lc,Lc.length+1,Eb)return(OK);小小 结结 逻辑结构逻辑结构 顺序存储结构顺序存储结构 主要操作的实现：主要操作的实现：InitList、DestroyList、ListInsert、ListDelete、GetItem、ListMerge 一片连续的存储区域一片连续的存储区域 预先分配预先分配 数组数组 复习和作业复习和作业作业：2.2(1,2)2.11，2.21复习：C语言中的指针