免费智能真题库 > 历年试卷 > 程序员 > 2016年上半年 程序员 上午试卷 综合知识
  第34题      
  知识点:   线性表   存储结构   数组
  关键词:   数组   顺序存储   线性表        章/节:   常用数据结构       

 
对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构数组存储),则在等概率下,删除一个元素平均需要移动的元素数为(34)。
 
 
  A.  n
 
  B. 
 
  C. 
 
  D.  log n
 
 
 

 
  第37题    2019年下半年  
   34%
单向循环链表如下图所示,以下关于单向循环链表的叙述中,正确的是(37) 。

  第37题    2019年上半年  
   51%
以下关于单链表存储结构特征的叙述中,不正确的是( )。
  第37题    2019年下半年  
   34%
单向循环链表如下图所示,以下关于单向循环链表的叙述中,正确的是(37) 。

   知识点讲解    
   · 线性表    · 存储结构    · 数组
 
       线性表
               线性表的顺序存储结构
               1)顺序表的概念
               线性表的顺序存储结构采用一组连续的存储单元依次存储线性表中的各数据元素。建立一个数组V,线性表的长度为NV[i]表示第i个分量,第i个分量是线性表中第i个元素ai在计算机存储器中的映象,即V[i]=ai。若线性表的第一个元素的存储地址是LOC(a1),每个元素用L个存储单元,则表的第i个元素的存储地址为:LOC(ai)=LOC(a1)+(i-1)*L
               假设线性表的数据元素的类型为ElemType(在实际应用中,此类型应根据实际问题中出现的数据元素的特性具体定义,如为int、float类型等),线性表的顺序表的C语言描述如下:
               
               从中可以看出,顺序表是由数组data和len两部分组成的。为了反映data和len之间的关系,上述类型定义中将它们说明为结构体类型Sqlist的两个域。这样,Sqlist类型就完全描述了顺序表的组织。
               2)基本运算在顺序表上的实现
               由于C语言中数组的下标是从0开始的,所以,在逻辑上所指的"第k个位置"实际上对应的是顺序表的"第k-1个位置"。这里仅给出在顺序表上线性表的插入和删除函数。
               (1)插入函数。
               插入函数的语法如下:
               
               (2)删除函数。
               删除函数的语法如下:
               
               3)插入和删除元素算法的时间复杂度分析
               (1)插入算法的时间复杂度。
               插入算法的时间复杂度的分析如下:
               
               其中pi是在第i个元素前插入元素的概率,ci是在第i个元素前插入元素时元素移动次数。
               (2)删除算法的时间复杂度。
               删除算法的时间复杂度的分析如下:
               
               其中pi是在第i个元素前删除元素的概率,ci是在第i个元素前删除元素时元素移动次数。
               可见,插入和删除算法的时间复杂度均为On)。
               线性表的单链表存储结构
               单链表中的每个节点由两部分组成:数据域和指针域。节点形式如下:
               
               其中,data部分称为数据域,用于存储线性表的一个数据元素(节点)。next部分称为指针域或链域,用于存放一个指针,该指针指向本节点所含数据域元素的直接后继所在的节点。若数据元素的类型用ElemType表示,则单链表的类型定义如下:
               
               单链表分为带头节点(其next域指向第一个节点)和不带头节点两种类型,由于头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致,因而可简化运算的实现过程。
               在单链表上实现线性表基本运算的函数如下。
               1)初始化函数initlist(Slink *head)
               初始化函数用于创建一个头节点,由head指向它,该节点的next域为空,data域未设定任何值。由于调用该函数时,指针head在本函数中指向的内容发生改变,为了返回改变的值,因此使用了应用型参数,其时间复杂度为O(1)。初始化函数的语法如下:
               
               2)插入函数insert(Slink *head, int i, ElemType x)
               插入函数的设计思想是:创建一个data域值为x的新节点*p,然后插入到head所指向的单链表的第i个节点之前。为保证插入正确有效,必须查找到指向第i个节点的前一个节点的指针,主要的时间耗费在查找上,因而在长度为n的线性单链表进行插入操作的时间复杂度为On)。插入函数的语法如下:
               
               3)删除函数delete(Slink *head, int i, ElemType x)
               删除函数的设计思想是:线性链表中元素的删除要修改被删除元素前驱的指针,回收被删除元素所占的空间。主要的时间耗费在查找上,因而在长度为n线性单链表进行删除操作的时间复杂度为On)。删除函数的语法如下:
               
               4)查找函数get(Slink *head, int i)
               查找函数的设计思想是:线性链表中查找元素要找元素前驱的指针。在长度为n的线性单链表进行查找操作的时间复杂度为On)。查找函数的语法如下:
               
               5)求单链表长函数Length(Slink *head)
               求单链表长函数的设计思想是:通过遍历的方法,从头数到尾,即可得到单链表长。求单链表长函数的语法如下:
               
               带头节点的单链表和不带头节点的单链表的区别
               带头节点的单链表和不带头节点的单链表的区别主要体现在其结构上和算法操作上。
               在结构上,带头节点的单链表不管链表是否为空,均含有一个头节点;而不带头节点的单链表不含头节点。
               在操作上,带头节点的单链表的初始化为申请一个头节点,且在任何节点位置进行的操作算法一致;而不带头节点的单链表让头指针为空,同时其他操作要特别注意空表和第一个节点的处理。下面列举带头节点的单链表插入操作和不带头节点的插入操作的区别。
               定义单链表的节点类型如下:
               
               1)带头节点的单链表插入函数insert(Slink *head, int i, ElemType x)
               带头节点的单链表插入函数的设计思想是:创建一个data域值为x的新节点*p,然后插入到head所指向的单链表的第i个节点之前。为保证插入正确有效,必须查找到指向第i个节点的前一个节点的指针,主要的时间耗费在查找上,因而在长度为n的线性单链表中进行插入操作的时间复杂度为On)。
               2)不带头节点的单链表插入函数insert(inti, ElemTypex
               不带头节点的单链表插入函数的设计思想是:创建一个data域值为x的新节点*p,然后插入到单链表的第i个节点之前。由于不带头节点,当插入位值i=1时,其算法与i>1时有很大差别,必须单独处理。为保证插入正确有效,必须查找到指向第i个节点的前一个节点的指针,主要的时间耗费在查找上,因而在长度为n的线性单链表中进行插入操作的时间复杂度为On)。
               可见,带头节点的单链表插入操作和不带头节点的插入操作在算法实现上有很大的区别,主要体现在初始化、能否插入成功的判别及插入时的操作上,在带头节点的单链表上插入在任何位置上都是相同的,而在不带头节点单链表的第一个节点和其他节点前插入操作是不同的。
               对于带头节点的单链表和不带头节点的单链表在其他操作上的区别可类似得到。
               链表的指针修改的次序对结果的影响
               链表的指针修改必须保持其逻辑结构的次序,否则将违背线性表的特征,尤其是进行插入和删除操作。下面通过双向链表的插入操作来说明,若在如下1图所示的P所指向的节点之前插入一个S所指向的节点,则需进行指针的修改,修改指针的策略有如下2图和下3图所示两种,指针的修改次序为1, 2, 3, 4。根据线性表的性质可知,下图可保证指针修改成功;而下图中指针修改不成功,主要原因是其首先将P的前驱指向S,这样P节点的原前驱节点就不能找到了,因而指针修改步骤3和步骤4不成立。
               
               双向链表的节点插入前
               
               指针的修改策略1
               
               指针的修改策略2
               可见,指针的修改次序是链表插入成功与否的关键因素之一;同理,在进行节点的删除时也同样需要主要指针的次序。
               顺序存储结构上的算法如何移植到链式存储结构上
               很多优秀的算法都是建立在顺序存储结构上的,如何在链式存储结构上实现这些优秀算法,是考生应注意的问题。近年来,在不少程序员水平考试试题中都出现了这样的题目。这里,我们通过在顺序存储结构和链式存储结构两种存储结构上实现选择排序来说明。顺序存储结构下的算法sort的语法如下:
               
               依据顺序存储结构下的算法sort1可以拓展到链式存储结构下的算法sort2。下面将算法sort1拓展到链式存储结构下的算法sort2,语法如下:
               
               可见,只要充分领会顺序存储结构下的算法思想,熟悉链表存储结构就可通过掌握顺序存储结构下的算法得到链表存储结构下的相应算法。
 
       存储结构
               邻接矩阵表示法
               对于具有n个顶点的图G(V,E)来说,其邻接矩阵是一个n阶方阵,且满足
               
               由邻接矩阵的定义可知,无向图的邻接矩阵是对称的,有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边(或弧)相连,并且容易求得各个顶点的度。
               网(赋权图)的邻接矩阵可定义为
               
               邻接链表表示法
               邻接链表指的是为图的每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点vi的边(对于有向图是以vi为尾的弧)。邻接链表中的节点有表节点和表头节点两种类型。
               邻接矩阵和邻接链表表示法对有向图和无向图都适用。
 
       数组
               数组的定义及基本运算
               一维数组是长度固定的线性表,数组中的每个数据元素类型相同。n维数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
               设有n维数组Ab1b2,…,bn],其每一维的下界都为1,bi是第i维的上界。从数据结构的逻辑关系角度来看,A中的每个元素Aj1j2,…,jn](1≤jibi)都被n个关系所约束。在每个关系中,除第一个和最后一个元素外,其余元素都只有一个直接后继和一个直接前驱。因此就单个关系而言,这n个关系仍是线性的。
               以下面的二维数组Am][n]为例,可以把它看成是一个定长的线性表,它的每个元素也是一个定长线性表。
               
               可将A看作一个行向量形式的线性表:
               Am*n=[[a11a12a1n][a21a22a2n]…[am1am2amn]]
               也可将A看作列向量形式的线性表:
               Am*n=[[a11a21am1][a12a22am2]…[a1na2namn]]
               数组结构的特点如下:
               (1)数据元素数目固定。一旦定义了一个数组结构,就不再有元素的增减变化。
               (2)数据元素具有相同的类型。
               (3)数据元素的下标关系具有上下界的约束且下标有序。
               在数组中通常做下面两种操作:
               (1)取值操作。给定一组下标,读其对应的数据元素。
               (2)赋值操作。给定一组下标,存储或修改与其相对应的数据元素。
               几乎所有的程序设计语言都提供了数组类型。实际上,在语言中把数组看成是具有共同名字的同一类型多个变量的集合。需要注意的是,不能对数组进行整体的运算,只能对单个数组元素进行运算。
               数组的顺序存储
               由于数组一般不作插入和删除运算,也就是说,一旦定义了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
               对于数组,一旦确定了它的维数和各维的长度,便可为它分配存储空间。反之,只要给出一组下标便可求得相应数组元素的存储位置,也就是说,在数据的顺序存储结构中,数据元素的位置是其下标的线性函数。
               二维数组的存储结构可分为以行为主序(按行存储)和以列为主序(按列存储)两种方法,如下图所示。
               
               二维数组的两种存储方式
               设每个数据元素占用L个单元,mn为数组的行数和列数,那么以行为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((i-1)×n+(j-1))×L
               同理,以列为主序优先存储的地址计算公式为:
               Loc(aij)=Loc(a11)+((j-l)×m+(i-1))×L
   题号导航      2016年上半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第34题    在手机中做本题