当前位置:甜馍馍地理信息网 >> 地理信息系统GIS >> 算法与数据结构 >> 正文 >>  [阅读资讯:2001年中国地质大学地信专业考研试题数据结构]

2001年中国地质大学地信专业考研试题数据结构

[ 来源:互联网 | 时间:2009年03月31日 | 收藏本文 ] 【

一、简答(20分)

1、若用二元组DS=(D,S)形式说明线性表L,应如何表示L中数据元素集D和关系集S?

2、有五个数据依次进栈:A,B,C,D,E,在各种出栈的序列中,以B,D先出栈的序列有哪几个?(B在D之前出栈)

3、简述循环队列的实现方法,并用图示予以说明,设h和t分别为循环队列Q[0..m]的头指针和尾指针,试给出求当前Q中元素个数的公式。

4、文件的基本组织方式有哪几种?

二、将6个数1,2,3,4,5,6,填入如图所示的二叉树的节点中,使之成为一颗二叉排序树。若把数3.5放入此树并使该树保持性质不变,增加一个节点可放在什么位置?画出两种可能的放置方案(6分)

三、设某通讯电文由A,B,C,D,E,F,G七个字符组成,它们在电文中出现的次数分别是9,5,4,6,2,8,1,试为这七个字符设计Huffman编码 (8分)

四、已知一棵二叉树B的中序遍历序列为DBHEAFJICG,后序遍历序列为DHEBJIFGCA,完成下列各题:(14分)

1、构造该二叉树B

2、写出按先序遍历B

3、画出B的后续前驱线索

五、已知带权的无向图G如下:(16分)

1、画出G的邻接多重表结构以及G的一棵最小生成树

2、写出从顶点V1出发,按深度优先和广度优先搜索G所得到的顶点序列

3、利用Dijkstra算法,求出从顶点V1到其余各顶点的最短路径,要求写出执行算法过程中各步的状态。

六、对长度为n的有序表进行折半查找,指出其平均查找长度,并证明之。(8分)

七、某整型数组A中的9个元素值依次为:

18,10,35,6,27,3,44,30,12

将A中元素按从小到大排序:(不用写算法)(16分)

1、第一个元素值18作为分割数,试写出用“快速排序”对A进行排序的第一趟过程。

2、用“堆排序”,试写出建立初始堆的过程,以及将第一个选出的元素放在A的最后位置上,将A调整为堆后的A中结果。

八、请用PASCAL或C语言设计以下算法 (12分)

1、若以二叉链表作为二叉树B的存储结构,t为指向根节点的指针变量,试编写出B中节点的数目的非递归算法。

2、已知哈希表HT[m],哈希函数为f(x),用链地址法处理冲突(同一线性链表中的记录按关键字递减有序, 排列, ),试编写算法;在表中插入关键字值为K的一项。

【推荐本文】 【打印本页】 【返回顶部

>> 相关文章:

● 上一篇文章:在VC++中嵌入MapX的集成二次开发
● 下一篇文章:复合数据集 CAD到GIS的数据格式转换
最新文章
推荐文章