软考在线  |  计算机技术与软件专业技术资格(水平)考试   |   [请选择科目]
[ 成为 VIP会员 ]        登录  |  注册      我的  购物车
0
 
科目切换  联系我们 
    
  |   [请选择科目]

VIP:有效提升20分!  真题  历年真题 (可免费开通)/  分章知识真题/ 机考模拟平台/  最难真题榜/  自测/  攻打黄金十二宫/  真题检索/  真题下载/  真题词库
知识   必会知识榜/  最难知识榜/  知识点查询/      文档   学习计划/  精华笔记/  试题文档     纸质图书   《百科全书》HOT!!/         /        首页/  专区/  手机版/ 
免费智能真题库 > 历年试卷 > 程序员 > 2014年下半年 程序员 上午试卷 综合知识
  第43题      
  知识点:   图的存储结构
  章/节:   常用数据结构       
  错误率: 44%      难度系数:      
  感谢学员18852868..对完善本题做出的杰出贡献,并已派发奖金。
  感谢学员sxsfeq@q..对完善本题做出的杰出贡献,并已派发奖金。

 
对于下图,从顶点1进行深度优先遍历时,不可能得到的遍历序列是(42);若将该图用邻接矩阵存储,则矩阵中的非0元素数目为(43)。
 
 
  A.  7
 
  B.  8
 
  C.  14
 
  D.  16
 
 
 确定 并 查看答案解析     知识点讲解  我要标记      有奖找茬      上一题        下一题 
 

  相关试题:图          更多>  
 
  第40题    2019年下半年  
   34%
以下关于下图所示有向图G的说法中,正确的是(40)。
  第42题    2021年上半年  
   17%
某有向图G如下图所示,其邻接矩阵的规模是( )。
  第41题    2009年下半年  
   42%
以下关于图及其存储结构的叙述中,正确的是(41)。
   知识点讲解    
   · 图的存储结构
 
       图的存储结构
        图主要有以下4种存储结构:邻接矩阵、邻接表、邻接多重表及十字链表。其中最常用的存储结构为邻接矩阵和邻接表,尤其是邻接表。
        邻接矩阵是表示顶点之间相邻关系的矩阵。有n个顶点的图G=(V,E)的邻接矩阵为n阶方阵,其定义为:
        
        将邻接矩阵中的0、1换成权值,就是图的邻接矩阵。无向图的邻接矩阵是对称矩阵;顶点vi的度是邻接矩阵中第i行(或第i列)的元素1之和。有向图的邻接矩阵不一定是对称矩阵;顶点vi的出度是邻接矩阵中第i行元素之和,入度是邻接矩阵中第i列的元素之和。
        可见,通过邻接矩阵可以很容易地判定顶点间有无边(弧),容易计算顶点的度(出度、入度);缺点是所占空间只和顶点个数有关,和边数无关,在边数较少时,空间浪费较大。一般在顶点数较少且边数稠密时应用邻接矩阵。
        邻接表是为克服邻接矩阵在图为稀疏图时的空间浪费大这个缺点而提出的。
        邻接表是顶点的向量结构和边(弧)的单链表结构的集合,每个顶点节点包括两个域,将n个顶点放在一个向量中(称为顺序存储的节点表);一个顶点的所有邻接点链接成单链表,该顶点在向量中有一个指针域指向其第一个邻接点。邻接表的结构如下:
        顶点节点
        边(弧)节点
        其中,vexdata是顶点数据,firstarc是指向该顶点第一个邻接点的指针,adjvex是邻接点在向量中的下标,info是邻接点的信息,next是指向下一邻接点的指针。
        对无向图,容易求各顶点的度;边表中节点个数是边数的两倍。对有向图,容易求顶点的出度;若求顶点的入度则不容易,要遍历整个表。为了求顶点的入度,有时可设逆邻接表(指向某顶点的邻接点链接成单链表)。所谓逆邻接表就是对图中的每个顶点i建立一个单链表,把被i邻接的顶点放在一个链表中,即边表中存放的是入度边而不是出度边。一般在处理以顶点为主且为边稀疏时用邻接表。
        邻接多重表是为了解决邻接表不利于处理以边为主的情况,因为在邻接表中,每条边需要两个边节点,在以边为主处理图时,需判断此边是否处理过,增加了复杂性。图的邻接多重表中每个边只有一个节点,其节点结构如下:
        顶点节点
        边节点
        十字链表为邻接表不利于求出顶点的入度这个缺点而提出的,其节点结构如下:
        顶点节点
        弧节点
   题号导航      2014年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第43题    在手机中做本题
    在线人数   共计 10789人 在线 
    553987795@..     wangchunro..     hesht2006@..     lishunbook..     yzyingze@1..     jianjiangw..
    lkfd@yahoo..     qunlan163@..     czc318@163..     piaolingde..     099804055@..     906661038@..
    erinlcy@ya..     270718988@..     569777753@..     1330553868..     wolfpeople..     faxx99@sin..
    1350611007..     hw891123@1..     cw_jun2@si..     jt8258@163..     814114741@..     jsyzluanju..
    samuel.xu@..     pamela.081..     htawlh@126..     zhangwodee..     zgxlym123@..     yuansl03@s..
    hncatc@163..     qimingxin6..     438675357@..     wsyqgy2005..     26830176@q..     jinlei1986..
    dingwei619..     zhangxin29..     sxl5409@so..     zhangya031..     huajuok@16..     nuijiashen..

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。



京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2025 All Rights Reserved 软考在线版权所有