Questions Multiple Choice Questions

The basic unit of data is ( ). A. Data Structure B. Data Element C. Data Item D. File In logical terms, data structures can be classified into ( ). A. Dynamic and Static Structures B. Compact and Non-compact Structures C. Internal and External Structures D. Linear and Non-linear Structures The condition for an unheaded singly linked list head to be empty is ( ). A. head = NULL B. head->next = NULL C. head->next = head D. head != NULL To insert a node pointed by s after the node pointed by p in a singly linked list, execute: A. s->next = p; p->next = s; B. s->next = p->next; p->next = s; C. s->next = p->next; p = s; D. p->next = s; s->next = p; A string is a special type of linear list where its specificity lies in ( ). A. Sequential storage B. Each element is a character C. Linked storage D. Each element can be multiple characters A two-dimensional array M consists of strings made up of 6 characters (each taking one memory cell). Row indices range from 0 to 8, column indices from 0 to 9. At least how many memory cells are needed to store M? A. 90 B. 180 C. 240 D. 540 If a stack uses an array of size n for sequential storage, and top == n indicates an empty stack, what operation should be performed on the top pointer before pushing an element? (top is the stack pointer) A. top++ B. top-- C. top = 0 D. top For a queue of length n stored in a circular single-linked list with only a head pointer, what are the time complexities for enqueue and dequeue operations respectively? A. O(1), O(1) B. O(1), O(n) C. O(n), O(1) D. O(n), O(n) In any binary tree, the relative order of leaf nodes remains unchanged in preorder, inorder, and postorder traversals. A. Unchanged B. Changed C. Uncertain D. None of the above Threaded binary trees use ( ) fields to store successor node addresses. A. Ichild B. data C. rchild D. root The purpose of adding a header node in a singly linked list is ( ). A. To ensure at least one node exists B. To mark the position of the first node C. To facilitate implementation of operations D. To indicate that the singly linked list is a linear list's linked representation Given an undirected graph G = (V, E) where V = {a, b, c, d, e, f}, E = {(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}, which of the following sequences is a valid DFS traversal starting from vertex a? A. a, b, e, c, d, f B. a, c, f, e, b, d C. a, e, b, c, f, d D. a, e, d, f, c, b To minimize collision frequency in hash tables, p should typically be chosen as ( ) when using division method for hashing. A. Maximum even number less than or equal to m B. m C. Minimum prime number greater than or equal to m D. Maximum prime number less than or equal to m The matrix chain multiplication problem can be solved using which of the following methods? A. Greedy Algorithm B. Divide-and-Conquer Recursive Algorithm C. Dynamic Programming D. Kruskal Algorithm Which statement about dynamic programming algorithms is incorrect? A. Used to solve problems with optimal substructure B. Calculates optimal values using a top-down approach C. Subproblems often overlap in dynamic programming D. Solves subproblems first, then constructs the solution to the original problem

True or False Questions

Algorithm time complexity depends on problem size and initial data state. Sequential lists do not require additional space to represent logical relationships between elements. For a doubly linked list, node *p's location is stored in both its predecessor's next pointer and its successor's previous pointer. In a binary tree, subtrees have no left-right ordering. In a tree structure, each node may have multiple predecessors and successors. KMP algorithm avoids backtracking of the main string pointer during pattern matching. An empty string contains zero characters. The bottom element of a stack cannot be deleted. A stack is a linear list with restrictions on push and pop operations. The adjacency matrix of an undirected graph is a diagonal matrix. Directed graph traversal cannot use breadth-first search. When different nodes share the same subsequent hash address, this phenomenon is called "collision". Dynamic programming is more efficient than memoization when all subproblems must be solved at least once. Problems solvable by divide-and-conquer often exhibit overlapping subproblems. A greedy algorithm makes locally optimal choices at each step.

Fill-in-the-blank Questions

When input data is invalid, algorithms should respond appropriately instead of producing unexpected outputs. This property is known as ( ). Storage structures where logically adjacent elements are physically non-adjacent, and logical relationships are represented by pointers, are called ( ) storage structures. The first element of a sequential list has an adress of 200, and each element occupies 4 bytes. What is the address of the 7th element? The fundamental idea of the linked list representation is to use ( ) to denote logical relationships betweeen nodes. The operation that finds the first occurrence of a substring within a main string is called ( ). A two-dimensional array A uses row-major order, with row index i ranging from 0 to 10, column index j from 0 to 5, each element occupying 4 bytes, and A[0][0] having address 1000. What is the address of A[8][4]? Given an input sequence 1, 2, 3, ..., n to a stack, how many different output sequences exist for the second element? A circular queue Q has a capacity of M, with front and rear pointers. How many elements does the queue contain? In a binary linked list with n empty link fields, how many nodes are there in total? In a binary tree, let N₀ be the number of nodes with degree 0 and N₂ be the number of nodes with degree 2. What is the relationship between N₀ and N₂? Given a binary tree with preorder traversal "abdgcefh" and inorder traversal "dgbacehf", what is the postorder traversal? For block search, the table should be ( ). The general form of an index entry in an index table is: (Key, ( )) Greedy algorithms must satisfy the properties of optimal substructure and ( ). A complete undirected graph with n vertices can have at most ( ) edges.

Problem-Solving Questions

Given an array A storing a linked linear list with head pointer A[0].next, write out the list in the specified format. A 0 1 2 3 4 5 6 7 List: ( ) Sort the key sequence 63, 83, 43, 22, 67, 65, 76, 54, 99, 68, 77, 14 using merge sort, showing results after each pass: First pass: [ ][ ][ ][ ][ ][ ] Second pass: [ ][ ][ ] Third pass: [ ] Final result: Given the key sequence (23, 34, 56, 33, 45, 28, 67, 11, 50, 07, 47), construct a hash table of size 15 using division remainder method: (1) Design a suitable hash function. (2) Calculate the load factor. (3) Draw the hash table constructed using chaining with head insertion. Integer sequence 1, 2, 3, 4 enters a stack sequential, and pops can occur at any time. Answer the following: (1) With sequence Push(1), Pop(), Push(2), Push(3), Pop(), Pop(), Push(4), Pop(), what is the output sequence? (2) Can you get output sequences 1423 and 1432? Why or why not? (3) Analyze which of the 24 permutations of 1, 2, 3, 4 can be generated by stack operations. Given an undirected graph, apply Prim's algorithm starting from vertex 1 to generate minimum spanning trees. Input sequence {40, 28, 6, 72, 100, 3, 54, 1, 80, 91, 38}. Construct a binary search tree, then delete node 72. Draw both the original and modified trees.

Algorithm Design Questions

Assuming a binary tree is stored using a binary linked list, design a recursive algorithm to count leaf nodes.

typedef int Elemtype;
typedef struct node{
　　Elemtype  data;
　　①      //define left and right subtrees
}BinNode,*BinTree;

int num=0;
void CountLeaves(BinNode *p, int num){
//num is the number of leaves
    if(p!=Null){
        if((!(p->Ichild)&&!( p->rchild))
            ②  
    　　③    //count leaves in left subtree
    　　④    //count leaves in right subtree
　　}
}        

For a circular queue with a flag tag to distinguish between empty and full states, complete the enqueue and dequeue functions.

typedef int QElemType;    //element type in circular queue

typedef struct{
    QElemType base[maxsize];
    int  front;
    int  rear;
    int  tag;
}CyQueue;

Status EnCyQueue(CyQueue *Q, int x)    //enqueue algorithm with tag
{
    if(Q. front == Q. rear&&Q. tag==1)    //tag=0 means empty, 1 means full
        return OVERFLOW;
    Q. rear =(Q. rear+1)%MAXSIZE;
    Q. base[   ①   ]=x;
    if(    ②   )
        Q. tag=1;
}

Status DeCyQueue(CyQueue*Q, int x)  //dequeue algorithm
{
    if(Q. front ==Q. rear&&Q. tag==0)
        return INFEASIBLE;
    ③    ;
    ④    ;
    if(   ⑤  )
        Q. tag=0;
}

Given an undirected graph with m vertices stored in row-major adjacency matrix, implement the following algorithms: (1) Count the number of edges in the graph

int edges(int  *a, int m)    //a stores the matrix
{
    int i,j;
    int e=0;
    for(i=0;i<m;i++)
        for(j=0; ① ;j++)
            if(②)
                  ③ ;
    return e;
}

(2) Check if vertices i and j are connected

int isadj(int i, int j, int *a, int m)
{return     ④  ;}

Answers Multiple Choice Answers

B D A B B D B D A C C D D C B

True or False Answers

✓ ✓ ✓ ✗ ✗ ✓ ✗ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✓

Fill-in-the-blank Answers

Robustness Linked 224 Pointer Pattern Matching 1208 n-1 (rear-front+M) % M n-1 N₀ = N₂ + 1 gdbehfca Block-wise unordered, inter-block ordered Address Greedy Selection n(n-1)/2