欢迎来到麦多课文档分享! | 帮助中心 海量文档,免费浏览,给你所需,享你所想!
麦多课文档分享
全部分类
  • 标准规范>
  • 教学课件>
  • 考试资料>
  • 办公文档>
  • 学术论文>
  • 行业资料>
  • 易语言源码>
  • ImageVerifierCode 换一换
    首页 麦多课文档分享 > 资源分类 > DOC文档下载
    分享到微信 分享到微博 分享到QQ空间

    [考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编4及答案与解析.doc

    • 资源ID:844589       资源大小:63KB        全文页数:12页
    • 资源格式: DOC        下载积分:2000积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    二维码
    微信扫一扫登录
    下载资源需要2000积分(如需开发票,请勿充值!)
    邮箱/手机:
    温馨提示:
    如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如需开发票,请勿充值!如填写123,账号就是123,密码也是123。
    支付方式: 支付宝扫码支付    微信扫码支付   
    验证码:   换一换

    加入VIP,交流精品资源
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    [考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编4及答案与解析.doc

    1、计算机专业基础综合数据结构(图)历年真题试卷汇编 4 及答案与解析一、单项选择题1 若一个有向图具有拓扑排序序列,那么它的邻接矩阵必定为( )。【中国科学技术大学 1997 一、3(1 分)2004】(A)对称矩阵(B)稀疏矩阵(C)三角矩阵(D)一般矩阵2 采用邻接表存储的图的深度优先遍历算法类似于树的( ),而其广度优先遍历算法类似于树的( ) 。【北京交通大学 2007】(A)中序遍(B)先序遍历(C)后序遍(D)按层次遍历3 执行( ) 操作时,需要使用队列作辅助存储空间。【华中科技大学 2006 一、1(2分)】(A)查找哈希(Hash)表(B)广度优先搜索图(C)先序 (根)遍历二

    2、叉树(D)深度优先搜索图4 图的 BFS 生成树的树高比:DFS 生成树的树高( )。【青岛大学 2004 一、8(3分)】(A)小或相等(B)小(C)大或相等(D)大5 无向图 G=(V,E),其中:V=a,b,c,d,e ,f ,E=(a,b),(a,e) ,(a,c),(b,e),(c,f) ,(f,d),(e,d),对该图进行深度优先遍历,得到的顶点序列正确的是( )。【南京理工大学 2001 一、14(15 分) 】(A)a,b, e,c,d,f(B) a,c ,f,e ,b,d(C) a,e ,b,c,f,d (D)a,e,d,f, c,b6 设图如下所示,在下面的 5 个序列中,

    3、符合深度优先遍历的序列有多少? ( )。【南京理工大学 2000 一、20(15 分)】 a e b d f c ;a cf d e b; a e df c b; a efd c b; a efd b c(A)5 个(B) 4 个(C) 3 个(D)2 个6 下图中给出由 7 个顶点组成的无向图。从顶点 1 出发,对它进行深度优先遍历得到的序列是(),而进行广度优先遍历得到的顶点序列是()。【中科院软件所1999 六、2(1)(2 分)】7 (A)1354267(B) 1347652(C) 1534276(D)1247653(E)以上答案均不正确8 (A)1 534267(B) 1 72645

    4、3(C) 1 354276(D)1 247653(E)以上答案均不正确9 下面哪一方法可以判断出一个有向图是否有环(回路)?( )【东北大学 2000 42(4 分) 】(A)深度优先遍历(B)拓扑排序(C)求最短路径(D)求关键路径10 判断有向图是否有回路,除了可以用拓扑排序外,还可以用( )。【南京理工大学 2004 一、7(1 分) 】(A)求关键路径的方法(B)广度优先遍历算法(C)求最短路径的算法(D)深度优先遍历算法11 在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( ) 。【合肥工业大学 2001 一、2(2 分)】(A)O(n)(B) O(n+e)(C)

    5、 O(n2)(D)O(n 2)12 在求边稠密的图的最小代价生成树时,采用( )算法较合适。【上海交通大学2005 四、7(2 分) 】(A)普里姆(Prim)(B)克鲁斯卡尔(Kruskal)(C)迪杰斯特拉(Dijkstra)(D)其他13 在具有 n 个顶点的图 G 中,若最小生成树不唯一,则 ( )。【电子科技大学2008 一、2(1 分) 】(A)G 的边数一定大于 n-1(B) G 的权值最小的边一定有多条(C) G 的最小生成树的代价不一定相等(D)上述选项都不对14 (1)求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无

    6、意义; (2)利用 Dijkztra 求每一对不同顶点之间的最短路径的算法时间是 O(n3)(图用邻接矩阵表示) ; (3)Floyd 求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。上面不正确的是( )。【南京理工大学 2000 一、21(15 分)】(A)(1),(2),(3)(B) (1)(C) (1),(3)(D)(2),(3)15 当各边上的权值( ) 时,BFS 算法可用来解决单源最短路径问题。【中科院计算所 2000 一、3(2 分) 】(A)均相等(B)均互不相等(C)不一定相等16 求解最短路径的 Floyd 算法的时间复杂度为( )。【合肥工业大学 199

    7、9 一、2(2分)】【 中南大学 2005 一、8(2 分)】(A)O(n)(B) O(n+e)(C) O(n*n)(D)O(n *n*n)17 已知有向图 G=(V,E),其中 V=V1,V 2,V 3,V 4,V 5,V 6,V 7,庐1,V 2, 1,V 3, 1,V 4, 2,V 5, 3,V 5, 3,V 6, 4,V 6, 5,V 7, 6,V 7,G 的拓扑序列是( ) 。【北京航空航天大学 2000 一、 7(2 分)】(A)V 1,V 3,V 4,V 6,V 2,V 5,V 7 (B) V1,V 3,V 3,V 6,V 4,V 5,V 7(C) V1,V 3,V 4,V 5,

    8、V 2,V 6,V 7(D)V 1,V 2,V 5,V 3,V 4,V 6,V 718 若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列( )。【 中科院计算所 1998 二、6(2 分) 】【中国科技大学 1998 二、6(2 分)】(A)存在(B)不存在19 一个有向无环图的拓扑排序序列( )是唯一的。【北京邮电大学 2001 一、3(2分)】(A)一定(B)不一定20 在有向图 G 的拓扑序列中,若顶点所在顶点 Vj 之前,则下列情形不可能出现的是( )。【南京理工大学 2000 一、9(15 分) 】【江苏大学 2006 一、1(2 分)】(A)G 中有弧 j(

    9、B) G 中有一条从 Vi 到 Vj 的路径(C) G 中没有弧 i,V j(D)G 中有一条从 Vj 到 Vj 的路径21 在用邻接表表示图时,拓扑排序算法时间复杂度为( )。【合肥工业大学 2000一、2(2 分) 】【 南京理工大学 2001 一、9(15 分)】【青岛大学 2002 二、3(2 分)】(A)O(n)(B) D(n+e)(C) O(n*n)(D)D(n *n*n)二、判断题22 最小代价生成树是唯一的。( )【山东大学 2001 一、5(1 分)】(A)正确(B)错误23 一个网(带权图) 都有唯一的最小生成树。( ) 【大连海事大学 2001 一、14(1 分)】(A)

    10、正确(B)错误24 连通图上各边权值均不相同,则该图的最小生成树是唯一的。( )【哈尔滨工大 2000 三、3(1 分) 】【烟台大学 2007 二、12(1 分)】【中国海大 2007 二、10(1 分)】(A)正确(B)错误25 无向连通图的最小生成树是唯一的。( )【上海海事大学 2005 一、7(2 分)】(A)正确(B)错误26 图的最小支撑树是唯一的。( ) 【吉林大学 2007 一、6(1 分)】(A)正确(B)错误27 带权的连通无向图的最小代价生成树是唯一的。( )【东南大学 2001 一、5(1分)】(A)正确(B)错误28 若连通图上各边的权值均不相同,则该图的最小生成树

    11、是唯一的。( )【同济大学 2004】(A)正确(B)错误29 在图 G 的最小生成树 G1 中,可能会有某条边的权值超过未选边的权值。( )【合肥工业大学 2000 二、7(1 分)】(A)正确(B)错误30 所谓赋权无向图 G 的最小生成树 T,就是将 G 中各结点间的最短路径作为边而构造出的 G 的子图。( )【上海交通大学 1994 一、 5(2 分)】(A)正确(B)错误31 最小生成树的 Kruskal 算法是一种贪心法。( )【华南理工大学 2002 一、6(1 分)】【烟台大学 2007 二、10(1 分)】(A)正确(B)错误计算机专业基础综合数据结构(图)历年真题试卷汇编

    12、4 答案与解析一、单项选择题1 【正确答案】 D【试题解析】 若是下三角矩阵,说明编号大的顶点是弧尾,编号小的顶点是弧头,不会出现编号小的顶点指向编号大的顶点的现象。上三角矩阵恰恰相反。这两种情况说明该有向图可以拓扑排序,但是具有拓扑排序序列的有向图的邻接矩阵不一定是三角矩阵。有向无环图具有拓扑排序序列,其邻接矩阵没有明显特征。2 【正确答案】 B,D3 【正确答案】 B4 【正确答案】 A5 【正确答案】 D6 【正确答案】 D【试题解析】 第一个和第四个序列符合深度优先遍历。7 【正确答案】 C8 【正确答案】 C9 【正确答案】 A,B10 【正确答案】 D11 【正确答案】 B12 【

    13、正确答案】 A13 【正确答案】 A【试题解析】 生成树有 n 个顶点和 n1 条边。最小生成树是权值之和最小的那棵生成树。若最小生成树不唯一,一定是有权值相等的边,但未必是权值最小的边相等。最小生成树的代价一定相等。当然,G 的边数一定大于 n1,否则,就只有一棵生成树了。14 【正确答案】 C15 【正确答案】 A16 【正确答案】 D17 【正确答案】 A18 【正确答案】 A19 【正确答案】 B20 【正确答案】 D【试题解析】 若有向图 G 的拓扑序列中,顶点 Vi 在顶点 Vj 之前,不可能出现有一条从 Vj 到 Vi 的路径。因为若是有这样一条路径,说明图中存在回路,不可能拓扑排序成功。A、B 和 C 都可能存在,即本题选择 D。21 【正确答案】 B二、判断题22 【正确答案】 B23 【正确答案】 B24 【正确答案】 A25 【正确答案】 B26 【正确答案】 B27 【正确答案】 B28 【正确答案】 A29 【正确答案】 A30 【正确答案】 B31 【正确答案】 A


    注意事项

    本文([考研类试卷]计算机专业基础综合数据结构(图)历年真题试卷汇编4及答案与解析.doc)为本站会员(towelfact221)主动上传,麦多课文档分享仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文档分享(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1 

    收起
    展开