GATE 2018 CS 组 3

答案： D

说明

给定 a_n = 2n + 3

序列 an 的生成函数 G(x) 是

展开上述函数，我们得到，
= 2(0+x+2x²+3x³+.....) + 3(1+x+x2+......)
现在我们取 (0+x+2x²+3x³+.....)
= x (1 + 2x + 3x² + .....)
= x / (1-x)²
同样，1+x+x²+..... = 1 / (1-x)

现在将这些值代入 G(x) 我们得到，
G(x) = 2(x/(1-x)²) + 3(1 / 1-x )
        = 2x+3-3x / (1-x)²)
        = 3-x / (1-x)²

因此，正确的选项是 (D)。

答案： A

说明

char 'a' + 2 将变成 'c'
所以，Ournode p = {'1','0','c'}
*((char*)q+1) == p[1]
*((char*)q+2) == p[2]
printf("%c, %c", *((char*)q+1), *((char*)q+2));
因此，输出 = 0,c
因此，正确的选项是 (A)。

答案： B

说明

创建新节点 N

Enqueue(){
       N -> Data = Data
       N -> Next = Head
       Head = N
}

在此入队操作中，仅涉及指针操作，这需要恒定的时间量。

因此，时间复杂度 = O(1)

从尾部删除一个节点

对于出队操作，我们将单链表的倒数第二个节点的 next 指针设为 NULL。 在单链表中，我们无法访问它的上一个节点，因此我们需要遍历整个链表才能获得链表的倒数第二个节点，即

Dequeue(){
       temp = head
       While(temp -> Next -> Next != NULL)
         temp = temp->next
       temp -> next = NULL
       tail = temp
}

由于我们为每个出队操作遍历整个链表。

所以，时间复杂度 = O(n)

答案： D

说明

左侧，

     (p⊕p)⊕q = 1⊕q = 1.q' + 0.q = q'

右边

     (p⊙p')⊙(q') = 0⊙(q') = 0(q') + 1.(q')' = q

因此，LHS ≠ RHS 因此，选项 (D) 是正确的答案。

答案： D

说明

在 RISC 中，指令长度不能变化。 它通常是固定的，为 32 位。 在 CISC 中，指令长度可以在 16 到 64 位之间。

仅当指令固定时才使用硬连线控制单元。

寄存器到寄存器的操作在 RISC 中始终是可能的。 CISC 可以同时具有寄存器到寄存器的操作和内存到内存的指令。

答案： D

说明

如果 NFA 具有 n 个状态，则等效的 DFA 最多可以有 2ⁿ 个状态。

因此，最小 DFA 中的状态数 -> k ≤ 2ⁿ

答案： B

说明

我们知道，递归可枚举语言在联合、交集、连接下封闭，但在求补下不封闭。

所以，我们可以很容易地说选项 (A) 是正确的答案。

答案： B

说明

类型检查在语义分析阶段执行，解析在语法分析阶段执行。 由于语法分析阶段先于语义分析，因此类型检查始终在解析之后完成。 因此，选项 (B) 是错误的，是正确的答案。