免费智能真题库 > 历年试卷 > 软件设计师 > 2012年上半年 软件设计师 上午试卷 综合知识
  第57题      
  知识点:   队列   
  关键词:   队列   容量        章/节:   计算机软件知识       

 
对于一个长度大于1且不存在重复元素的序列,令其所有元素依次通过一个初始为空的队列后,再通过一个初始为空的。设队列的容量都足够大,一个序列通过队列)的含义是序列的每个元素都入队()且出队列(桟)一次且仅一次。对于 该序列在上述队列上的操作,正确的叙述是(57)
 
 
  A.  出队序列和出栈序列一定相同
 
  B.  出队序列和出栈序列一定互为逆序
 
  C.  入队序列与出队序列一定相同,入栈序列与出栈序列不一定相同
 
  D.  入栈序列与出栈序列一定互为逆序,入队序列与出队序列不一定互为逆序
 
 
 

 
  第52题    2013年上半年  
   21%
设元素序列a,b,c,d,e,f经过初始为空的栈S后,得到出栈序列cedfba,则栈S的最小容量为 (52)。
  第48题    2019年下半年  
   61%
计算机执行程序时,内存分为静态数据区、代码区、栈区和堆区。其中(48)一般在进行函数调用和返回时由系统进行控制和管理,(49)由..
  第60题    2014年上半年  
   48%
某双端队列如下图所示,要求元素进出队列必须在同一端口,即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出,则对于4个..
   知识点讲解    
   · 队列    · 
 
       队列
        1)队列的定义及基本运算
        队列是一种先进先出(FIFO)的线性表,它只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入元素的一端称为队尾(Rear),允许删除元素的一端称为队头(Front)。
        对队列进行的基本操作如下。
        (1)置队空InitQueue(Q):创建一个空的队列Q。
        (2)判队空Empty(Q):判断队列是否为空。
        (3)入队EnQueue(Q,x):将元素x加入到队列Q的队尾,并更新队尾指针。
        (4)出队DeQueue(Q):将队头元素从队列Q中删除,并更新队头指针。
        (5)读队头元素Frontque(Q):返回队头元素的值,但并不更新队头指针。
        2)队列的存储结构
        (1)顺序存储。队列的顺序存储结构是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在队列的两端进行,因此设置队头指针和队尾指针,分别指示当前的队首元素和队尾元素。
        在顺序队列中,为了降低运算的复杂度,元素入队时只需修改队尾指针,元素出队时只需修改队头指针。由于顺序队列的存储空间是提前设定的,所以队尾指针会有一个上限值,当队尾指针达到其上限时,就不能只通过修改队尾指针来实现新元素的入队操作了。此时,可通过整除取余运算将顺序队列假想成一个环状结构,称之为循环队列。在队列空和队列满的情况下,循环队列的队头、队尾指针指向的位置是相同的。为了区别队空和队满的情况,可采用两种处理方式:其一是设置一个标志位,以区别头、尾指针的值相同时队列是空还是满;其二是牺牲一个元素空间,约定以"队列的尾指针所指位置的下一个位置是头指针时"表示队列满,头、尾指针的值相同时表示队列空。
        (2)链式存储。用链表表示的队列简称为链队列。为了便于操作,给链队列添加一个头节点,并令头指针指向头节点。队列为空的判定条件是:头指针和尾指针的值相同,且均指向头节点。
        3)队列的应用
        队列结构常用于处理需要排队的场合,如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
 
       栈
        1)栈的定义及基本运算
        栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此,栈又称为先进后出(FILO,或后进先出)的线性表。栈进行插入和删除操作的一端称为栈顶,另一端称为栈底。不含数据元素的栈称为空栈。
        对栈进行的基本操作有以下几种。
        .置空栈InitStack(S):创建一个空栈S。
        .判栈空Empty(S):当栈S为空栈时返回真值;否则返回假值。
        .入栈Push(S,x):将元素x加入栈顶,并更新栈顶指针。
        .出栈Pop(S):将栈顶元素从栈中删除,并更新栈顶指针。若需要得到栈顶元素的值,可将Pop(S)定义为一个函数,它返回栈顶元素的值。
        .读栈顶元素Top(S):返回栈顶元素的值,但不修改栈顶指针。
        2)栈的存储结构
        (1)顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素,同时附设指针top指示栈顶元素的位置。在顺序存储方式下,需要预先定义或申请栈的存储空间,也就是说,栈空间的容量是有限的。因此在顺序栈中,当一个元素入栈时,需要判断是否栈满,若栈满,则元素入栈会发生上溢现象。
        利用栈底位置不变的特性,可以让两个顺序栈共享一个一维数据空间,以互补余缺,实现方法是:将两个栈的栈底位置分别设在存储空间的两端,让它们的栈顶各自向中间延伸。这样,两个栈的空间就可以相互调节,只有在整个存储空间被占满时才发生上溢,这样一来产生上溢的概率要小得多。
        (2)链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行,因此不必设置头节点,链表的头指针就是栈顶指针。
        3)栈的应用
        栈的典型应用包括表达式求值、括号匹配等,在计算机语言的实现中以及将递归过程转变为非递归过程的处理中,栈有重要的作用。
   题号导航      2012年上半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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题    在手机中做本题