免费智能真题库 > 历年试卷 > 软件设计师 > 2018年下半年 软件设计师 上午试卷 综合知识
  第57题      
  知识点:   存储结构      指针   栈的存储结构
  关键词:   后进先出   链表   指针        章/节:   计算机软件知识       

 
的特点是后进先出,若用单链表作为存储结构,并用头指针作为指针,则( )。
 
 
  A.  入栈和出栈操作都不需要遍历链表
 
  B.  入栈和出栈操作都需要遍历链表
 
  C.  入栈操作需要遍历链表而出栈操作不需要
 
  D.  入栈操作不需要遍历链表而出栈操作需要
 
 
 

 
  第34题    2021年上半年  
   26%
设有栈S和队列Q初始状态为空,数据元素序列a,b,c,d,e,f依次通过栈S,且多个元素从S出栈后立即进入队列Q,若出队的序列是b,d,f,e,..
  第60题    2009年上半年  
   44%
下面关于栈和队列的叙述,错误的是(60)。
  第22题    2020年下半年  
   24%
在程序的执行过程中,系统用( )实现嵌套调用(递归调用)函数的正确返回。
  相关试题:图          更多>  
 
  第17题    2017年上半年  
   32%
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完..
  第60题    2011年上半年  
   37%
设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边),则该矩阵..
  第59题    2013年下半年  
   29%
在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。
   知识点讲解    
   · 存储结构    ·     · 指针    · 栈的存储结构
 
       存储结构
               邻接矩阵表示法
               对于具有n个顶点的图G(V,E)来说,其邻接矩阵是一个n阶方阵,且满足
               
               由邻接矩阵的定义可知,无向图的邻接矩阵是对称的,有向图的邻接矩阵就不一定对称了。借助邻接矩阵易判定任意两个顶点之间是否有边(或弧)相连,并且容易求得各个顶点的度。
               网(赋权图)的邻接矩阵可定义为
               
               邻接链表表示法
               邻接链表指的是为图的每个顶点建立一个单链表,第i个单链表中的节点表示依附于顶点vi的边(对于有向图是以vi为尾的弧)。邻接链表中的节点有表节点和表头节点两种类型。
               邻接矩阵和邻接链表表示法对有向图和无向图都适用。
 
       栈
        1)栈的定义及基本运算
        栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出(FILO,或后进先出)的线性表。栈进行插入和删除操作的一端称为栈顶,另一端称为栈底。不含数据元素的栈称为空栈。
        对栈进行的基本操作有以下几种。
        .置空栈InitStack(S):创建一个空栈S。
        .判栈空Empty(S):当栈S为空栈时返回真值;否则返回假值。
        .入栈Push(S,x):将元素x加入栈顶,并更新栈顶指针。
        .出栈Pop(S):将栈顶元素从栈中删除,并更新栈顶指针。若需要得到栈顶元素的值,可将Pop(S)定义为一个函数,它返回栈顶元素的值。
        .读栈顶元素Top(S):返回栈顶元素的值,但不修改栈顶指针。
        2)栈的存储结构
        (1)顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时附设指针top指示栈顶元素的位置。在顺序存储方式下,需要预先定义或申请栈的存储空间,也就是说,栈空间的容量是有限的。因此在顺序栈中,当一个元素入栈时,需要判断是否栈满,若栈满,则元素入栈会发生上溢现象。
        利用栈底位置不变的特性,可以让两个顺序栈共享一个一维数据空间,以互补余缺,实现方法是:将两个栈的栈底位置分别设在存储空间的两端,让它们的栈顶各自向中间延伸。这样,两个栈的空间就可以相互调节,只有在整个存储空间被占满时才发生上溢,这样一来产生上溢的概率要小得多。
        (2)链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行,因此不必设置头节点,链表的头指针就是栈顶指针。
        3)栈的应用
        栈的典型应用包括表达式求值、括号匹配等,在计算机语言的实现中以及将递归过程转变为非递归过程的处理中,栈有重要的作用。
 
       指针
        指针是C语言中最为重要也是最难的一个关键点,很多数据结构都是基于指针实现的,如链表、链式队列、链栈、二叉树等。
        所谓指针,就是一个用来存储地址的变量。这可谓指针的本质,需要牢记。
        也许你会很纳闷,指针为什么一定要定义成某类型(int、char)呢?指针不能就是"指针类型"吗?接触过汇编的人就很容易理解为什么。存储单元的单位是字节,就是说一般地址是按字节编址的,对一个地址进行操作(读取或赋值)就要指明是对单字节(不用特别声明)、两字节(WORD PTR),还是双字节(四字节,DWORD PTR)进行操作。同样,指针是存储地址的,即指针就是一个地址,自然也要说明其类型;而且,这个类型还关乎指针自加自减时真正加减的字节数。
        顺便说一下,数组名也是指针。数组在申请空间时,数组名存储该存储空间的首地址。注意:数组名存储的是地址,因此也是指针,只是该指针一旦赋值后就不能修改,即所谓常指针。当直接输出数组名时,输出的其实是数组的首地址。这样,当形参声明为指针时,亦可将数组名作为实参进行传递。因此,可以用指针的方式访问数组中的元素,如下例采用指针的方式遍历输出数组。
        
        当指针作为函数参数传递时,需要特别注意C语言中的"值"传递原则。下例中的函数希望为指针p申请空间,但不能达到目的,为什么呢?
        
        归根结底,C函数的形参与实参之间只是"值传递":当形参是普通变量时,传递的是实参的值;当形参是指针时,传递的是指针变量的值,即某变量的地址,这样可以通过指针成功地改变其所指单元的值,但自身的改变不会传回给实参。上例可改为:
        
        注意:这样修改后,调用时实参应该是指针的"地址"(或指向指针的指针)。这样即上面所说的可以改变指针所指单元的值,因此可达到预期目的。
 
       栈的存储结构
        (1)栈的顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下,需要预先定义或申请栈的存储空间,也就是说栈空间的容量是有限的。因此在顺序栈中,当一个元素入栈时,需要判断是否栈满(栈空间中没有空闲单元),若栈满,则元素入栈会发生上溢现象。
        (2)栈的链式存储。为了克服顺序存储的栈可能存在上溢的不足,可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行,因此不必设置头结点,链表的头指针就是栈顶指针。
   题号导航      2018年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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题    在手机中做本题