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

主要操作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)第1页/共59页顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素a1a2…ai-1ai…an线性表的起始地址(基地址)第2页/共59页定义数据类型SqList第3页/共59页LIST_INIT_SIZE

100#define#definetypedefLISTINCREMENT

10struct{*elem;length;listsize;ElemTypeintint}

SqList;使用SqListSqListL;Lelemlengthlistsizeint

a;第4页/共59页……elemlength=6listsize=

100L使用SqList第5页/共59页部分操作的实现InitList(&L)DestroyList(&L)ListInsert(&L,

i,

e)ListDelete(&L,

i,

&e)GetItem(L,

i,

&e)ListMerge(&La,

Lb)第6页/共59页ListMerge(La,

Lb,

&Lc)InitList—功能第7页/共59页原型：Status

InitList(SqList

&L)作用：给elem，length和listsize赋值过程：1、申请存储空间，首地址存放到elem2、length=03、listsize=LIST_INIT_SIZEInitList—功能……0第8页/共59页100LelemlengthlistsizeInitList-申请内存#include

<malloc.h>elem

=

(ElemType

*)

malloc(LIST_INIT_SIZE

*

sizeof(ElemType))0elem1100elem没有获得内存，出错第9页/共59页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);}第10页/共59页DestroyList—功能第11页/共59页原型：Status

DestroyList(SqList

&L)作用：释放L以前申请的内存过程：1、释放elem指示的连续存储单元

2、L.length=03、L.listsize=0LDestroyList—功能……06第12页/共59页10

0DestroyListStatus

DestroyList(SqList

&L){free(L.elem);L.length=0;L.listsize=0;return(OK);}第13页/共59页GetIem—功能第14页/共59页原型：Status

GetItem(SqList

L,int

i,ElemType

&e)作用：取出ai的值过程：1、判断i的合法性

2、e=aiGetItem—功能L10100a1

a2

a3

a4

a5

a6

a7

a8

a9a10GetItem(L,

6,

e)第15页/共59页eGetIem—合法性判断第16页/共59页线性表中L有length个元素a1

a2

a3

...alength数据元素的下标为1，2，…，length1≤i≤lengthGetItem—ai的位置a1

a2

a3

a4

a5

a6

a7

a8

a9a10数据元素elema1

elem

+

0a2

elem

+

1a3

elem

+

2第17页/共59页ai

elem

+

i

-

1e=*(elem

+

i

–

1)GetItem—ai的位置a1

a2

a3

a4

a5

a6

a7

a8

a9第18页/共59页a10数据元素elem[0]a1

elem[0]a2

elem[1]a3

elem[2]ai

elem[

i

–

1]e=elem[

i

–

1]elem[1]elem[9]GetItemStatus

GetItem(SqList

L,

int

i,

ElemType

&e){if(i<1

||

i>L.length)

return(ERROR);e=L.elem[i

-

1];

//

e=*(L.elem

+

i

–

1)return

(OK)}第19页/共59页ListInsert—功能第20页/共59页原型：Status

ListInsert(SqList

&L,int

i,ElemType

e)作用：把e插入线性表，作为第i个数据元素ListInsert—功能第21页/共59页<ai-1,

ai>→

<ai-1,

e>,

<e,

ai>逻辑结构的变化(a1,

…,

ai-1,

ai,

…,

an)

→

(a1,

…,

ai-1,

e,

ai,

…,

an)ListInsert—功能a1

a2

e

a3

a4

a5

a6a1

a2

a3

a4

a5

a66存储结构的变化ListInsert(L,

3,

e)length7第22页/共59页lengthListInsert—功能第23页/共59页过程：1、判断i的合法性2、移动3、赋值4、length++ListInsert—i的合法性L7100a1

a2

a3

a4

a5

a6

a71≤i≤8第24页/共59页一般的1≤i≤length+1ListInsert—移动a1

a2

e

a3

a4

a5

a6a1

a2

a3

a4

a5

a66length7lengtha7

a6a6

a5a5

a4a4

a3a

=ak+1

kk=length

→

i第25页/共59页ListInsert—移动方法一：数组元素L.elem[i-1]=e;ak+1

=

akk=length

→

i第26页/共59页j=L.length-1;While(

j>=i-1){L.elem[j+1]=L.elem[j];j--;}for(int

j=L.length;j>=i;j++)L.elem[j]=

L.elem[j-1];L.elem[i-1]=e;ListInsert—移动方法二：移动指针q=L.elem

+

(i-1);p=L.elem

+

L.length-1while(p>=q)

{*(p+1)=*p;p--;}q指向了aiP开始时指向了a第27页/共59页length*q=e;k=length

→

iak+1=akListInsert—移动ListInsert(L,

5,

66)q=L.elem

+

(i-1);for(p=L.elem

+

L.length-1;

p>=q;

p--)

*(p+1)=*p;*q=e;L.length-10p

ppp

q21

18

30

75

4626

5462

5867

87第28页/共59页ListInsert—移动L7a1

a2

a3

a4

a5

a6

a7表满的条件？length=listsizea1

a2

a3

a4

a5

a6

a7710第29页/共59页ListInsert—移动第30页/共59页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第31页/共59页Status

ListInsert(SqList

&L,

int

i,

ElemType

e){if(

i<1

||

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=e;L.length++;return(OK);}移动q=L.elem

+

(i-1);p=L.elem

+

L.length-1;while(

p>=q){

*(p+1)=*p;

p--}赋值长度增加第32页/共59页for(int

j=L.length-1;j>=i-1;j++)L.elem[j+1]=

L.elem[j];L.elem[i-1]=e;++L.length;ListInsert1、在什么情况下，移动次数最少，最少移动次数是多少？2、在什么情况下，移动次数最多，最多移动次数是多少？3、在插入每个位置的概率相同的情况下，移动次数的期望值是多少？第33页/共59页List

Delete—功能第34页/共59页原型：Status

ListDelete(SqList

&L,int

i,ElemType

&e)作用：取出线性表L的第i个数据元素的值，并删除ListDelete—功能第35页/共59页逻辑结构的变化(a1,

…,

ai-1,

ai,

ai+1…,

an)

→

(a1,

…,

ai-1,

ai+1,

…,an)<ai-1,

ai>

<ai,

ai+1>→

<ai-1,

ai+1>ListDelete—功能存储结构的变化a1

a2

a4

a5

a6a1

a2

a3

a4

a5

a6ListDelete(L,

3,

e)65第36页/共59页lengthelengthList

Delete—功能第37页/共59页过程：1、判断i的合法性2、取值3、移动4、length--ListDelete—i的合法性L7100a1

a2

a3

a4

a5

a6

a71≤i≤7第38页/共59页一般的1≤i≤lengthListDelete—移动a3

a4a4

a5a5

a6a

=ak-1

kk=i+1

→

lengtha1

a2

a4

a5

a6a1

a2

a3

a4

a5

a66length5length第39页/共59页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开始时指向了alengthp指向了ai+1第40页/共59页ListDelete—移动第41页/共59页方法二：数组元素j=i;while(j<=L.length-1){L.elem[j-1]=L.elem[j];j++;}ak-1=akk=i+1

→

lengthListDelete第42页/共59页Status

ListDelete(SqList

&L,

int

i,

ElemType

&e){return(ERROR);if(

i<1

||

i>

L.length)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.elem[i-1];for(int

j=i;j<=L.length-1;j++)L.elem[j-1]=

L.elem[j];--L.length;ListDelete1、在什么情况下，移动次数最少，最少移动次数是多少？2、在什么情况下，移动次数最多，最多移动次数是多少？3、在删除每个位置的概率相同的情况下，移动次数的期望值是多少？第43页/共59页ListMerge—功能第44页/共59页原型：Status

ListMerge(SqList

&La,SqList

Lb)作用：把Lb中的数据元素添加到La的表尾注意：不破坏Lb表ListMerge—功能a1

a2

a3

a4

a5

a6b1

b2

b3LaLb第45页/共59页b1

b2

b3ListMerge—功能第46页/共59页过程：1、取出Lb的一个数据元素bi2、把bi插入到La的表尾3、重复1-2，使得i=1,2,…,Lb.lengthListMerge第47页/共59页Status

ListMerge(SqList

&La,

SqList

Lb){for(int

i=1;

i<=Lb.length;

i++){GetItem(Lb,

i,

e);}}return(OK);code=ListInsert(La,

La.length+1,

e);if(code

!=

OK)

return(ERROR);ListMergeStatus

ListMerge(SqList

&La,

SqList

Lb){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;}For

(int

i=1;

i<=Lb.length;

i++){La.elem[La.length]=Lb.elem[i-1];La.length++;}return(OK);}第48页/共59页ListMerge—功能第49页/共59页原型：Status

ListMerge(SqList

La,SqList

Lb,SqList

&Lc)La:

a1≤

a2

≤a3……

≤amLb:

b1≤

b2

≤b3……

≤bn作用：把有序表La和Lb合并得到一个新的有序表Lc:c1≤c2

≤c3……≤cm+nci=aj

or

ci=bkListMerge—功能13

6

1028

9LaLb12

3

689

10Lc第50页/共59页ListMerge—分析13

6

10

1128

9LaLbLapb1

2

3

6

8

9

10pa

pa

pa

papbpb

pb11pa

pa第51页/共59页ListMerge—分析第52页/共59页分析：1、首先建立空表Lc2、从La和Lb中余下未处理的数据元素中选取最小的一个e3、把e插入表尾4、重复n+m次2和3ListMerge

—分析第53页/共59页1、首先建立空表LcInitList(Lc);2、pa和pb分别表示La和Lb中余下未处理的第一个数据元素（初始时pa=1,pb=1）GetItem(La,

pa,

Ea);

GetItem(Lb,

pb,

Eb);if(Ea<Eb){

e=Ea;