Single choice questions

1The algorithm must have five characteristics: input, output, and ( ).

AFeasibility, portability, and extensibility BFeasibility, certainty and fineness

CCertainty, fineness and stability DLegibility, stability and security

2If the linear table adopts the chain storage structure, the addresses of the available storage

units in memory ().

Amust be continuous Bcan be continuous or continuous

Cmust be discontinuous Dmust be partially contiguous

3Let the pointer p in the single linked list point to node m. To delete the node after m (if it

exists), modify the pointer by ().

Ap = p->next->next; Bp = p->next;

C q = p->next; p->next = p->next->next; free(q); Dp->next = p;

4The operation of inserting the node pointed to by s after the node pointed to by p of the

circular double-linked list is ().

Ap->right = s; s->left = p; p->right->left = s; s=->right = p->right;

Bp->right = s; p->right->left = s; s->left = p; s->right = p->right;

Cs->left = p; s->right = p->right; p->right = s; p->right->left = s;

Ds->left = p; s->right = p->right; p->right->left = s; p->right = s;

5If the input sequence of a stack is 6 5 4 3 2 1, the following sequence that may be the

output sequence of the stack is ().

A. 1 4 3 5 2 6 B. 6 5 4 1 3 2 C. 3 1 4 2 6 5 D. 5 6 3 4 2 1

6Suppose there is a recursive algorithm as follows:

int fact(int n)

{ //n>=0

if (n<=0) return 1;

else return n*fact(n-1);

}

The number of times this function needs to be called to calculate fact(n) is ().

A. n-1 B. n+1 C. n D. n+2

7Let the string s1 = ABCDEFG

s2 = PQRST function con(x,y) returns the

concatenation string of x and y stringssubs(s,i,j) returns the substring of j characters from

the sequence number i of string slen(s) returns the length of string sThen the result string

of con(subs(S1, 2, len(S2)), subs(S1, len(S2), 2)) is ().

A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF

8There are ( ) nodes in the k-th layer of a full m fork tree with depth h.1 <= k <= h

A. mk-1 B. mk

-1 C. mh-1 D. mh

-1

9 n n >= 2 characters with different weights form a Huffman tree, which of the following

descriptions of the tree is wrong ().

AThe tree must be a complete binary tree

BThere must be no node of degree 1 in the tree

CThe two nodes with the lowest weights in the tree must be brother nodes

DThe weight of any non-node in the tree must not be less than the weight of any

node in the next layer

10The following () is suitable for constructing a minimal spanning tree of sparse graph G.

APrim algorithm BFloyd algorithm

CKruskal algorithm DDijkstra algorithm

11Given the adjacency matrix of the graph as shown below, the result of depth-first

traversal from vertex v0 is ().

1 100010

0 001101

1011010

1 100110

1000100

1 001001

0 1 11101

A0 2 4 3 1 5 6 B0 1 3 4 2 5 6

C0 1 3 6 5 4 2 D0 3 6 1 5 4 2

12Which of the following statements is true about hash table search ().

AThe more complex the hash function construction, the better, because it has

better randomness and less conflict

BThe divided-residual method is the best of all hash table functions

CThere is no such thing as a good or bad hash function, it depends on the

situation.

DThe average search length of the hash table is also sometimes related to the

total number of records

13 Binary search ordered table 4, 6, 10, 12, 20, 30, 50, 70, 88, 100. If you look for element

58 in the table, it will fail when compared with elements () in the table in turn.

A20703050 B30887050

C2050 D308850

14A heap is a () sort whose shape is a ().

AInsertionBinary sort tree BSelectionComplete binary tree

CExchangeFull binary tree DMergeBalanced binary tree

15Sort a set of data {2, 12, 16, 88, 5, 10}, if the first three sorting results are as follows:

The first{2, 12, 16, 5, 10, 88}

Second{2, 12, 5, 10, 16, 88}

Third{2, 5, 10, 12, 16, 88}

ABubble sort BHill sort

CMerge sort DRadix sort