内容发布更新时间 : 2024/5/18 10:38:58星期一 下面是文章的全部内容请认真阅读。

2001数据结构与程序设计真题(1)

2001数据结构与程序设计真题 试题内容:

一、试给出下列有关并查集(mfsets)的操作序列的运算结果：

union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9),union(1,8),union(3,10),union(3,11),union(3,12),union(3,13),union(14,15),union(16,0),union(14,16),union(1,3),union(1,14)。（union是合并运算，在以前的书中命名为merge） 要求

(1)对于union(i,j)，以i作为j的双亲；（5分） (2)按i和j为根的树的高度实现union(i,j)，高度大者为高度小者的双亲；（5分）

(3)按i和j为根的树的结点个数实现union(i,j)，结点个数大者为结点个数小者的双亲；（5分）

二、设在4地（a,b,c,d）之间架设有6座桥,如图所示: 要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地

(1)试就以上图形说明:此问题有解的条件是什么?(5分) (2)设图中的顶点数为n,试用c或pascal描述与求解此

2016全新精品资料-全新公文范文-全程指导写作 –独家原创

1 / 3

问题有关的数据结构并编写一个算法,找出满足要求的一条回路.(10分)

三、针对以下情况确定非递归的归并排序的运行时间(数据比较次数与移动次数):

(1)输入的n个数据全部有序;(5分) (2)输入的n个数据全部逆向有序;(5分) (3)随机地输入n个数据.(5分) 四、简单回答有关avl树的问题.

(1)在有n个结点的avl树中,为结点增加一个存放结点高度的数据成员,那么每一个结点需要增加多少个字位(bit)?(5分)

(2)若每一个结点中的高度计数器有8bit,那么这样的avl树可以有多少层?最少有多少个关键码?(5分) 五、设一个散列表包含hashsize=13个表项,.其下标从0到12,采用线性探查法解决冲突.请按以下要求,将下列关键码散列到表中.

101003245581263292004000

(1)散列函数采用除留余数法,用%hashsize(取余运算)将各关键码映像到表中.请指出每一个产生冲突的关键码可能产生多少次冲突.(7分)

(2)散列函数采用先将关键码各位数字折叠相加,再用%hashsize将相加的结果映像到表中的办法.请指出每

2016全新精品资料-全新公文范文-全程指导写作 –独家原创

2 / 3

一个产生冲突的关键码可能产生多少次冲突.;(8分) 六、设一棵二叉树的结点定义为 structbintreenode{ elemtypedata;

bintreenode*leftchild,*rightchild; }

现采用输入广义表表示建立二叉树.咛骞娑ㄈ缦? (1)树的根结点作为由子树构成的表的表名放在表的最前面;

(2)每个结点的左子树和右子树用逗号隔开.若仅有右子树没有左子树,逗号不能省略.

(3)在整个广义表表示输入的结尾加上一个特殊的符号(例如”#”)表示输入结果.

例如,对于如右图所示的二叉树,其广义表表示为a(b(d,e(g,)),c(,f)) a /\\ bc

2016全新精品资料-全新公文范文-全程指导写作 –独家原创

3 / 3