当前位置：问答库＞考研试题

一、算法设计题

1． 设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为〇(n)。

【答案】算法如下:

//n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前

//用类C 语言编写，数组下标从0开始

//交换A[i]与

A[j]

//算法Arrange 结束

2． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

3． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

4． 试将下列递归过程改写为非递归过程。

【答案】算法如下:

5． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。

和

分别指示结点i 的左儿子和右儿子，

，使

) 表示i 的左(右) 儿子为空。试写一个

存放结点i 的父亲；然后再写一个判别结点u 是否

算法，由L 和R 建立一个一维数组为结点V 的后代的算法。

【答案】算法如下:

和

是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

T 数组初始化

若结点i 的左子女是则结点L 的

双亲是结点

i

若结点i 的右子女是R , 则R 的

双亲是i

本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代

判断U 是否是V 的后代

二、应用题

6． 写出下面算法中带标号语句的频度。

TYPE

Ar ＝ARRAY[l...n]OF datatype；

PROCEDURE penn(a:ar ；k ，n :integer) ； V AR x:datatype ；i :integer ； BEGIN (1)IF k＝n THENBEGIN

(2)FOR i:＝l TO nDO (3)write(a[i])；

(4)FOR i:＝k TO n DO (5)A[i]:＝a[i]+i*i； (6)perm(a, k+1, n) ；

设k 的初值等于1。

【答案】(1)这是一个递归调用，因k 初值为1, 由语句(6)知，每次调用k 增1，故第(1)语句执行n 次，所以频度是n 。

(2)这是FOR 循环语句，在满足(1)的条件下执行，该语句进入循环体(3)n次，加上最后一次判断出界，故执行了n ＋1次，所以频度是n ＋1。

(3)这是循环体语句，共执行了n 次，所以频度是n 。

(4)这是循环语句，当k ＝l 时判断n ＋1次(进入循环体(5)n次) ，k ＝2时判断n 次，最后一次k ＝n ﹣l 时判断3次，故执行次数是(n＋1) ＋n ＋... ＋3＝(n＋4)(n﹣1)/2次，所以频度是(n＋4)(n﹣1)/2。

(5)语句(5)是(4)的循环体，每次比(4)少一次判断，故执行次数是n ＋(n﹣1) ＋... ＋2＝(n＋2)(n﹣1)/2次，所以频度是(n＋2)(n﹣1)/2。

(6)这是循环体语句，共执行了n ﹣1次，所以频度是n ﹣1。