数据结构精选考研试题(5)

[注] 编写程序可选用PASCAL 或 C 语言（2002年）

算法描述采用类语言，应加上必要的注释 所有答案均要求写在答题纸上

一、 回答问题 [15分] 1．结构化程序设计

2．面向对象开发方法与面向过程开发方法的不同之处 3．数据类型含义与作用 4．稳定排序与不稳定排序 二、简述方法与原因 [20分]

1． 分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表

按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。

2．实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法，若不能，请简述原因。

3.有n个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简述处理方法。

4．说明在图的遍历中，设置访问标志数组的作用。

5.在一个连通无向图上，欲求从一点VI到另一点VJ（VI≠VJ）所经结点数目最少的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。

三、构造结果 [25分]

1. 二叉树按二叉链表方式存放，其中的data域为char类型，已

有按前序方式构造二叉树的算法，若输入序列为AB□CD□□ED□G□□□，请给出构造的相应二叉树。

2.已知Ackerman函数定义如下：

n+1 当m=0时

akm(m,n) = akm(m-1,1) 当m≠0,n=0时

akm(m-1, akm(m,n-1)) 当m≠0,n≠0时

写出akm(2,1)时调用时变化过程与执行结果。

3. 对于正整数A、B，说明下面程序段定义了什么函数功能，要求重写程序段，使之完成原函数功能，且执行时间仅可能短。 Unsigned int f(a,b) int a,b;

{if (a*b==0)

return (a+b)

else return(f(b-(b/a)*a,a); (注：b/a相当整除) }

4. 写出在中序线索树BT中找结点X的后继结点的函数过程。

5.对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul），哈希函数为H（K）=关键字中第一个字母在字母表中的序号）MOD 7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。

四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。[10分]

五、 一棵树采用孩子-兄弟方式存放，结点结构为

fch data nsib level

其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。 设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[10分]

六、 以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分

析算法的时间复杂度. [10分] 七、 编写程序，要求完成：

建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。

在此链表上实现对二进制数加1的运算，并输出运算结果。[10分]

[注]编写程序可选用Pascal或C语言，算法描述采用类语言(1997年) 一、 简答下列问题：[15分]

1． 结构化程序设计目的、结构、方法 2． 面向对象程序设计语言的特征

3． 程序测试目的及程序可能存在的错误类型

4． 常用的参数传递方式的名称与作用

5． 为什么说数组和广义表是线性表的推广

二、 写出要求结果[38分]

1． 给定权值{7，3，6，12，8，15}，构造相应哈夫曼树，并计算其带权路径长度。

2． 有一组关键码49，38，65，97，76，13，27，43，采用堆排序方法，请写出每趟排

序结果。

3． 在后序线索树中，要找出结点P的前趋结点，请写出有关语句

Ltag Lc data Rtag Rc 4． 快速排序方法中，能否用队列代替栈，请简要说明理由。

5． 设有关键字序列{32，53，78，12，25，62，43}，哈希函数H(K)=K mod 7，用线

性探测再散列方法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与查找不成功的平均查找长度。

6． 有一棵二叉排序树，树中结点各不相同，欲得到一个由大到小的结点值递减序列，

你认为应当采用什么方法，便可得到要求结果。

7． 给出右边有向图G的邻接表表示，按Dijkstra算法，给出由V0到其余各顶点的最

短路径。（要求按算法步骤次序，产生各个最短路）

100 60 30 4 10 10 20

5 50

8． 对于正整数a,b,使说明下面的过程定义了什么函数功能，并要求把它重写，使得

能完成原来功能，且执行时间尽可能短。

Unsigned int f(a,b)

Unsigned int a,b;

{if (a*b==0) （ 注：==是相等） return (a+b); else

return(f(b-(b/a)*a,a)); （ 注：b/a相当整除） }

三、 编写一程序：

（1） 输入m个1-n之间正整数（m>n），统计其中1-n中各个数值个数到C数组 （2） 将数组C[1:n]中所有奇数移到偶数之前，要求时间复杂度为O(n)。[8分]

四、 编写一程序，将一个循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅含奇次项或偶数项，并要求利用原链表中的结点空间来构成这两个链表。[8分]

五、 棵树采用孩子-兄弟方式存放，结点结构为

fch data nsib level

其中fch 表示指向第一个孩子，nisib表示指向下一个兄弟, level表示结点层次。 设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[8分]

六、 一棵二叉树的内部路径长度等于从树根到每个结点路径长度之和，二叉树用二叉链表存放，请用递归算法，编写一个二叉树内部路径长度算法。[8分]

七、 一棵二叉树用二叉链表存放，且二叉树中结点各不相同。编写一算法，查找数据域为x的结点，并打印输出值为x结点的所有祖先。[8分]

八、 有N×N个元素（N=2m）构成的二维阵列，将其转换成一个四叉树表示，转换原则如下： 将阵列4等分为四个子区域，做为四叉树的四个分支，若该子区域所有元素值均为0或均为1，则对应的四叉树为叶子结点，填值为1或0；若该子区域值不一致，则对该区域可再划分，形成下一层的子树，递归重复，直到每个子区域对应相应叶结点或到达元素这一级为止。 要求：写出从二维阵列转换生成四叉树的算法基本思路，再给出从二维阵列转换生成四叉树的算法。[7分]

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构精选考研试题(5)在线全文阅读。