数据结构试题,模拟考试题

数据结构试题

单选题

在数据结构的讨论中把数据结构从逻辑上分为（C）

A内部结构与外部结构B静态结构与动态结构

C线性结构与非线性结构D紧凑结构与非紧凑结构。

2、采用线性链表表示一个向量时,要求占用的存储空间地址（D）

A必须是连续的B部分地址必须是连续的

C•定是不连续的D可连续可不连续

3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（D）»

ABn/2C(n-l)/2D(n+l)/2

4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点S,则执行

(D)。

AS-*link=p-link;pfink=s;

Bp-link=s;s-link=q;

Cp->link=s—link;s-link=p;

Dq-,-link=s;s-*link=p;

5、如果想在4092个数据中只需要选择其中最小的5个，采用(C）方法最好。

A起泡排序B堆排序C锦标赛排序D快速排序

6、设有两个串t和p,求p在t中首次出现的位置的运算叫做（B

A求子串B模式匹配C串替换D串连接

7、在数组A中，每一个数组元素占用3个存储字,行下标i从1至1J8,列下标j从1

到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字

数是（C）。

A80B100C240D270

8、将•个递归算法改为对应的非递归算法时，通常需要使用（A)o

A栈B队列C循环队列D优先队列

9、一个队列的进队列顺序是1,2,3,4,则出队列顺序为（C）o

10、在循环队列中用数组存放队列元素，其队头和队尾指针分别为front和rear,

则当前队列中的元素个数是（D）。

A（front-rear+1）%mB(rear-front+1)%m

C（front-rear+m）%mD(rear-front+m)%m

11、一个数组元素a国与（A)的表示等价。

A*(a+i)Ba+iC*a+iD&a+i

12、若需要利用形参宜接访问实参,则应把形参变量说明为(B）参数。

A指针B引用c值D变量

13、下面程序段的时间复杂度为(C)

for(inti=0;i<m;i-H-)

for(intj=O;j<n;j++)

a[i][j]=i*j;

AO(m2)BO(n2)CO(m*n)DO(m+n)

14、下面程序段的时间复杂度为(B)

intf(unsignedintn){

if(n==0||n==1)return1;

elsereturnn*f(n-l);

A0(1)BO(n)CO(n2)DO(n!)

15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址（D）。

A必须是连续的

B部分地址必须是连续的

C一定是不连续的

D连续或不连续都可以

16、数据结构的定义为（D,S）,其中口是（B）的集合。

A算法B数据元素C数据操作D逻辑结构

17、算法分析的目的是（A）。

A找出数据结构的合理性

B研究算法中输入和输出的关系

C分析算法的效率以求改进

D分析算法的易懂性和文档性

18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B）。

As->link=p;p->link=s;

Bs->link=p->link;p->link=s;

Cs->link=p->link;p=s;

Dp->link=s;s->link=p;

19、设单链表中结点结构为（data,link）.已知指针q所指结点是指针p所指结点的直接前驱，

若在*q与*p之间插入结点*s,则应执行下列哪一个操作（B）

As->link=p->link;p->link=s;Bq->link=s;s->link=p

Cp->link=s->link;s->link=p;Dp->link=s;s->link=q;

20、设单链表中结点结构为（data,link）.若想摘除结点*p的直接后继，则应执行下列明E一个操

作（A）

Ap->link=p->link->link;

Bp=p->link;p->link=p->link->link;

Cp->link=p->link;Dp=p->link->link;

21、设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单循环链

表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D）

As=rear;rear=rear->link;deletes;

Brear=rear->link;deleterear;

Crear=rear->link->link;deleterear;

Ds=rear->link->link;rear->link->link=s->link;deletes;

22、设单循环链表中结点的结构为（data,link），且first为指向链表表头的指针，current为链

表当前指针，在循环链表中检测current是否达到链表表尾的语句是（D）。

Acurrent->link=nullBfirst->link=current

Cfirst=currentDcurrent->link=first

23、•个栈的入栈序列为a,b,c,则出栈序列不可能的是（C）

Ac,b,aBb,a,cCc,a,bDa,c,b

24、栈的数组表示中，top为栈顶指针，栈空的条件是（A）。

Atop=0Btop=maxSizeCtop=maxSizeDtop=-1

25、栈和队列的共同特点是（C）。

A都是先进后出B都是先进先出

C只允许在端点处插入和删除D没有共同点

26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r，则判断队空的条件为

(D).

AfH==rBr+l==fC4=0D4=r

27、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（B）

An-2Bn-1CnDn+1

28、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插

入一个元素时，首先应执行（）语句修改top指针。

Atop++;Btop—;Ctop=0;Dtop;

29、设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想摘除链式栈的栈

顶结点，并将被摘除结点的值保存到x中，则应执行下列（A）操作。

Ax=top->data;top=top->link;Btop=top->link;x=top->data;

Cx=top;top=top->link;Dx=top->data;

30、设循环队列的结构是：

constintMaxsize=100;

typedefintDataType;

typcdefstruct{

DataTypedata[Maxsize];

Intfront,rear;

}Queue;

若有一个Queue类型的队列Q,试问判断队列满的条件应是下列哪一个语句(D)

AQ.front==Q.rear;BQ.front-Q.rear==Maxsize;

CQ.front+Q.rear==Maxsize;DQ.front==(Q.rear+1)%Maxsize;

31、设有一个递归算法如下：

intfact(intn)

{if(n<=0)return1;

elsereturnn*fact(n-l);

)

下面正确的叙述是(B)

A计算fact(n)需要执行n次递归Bfact(7)=5040

C此递归算法最多只能计算到foct(8)D以上结论都不对

32、设有一个递归算法如下

intx(intn){

if(n<=3)return1;

elsereturnx(n-2)+x(n-4)+1;

试问计算x（x（8））时需要计算（D）次x函数。

A8次B9次C16次D18次

33、设有广义表D（a,b,D）,其长度为(B）,深度为（A)

A8B3C2D5

34、广义表A（a）,则表尾为（C)

AaB(())C空表D(a)

35、下列广义表是线性表的有（C）

AE(a,(b,c))BE(a,E)CE(a,b)DE(a,L())

36、递归表、再入表、纯表、线性表之间的关系为（C)

A再入表＞递归表〉纯表〉线性表B递归表＞线性表〉再入表》纯表

C递归表》再入表＞纯表〉线性表D递归表》再入表＞线性表〉纯表

37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（B）的二叉树。

A空或只有一个结点B高度等于其结点数

C任一结点无左孩子D任一结点无右孩子

38、对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为n2.，则（A）

An0=n2+lBn2=n0+1Cn0=2n2+1Dn2=2n0+l

39、山权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B）

A24B73C48D53

40、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为

dal,则第I个结点的地址为（A）。

Adal+（I-l）*mBdal+I*mCdal-I*mDdal+（I+l）*m

41、34具有35个结点的完全二叉树的深度为（A）

A5B6C7D8

42、对线性表进行折半搜索时，要求线性表必须（C）

A以链接方式存储且结点按关键码有序排列B以数组方式存储

C以数组方式存储且结点按关键码有序排列D以链接方式存储

43、顺序搜索算法适合于存储结构为（B）的线性表。

A散列存储B顺序存储或链接存储

C压缩存储D索引存储

44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（C）

AO（n2）BO（nlog2n）CO（log2n）DO（n）

45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为（A）

AnBn+1Cn-1Dn+e

46、判断•个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C）。

A求关键路径的方法B求最短路径的Dijkstra方法

C深度优先遍历算法D广度优先遍历算法

47、在10阶B-树中根结点所包含的关键码个数最多为（C）,最少为（A）

A1B2C9D10

48、对包含n个元素的散列表进行搜索，平均搜索长度为（C）

AO（log2n）BO（n）C不直接依赖于nD上述都不对

填空题（）

1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种

2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种

3、一种抽象数据类型包括（数据）和（操作）两个部分。

设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配）

栈、队列逻辑上都是（线性存储）结构。

线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）

的，树形结构中数据元素间的关系是（一对多）的。

栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）

8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由•个

或多个空格组成的串）称为空格串。

9、设目标串T="abccdcdccbaa”,模式P="cdcc”则第（6）次匹配成功。

10、・维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有

（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组若采用

按行优先存放的方式，则任一数组元素相对于A[0][0]的地址为（n*i+j）»

11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元

素（写）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。

12、在一个循环队列Q中，判断队空的条件为（Q.front==Q.rear）,判断队满的条件为

（（Q.rear+l）%MaxSize==q.front）

13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1）。

14、一棵高度为5的满二叉树中的结点数为（63）个，一棵高度为3满四叉树中的结点

数为（85）个。

15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编

号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为（2*i+l）,右子女结

点为（2*i+2）,双亲结点（i>=l）为（T（i-l）/2-i）.

16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结

点的值是所有结点中的（最小值）。

17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元

素的地址为LOC（al）,那么，LOC（ai尸LOC（al）+（i-l）*k。

18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外,

还可以最多对（4）个字符编码。

19、设高度为h的空二叉树的高度为-1,只有一个结点的二叉树的高度为0,若设二叉树只

有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+l）个。

20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。

21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。

22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7

有10个叶子结点，则整个二叉树的结点数最多是（235）

23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。

24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（5）,判定树中

前5层的结点数为（31）,最后一层的结点数为（19）。

25、在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。在一个具有n个顶点

的无向完全图中，包含有（n（n-l）/2）条边，在个具有n个顶点的有向完全图中，包含

有（n（n-l））条边。

26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和

（n-1）o

27、设线性表中元素的类型是实型，其首地址为1024,则线性表中第6个元素的存储位置

是（1044）。

28、在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反

序，则最好选择（选择排序）。

29、算法是对特定问题的求解步骤的一种描述，它是（指令）的有限序列，每一条（指令）

表示一个或多个操作。

30、对于一个具有n个顶点肯e条边的无向图，进行拓朴排序时，总的进间为（n）

31、构造哈希函数有三种方法，分别为（平方取中）法、（除留余数）法、（折迭移位）法。

32、处理冲突的三种方法，分别为（线性探测）、（随机探测）、（链地址法）。

33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间

复杂度为（0（n2））、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（0

（elog2e））

34、快速排序在平均情况下的时间复杂度为（0（nlog2n））,在最坏情况下的时间复杂度为

（O（n2））;快速排序在平均情况下的空间复杂度为（0（Iog2n））,在最坏情况下的空间

复杂度为（0（n））o

35、假定一组记录的排序码为（46,79,56,38,40,80）,对其进行归并排

序的过程中，第二趟排序后的结果是（[38465679][4080]）

36、假定一组记录的排序码为（46,79,56,38,40,80）,对其进行快速排

序的第一次划分的结果是（[3840]46[567980]）。

37、一个结点的子树的（个数）称为该结点的度。度为（零）的结点称为叶结点

或终端结点。度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（最

大值）称为树的度。

38、设Ki=Kj（l〈=i<=n,l〈=j<=n,joi）且在排序前的序列中Ri领先于Rj（i<j）,若排序后的序

列中Ri仍领先于Rj,则这种排序方法是（稳定的），反之是（不稳定的）。

40、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（0（log2n»,整

个排序过程的时间复杂度为（0（nlog2n））。

41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。

42、假定一个线性表为（“abcd","baabd”,"bceF,“c^”,“ahij","bkwte”,“ccdt",“aayb”），若按照字

符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子

表的长度分别为（3）,（3）,（2）o

43、对于包含50个关键码的3阶B-树，其最小高度为（4）,最大高度为（5）。

44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减

1）

45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度

m=20的散列表，每个散列地址的同义词子表的长度平均为（5）。

46、在散列存储中，装载因子a又称为装载系数，若用m表示散列表的长度，n表示待散列

存储的元素的个数，贝等于（n/m）o

47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第i列中“1”

的个数是第i个顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第

i个顶点的（度），矩阵中“1”的个数的一半是图中的（边数）。

48、在对m阶B-树中，每个非根结点的关键码数最少为（Fm/2-i-1）个，最多为（m-1）个,

其子树棵数最少为（fm/2-i）,最多为（m）。

判断题

数据元素是数据的最小单位（X）。

数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（，）.

数据结构是指相互之间存在一种或多种关系的数据元素的全体（义）。

从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构（4）。

线性表的逻辑顺序与物理顺序总是•致的（义）。

二维数组是其数组元素为线性表的线性表（X）。

每种数据结构都应具备三种基本运算：插入、删除、搜索（Y）。

非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（X）

空串与由空格组成的串没有区别。（X）

10、将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。（Y）

11、深度为h的非空二叉树的第h层最多有2h-l个结点（X）

12、完全二叉树就是满二叉树。（X）

13、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（4）

14、带权连通图的最小生成树的权值之和••定小于它的其它生成树的权值之和。N）

15、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。

（4）

若有•个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树

的前序遍历结果序列的最后一个结点。N）

17、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜

索时间。（X）

18、最优二叉搜索树一定是平衡的二叉搜索树。（4）

19、AOE网是一种带权的无环连通图。W）

20、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树

都是相同的（X）。

21、二叉排序树可以是一棵空树（Y）

22、线性表中所有结点的类型必须相同。（Y）

23、n个结点的有向图，若它有n（n—1）条边，则它一定是强连通的。（4）

24、任何无环的有向图，其结点都可以排在一个拓扑序列里。N）

25、队列逻辑上是一个下端口和上端能增加又能减少的线性表（X）

26、二叉树是树的一种特殊情况（T）

27、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图

中顶点个数有关，而与图的边数无关川）。

28、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（X）

29、连通分量是无向图中的极小连通子图。（X）

30、在AOE网络中一定只有一条关键路径。（X）

31、关键活动不按期完成就会影响整个工程的完成时间。（Y）

32、平衡二叉树的左右子树深度之差的绝对值不超过1。（<）

33、快速排序是对起泡排序的一种改进。（<）

34、直接选择排序稳定。（X）

35、堆排序占用的辅助空间很大。（X）

36、在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在（0,1）之间。（X）

37、B-树是一种动态索引结构，它既适用于随机搜索，也适用于顺序搜索。（X）

38、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（X）

39、任何一个关键活动延迟，那么整个工程将会延迟。（Y）

40、任何一个关键活动提前完成，那么整个工程将会提前完成。（义）

四、运算应用题

1、在一个有n个元素的顺序表的第i个元素（l<i<n）之前插入一个新元素时，需要向后

移动多少个元素？

答案：需要向后移动n-i+1个元素

当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈

序列？

答案：

可能的出栈序列有种，6457321不是合理的出栈序列。

1114*13*12*11*10*9*8

=-*------------------------------=429

771GZ87*6*5*4*3*2*1

简单（直接）选择排序是一种稳定的排序方法吗？试举例说明？

答案：是不稳定的排序方法。下面就是不稳定的例子。只要能举反例即可。

{275275*512061}i=1

(061275*512275}i=2

{061275*512275}i=3

{061275*275512

4、设有序顺序表为{10,20,30,40,50,60,70},采用折半搜索时，搜索成功的平均搜索长

度是多少？

答案：ASLsucc=（l*l+2*2+3*4）/7=17/7

5、在结点个数为n（n>l）的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多

少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

答案：结点个数为n时，高度最小的树的高度为1,有2层；它有n-1个叶结点，1个分支

结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。

6、・棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结

点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进

行编号，试问：

（1）各层的结点个数是多少？

（2）编号为i的结点的父结点（若存在）的编号是多少？

（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？

（4）编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？

（5）若结点个数为n,则高度h是n的什么函数关系？

答案：

（1）各层的结点个数是ki（i=0,l,2,....,h）

（2）编号为i的结点的父结点（若存在）的编号是L（i+k-2）/kJ

（3）编号为i的结点的第m个孩子结点（若存在）的编号是（i-l）*k+m+l

（4）当（i-l）%ko0时有右兄弟，右兄弟的编号为i+l

（5）若结点个数为n,则高度h和n的关系为：h=logk（n*（k-1）+1）-1（n=0时h=-l）

7、写出下列中缀表达式的后缀形式：

(1)A*-B+C

(2)(A+B)*D+E/(F+A*D)+C

(3)A&&B||!(E>F)｛注:按C++的优先级)

(4)!(A&&!((B<C)||(C>D)))||(C<E)

答案：各中缀表达式的后缀形式如下：

(1)AB・*C+

(2)AB+D*EFAD*+/+C+

(3)AB&&EF>!||

(4)ABC<CD>||!&&!CE<||

8、画出下列广义表的图形表示和它们的存储表示:

(l)D(A(c),B(e),C(a,L(b,c,d)))

(2)Jl(J2(Jl,a,J3(J1)),J3(J1))

答案：广义表(1)的图形表示为：

广义表（1）的存储表示为:

广义表（2）的存储表示为:

D

9、题目：

答案:

10、将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。(7分)

答案：

11、根据所给有向图，写出一个拓扑序列。（5分）

其中的一个拓扑序列为：VI,V2,V3,V4,V5,V6,V7

12、将给定的图简化为最小的生成树，要求从顶点1出发。（7分）

13、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05,0.29,0.07,

0.08,0.14,0.23,0.03,0.11试设计赫夫曼编码。

答案：

为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8,所以要构造的赫夫曼树

共有m=2n-l=2*8-l=15个结点。生成的赫夫曼树为下图所示：

赫夫曼编码为：概率为0.23的字符编码为：00

概率为0.11的字符编码为：010

概率为0.05的字符编码为：0110

概率为003的字符编码为:0111

概率为0.29的字符编码为：10

概率为0.14的字符编码为：110

概率为0.07的字符编码为：1110

概率为0.08的字符编码为：1H1

14、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,

试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。

答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：

15、在结点个数为n(n>l)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多

少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

答案：结点个数为n时，高度最小的树的高度为1,有2层；它有n-1个叶结点，1个分支

结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。

16、对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的

AVL树，其最大高度是多少？最小高度是多少？

答案：设高度为h(空树的高度为-1)的AVL树的最少结点为Nh,则Nh=Fh+3-l。

Fh是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log2(n+l),

最小高度为Flog2(n+l)-)-lo

17、7-7设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,

765,897,908。试画出对其进行折半搜索时的判定树，并计算搜索成功的平均搜索长度和搜

索不成功的平均搜索长度。

ASLSUCC=1/14(1+2*2+3*4+4*7)=45/14

ASLUNSUCC=1/15(3*1+4*14)=59/15

(1)这个工程最早可能在什么时间结束。

(2)求每个事件的最早开始时间Ve[i]和最迟开始时间

(3)求每个活动的最早开始时间e()和最迟开始时间1()o

(4)确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个

工程提前完成。

答案：按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间VI,然

后再计算各个活动的最早可能开始时间e和最迟允许开始时间1,根据1-e是否等于0来确定

19、已知有五个待排序的记录，其关键字分别为:256,301,751,129,937,863,742,694,

076,438请用快速排序的方法将它们从小到大排列。

答案：

第一次排序:(076,129),256,(751,937,863,742,694,301,439)

第二次排序:076,129,256,(438,301,694,742),751,(863,937)

第三次排序：076,129,256,301,438,(694,742),751,(863,937)

第四次排序：076,129,256,301,438,694,742,751,(863,937)

第五次排序:076,129,256,301,438,694,742,751,863,937

20、设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的

平均比较次数不超过2次。试问散列表需要设计多大？(设a是散列表的装载因子，则有

ASLsucc=(1+1/(1-a))/2)。

答案：已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsuccW2,则有：

ASLsucc=1/2(1+1/(1-a))W2解得aW2/3,又有：a=n/m=150/m

两式联立得：150/m<2/3,解得：m)225.

所以散列表需要设计225个单位。

五、算法分析题

1、给出下列递归过程的执行结果

voidunknown(intw){

if(w){

unknown(w-1);

for(inti=1;i<=w;i++)cout«w«'

cout«endl;

}

)

调用语句为unknown(4)。

答案：

(1)1

22

333

4444

2、给出递归过程的执行结果

voidunknown(intn){

cout«n%10;

if(int(n/10))unknown(int(n/10));

}

调用语句为unknown(582)。

答案：285

3、给出递归过程的执行结果

intunknown(intm){

intvalue;

if(!m)value=3;

elsevalue=unknown(m-1)+5;

returnvalue;

_}

执行语句为cout«unknown(3)。

答案：18

4、设有一个二维数组假设A[0][0]存放位置在644(10),A[2][2]存放位置在676

(10),每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进

制表示。

答案：设数组元素存放在起始地址为Loc(i,j)的存储单元中。

因为：Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676

所以：n=(676-2-644)/2=15

所以：Loc(3,3尸Loc(0,0)+3*15+3=644+45+3=692

5、设单链表结构为structListNode{

intdata;

ListNode*link;

)；

下面的程序是以单链表为存储结构，实现二路归并排序的算法，要求链表不另外占用存储空

间，排序过程中不移动结点中的元素，只改各链结点中的指针，排序后r仍指示结果链表的

第•个结点。在初始状态下，所有待排序记录链接在一个以r为头指针的单链表中。例如，

r一|25|十-|34|+-|18|卜|94|长同+159|长而厂4|63|人|

在算法实现时，利用了■个队列做为辅助存储，存储各有序链表构成的归并段的链头指针。

初始时，各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue,其可直接使

用的相关操作有

■置空队列操作：makeEmpty();

■将指针x加入到队列的队尾操作：EnQueue(ListNode*x);

■退出队头元素，其值由函数返回的操作：ListNode*DlQueue();

■判队列空否的函数，空则返回1,不空则返回0：intIsEmpty()。

解决方法提示：

＞程序首先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，其表头指针

存放在一个指针队列中。

＞当队列不空时，从队列中退出两个有序子链表，对它们进行二路归并，结果链表的表头指

针存放到队列中。

＞如果队列中退出一个有序子链表后变成空队列，则算法结束。这个有序子链表即为所求。

在算法实现时有6处语句缺失，清阅读程序后补上。

(1)两路归并算法

voidmerge(ListNode*ha,ListNode*hb„ListNode*&he){

ListNode*pa,*pb,*pc;

if(hafdata<=hb-^data){he=ha;pa=haflink;pb=hb;}

else{he=hb;pb=hb-*link;pa=ha;}

pc=he;

while(pa&&pb)

pafdata<=pbfdata

pc-*link=pa;pc=pa;

)

if(pa)pc->link=pa;

elsepc-•-link=pb;

);

(2)归并排序主程序

voidmergesort(ListNode*r){

ListNode*s,t;QueueQ;

if(!r)return;

s=r;|Q.EnQueue(r)|;

while(s){

t=sflink;

while(t!=0&&sfdatav=t—data){s=t;t=t->link;}

if(t){

s-*link=0;s=t;Q.EnQueue(s);

)

)

while(!Q.IsEmpty()){

r=Q.DlQueue();

if(Q.IsEmpty())break;

s=Q.DlQueue();

merge(r,s,t);|Q.EnQueue(t)|;

)

}

6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语

句。(7分)

voiddemo2(LinkListhead,ListNode*p)

{//head是带头结点的单链表，删除P指向的结点

ListNode*q=head;

while(q&&q->next!=p)q=q->next;

if(q)Error(<4*pnotinhead")；

q->next=p->next;

free(p);

}

已知一完全二叉树从根结点开始，自顶向下，同一层自左向右连续编号，根结点的编号为0,

阅读以下程序请回答该程序所实现的功能：

template<classtype>

voidlinkedtosequent(Bintreenode<Type>*t,typea[],inti){

if(t!=Null){

a[]=t->getData();

linkcdtosequcnt(t->getleftchild(),a,2*i+1);

linkedtosequent(t->getrightchild(),a,2*i+2);

}}

主程序调用方式：Iinkedtosequent(t.root,a,0);

答案：该程序的功能是：将用二叉链表表示的完全二叉树转换为二叉树的顺序(数组)表示。

8、设散列表为HT[13],散列函数为H(key)=key%13o用闭散列法解决冲突，对下列关键

码序列12,23,45,57,20,03,78,31,15,36造表。

(1)采用线性探查法寻找下一个空位，画出相应的散列表，并计算等概率下搜索成功的平均

搜索长度和搜索不成功的平均搜索长度。

(2)采用双散列法寻找下一个空位，再散列函数为RH(key)=(7*key)%10+1,寻找下一个

空位的公式为Hi=(Hi-1+RH(key))%13,H1=H(key)。画H；相应的散列表，并计算等概率

下搜索成功的平均搜索长度。

答案：使用散列函数H(key)=keymod13有：

H(12)=12,H(23)=10,H(45)=6,H(57)=5,H(20)=7,H(03)=3,H(78)

=0,H(31)=5,H(15)=2,H(36)=10

利用线性探查法造表：

0123456789101112

78150357452031233612

1111114121

搜索成功的平均搜索长度为：

ASLsucc=l/10(1+1+1+1+1+1+4+1+2+1)=14/10

搜索不成功的平均搜索长度为：

ASLunsucc=l/13(2+1+3+2+1+5+4+3+2+1+5+4+3)=36/13

利用双散列法造表：

Hi=(Hi-1+RH(key))%13,Hi=H(key)

0123456789101112

78150357452031362312

1111113511

9、阅读下面7匣序，』「旨出其算法的功能并求出其时卜间复杂度。

intPrime(intn){

inti=2,x=(int)sqrt(n);

while(i<=x){

if(n%i==O)break;

i++；

)

if(i>x)return1;

elsereturn0;

}

(2)intsum1(intn){

intp=l,s=O;

fdr(inti=l;i<=n;i++)

{p*=i;s+=p;}

returns;

答案：(1)程序功能是判断n是否是•个素数，若是则返回数值1,否则返回数值

0,该算法的时间复杂度为O(sqrt(n)).

(2)程序功能是计算Eni=li!,该算法的时间复杂度为O(n).

10、判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法的

处填入正确的语句。

intsymmctry(DblListDL){