免费智能真题库 > 历年试卷 > 软件设计师 > 2013年下半年 软件设计师 上午试卷 综合知识
  第57题      
  知识点:   存储结构   线性表
  关键词:   线性表        章/节:   计算机软件知识       

 
以下关于线性表存储结构的叙述,正确的是(57)。
 
 
  A.  线性表采用顺序存储结构时,访问表中任意一个指定序号元素的时间复杂度为常量级
 
  B.  线性表采用顺序存储结构时,在表中任意位置插入新元素的运算时间复杂度为常量级
 
  C.  线性表采用链式存储结构时,访问表中任意一个指定序号元素的时间复杂度为常量级
 
  D.  线性表采用链式存储结构时,在表中任意位置插入新元素的运算时间复杂度为常量级
 
 
 

  相关试题:链表          更多>  
 
  第58题    2016年下半年  
   23%
设有一个包含n个元素的有序线性表。在等概率情况下删除其中的一个元素,若采用顺序存储结构,则平均需要移动(58)个元素;若采用..
  第60题    2009年下半年  
   44%
单向链表中往往含有一个头结点,该结点不存储数据元素,一般令链表的头指针指向该结点,而该结点指针域的值为第一个元素结点的指..
  第51题    2013年上半年  
   28%
采用顺序表和单链表存储长度为n的线性序列,根据序号查找元素,其时间复杂度分别为 (51)。
  相关试题:图          更多>  
 
  第60题    2017年下半年  
   45%
以下关于无向连通图G的叙述中,不正确的是( )。
  第18题    2013年下半年  
   32%
下图是一个软件项目的活动图,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,则里程碑(17)在关键路径上。若在实际项目进..
  第61题    2018年下半年  
   43%
图G的邻接矩阵如下图所示(顶点依次表示为v0、v1、v2、v3、v4、v5),G是(60)。对G进行广度优先遍历(从v0开始),可能的遍历序..
   知识点讲解    
   · 存储结构    · 线性表
 
       存储结构
               邻接矩阵表示法
               对于具有n个顶点的图G(V,E)来说,其邻接矩阵是一个n阶方阵,且满足
               
               由邻接矩阵的定义可知,无向图的邻接矩阵是对称的,有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边(或弧)相连,并且容易求得各个顶点的度。
               网(赋权图)的邻接矩阵可定义为
               
               邻接链表表示法
               邻接链表指的是为图的每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点vi的边(对于有向图是以vi为尾的弧)。邻接链表中的节点有表节点和表头节点两种类型。
               邻接矩阵和邻接链表表示法对有向图和无向图都适用。
 
       线性表
               线性表的定义
               线性表是n个元素的有限序列,通常记为(a1,a2,…,an)。其特点如下。
               .存在唯一的一个称为"第一个"的元素。
               .存在唯一的一个称为"最后一个"的元素。
               .除了表头外,表中的每一个元素均只有唯一的直接前驱。
               .除了表尾外,表中的每一个元素均只有唯一的直接后继。
               线性表的存储结构
               1)顺序存储
               线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下,存储逻辑关系无须占用额外的存储空间。其优点是可以随机存取表中的元素,缺点是插入和删除操作需要移动大量的元素。
               一般地,在线性表的顺序存储结构中,第i个元素ai的存储位置为
               LOC(ai)=LOC(a1)+(i-1)×L
               式中,LOC(a1)为表中第一个元素的存储位置;L为表中每个元素所占空间的大小。
               2)链式存储
               线性表的链式存储是指用节点来存储数据元素,节点的空间可以是连续的,也可以是不连续的,因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请,无须事先分配。最基本的节点结构如下图所示。
               
               最基本的节点结构
               其中,数据域用于存储数据元素的值,指针域则存储当前元素的直接前驱或直接后继信息,指针域中的信息称为指针(链)。n个节点通过指针连成一个链表,若节点中只有一个指针域,则称为线性链表(单链表)。
               线性表采用链表作为存储结构时,不能进行数据元素的随机访问,但其优点是插入和删除操作不需要移动元素。以下是几种其他链表结构。
               (1)双向链表。每个节点包含两个指针,指明直接前驱和直接后继元素,可在两个方向上遍历链表。
               (2)循环链表。表尾节点的指针指向表中的第一个节点,可在任何位置上开始遍历整个链表。
               (3)静态链表。借助数组来描述线性表的链式存储结构。
               在链式存储结构中,只需要一个指针(头指针)指向第一个节点,就可以顺序访问到表中的任意一个元素。为了简化对链表状态的判定和处理,特别引入一个不存储数据元素的节点,称为头节点,将其作为链表的第一个节点并令头指针指向该节点。
               线性表的插入和删除运算
               1)基于顺序存储结构的运算
               插入元素前要移动元素以挪出空的存储单元,然后再插入元素;删除元素时同样需要移动元素,以填充被删除的存储单元。在等概率下平均移动元素的次数分别是
               
               2)基于链式存储结构的运算
               在链式存储结构下进行插入和删除,其实质都是对相关指针的修改。
               (1)在单向链表中插入节点时,指针的变化情况如下图所示。
               
               单向链表插入节点时的指针变化情况
               (2)在单向链表中删除节点时,指针的变化情况如下图所示。
               
               单向链表删除节点时的指针变化情况
               (3)在双向链表中插入节点时,指针的变化情况如下图所示。
               
               双向链表插入节点时的指针变化情况
               (4)在双向链表中删除节点时,指针的变化情况如下图所示。
               
               双向链表删除节点时的指针变化情况
               注意:以上3图中①为插入运算前的指针走向;②为插入运算后的指针走向;虚线为插入后的指针指向。
   题号导航      2013年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第57题    在手机中做本题