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

线性表(List)逻辑结构和主要操作顺序存储结构部分操作的实现小结和作业第一页，共六十页。逻辑结构D＝{a1,

a2,

…,

ai

,an}S＝{

<ai-1

,ai

>|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)第三页，共六十页。顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素a1a2…ai-1ai…

an线性表的起始地址(基地址)第四页，共六十页。定义数据类型

SqList#define#definetypedefLIST_INIT_SIZE

100LISTINCREMENT

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

SqList;第五页，共六十页。使用

SqListSqList

L;Lelemlengthlistsizeint

a;第六页，共六十页。……elemlength=6listsize=

100L使用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—功能原型：Status

InitList(SqList

&L)作用：给elem，length和listsize赋值过程：1、申请存储空间，首地址存放到elem2、length=03、listsize=LIST_INIT_SIZE第九页，共六十页。InitList—功能……01

0Lelemlengthlistsize第十页，共六十页。InitList-申请内存#include

<malloc.h>elem

=

(ElemType

*)

malloc(LIST_INIT_SIZE

*

sizeof(ElemType))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—功能原型：Status

DestroyList(SqList

&L)作用：释放L以前申请的内存过程：1、释放elem指示的连续存储单元2、L.length=03、L.listsize=0第十三页，共六十页。LDestroyList—功能……0610

0第十四页，共六十页。DestroyListStatus

DestroyList(SqList

&L){free(L.elem);L.length=0;L.listsize=0;return(OK);}第十五页，共六十页。GetIem—功能原型：Status

GetItem(SqList

L,int

i,ElemType

&e)作用：取出ai的值过程：1、判断i的合法性2、e=ai第十六页，共六十页。GetItem—功能L10100a1

a2

a3

a4

a5

a6

a7

a8

a9a10GetItem(L,

6,

e)e第十七页，共六十页。GetIem—合法性判断线性表中L有length个元素a1

a2

a3

...alength数据元素的下标为1，

2，…，length1≤i≤length第十八页，共六十页。GetItem—ai的位置a1a2

a3

a4a5

a6

a7a8

a9a10数据元素elema1

elem

+

0a2

elem

+

1a3elem

+

2ai

elem

+

i

-

1e=*(elem

+

i

–

1)第十九页，共六十页。GetItem—ai的位置a1

a2

a3

a4

a5

a6

a7

a8a9a10数据元素a1

elem[0]a2

elem[1]a3elem[2]aielem[

i

–

1]e=elem[

i

–

1]elem[0]

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)}第二十一页，共六十页。ListInsert—功能原型：Status

ListInsert(SqList

&L,int

i,ElemType

e)作用：把e插入线性表，作为第i个数据元素第二十二页，共六十页。ListInsert—功能逻辑结构的变化(a1,

…,

ai-1,

ai,

…,

an)

→

(a1,

…,

ai-1,

e,

ai,

…,

an)<ai-1,

ai>

→

<ai-1,

e>,

<e,

ai>第二十三页，共六十页。ListInsert—功能存储结构的变化ListInsert(L,

3,

e)length6a1a2a3a4a5a6length7a1a2ea3a4a5a6第二十四页，共六十页。ListInsert—功能过程：1、判断i的合法性2、移动3、赋值4、length++第二十五页，共六十页。ListInsert—i的合法性L7100a1

a2

a3

a4

a5

a6

a71≤i≤8一般的1≤i≤length+1第二十六页，共六十页。ListInsert—移动a1a2a3a4a5a6a1a2ea3a4a5a6length6length7a7

a66a

a5a5

a4a4

a3a

=ak+1

kk=length

→

i第二十七页，共六十页。ListInsert—移动L.elem[i-1]=e;ak+1

=

ak方法一：数组元素k=length

→

ij=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开始时指向了alength*q=e;k=length

→

iak+1=ak第二十九页，共六十页。ListInsert—移动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-1pp

q21

18

30

75

64620p

p5462

5867

87第三十页，共六十页。ListInsert—移动L7a1

a2

a3

a4

a5

a6

a7表满的条件？length=listsizea1

a2

a3

a4

a5

a6

a7710第三十一页，共六十页。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;}第三十二页，共六十页。ListInsertStatus

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;}第三十三页，共六十页。ListInsertq=L.elem

+

(i-1);p=L.elem

+

L.length-1;*q=e;L.length++;return(OK);}移动while(

p>=q){

*(p+1)=*p;

p--}赋值长度增加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、在插入每个位置的概率相同的情况下，移动次数的期望值是多少？第三十五页，共六十页。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<ai-1,

ai>

<ai,

ai+1>→

<ai-1,

ai+1>第三十七页，共六十页。ListDelete—功能存储结构的变化a1

a2

a4

a5

a6a1

a2

a3

a4

a5

a6ListDelete(L,

3,

e)65lengthelength第三十八页，共六十页。List

Delete—功能过程：1、判断i的合法性2、取值3、移动4、length--第三十九页，共六十页。ListDelete—i的合法性L7100a1

a2

a3

a4

a5

a6

a71≤i≤7一般的1≤i≤length第四十页，共六十页。ListDelete—移动a3

a44a

a5a5

a6a

=ak-1

kk=i+1

→

lengthlength6a1a2a3a4a5

a6length5a1a2a4a5a6第四十一页，共六十页。ListDelete—移动p=L.elem

+

(i-1);e=*p;q=L.elem

+

L.length-1;方法一：移动指针p指向了aiq开始时指向了alengthfor(++p;

p<=q;

p++)

*(p-1)

=*p;p指向了ai+1第四十二页，共六十页。ListDelete—移动方法二：数组元素j=i;while(j<=L.length-1){L.elem[j-1]=L.elem[j];j++;}ak-1=akk=i+1

→

length第四十三页，共六十页。ListDeleteStatus

ListDelete(SqList

&L,

int

i,

ElemType

&e){if(

i<1

||

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

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

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

ListMerge(SqList

&La,SqList

Lb)作用：把Lb中的数据元素添加到La的表尾注意：不破坏Lb表第四十六页，共六十页。ListMerge—功能b1

b2

b3La

a1

a2

a3

a4

a5

a6Lbb1b2

b3第四十七页，共六十页。ListMerge—功能过程：1、取出Lb的一个数据元素bi2、把bi插入到La的表尾3、重复1-2，使得i=1,2,…,Lb.length第四十八页，共六十页。ListMergeStatus

ListMerge(SqList

&La,

SqList

Lb){for(int

i=1;

i<=Lb.length;

i++){GetItem(Lb,

i,

e);code=ListInsert(La,

La.length+1,

e);if(code

!=

OK)

return(ERROR);}return(OK);}第四十九页，共六十页。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);}第五十页，共六十页。ListMerge—功能原型：Status

ListMerge(SqList

La,SqList

Lb,SqList

&LcLa:

a1≤

a2

≤a3……

≤amLb:

b1≤

b2

≤b3……

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

c1≤

c2

≤c3……

≤cm+nci=aj

or

ci=bk第五十一页，共六十页。ListMerge—功能13

6

102

8

9LaLb12

3

6

8

9

10Lc第五十二页，共六十页。ListMerge—分析1

3

6

10

1128

9LaLbLapb123

68910pa

pa

pa

papbpb

pb11pa

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

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

pa,

Ea);

GetItem(Lb,

pb,

Eb);if(Ea<Eb