数据结构试题(含答案)

数据结构试题

一、 单选题

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

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

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

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

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

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

3、采用顺序搜索方法查找长度为

n

的顺序表时，搜索成功的平均搜索长度为（ D ）。

A

n

B

n

/2 C (

n

-1)/2 D (

n

+1)/2

4、在一个单链表中，若

q

结点是

p

结点的前驱结点，若在

q

与

p

之间插入结点

s

，则执行

（ D ）。

A

s

→

link

=

p

→

link

;

p

→

link

=

s

;

B

p

→

link

=

s

;

s

→

link

=

q

;

C

p

→

link

=

s

→

link

;

s

→

link

=

p

;

D

q

→

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

中，每一个数组元素

A

[i][j]占用3个存储字，行下标

i

从1到8，列下标

j

从1到

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

（ C ）。

A 80 B 100 C 240 D 270

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

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

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

10、在循环队列中用数组

A

[0..

m

-1] 存放队列元素，其队头和队尾指针分别为

front

和

rear

，则

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

A (

front

-

rear

+ 1) %

m

B (

rear

-

front

+ 1) %

m

C (

front

-

rear

+

m

) %

m

D (

rear

-

front

+

m

) %

m

11、一个数组元素a[i]与（ A ）的表示等价。

A *（a+i） B a+i C *a+i D &a+i

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

A 指针 B 引用 C 值 D 变量

13、下面程序段的时间复杂度为（ C ）

for (int i=0;i

for (int j=0;j

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

A O(m

2

) B O(n

2

) C O(m*n) D O(m+n)

14、下面程序段的时间复杂度为（ B ）

int f(unsigned int n) {

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

else return n*f(n-1);

}

A O(1) B O(n) C O(n

2

) D O(n

!)

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

A 必须是连续的

B 部分地址必须是连续的

C 一定是不连续的

D 连续或不连续都可以

16、数据结构的定义为(D，S)，其中D是( B )的集合。

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

17、算法分析的目的是( A )。

A 找出数据结构的合理性

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

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

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

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

A s->link=p;p->link=s; B s->link=p->link;p->link=s;

C s->link=p->link;p=s; D p->link=s;s->link=p;

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

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

A s->link=p->link; p->link=s; B q->link=s; s->link=p

C p->link=s->link; s->link=p; D p->link=s; s->link=q;

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

（ A ）

A p->link=p->link->link; B p=p->link; p->link=p->link->link;

C p->link=p->link; D p=p->link->link;

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

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

A s=rear; rear=rear->link; delete s; B rear=rear->link; delete rear;

C rear=rear->link->link; delete rear; D s=rear->link->link;

rear->link->link=s->link; delete s;

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

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

A current->link =null B first->link=current

C first=current D current->link=first

23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。

A c,b,a B b,a,c C c,a,b D a,c,b

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

A top=0 B top=maxSize C top=maxSize D top=-1

25、栈和队列的共同特点是( C )。

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

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

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

A f+1= =r B r+1= =f C f= =0 D f= =r

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

A n-2 B n-1 C n D n+1

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

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

A top++; B top--; C top=0; D top;

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

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

A x=top->data; top=top->link; B top=top->link; x=top->data;

C x=top; top=top->link; D x=top->data;

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

const int Maxsize=100;

typedef int Data Type;

typedef struct {

Data Type data[Maxsize];

Int front, rear;

} Queue;

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

A = = ; B - = = Maxsize;

C + = = Maxsize; D = = (+1)% Maxsize;

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

int fact (int n )

{ if (n<=0) return 1;

else return n*fact(n-1);

}

下面正确的叙述是（ B ）

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

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

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

int x (int n) {

if (n<=3) return 1;

else return x(n-2)+x(n-4)+1;

}

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

A 8 次 B 9 次 C 16 次 D 18次

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

A ∞ B 3 C 2 D 5

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

A a B (( ) ) C 空表 D （a）

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

A E（a,(b,c)） B E(a,E) C E (a,b) D E(a,L( ) )

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

A 再入表>递归表>纯表>线性表 B 递归表>线性表>再入表>纯表

C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表

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

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

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

38、对于任何一棵二叉树T，如果其终端结点数为n

0，

度为2的结点为n

2

.,则( A )

A n

0=

n

2

+1 B n

2

= n

0

+1 C n

0=

2n

2

+1 D n

2

=2n

0

+1

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

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

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

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

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

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

A 24 B 73 C 48 D 53

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

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

A da1+(I-1)*m B da1+I*m C da1-I*m D da1+(I+1)*m

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

A 5 B 6 C 7 D 8

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

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

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

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

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

C 压缩存储 D 索引存储

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

A O（n

2

） B O（n log

2

n） C O（log

2

n） D O（n）

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

A n B n+1 C n-1 D n+e

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

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

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

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

A 1 B 2 C 9 D 10

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

A O（log

2

n） B O（n） C 不直接依赖于n D 上述都不对

二、 填空题（）

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

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

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

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

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

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

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

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

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

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

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

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

（ (+1)%MaxSize= = ）

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

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

（ 85 ）个。

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

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

（ 2*i+2 ），双亲结点（i>=1 ）为（「(i-1)/2 ┐ ）.

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

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

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

地址为LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。

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

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

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

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

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

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

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

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

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

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

５层的结点数为（３１），最后一层的结点数为（１９）。

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

向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有

（ n(n-1) ）条边。

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

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

( 1044)。

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

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

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

一个或多个操作。

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

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

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

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

度为（ Ｏ（n

2

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

2

e） ）

34、快速排序在平均情况下的时间复杂度为（Ｏ（nlog

2

n）），在最坏情况下的时间复杂度为（Ｏ

（n

2

））；快速排序在平均情况下的空间复杂度为（Ｏ（log

2

n）），在最坏情况下的空间复杂

度为（Ｏ（n））。

35、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行归并排序的

过程中，第二趟排序后的结果是（［３８ ４６ ５６ ７９］［４０ ８０］）

36、假定一组记录的排序码为（４６，７９，５６，３８，４０，８０），对其进行快速排序的

第一次划分的结果是（［３８ ４０］４６［５６ ７９ ８０］）。

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

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

称为树的度。

38、设K

i

=K

j

(1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中R

i

领先于R

j

(i

列中R

i

仍领先于

R

j

，则这种排序方法是（稳定的），反之是（不稳定的）。

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

2

n）），整个

排序过程的时间复杂度为（Ｏ（nlog

2

n））。

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

42、假定一个线性表为（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”

aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的

a,b,c三个子表的长度分别为（３），（３），（２）。

43、对于包含５０个关键码的３阶B-树，其最小高度为（４），最大高度为（５）。

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

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

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

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

的元素的个数，则α等于（n/m）。

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

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

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

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

其子树棵数最少为（「m/2┐），最多为（m）。

三、 判断题

1、 数据元素是数据的最小单位（╳）。

2、 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的(√).

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

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

5、 线性表的逻辑顺序与物理顺序总是一致的（╳）。

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

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

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

9、 空串与由空格组成的串没有区别。（╳ ）

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

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

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

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

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

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

（ √ ）

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

树的前序遍历结果序列的最后一个结点。（√）

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

时间。（╳）

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

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

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

相同的（╳）。

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

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

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

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

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

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

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

点个数有关，而与图的边数无关（√）。

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

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

30、在ＡＯＥ网络中一定只有一条关键路径。（╳）

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

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

33、快速排序是对起泡排序的一种改进。( √ )

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

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

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

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

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

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

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

四、运算应用题

1、在一个有

n

个元素的顺序表的第

i

个元素（1 

i



n

）之前插入一个新元素时，需要向

后移动多少个元素？答案：需要向后移动

n- i

+ 1个元素

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

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

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

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

{ 275 275* 512 061 }

i

= 1

{ 061 275* 512 275 }

i

= 2

{ 061 275* 512 275 }

i

= 3

{ 061 275* 275 512 }

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

长度是多少？

答案：

ASL

succ

= (1*1 + 2*2 + 3*4 ) / 7 = 17 / 7

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

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

答案：结点个数为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）各层的结点个数是k

i

(i=0,1,2,....,h)

（2）编号为i的结点的父结点(若存在)的编号是└ (i+k-2)/k」

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

（4）当(i-1)%k<>0时有右兄弟， 右兄弟的编号为 i+1

（5）若结点个数为 n ，则高度h和n 的关系为：h=log

k

(n*(k-1)+1)-1 (n=0时h=-1)

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||!&&!CE<||

1

7

1141312111098

71

C

14



8



7654321

429

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

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

J1

0 J1 2 2 ^

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

答案：广义表（1）的图形表示为： 广义表（2）的图形表示为：

D

A

B

C

J1

c a

L

J2 J3

e

b

c

d

a

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

A

0 A 1 C ^

B

0 B 1 e ^

D

0 D 2 2 2 ^

C

0 C 1 a 2 ^

L

0 L 1 b 1 C 1 d ^

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

J2

0 J2 2 1 a

J3

0 J3 2 ^

9、题目：11、将下面的森林变换成二叉树（7分）。

A E

B C D F

2 ^

G

H I

J

K

A

B

E

C

F

G

D

H

I

J

K

答案：

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

*

+

+

+

f

g

h

+

*

a b

c

+

答案：

d e

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

3

1

4

6

2

5

7

答案：其中的一个拓扑序列为：V1，V2，V3，V4，V5，V6，V7

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

8

1

5

2

3

3

15

10

12

4

7

5

6

2

6

9

7

答案:

1

5

2

3

3

15

4

7

5

6

2

6

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-1=2*8-1=15个结点。生成的赫夫曼树为下图所示。

1

0

0

1 0 1

23

0

29

1

0 1

11

0

14

1

0

1

5

3

7 8

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

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

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

概率为0.03的字符编码为：0111

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

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

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

概率为0.08的字符编码为：1111

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

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

A

B

F

E C

G

D

H J

I

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

这棵二叉树的后序遍历序列为：EDCBIHJGFA

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

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

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

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

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

树, 其最大高度是多少? 最小高度是多少?

答案：设高度为h(空树的高度为-1)的AVL树的最少结点为N

h

，则N

h

= F

h+3

-1。

F

h

是斐波那契数。又设AVL树有n个结点，则其最大高度不超过3/2*log

2

(n+1),

最小高度为「log

2

(n+1) ┐-1。

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

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

成功的平均搜索长度。

509

154 677

017 275

553 897

094 170 503

512 612 765 908

答案：折半搜索时的判定树为：

ASL

SUCC

=1/14（1+2*2+3*4+4*7）=45/14

ASL

UNSUCC

=1/15（3*1+4*14）=59/15

18、试对下图所示的AOE网络

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

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

(3) 求每个活动的最早开始时间

e

( )和最迟开始时间

l

( )。

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

提前完成。

答案：按拓朴有序的顺序计算各个顶点的最早可能开始时间V

e

和最迟允许开始时间V

l

，然后再

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

从而确定关键路径。

V

e

V

l

e

L

l-e

<1,2>

0

17

17

<1,3>

0

0

0

<3,2>

15

15

0

<2,4>

19

27

8

<2,5>

19

19

0

<3,5>

15

27

12

<4,6>

29

37

8

①

0

0

③

19

19

②

15

15

④

29

37

⑤

38

38

⑥

43

43

}

}

unknown

(

w

-1 );

for ( int

i

= 1; i <=

w

;

i

++ ) cout <<

w<<' '

;

cout << endl;

调用语句为

unknown

(4)。

答案：(1) 1

2 2

3 3 3

<5,6>

38

4 4 4 4

void

0

unknown

( int

n

) {

cout <<

n

% 10 ;

}

调用语句为

unknown

( 582 )。

if ( int (

n

/ 10 ) )

unknown

( int (

n

/ 10 ) );

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

38

此工程最早完成时间为43，关键路径为<1,3><3,2><2,5><5,6>

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次。试问散列表需要设计多大？ (设是散列表的装载因子，则有ASL

succ

= ( 1+1/ (1-) )/2)。

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

succ

≤2，则有：ASL

succ

=1/2（1+1/（1-））≤2 解得 ≤2/3 ，又有：=n/m=150/m

两式联立得：150/m≤2/3,解得：m≥225.

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

五、算法分析题

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

void

unknown

( int

w

) {

if (

w

) {

答案： 285

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

int

unknown

( int

m

) {

int

value

;

if ( !

m

)

value

= 3;

else

value

=

unknown

(

m

-1 ) + 5;

return

value

;

}

执行语句为 cout <<

unknown

(3)。

答案： 18

4、 设有一个二维数组

A

[

m

][

n

]，假设

A

[0][0]存放位置在644

（10）

，

A

[2][2]存放位置在676

（10）

，

每个元素占一个空间，问

A

[3][3]

（10）

存放在什么位置？脚注

（10）

表示用10进制表示。

答案：设数组元素A[i][j]存放在起始地址为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、设单链表结构为 struct

ListNode

{

int

data

;

ListNode

*

link

;

};

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

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

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

在算法实现时，利用了一个队列做为辅助存储

, 存储各有序链表构成的归并段的链头指针。

初始时, 各初始归并段为只有一个结点的有序链表。队列的数据类型为

Queue

, 其可直接使用的

相关操作有

 置空队列操作：

makeEmpty

( );

 将指针

x

加入到队列的队尾操作：

EnQueue

(

ListNode

*

x

);

 退出队头元素, 其值由函数返回的操作：

ListNode

*

DlQueue

( );

 判队列空否的函数, 空则返回1, 不空则返回0：int

IsEmpty

( )。

解决方法提示：

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

存放在一个指针队列中。

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

针存放到队列中。

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

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

(1) 两路归并算法

void

merge

(

ListNode * ha

,

ListNode

*

hb,,

ListNode *

&

hc

) {

ListNode *pa, *pb, *pc

;

if (

ha

→

data

<=

hb

→

data

) {

hc

=

ha

;

pa

=

ha

→

link

;

pb

=

hb

; }

else {

hc

=

hb

;

pb

=

hb

→

link

;

pa

=

ha

; }

pc

=

hc

;

while (

pa

&&

pb

)

if (

pa

→

data

<=

pb

→

data

)

{

pc

→

link

=

pa

;

pc

=

pa

;

pa

=

pa

→

link

;

}

else

{

pc

→

link

=

pb

;

pc

=

pb

;

pb

=

pb

→

link

;

}

if (

pa

)

pc

→

link

=

pa

;

else

pc

→

link

=

pb

;

};

(2) 归并排序主程序

void

mergesort

(

ListNode

*

r

) {

ListNode

*

s

,

t

;

Queue

Q

;

if ( !

r

)

return;

s

=

r

;

e

(

r

) ;

while (

s

) {

t

=

s

→

link

;

while (

t

!= 0 &&

s

→

data

<=

t

→

data

) {

s

=

t

;

t

=

t

→

link

; }

if (

t

) {

s

→

link

= 0;

s

=

t

;

e

(

s

) ;

}

}

while ( !

y

( ) ) {

r

=

Q

.

DlQueue

( );

if (

y

( ) ) break;

s

=

Q

.

DlQueue

( );

merge

(

r

,

s

,

t

);

e

(

t

) ;

}

}

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

分）

void demo2(LinkList head,ListNode *p)

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

ListNode *q=head;

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

if (q) Error(“*p not in head”);

q->next=p->next;

free(p);

}

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

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

template

void linkedtosequent(Bintreenode *t,type a[ ],int i){

if (t!=Null){

a[]=t->getData();

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

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

}}

主程序调用方式：linkedtosequent(,a,0);

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

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

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

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

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

(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (

key

) = (7*

key

) % 10 + 1, 寻找下一个空

位的公式为 H

i

= (H

i-1

+ RH (

key

)) % 13, H

1

= H (

key

)。画出相应的散列表, 并计算等概率下搜

索成功的平均搜索长度。

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

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

利用线性探查法造表：

0

78

1

1

2

15

1

3

03

1

4

5

57

1

6

45

1

7

20

1

8

31

4

9

10

23

1

11

36

2

12

12

1

0

78

1

1

2

15

1

3

03

1

4

5

57

1

6

45

1

7

20

1

8

31

3

9

36

5

10

23

1

11

12

12

1

9、阅读下面程序，指出其算法的功能并求出其时间复杂度。

（1） int Prime(int n){

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

while(i<=x){

if(n%i==0)break;

i++;

}

if(i>x) return 1;

else return 0;

}

(2)int sum1(int n){

int p=1,s=0;

for(int i=1;i<=n;i++)

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

return s;

}

答案：（1）程序功能是判断n是否是一个素数，若是则返回数值1，否则返回数值0，

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

（2）程序功能是计算∑

填入正确的语句。

int symmetry(DblList DL) {

int sym=1;

DblNode p=DL->rLink,q=DL->lLink;

While(p!=q&&p->lLink==q)&& sym==1 )

if (p->data==q->data){

p=p->rLink;

q=q->lLink;

}

else sym=0;

n

i=1

i!，该算法的时间复杂度为O（n）.

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

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

ASL

succ

=1/10（1+1+1+1+1+1+4+1+2+1）=14/10

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

ASL

unsucc

=1/13（2+1+3+2+1+5+4+3+2+1+5+4+3）=36/13

利用双散列法造表：

H

i

=（H

i-1

+

RH(key)）%13, H

i

=H(key)

return sym;}

11、阅读下面程序，指出其算法的功能

#include “stack.h”

int BaseTrans(int N,int B) {

int i,result=0;StackS;

while(N!=0){i=N%B;N=N/B;(i);}

while(!y()){i=();();

result=result*10+i;}

return result;

}

答案：该算法是将一个非负的十进制整数N转换为另一个基数为B的B进制数。

12、阅读下面程序，指出其算法的功能

template

void BinaryTree::binsearchTree(BinTreeNode*t,int &bs) {

if(t!=Null){

if((t->letfchild==Null||t->data>t->leftchild->data)&&

(t->rightchild==Null||t->datarightchild->data)) {

bs=1;

binsearchTree(t->leftchild,bs);

if(bs) binsearchTree(t->rightchild,bs);

}

else bs=0;

} }

答案：该算法是判别给定的以二叉链表存储的二叉树是否是二叉搜索树。采用递归算法，对树中

的所有结点检查是否左子树上结点的关键码都小于它的关键码，右子树上结点的关键码都大于它

的关键码。如满足上述条件，则是二叉搜索树。

六、综合算法题

1、试设计一个实现下述要求的查找运算函数

Locate

。设有一个带表头结点的双向链表

L

，

每个结点有4个数据成员：指向前驱结点的指针

llink

、指向后继结点的指针

rlink

，存放字符数

据的成员

data

和访问频度

freq

。所有结点的

freq

初始时都为0。每当在链表上进行一次

Locate

(

L

,

x

) 操作时，令元素值为

x

的结点的访问频度

freq

加1，并将该结点前移，链接到与它的访问频

度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点

总是靠近表头。

答案：

(1) 定义链表结构

struct

DoubleListNode

{

char

data

;

int

freq

;

DoubleListNode

*

llink

, *

rlink

;

};

初始时，所有结点的

freq

域的值都为0。

(2) 定义函数

DoubleListNode

*

locate

(

DoubleListNode

*

f

; char &

x

) {

DoubleListNode *

p

, *

q

;

p

=

f

→

rlink

; /*跳过表头结点*/

while (

p

!=

NULL

&&

p

→

data

!=

x

)

p

=

p

→

rlink

; /*搜索*/

if (

p

) {

p

→

freq

++;

q

=

p

→

llink

;

p

→

rlink

→

llink

=

q

;

q

→

rlink

=

p

→

rlink

; /*从链中摘下

p

*/

while (

q

!=

f

&&

q

→

freq

<

p

→

freq

)

q

=

q

→

llink

;

p

→

llink

=

q

;

p

→

rlink

=

q

→

rlink

;

q

→

rlink

→

llink

=

p

;

q

→

rlink

=

p

; /*在

q

后面插入

p

*/

}

return

p

;

}

2、已知A[n]为整数数组，试写出实现下列运算的递归算法：

(1) 求数组A中的最大整数。

(2) 求n个整数的和。

(3) 求n个整数的平均值

答案：#include

class RecurveArray{

private:

int *Elements;

int ArraySize;

int CurrentSize;

public:

RecurveArray (int MaxSize=10):

ArraySize(MaxSize),Elements(new int[MaxSize]){ }

~ RecurveArray ( ){delete[ ] Elements;}

void InputArray( ) ;

int Maxkey(int n);

int sum(int n);

float Average (int n);

};

void RecurveArray:: InputArray( ) {

cout<<”Input the number of Array :n”;

for (int i=0;i< ArraySize;i++) cin>> Elements[i];

}

int RecurveArray::Maxkey(int n) {

if(n= =1) return Elements[0];

int temp= Maxkey(n-1);

if(Elements[n-1]>temp) return Elements[n-1];

else return temp;

}

int RecurveArray::Sum(int n) {

if (n= =1) return Elements[0];

else return Elements[n-1]+Sum(n-1);

}

float RecurveArray::Average(int n) {

if (n= =1) return (float)Elements[0];

else return ((float) Elements[n-1]+(n-1)*Average(n-1))/n;

}

int main(int argc, char *argv[ ]){

int size=1;

cout<<” the Elements:”;

while (size<1) cin>>size;

RecurveArray ra(size);

rray( );

Cout<<”n The max is :”<<(e)<

Cout<<”n The Sum is :”<

Cout<<”n The ave is :”<

Return 0;

}

3、 试编写一个函数计算n!*2

n

的值，结果存放于数组A[arraySize]的第n个数组元素中，0  n

 arraySize。若设计算机中允许的整数的最大值为maxInt，则当n > arraySize或者对于某一个

k (0  k  n)，使得k!*2

k

> maxInt时，应按出错处理。可有如下三种不同的出错处理方式：

(1) 用cerr <<及exit (1)语句来终止执行并报告错误；

(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；

(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。

用你认为是最好的方式实现它。

答案：#include “iostream.h”

#define arraySize 100

#define MaxInt 0x7fffffff

int calc (int t[ ],int n){

int i,edge=MaxInt/n/2;

t[0]=1;

if (n!=0) {

for (i=1;i

t[i]=t[i-1]*i*2;

if(t[i]>edge) return 0;

}

t[n]=t[n-1]*n*2;

}

cout<<”t[“<

return 1;

}

void main()

{int A[arraySize];int i;

for(i=0;i

if(!calc(A,i) ){

cout<<”failed at ”<

break;}}

4、 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测

试数据来验证这个算法。

答案：

include

include”string.h”

const int charnumber=128;

void frequency(string&s,int C[ ]){

for(int i=0;i< charnumber;i++) C[i]=0;

for( i=0;i< ();i++) C[atoi(s[i])]++;

for( i=0;i< charnumber;i++)

if(C[i]>0) cout<<”(”<

}

测试数据 s=”cast cast sat at a tasa0”

测试结果

A

C

c

2

a

7

s

4

t

5

空格

5

for(j=0;j

if(row[i]= =col[j])

cout<<”The saddle point is :(“<

delete[ ]row; delete[ ]col;

}

此算法有3个并列二重循环，其时间复杂度为O(m*n).

6、试编写一个函数，将一个有n个非零元素的整数一维数组A[n]拆分为两个一维数组，使

得A[ ]中大于零的元素存放在B[ ]中，小于零的元素存放在C[ ]中。

答案：

void fenjie(int A[],int B[],int C[],int n,int &pb,int &pc){

pb=pc=-1;

for(int k=0;k

if(A[k]>0) B[++pb]=A[k];

else C[++pc]=A[k];}

7、已知在一维数组A[m+n]中依次存放着两个顺序表（a

0,

a

1,

... a

m-1,

）和（b

0,

b

1,

... b

n-1,

），试

编写一个函数，将数组中两个顺序表的位置互换，即交（b

0,

b

1,

... b

n-1,

）放在（a

0,

a

1,

... a

m-1,

）

的前面。

答案：#define mpn 20

typedef int DataType;

void inverse(DataType A[ ],int st, int ed);

void exchange(DataType A[ ],int m, int n){

inverse(A,0,m+n-1);

inverse(A,0,n-1);

inverse(A,n,m+n-1);

}

void inverse(DataType A[ ],int st, int ed){

int md=(st+ed)/2;

for(int i=0;i

{ DataType temp=A[st+i]; A[st+i]= A[ed-i]; A[ed-i]=temp;}}

8、 设有一个表头指针为

h

的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点

的链接方向逆转，如下图所示。要求逆转结果链表的表头指针

h

指向原链表的最后一个结点。

5、 若矩阵

A

m



n

中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则

称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中

的位置（若鞍点存在时），并分析该函数的时间复杂度

答案：int minmax(int A[ ][ ],const int m,const int n) {

int *row=new int [m]; int *col=new int [n];

int i,j;

for(i=0;i

row[i]=A[i][0];

for(j=1;j

if(A[i][j]

}

for(j=0;j

col[i]=A[0][j];

for(i=1;i

if(A[i][j]>col[j]) col[j]=A[i][j];

}

for(i=0;i

答案：templatevoid List ::Inverse(){

if(first==Null) return ;

ListNode*p=first->link,*pr=Null;

While(p!=Null){

First->link=pr;

Pr=first;first=p;p=p->link;

}

first->link=pr;

}