免费智能真题库 > 历年试卷 > 程序员 > 2010年下半年 程序员 上午试卷 综合知识
  第42题      
  知识点:      矩阵
  关键词:   邻接矩阵        章/节:   常用数据结构       

 
的邻接矩阵如下所示,则该为(42)。
 
 
  A. 
 
  B. 
 
  C. 
 
  D. 
 
 
 

  相关试题:图          更多>  
 
  第40题    2016年上半年  
   52%
某图G的邻接矩阵如下所示。以下关于该图的叙述中,错误的是(40)。
  第42题    2016年下半年  
   30%
设某无向图的顶点个数为n,则该图最多(42)条边;若将该图用邻接矩阵存储,则矩阵的行数和列数分别为(43)。
  第40题    2019年下半年  
   35%
以下关于下图所示有向图G的说法中,正确的是(40)。
   知识点讲解    
   ·     · 矩阵
 
       图
               图的基本概念
               图是重要的一类非线性结构,应用极为广泛,其形式化定义可写为:
               Graph=(V,R)
               其中,V={x|x∈datatype},R={VR}, VR={<x,y>|Px,y)∧(x,yV)}。
               在图中,数据元素常称为顶点,V是顶点的有穷集合;R是边(弧)的有穷集合。可见,从逻辑上看,图是由顶点和边组成,边反映出顶点之间的联系。
               图的存储结构
               图主要有以下4种存储结构:邻接矩阵、邻接表、邻接多重表及十字链表。其中最常用的存储结构为邻接矩阵和邻接表,尤其是邻接表。
               邻接矩阵是表示顶点之间相邻关系的矩阵。有n个顶点的图G=(V,E)的邻接矩阵为n阶方阵,其定义为:
               
               将邻接矩阵中的0、1换成权值,就是图的邻接矩阵。无向图的邻接矩阵是对称矩阵;顶点vi的度是邻接矩阵中第i行(或第i列)的元素1之和。有向图的邻接矩阵不一定是对称矩阵;顶点vi的出度是邻接矩阵中第i行元素之和,入度是邻接矩阵中第i列的元素之和。
               可见,通过邻接矩阵可以很容易地判定顶点间有无边(弧),容易计算顶点的度(出度、入度);缺点是所占空间只和顶点个数有关,和边数无关,在边数较少时,空间浪费较大。一般在顶点数较少且边数稠密时应用邻接矩阵。
               邻接表是为克服邻接矩阵在图为稀疏图时的空间浪费大这个缺点而提出的。
               邻接表是顶点的向量结构和边(弧)的单链表结构的集合,每个顶点节点包括两个域,将n个顶点放在一个向量中(称为顺序存储的节点表);一个顶点的所有邻接点链接成单链表,该顶点在向量中有一个指针域指向其第一个邻接点。邻接表的结构如下:
               顶点节点
               边(弧)节点
               其中,vexdata是顶点数据,firstarc是指向该顶点第一个邻接点的指针,adjvex是邻接点在向量中的下标,info是邻接点的信息,next是指向下一邻接点的指针。
               对无向图,容易求各顶点的度;边表中节点个数是边数的两倍。对有向图,容易求顶点的出度;若求顶点的入度则不容易,要遍历整个表。为了求顶点的入度,有时可设逆邻接表(指向某顶点的邻接点链接成单链表)。所谓逆邻接表就是对图中的每个顶点i建立一个单链表,把被i邻接的顶点放在一个链表中,即边表中存放的是入度边而不是出度边。一般在处理以顶点为主且为边稀疏时用邻接表。
               邻接多重表是为了解决邻接表不利于处理以边为主的情况,因为在邻接表中,每条边需要两个边节点,在以边为主处理图时,需判断此边是否处理过,增加了复杂性。图的邻接多重表中每个边只有一个节点,其节点结构如下:
               顶点节点
               边节点
               十字链表为邻接表不利于求出顶点的入度这个缺点而提出的,其节点结构如下:
               顶点节点
               弧节点
 
       矩阵
        矩阵是很多科学与工程计算问题中研究的数学对象。在数据结构中主要讨论如何在尽可能节省存储空间的情况下,使矩阵的各种运算能高效地进行。
        在一些矩阵中,存在很多值相同的元素或者是零元素。为了节省存储空间,可以对这类矩阵进行压缩存储。压缩存储的含义是为多个值相同的元素只分配一个存储单元,对零元不分配存储单元。
               特殊矩阵
               常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵等。对于特殊矩阵,由于其非零元的分布都有一定的规律,所以可将其压缩存储在一维数组中,并建立起每个非零元在矩阵中的位置与其在一维数组中的位置之间的对应关系。
               若矩阵An×n中的元素有aij=aji(1≤ijn)的特点,则称之为对称矩阵。
               若为对称矩阵中的每一对元素分配一个存储单元,那么就可将n2个元素压缩存储到能存放nn+1)/2个元素的存储空间中。不失一般性,以行为主序存储下三角(包括对角线)中的元素。假设以一维数组Bnn+1)/2]作为n阶对称矩阵A中元素的存储空间,则Bk](0≤k<nn+1)/2)与矩阵元素aijaji)之间存在着一一对应的关系。
               
               对角矩阵是指矩阵中的非零元素都集中在以主对角线为中心的带状区域中,即除了主对角线上和直接在对角线上、下方若干条对角线上的元素外,其余的矩阵元素都为零。一个n阶的三对角矩阵如下图所示。
               
               三对角矩阵示意图
               若以行为主序将n阶三对角矩阵An×n的非零元素存储在一维数组Bk](0≤k<3n-2)中,则元素位置之间的对应关系为:
               k=3×(i-1)-1+j-i+1=2i+j-3(1≤ijn
               其他特殊矩阵可作类似的推导和计算,这里不再一一说明。
               稀疏矩阵
               在一个矩阵中,若非零元素的个数远远少于零元素的个数,且非零元素的分布没有规律,则称之为稀疏矩阵。
               对于稀疏矩阵,存储非零元素时必须同时存储其位置(即行号和列号),所以三元组(ijaij)可唯一确定矩阵中的一个元素。由此,一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
               一个6行7列的稀疏矩阵如下图所示,其三元组表为(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))。
               
               稀疏矩阵示意图
               稀疏矩阵的三元组表构成一个线性表,其顺序存储结构称为三元组顺序表,其链式存储结构称为十字链表。
   题号导航      2010年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第42题    在手机中做本题