搜索
南京邮电学院2001年攻读硕士学位研究生入学考试数据结构试题一、完成下列各题（每小题6分，共18分）：1、已知字符串p=‘abbabbac’，计算next(7)和nextval(7)的值。2、给出下列排序算法最坏的情况时间复杂性，并指出其中那些算法是稳定的？⑴快速排序⑵简单选择排序⑶堆排序3、设度为m的树采用多重链表存储，每个结点有m+1个域，其中有一个数据域，m个指向孩子的指针域。则空指针的数目是多少？说明这种存储方式的利弊。二、完成下列各题：（每小题8分，共40分）1、设二叉树以带右链的先序次序存储，其存储结构如下：6350009000EHFIGABDCJ12345678910则画出该二叉树。2、对于下列AOE网络，求出各活动可能的最早开始时间和允许的最晚完成时间，并问整个工程的最短完成时间是多少？a1=2a10=8a4=2a3=1623514a5=5a8=2a9=9a7=7a8=4a2=73、设有13个初始游程，其长度分别为28，16，33，19，5，7，18，20，12，31，38，22，10。试画出4路合并最佳合并树，并计算它的加权路径长度。4、设散列表ht的长度为11，散列函数h1(key)=keymod11,h2(key)=keymod9+1。采用双重探查法解决冲突，请从空表开始，依次插入下列关键字值序列：70，25，80，35，60，45，50，55，建立散列表。5、设有初始关键字值序列为：71，74，2，72，54，93，52，28，现采用堆排序方法进行排序，请给出手工执行堆排序的过程。三、设E是一棵扩充二叉树的外路径长度，I是内路径长度，n是内结点个数。试写出三者的关系式，并使用数学归纳法证明之。（10分）四、有序表以顺序方式存储，其存储结构说明如下：Typelist=array[1..n]ofinteger实现下列对半查找的函数过程：Functionbisearch(r:list;low,high,tkey:integer):integer;其中，tkey为待查关键字值。若tkey在表r中，则返回该关键字值在表中的位置，否则返回0。并画出n=10的对半查找判定树。（16分）五、已知有n个结点的树以双亲表示法存储在一堆数组中。请设计一个的算法求树中每个结点的层次和树的高度，将求得的每个结点的层次保存在一维数组c中，并分析你所设计的算法的时间复杂性。（16分）