免费智能真题库 > 历年试卷 > 程序员 > 2019年下半年 程序员 上午试卷 综合知识
  第36题      
  知识点:      函数调用   数据结构
  章/节:   常用数据结构       

 
数据结构中的(36)常用来对函数调用和返回处理的控制进行支持。
 
 
  A.  栈
 
  B.  队列
 
  C.  有序树
 
  D.  有向图
 
 
 

 
  第37题    2014年下半年  
   47%
对于一个初始为空的栈,其入栈序列为abc时,其出栈序列可以有(37)种。
  第38题    2012年上半年  
   69%
设循环队列Q的定义中有rear和size两个域变量,其中,rear指示队尾元素之后的位置,size表示队列的长度,如图所示(队列长度为3,队..
  第37题    2017年上半年  
   33%
为支持函数调用及返回,常采用称为“( )”的数据结构。
   知识点讲解    
   ·     · 函数调用    · 数据结构
 
       栈
               栈的定义
               栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶,相反,栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素,不含任何数据元素的栈称为空栈。栈的特点为后进先出(Last In First Out, LIFO)。
               下图是一个栈的示意图,通常用指针top指示栈顶的位置,用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。
               
               栈的出入示意图
               栈的基本操作
               栈的基本操作主要有以下6种。
               .InitStack(&S):初始化操作,构造一个空栈S。
               .StackEmpty(S):若栈S为空栈,返回1,否则返回0。
               .Push(&S, e):插入元素e为新的栈顶元素。
               .Pop(&S,&e):删除S的栈顶元素,并用e返回其值。
               .GetTop(S,&e):用e返回S的栈顶元素。
               .ClearStack(&S):将S清为空栈。
               栈的顺序存储结构
               栈的顺序存储用向量作为栈的存储结构,向量S表示栈,m表示栈的大小,用指针top指向栈顶位置,S[top]表示栈顶元素,当在栈中进行插入、删除操作时,都要移动栈指针;而当top=m-1时,则栈满,当top=-1时,表示栈空。同时为了避免浪费空间可以采用双栈机制,即向量的两端为栈底。
               栈的顺序存储结构的C语言描述如下:
               
               栈的说明如下。
               .由于C语言的数组下标的范围从0至StackSize-1,初始化设置sq.top=-1。
               .栈空条件为sq.top=-1,栈满条件为sq.top=StackSize-1。
               .栈顶元素为sq.data[sq.top]。
               .元素压栈的规则为:在栈不满时,先改变栈顶指针(top=top+1),再压栈。出栈时,在桟非空时,先取栈顶元素的值,再修改栈顶指针(top=top-1)。
               .栈中元素的个数为当前栈顶指针加1。
               在顺序栈上实现基本操作的有关函数如下。
               1)初始化InitStack(SqStack *S)
               
               2)判空StackEmpty(SqStack S)
               
               3)压栈Push(SqStack *S, ElemType e)
               
               4)出栈Pop(SqStack *S, ElemType *e)
               
               5)取栈顶GetTop(SqStack *S, ElemType*e)
               
               6)清栈ClearStack(SqStack *S)
               
               栈的链式存储结构
               栈的链式存储也叫链栈,我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分有头节点和无头节点两种。带头节点的链栈操作比较方便。
               链栈的节点类型定义如下:
               
               链栈的约定与说明如下。
               .栈以链表的形式出现,链表(不带头节点)首指针为S,即栈顶为S,链表尾节点为栈底。
               .初始化时,S=NULL(不带头节点);S=(LStack *),malloc(sizeof(LStack)),S→next=NULL(带头节点)。
               .栈顶指针的引用为S(不带头节点)或S→next(带头节点),栈顶元素的引用为S→data(不带头节点)或S→next→data(带头节点)。
               .栈空条件为S==NULL(不带头节点)或S→next=NULL(带头节点)。
               .进栈操作和出栈操作与单链表在开始节点的插入和删除操作一致。
               对不带头节点的链栈,其基本操作函数如下。
               1)初始化initstack(LStack *S)
               
               2)压栈(入栈)push(LStack *S, ElemType x)
               
               3)退栈(出栈)pop(LStack *S, ElemType *x)
               
               4)读栈顶元素gettop(LStack *S, ElemType *x)
               
               5)判栈空isempty(LStack *S)
               
               栈的应用
               栈具有广泛的应用,例如,求表达式的值及递归到非递归等。
               1)表达式求值
               在源程序编译中,若要把一个含有表达式的赋值语句翻译成正确求值的机器语言,首先应正确地解释表达式。例如,对赋值语句X=4+8×2-3;,其正确的计算结果应该是17,但若在编译程序中简单地按自左向右扫描的原则进行计算,则为:X=12×2-3=24-3=21。这个结果显然是错误的。因此,为了使编译程序能够正确地求值,必须事先规定求值的顺序和规则。通常采用运算符优先法。
               2)递归到非递归
               将一个递归算法转换为功能等价的非递归算法有很多方法,可以使用栈保存中间结果。其一般形式如下:
               
               例如,求n!的递归函数如下:
               
               使用转换成等价的非递归算法如下:
               
               其中,st[top][0]用于存放n值,st[top][1]用于存放n!值,在初始时,设置st[top][1]为0,表不n!尚未求出。
 
       函数调用
        当在一个函数(称为调用函数)中需要使用另一个函数(称为被调用函数)实现的功能时,便以名字进行调用,称为函数调用。在使用一个函数时,只要知道如何调用即可,并不需要关心被调用函数的内部实现。因此,程序员需要知道被调函数的名字、返回值和需要向被调函数传递的参数(个数、类型、顺序)等信息。
        函数调用的一般形式为:
        
        在C程序的执行过程中,通过函数调用使得被调用函数得以执行。函数体中若调用自己,则称为递归调用。
        C语言采用传值方式将实参传递给形参。调用函数和被调用函数之间交换信息的方法主要有两种:一种是由被调用函数把返回值返回给调用函数,另一种是通过参数带回信息。函数调用时,实参与形参间交换信息的主要有传值调用和引用调用两种方法。
        (1)传值调用(Call by value)。若实现函数调用时实参向形参传递相应类型的值,则称为是传值调用。这种方式下形参不能向实参传递信息。
        例如,下面给出函数swap定义,其功能是交换两个整型变量值。
        
        函数调用为:swap(a,b);
        因为是传值调用,swap函数运行后只能交换x和y的值,而实参a和b的值并没有交换。
        在C语言中,要实现被调用函数对实参的修改,必须用指针作形参,调用时需要先对实参进行取地址运算,然后将实参的地址传递给指针形参。本质上仍属于传值调用。
        下面给出函数swap的定义,其功能是交换两个整型变量值。
        
        函数调用为:swap(&a,&b);
        由于形参px、py分别得到了实参变量a、b的地址,所以px指向的对象*px即为a,py指向的对象*py就是b,因此在函数中交换*px和*py的值实际上就是交换实参a和b的值,从而实现了调用函数中两个整型变量值的交换。这种方式是通过数据的间接访问来完成运算要求的。
        (2)引用调用。引用是C++中增加的数据类型,当形参为引用类型时,函数中对形参的访问和修改实际上就是针对相应实参所作的访问和改变。例如:
        
        函数调用为:swap(a,b);
        引用调用方式下调用swap(a,b)时,x、y就是a、b的别名,因此,函数调用完成后,交换了实参a和b的值。
 
       数据结构
        根据数据元素之间关系的不同特性,通常有下列4类基本的逻辑结构,即集合结构、线性结构、树形结构、图形结构。
        1)线性结构
        线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外,每个元素均只有一个直接前驱;除最后一个元素外,每个元素都只有一个直接后继。
        栈是限定仅在表尾进行插入或删除操作的线性表,是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。
        队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入,而在另一端删除元素。
        2)树
        树是nn≥0)个互不相交的有限集,当n=0时称为空树。在一棵非空树中,有且仅有一个节点称为根节点;当n>1时,其余的节点可分为若干个不相交的集合,其中每一个集合本身又是一棵树,这些集合称为根节点的子树。
        3)图
        图是由两个集合VE组成的二元组,记为G=(V, E),其中V是顶点的非空有限集合,E是图中边的有限集合。
   题号导航      2019年下半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第36题    在手机中做本题