数据结构与算法：试题解析与实践

数据结构与算法试题数据结构与算法试题一、单选题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<m;i++) for="" (int="" j="0;j<n;j++)" a[i][j]="i*j;" a="" o(m2)="" b="" o(n2)="" c="" o(m*n)="" d="" o(m+n)="" 14、下面程序段的时间复杂度为(="" )="" int="" f(unsigned="" n)="" {="" if(n="=0" ||="" n="=1)" return="" 1;="" 数据结构与算法试题="" else="" n*f(n-1);="" }="" o(1)="" o(n)="" o(n="" !)="" 15、线性表若就是采用链式存储结构时,要求内存中可用存储单元的地址(="" )。="" 必须就是连续的="" 部分地址必须就是连续的="" 一定就是不连续的="" 连续或不连续都可以="" 16、数据结构的定义为(d,s),其中d就是(="" )的集合。="" 算法="" b数据元素="" 数据操作="" 逻辑结构="" 17、算法分析的目的就是(="" 找出数据结构的合理性="" 研究算法中输入与输出的关系="" 分析算法的效率以求改进="" 分析算法的易懂性与文档性="" 18、在一个单链表中,若p所指结点不就是最后结点,在p之后插入s所指结点,则执行(="" 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;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 )

数据结构与算法试题

的存储位置就是( 1044)。

28、在插入与选择排序中,若初始数据基本正序,则选择(插入排序),若初始数据基本反序,则最好选择(选择排序)。

29、算法就是对特定问题的求解步驟的一种描述,它就是(指令)的有限序列,每一条(指令)表示一个或多个操作。

30、对于一个具有n个顶点肯e 条边的无向图,进行拓朴排序时,总的进间为(n) 31、构造哈希函数有三种方法,分别为(平方取中)法、(除留余数)法、(折迭移位)法。

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

33、对于含有n个顶点与e条边的无向连通图,利用普里姆算法产生的最小生成树,其时间复杂度为( Ｏ(n2) )、利用克鲁斯卡尔算法产生的最小生成树,其时间复杂度为(Ｏ(elog2e) )

34、快速排序在平均情况下的时间复杂度为(Ｏ(nlog2n)),在最坏情况下的时间复杂度为(Ｏ(n2));快速排序在平均情况下的空间复杂度为(Ｏ(log2n)),在最坏情况下的空间复杂度为(Ｏ(n))。

35、假定一组记录的排序码为(４６,７９,５６,３８,４０,８０),对其进行归并排序的过程中,第二趟排序后的结果就是(［３８ ４６ ５６ ７９］［４０ ８０］)

36、假定一组记录的排序码为(４６,７９,５６,３８,４０,８０),对其进行快速排序的第一次划分的结果就是(［３８ ４０］４６［５６ ７９ ８０］)。

37、一个结点的子树的( 个数 )称为该结点的度。度为( 零 )的结点称为叶结点或终端结点。度不为( 零 )的结点称为分支结点或非终端结点。树中各结点度的( 最大值 )称为树的度。

数据结构与算法试题

38、设Ki=Kj (1<=i<=n, 1<=j<=n,j<>i)且在排序前的序列中Ri领先于Rj (i<j),若排序后的序列中ri仍领先于 rj,则这种排序方法就是(稳定的),反之就是(不稳定的)。="" 40="" 、在堆排序的过程中,对任一分支结点进行调整运算的时间复杂度为(Ｏ(log2n)),整个排序过程的时间复杂度为(Ｏ(nlog2n))。="" 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-="" +="" 1个元素="" 2、当一个栈的进栈序列为1234567时,可能的出栈序列有多少种？6457321就是否就是合理的出栈序列？="" 答案:="" 可能的出栈序列有="" 种,6457321不就是合理的出栈序列。="" 3、简单(直接)选择排序就是一种稳定的排序方法不？试举例说明？="" 4291="" 234567891011121314811717="" 14=*************=+c数据结构与算法试题="" (1)各层的结点个数就是ki="" (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=logk(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<||

8、 画出下列广义表的图形表示与它们的存储表示: (1) D(A(c), B(e), C(a, L(b, c, d)))

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

数据结构与算法试题

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

广义表(2)的图形表示为:

广义表(1)的存储表示为:

广义表(2)的存储表示为:

A

B C D

L c

e

a

b

c

d

J1

J3

J2 a

D

0 A 1 C ^ 0 B 1 e ^

A B

0 D

2

2

2 ^

0 C

1 a

2 ^

0 L

1 b

1 C

1 d ^

C L

0 J1

2

2 ^

0 J2

2

1 a

2 ^

0 J3

2 ^

J3

J2

J1

数据结构与算法试题

9、题目:11、将下面的森林变换成二叉树(7分)。

答案:

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

*

+

+

+

f

+ *

+

c b

a

h

g

A

C

D

B F

E

K

J

G

H

I

A

C

D

B

F

E

K

J

G

H

I

数据结构与算法试题

11、根据所给有向图,写出一个拓扑序列。(5分)

答案:

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

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

答案:

1

3

2

5

4

7

6

1

3

2

5

4

7 6

8

5

15

3 10

12

2 7 9

6 1

3

2

5

4

7

6

5

15

3 6 2

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个结点。生成的赫夫曼树为下图所示:

赫夫曼编码为:概率为0、23的字符编码为:00 概率为0、11的字符编码为:010

概率为0、05的字符编码为:0110

23

11

5

3

29 14

7 8

0 0

0

0 0 0 0 1 1

1

1 1 1 1 数据结构与算法试题

概率为0、03的字符编码为:0111 概率为0、29的字符编码为:10

概率为0、14的字符编码为:110 概率为0、07的字符编码为:1110 概率为0、08的字符编码为:1111

14、已知一棵二叉树的前序遍历的结果就是ABECDFGHIJ, 中序遍历的结果就是EBCDAFHIGJ, 试画出这棵二叉树,并给出这棵二叉树的后序遍历序列。

答案:根据前序序列与中序序列能得到唯一的二叉树,所得二叉树如图:

这棵二叉树的后序遍历序列为: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树的最少结点为Nh,则Nh = Fh+3 -1。

A

B

F G

E

C

D

H

J

I

数据结构与算法试题

Fh 就是斐波那契数。又设AVL树有n个结点,则其最大高度不超过3/2*log2(n+1), 最小高度为「log2(n+1) ┐-1。

17、7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度与搜索不成功的平均搜索长度。

____图(1)____

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

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

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

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

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

(3) 求每个活动的最早开始时间e( )与最迟开始时间l( )。

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

509

154

677

017

275

170

503

094 553

897

512 612 765 908

数据结构与算法试题

答案:按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve与最迟允许开始时间Vl,然后再计算各个活动的最早可能开始时间e与最迟允许开始时间l,根据l-e就是否等于0来确定关键活动,从而确定关键路径。

① ③ ② ④ ⑤ ⑥ Ve Vl

<1,2> <1,3> <3,2> <2,4> <2,5> <3,5> <4,6> <5,6> e 0 8 L 17 8 l-e

17

0

0

8

0

12

8

0

此工程最早完成时间为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次。试问散列表需要设计多大？ (设a就是散列表的装载因子,则有ASLsucc = ( 1+1/ (1-a) )/2)。

数据结构与算法试题

答案:已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsucc ≤2,则有:ASLsucc =1/2(1+1/(1-a))≤2 解得 a≤2/3 ,又有:a=n/m=150/m 两式联立得:150/m≤2/3,解得:m≥225、 所以散列表需要设计225个单位。

五、算法分析题

1、给出下列递归过程的执行结果 void unknown ( int w ) {

if ( w ) {

unknown ( w-1 );

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

cout << endl;

} }

调用语句为 unknown (4)。

答案:

(1) 1 2 2

3 3 3

4 4 4 4

2、给出递归过程的执行结果 void unknown ( int n ) {

cout << n % 10 ;

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

数据结构与算法试题

}

调用语句为unknown ( 582 )。

答案: 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为头指针的单链表中。例如,

____图(1)____

在算法实现时,利用了一个队列做为辅助存储, 存储各有序链表构成的归并段的链头指针。初始时, 各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue, 其可直接使用的相关操作有

n 置空队列操作:makeEmpty ( );

n 将指针x加入到队列的队尾操作:EnQueue ( ListNode * x ); n 退出队头元素, 其值由函数返回的操作:ListNode *DlQueue ( ); n 判队列空否的函数, 空则返回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; Q、EnQueue( 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;

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分)

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);

}

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

点的编号为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(t、root,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, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = 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 11 12 78 1 23 36 12 1

1

1

1

1

1

4

1

2

1

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

ASLsucc =1/10(1+1+1+1+1+1+4+1+2+1)=14/10 搜索不成功的平均搜索长度为:

ASLunsucc =1/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) 0 11 12 78 1 36 23 12 1

1

1

1

1

1

3

5

1

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)程序功能就是计算∑ni=1i!,该算法的时间复杂度为O(n)、

10、判断一个带表头结点的双向循环链表L就是否对称相等的算法如下所示,请在算法的 处填入正确的语句。

数据结构与算法试题

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; 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;S、Push(i);} while(!S、IsEmpty()){i=S、GetTop();S、Pop(); 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 <iostream、h> 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<<”No、of the Elements:”; while (size<1) cin>>size; RecurveArray ra(size); Ra、InputArray( );

Cout<<”\n The max is :”<<ra、maxkey(ra、maxsize)<<end1; cout<<”\n="" the="" sum="" is="" :”<<ra、="" (ra、maxsize)<<end1;="" ave="" :”<<ra、average(ra、maxsize)<<end1;="" return="" 0;="" }="" 3、="" 试编写一个函数计算n!*2n的值,结果存放于数组a[arraysize]的第n个数="" 数据结构与算法试题="" 组元素中,0="" £="" n="" arraysize。若设计算机中允许的整数的最大值为maxint,则当n=""> arraySize或者对于某一个k (0 £ k £ n),使得k!*2k > 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<n;i++){ t[i]="t[i-1]*i*2;" if(t[i]="">edge) return 0; }

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

cout<<”t[“<<n<<”]=”<<t[n]<<end1; return="" 1;="" 数据结构与算法试题="" }="" void="" main()="" {int="" a[arraysize];int="" i;="" for(i="0;i<arraySize;i++)" if(!calc(a,i)="" ){="" cout<<”failed="" at="" ”<<i<<”、”<<end1;="" break;}}="" 4、="" 编写一个算法frequency,统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。="" 答案:="" include="" <iostream、h=""> 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< s、length();i++) C[atoi(s[i])]++; for( i=0;i< charnumber;i++)

if(C[i]>0) cout<<”(”<<i<<”):\t”<<c[i]<<”\t”; }="" 测试数据="" s="”cast" cast="" sat="" at="" a="" tasaif(C[i]>0) cout<<”(”<<i<<”):\t”<<c[i]<<”\t”; }="" 测试数据="" s="”cast" cast="" sat="" at="" a="" tasa\0”="" 测试结果="" c="" t="" 空格="" 2="" 7="" 4="" 5="" 5、="" 若矩阵am´n中的某一元素a[i][j]就是第i行中的最小值,同时又就是第j列中的最大值,则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵,试="" 数据结构与算法试题="" 编写一个函数,确定鞍点在数组中的位置(若鞍点存在时),并分析该函数的时间复杂度="" 答案:int="" minmax(int="" a[="" ][="" ],const="" int="" m,const="" n)="" {="" *row="new" [m];="" *col="new" [n];="" i,j;="" for(i="0;i<m;i++){" row[i]="A[i][0];" for(j="1;j<n;j++)" if(a[i][j]<row[i])="" col[i]="A[0][j];" if(a[i][j]="">col[j]) col[j]=A[i][j]; }”="" 测试结果="" c="" t="" 空格="" 2="" 7="" 4="" 5="" 5、="" 若矩阵am´n中的某一元素a[i][j]就是第i行中的最小值,同时又就是第j列中的最大值,则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵,试="" 数据结构与算法试题="" 编写一个函数,确定鞍点在数组中的位置(若鞍点存在时),并分析该函数的时间复杂度="" 答案:int="" minmax(int="" a[="" ][="" ],const="" int="" m,const="" n)="" {="" *row="new" [m];="" *col="new" [n];="" i,j;="" for(i="0;i<m;i++){" row[i]="A[i][0];" for(j="1;j<n;j++)" if(a[i][j]<row[i])="" col[i]="A[0][j];" if(a[i][j]="">col[j]) col[j]=A[i][j]; }

for(i=0;i<m;i++){ for(j="0;j<n;j++)" if(row[i]="=col[j])" cout<<”the="" saddle="" point="" is="" :(“<<i<<”,”<<j<<”)”<<end1;="" delete[="" ]row;="" ]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<n;k++)" if(a[k]="">0) B[++pb]=A[k]; else C[++pc]=A[k];}

7、已知在一维数组A[m+n]中依次存放着两个顺序表(a0, a1, 、、、 am-1,)与(b0, b1, 、、、 bn-1,),试编写一个函数,将数组中两个顺序表的位置互换,即交(b0, b1, 、、、 bn-1,)放在(a0, a1, 、、、 am-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<md-st;i++) {="" datatype="" temp="A[st+i];" a[st+i]="A[ed-i];" a[ed-i]="temp;}}" 8、="" 设有一个表头指针为h的单链表。试设计一个算法,通过遍历一趟链表,将链表中所有结点的链接方向逆转,如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。="" 数据结构与算法试题

____图(1)____

答案: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; }