南京经济学院6742.docx
《南京经济学院6742.docx》由会员分享,可在线阅读,更多相关《南京经济学院6742.docx(11页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、南 京 财 经经 大 学2008年攻读读硕士学位研究生入入学考试(初初试)试卷考试科目: 819数据结结构与单片机机 适用专业: 计算机应用用技术 考试时间: 2008年年1月20日下午2:005:00 注意事项: 所有答案必必须写在答题题纸上,做在在试卷或草稿稿纸上无效。第一部分:数据据结构部分试试题(本部分共三大大题,共计775分)一、简答题(共共15题,每每题1分,共共计15分)1已知一有向向图的邻接表表存储结构如如下图所示。根根据有向图的的深度优先遍遍历算法,从从顶点v1出发,所所得到的顶点点序列为何?根据有向图图的广度优先先遍历算法,从从顶点v1出发,所所得到的顶点点序列又为何何?2
2、. 如果最常常用的操作是是取第i个结结点及其前驱驱,则采用单单链表、双链表、顺序表还是单循环链链表这四种存储方方式中的哪一一种最节省时时间?3. 已知一个个图如下图所所示,若从顶顶点a出发,则在在以下四种顶顶点序列中,哪哪一种是按照照深度优先搜搜索法进行遍遍历时可能得得到的序列?为什么? A. a, b, e, dd, c, f B. a, bb, c, e, f, dC. a, e, dd, f, c, b D. a, e, bb, d, c, f4. 向一个栈栈顶指针为HH的链栈中插插入一个s所指的结点时,应该该执行什么样的的运算?5试图在一个个循环顺序队队列中插入一一个元素,需需要判断该
3、队列是否已满。问这与队头头指针的值还还是与队尾指指针的值有关关?6数组元素之之间的关系是是线性的吗?是树形的吗吗?7若一个有向向图的邻接距距阵中对角线线以下的元素素均为零,则则该图是否存在拓扑扑有序序列?8采用邻接表表存储的图的的深度优先遍遍历算法类似似于二叉树的的哪种遍历?9. 广义表 (a,b,(c,d) 的表头、表尾尾是什么?10. 树最适适合用来表示示何种数据?11若广义表表A=(a,b,(c,d),(ee,(f,gg),则则 headd( taiil( heead( ttail( tail( A) ) ) ) ) = ?12. 树的基基本遍历策略略可分为先根根遍历和后根根遍历;二叉叉
4、树的基本遍遍历策略可分分为先序遍历历、中序遍历历和后序遍历历。这里,我我们把由树转转化得到的二二叉树叫做这这棵树对应的的二叉树。问问树的先根遍遍历序列与其其对应的二叉叉树的何种遍遍历序列相同同?13. 在一非非空二叉树的的中序遍历序序列中,根结结点的左、右右边各有哪些些结点?14在对线性性表进行折半半查找时,对对线性表本身身有何要求?15. 一棵二二叉树如图所所示,其中序序遍历的序列列为何?二、解析题(共共题,每题题6分,共计计36分)1请对下面的的无向带权图图,写出它的的邻接表,并并按克鲁斯卡卡尔算法求其其最小生成树树。2分别画出和和下列树对应应的各个二叉叉树:3简述以下算算法的功能(栈栈的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 南京 经济学院 6742
限制150内