Mixed practice set 3

Practice set

Q1MCQ2 marksPadding

On our 32-bit target, what does this print?

#include <stdio.h>
struct A { char c; int i; char d; };
struct B { char c; char d; int i; };
union U { int i; char c[6]; };

int main(void)
{
    printf("%d %d %d\n", (int)sizeof(struct A), (int)sizeof(struct B), (int)sizeof(union U));
    return 0;
}

• (A) 6 6 6
• (B) 12 8 8
• (C) 12 8 6
• (D) 9 6 8

Q2NAT2 marksStatic in recursion

What does this print?

#include <stdio.h>
int g(int n)
{
    static int c = 0;
    c++;
    if (n <= 0) return c;
    return g(n - 2) + n;
}

int main(void)
{
    printf("%d\n", g(5));
    return 0;
}

Numerical answer: ________

Q3NAT2 marksTrees

What does this print?

#include <stdio.h>
#include <stdlib.h>
struct tnode {
    int data;
    struct tnode *left, *right;
};

struct tnode *insert(struct tnode *t, int x)
{
    if (t == NULL) {
        t = malloc(sizeof(struct tnode));
        t->data = x;
        t->left = t->right = NULL;
    } else if (x < t->data) t->left = insert(t->left, x);
    else t->right = insert(t->right, x);
    return t;
}

int f(struct tnode *t)
{
    if (t == NULL) return 0;
    if (t->left == NULL && t->right == NULL) return t->data;
    return f(t->left) + f(t->right);
}

int main(void)
{
    int a[] = {50, 30, 70, 20, 40, 60, 80, 65}, i;
    struct tnode *root = NULL;
    for (i = 0; i < 8; i++) root = insert(root, a[i]);
    printf("%d\n", f(root));
    return 0;
}

Numerical answer: ________

Q4MCQ1 markConversions

What does this print?

#include <stdio.h>
int main(void)
{
    unsigned int u = 1;
    int i = -1;
    unsigned char c = 255;
    c++;
    printf("%d %d\n", i < u, c);
    return 0;
}

• (A) 1 256
• (B) 1 0
• (C) 0 256
• (D) 0 0

Q5NAT1 markLinked list

What does this print?

#include <stdio.h>
#include <stdlib.h>
struct node {
    int data;
    struct node *next;
};

struct node *build(int n)            /* list 1 -> 2 -> ... -> n */
{
    struct node *h = NULL, *p;
    while (n > 0) {
        p = malloc(sizeof(struct node));
        p->data = n--;
        p->next = h;
        h = p;
    }
    return h;
}

void show(struct node *h) { for (; h != NULL; h = h->next) printf("%d ", h->data); printf("\n"); }

int main(void)
{
    struct node *h = build(7), *slow = h, *fast = h;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    printf("%d\n", slow->data);
    return 0;
}

Numerical answer: ________

Q6MCQ1 markPrefix

The prefix form of a + b * (c − d) / e is:

• (A) + a * b / - c d e
• (B) + * a b / - c d e
• (C) + a / * b - c d e
• (D) / + a * b - c d e

Q7NAT1 markPostfix value

Evaluate the postfix expression 8 2 3 * + 4 2 / −.

Numerical answer: ________

Q8NAT2 marksCircular queue

A circular queue of size 8 uses front = slot before the first element. If front = 6 and rear = 2, how many elements are in it?

Numerical answer: ________

Q9MCQ2 marksBST delete

From the BST built by inserting 40, 20, 60, 10, 30, 50, 70, 25, 35, delete 20 using the inorder successor. The preorder is:

• (A) 40 25 10 35 30 60 50 70
• (B) 40 30 10 25 35 60 50 70
• (C) 40 25 10 30 35 60 50 70
• (D) 40 10 30 25 35 60 50 70

Q10NAT2 marksBST orders

How many insertion orders of {1, 2, 3, 4, 5} produce the same BST as 3 2 1 4 5?

Numerical answer: ________

Q11MCQ1 markHeaps

Bottom-up build-min-heap on 3 9 2 1 4 5 gives:

• (A) 1 2 3 4 5 9
• (B) 2 1 3 9 4 5
• (C) 1 3 2 9 4 5
• (D) 1 3 2 4 9 5

Q12MSQ2 marksRepresentations

For a graph with n vertices and e edges, which are true?

• (A) Adjacency lists use Θ(n + e) space.
• (B) BFS with a matrix costs Θ(n²).
• (C) The trace of A² is 2e (simple undirected).
• (D) An incidence matrix has n² cells.