2010学位课考试数据结构题目.doc

《2010学位课考试数据结构题目.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2010学位课考试---数据结构一简答题（每题5分，共40分）1.什么叫抽象数据类型？2.算法和程序有什么区别？3.双向链表中结点的一个重要特征是什么？4.写出堆栈的抽象数据类型的定义5.若有循环队列Q[Maximun]，队头指针和队尾指针为front和rear，在不设标志位的情况下，队空和队满的条件应该如何判断。入队和出队的操作如何实现？6.稀疏矩阵压缩存储时存储结构如何定义，给出其描述7.证明，对于任意一颗二叉树，n0=n2+1，这里分别表示度为0和度为2的结点数目8.有向图和无向图用邻接矩阵存储时各有什么特点？二解答题（每题12分，共48分）1.设一棵二叉树

2、的先序、中序遍历序列分别为：先序ABDFCEGH、中序BFDAGEHC（1）画出这棵二叉树（2）画出这棵二叉树的后序线索树（3）将这棵二叉树转换为对应的森林2.已知如下图所示的无向图（1）给出其存储结构的邻接链表表示（2）写出从顶点1出发的对其分别进行深度、广度优先遍历的结果1.对关键字集{30，15，21，40，25，26，36，37}，若哈希表长为10，哈希函数为H(key)=key%7，采用线性探测再散列方法解决冲突（1）画出哈希表（2）计算查找成功时的平均查找长度。2.已知某文件的记录关键字集为{50，10，50，40，45，85，80}，选择一种从平均性

3、能而言是最佳的排序方法进行排序，且说明其稳定性。三算法设计题（12分）设计算法将线性表逆置，存储结构为一带头结点的单链表，编程将链表颠倒过来，要求利用原来的结点完成，不开辟新的结点空间。