免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2019年上半年 数据库系统工程师 上午试卷 综合知识
第5题      2019年上半年 数据库系统工程师 上午试卷 综合知识
所属知识点   数据结构与算法        关键词   进栈
考点辞典            

 
令序列X、Y、Z的每个元素都按顺序进栈,且每个元素进栈和出栈仅一次。则不可能得到的出栈序列是( )。
 
 
  A.  X Y Z
 
  B.  X Z Y
 
  C.  Z X Y
 
  D.  Y Z X
 
 
 

  数据结构与算法 知识点 更多相关真题:    更多>  
 
  第21题    2012年上半年  
   30%
对于二维数组a[1..N,1..N]中的一个元素a[i,j](1≤i,j≤N),存储在a[i,j]之前的元素个数(21)。
  第27题    2009年上半年  
   62%
下面关于二叉排序树的叙述,错误的是(27)。
  第10题    2019年上半年  
   38%
已知有序数组a的前10000个元素是随机整数,现需查找某个整数是否在该数组中。以下方法中,( )的查找效率最高。
 

1)栈的定义及基本运算
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出(FILO,或后进先出)的线性表。栈进行插入和删除操作的一端称为栈顶,另一端称为栈底。不含数据元素的栈称为空栈。
对栈进行的基本操作有以下几种。
.置空栈InitStack(S):创建一个空栈S。
.判栈空Empty(S):当栈S为空栈时返回真值;否则返回假值。
.入栈Push(S,x):将元素x加入栈顶,并更新栈顶指针。
.出栈Pop(S):将栈顶元素从栈中删除,并更新栈顶指针。若需要得到栈顶元素的值,可将Pop(S)定义为一个函数,它返回栈顶元素的值。
.读栈顶元素Top(S):返回栈顶元素的值,但不修改栈顶指针。
2)栈的存储结构
未完......点击标题查看......
1)概念
栈(Stack)是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶(Top),表头端称为栈底(Bottom)。故栈是后进先出(LIFO)的线性表。
若有桟S=(S0, S1, …, Sn-1),则S0称为栈底节点,Sn-1称为栈顶节点。通常称桟的节点的插入为进栈(Push),栈的节点的删除为出栈(Pop)。
2)存储结构
桟有两种存储结构:顺序栈和链栈。
.顺序栈即栈的顺序存储结构,是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设指针top指示栈顶元素的当前位置。
.链栈即栈的链式存储结构,链表的第一个元素是栈顶元素,链表的末尾是栈底节点,链表的头指针就是栈顶指针,栈顶指针为空则是空栈。
未完......点击标题查看......
       栈的定义
       栈是只能在表的一端进行插入、删除的线性表。栈中允许插入、删除的一端称为栈顶,相反,栈中不允许插入、删除的一端称为栈底。处于栈顶位置的数据元素称为栈顶元素,不含任何数据元素的栈称为空栈。栈的特点为后进先出(Last In First Out, LIFO)。
       下图是一个栈的示意图,通常用指针top指示栈顶的位置,用指针bottom指向桟底。栈顶指针top动态反映栈的当前位置。
       
       栈的出入示意图
       栈的基本操作
       栈的基本操作主要有以下6种。
       .InitStack(&S):初始化操作,构造一个空栈S。
       .StackEmpty(S):若栈S为空栈,返回1,否则返回0。
未完......点击标题查看......
       栈的顺序存储结构
       栈的顺序存储用向量作为栈的存储结构,向量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)。
未完......点击标题查看......

 题号导航      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 /
 
↓第5题