欢迎来到天天文库
浏览记录
ID:51686367
大小:35.95 KB
页数:2页
时间:2020-03-15
《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分)设计算法将线性表逆置,存储结构为一带头结点的单链表,编程将链表颠倒过来,要求利用原来的结点完成,不开辟新的结点空间。
此文档下载收益归作者所有