免费智能真题库 > 历年试卷 > 软件设计师 > 2013年下半年 软件设计师 上午试卷 综合知识
  第58题      
  知识点:   队列   指针
  关键词:   存储空间   队列   容量   指针        章/节:   计算机软件知识       

 
设循环队列Q的定义中有front和size两个域变量,其中front表示队头元素的指针,size表示队列的长度,如下图所示(队列长度为3,队头元素为x、队尾元素为z)。设队列的存储空间容量为M,则队尾元素的指针为(58)。
 
 
  A.  (Q.front+Q.size-1)
 
  B.  (Q.front+Q.size-1+M)%M
 
  C.  (Q.front-Q.size)
 
  D.  (Q.front-Q.size+M)%M
 
 
 

 
  第57题    2022年下半年  
   58%
设栈初始时为空,对于入栈序列1,2,3…n这些元素经过栈之后得到出栈序列P1,P2,P3,.…Pn,若P3-4,则P1,P2不可能的值为()。
  第60题    2009年上半年  
   44%
下面关于栈和队列的叙述,错误的是(60)。
  第63题    2015年上半年  
   52%
优先队列通常采用(62)数据结构实现,向优先队列中插入—个元素的时间复杂度为(63)。
   知识点讲解    
   · 队列    · 指针
 
       队列
        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)队列的应用
        队列结构常用于处理需要排队的场合,如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。
 
       指针
        指针是C语言中最为重要也是最难的一个关键点,很多数据结构都是基于指针实现的,如链表、链式队列、链栈、二叉树等。
        所谓指针,就是一个用来存储地址的变量。这可谓指针的本质,需要牢记。
        也许你会很纳闷,指针为什么一定要定义成某类型(int、char)呢?指针不能就是"指针类型"吗?接触过汇编的人就很容易理解为什么。存储单元的单位是字节,就是说一般地址是按字节编址的,对一个地址进行操作(读取或赋值)就要指明是对单字节(不用特别声明)、两字节(WORD PTR),还是双字节(四字节,DWORD PTR)进行操作。同样,指针是存储地址的,即指针就是一个地址,自然也要说明其类型;而且,这个类型还关乎指针自加自减时真正加减的字节数。
        顺便说一下,数组名也是指针。数组在申请空间时,数组名存储该存储空间的首地址。注意:数组名存储的是地址,因此也是指针,只是该指针一旦赋值后就不能修改,即所谓常指针。当直接输出数组名时,输出的其实是数组的首地址。这样,当形参声明为指针时,亦可将数组名作为实参进行传递。因此,可以用指针的方式访问数组中的元素,如下例采用指针的方式遍历输出数组。
        
        当指针作为函数参数传递时,需要特别注意C语言中的"值"传递原则。下例中的函数希望为指针p申请空间,但不能达到目的,为什么呢?
        
        归根结底,C函数的形参与实参之间只是"值传递":当形参是普通变量时,传递的是实参的值;当形参是指针时,传递的是指针变量的值,即某变量的地址,这样可以通过指针成功地改变其所指单元的值,但自身的改变不会传回给实参。上例可改为:
        
        注意:这样修改后,调用时实参应该是指针的"地址"(或指向指针的指针)。这样即上面所说的可以改变指针所指单元的值,因此可达到预期目的。
   题号导航      2013年下半年 软件设计师 上午试卷 综合知识   本试卷我的完整做题情况  
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 /
 
第58题    在手机中做本题