免费智能真题库 > 历年试卷 > 程序员 > 2017年上半年 程序员 上午试卷 综合知识
第36题      
知识点   
分类   线性表       

 
对于一个相始为空的,其入序列为1、2、3、…、n (n>3) ,若出序列的第一个元素是1,则出序列的第n个元素( )
 
 
  A.  可能是2~n中的任何一个
 
  B.  一定是2
 
  C.  一定是n-1
 
  D.  一定是n
 
 
 

  相关试题     线性表    更多>  
 
  第34题    2015年上半年  
   34%
在解决计算机与打印机之间速度不匹配的问题时,通常设置一个打印数据缓冲区, 计算机将要输出的数据依次写入该缓冲区,而打印机则..
  第42题    2011年上半年  
   32%
输入受限的双端队列是指只有一端可以进行入队操作而从两端都可以进行出队操作的队列,如下图所示。对于输入序列1234,经过一个初始..
  第32题    2009年下半年  
   49%
设数组a[0..m,1..n]的每个元素占用1个存储单元,若元素按行存储,则数组元素a[i,j](0≤i≤m, 1≤j≤n)相对于数组空间首地..
 


   知识点讲解    
   · 
 
       栈
               栈的定义
               栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶,相反,栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素,不含任何数据元素的栈称为空栈。栈的特点为后进先出(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!尚未求出。


 题号导航      2017年上半年 程序员 上午试卷 综合知识   本试卷我的完整做题情况 
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题