ONE. Single-Choice
1．In the following data structure, (      ) is linear structure.
A．Forest                            B．Stack           
C．Graph                              D．Binary Tree
2．The Linked List is designed for conveniently (      ) data item.
A．getting                            B．inserting         
C．finding                            D．locating
3．In the four choices, (      ) is not the principles that algorithm designing must obey.
A．Correctness(正确性)                  B．Readability(可读性)
C．Robustness(健壮性)                D．Cyclicity(周期性)
4．Assume a sequence list as 6，5，4，3，2，1 is pushed in a stack, an impossible output sequence list is (      ).
A．3，4，6，5，2，1                B．4，5，3，1，2，6
C．5，4，3，6，1，2                D．2，3，4，1，5，6
5．A stack is a structure that follows the principle of (      ).
A．First-In/First-Out                  B．Lirst-In/Last-Out 
C．Last-In/First-Out                  D．Random In and Out
6．Removing the data item at index i in an array with n items, (      ) items need to be shifted(移动) left one position.
A．n-i                                B．n-i+1           
C．i                                  D．n-i-1
7．There is an algorithm with inserting an item to a ordered SeqList(顺序链表) and still keeping the SeqList ordered. The computational efficiency of this inserting algorithm is (      ).
A．O(log2n)                            B．O(1)           
C．O(n)                                D．O(n2)
8．The addresses which store Linked List (      ).
A．must be sequential                  B．must be partly sequential 
C．must be no sequential              D．can be sequential or discontinuous
9．According to the definition of Binary Tree, there will be (      ) different Binary Trees with 3 nodes.
A．6                                  B．5     
C．4                                  D．3
10．The depth of a Binary Tree is 5, it will have (      ) nodes at most.
    A．31                                B．32       
C．16                                D．10
11．In the following sorting algorithm, (      ) is an unstable algorithm.
A．the insertion sort(插入排序)        B．the bubble sort(气泡法排序)   
C．quicksort(快速排序)                D．mergesort(归并排序)
12．Assume that there is an ordered list consisting of 100 data items, using binary search(二分法查) to find a special item, the maximum comparisons is (      ).
A．25                                  B．1                 
C．10                                    D．7
13．The result from scanning a Binary Search Tree (二叉排序树) in inorder traversal is in ( 
    ) order.
A．descending or ascending            B．descending   
C．ascending                        D．out of order
14．To connect n vertices in an undirected graph, it needs (      ) edges at least.
A．n                                    B．n-1
C．n+1                                  D．1
15．In a directed graph with n vertexes, the maximum edges is (      ).
A．n(n+1)/2                            B．n(n-1)/2         
C．n(n-1)                              D．n2
16．The output from scanning a minimum heap(小顶堆) with level traversal algorithm (      ).
A．must be an ascending sequence.
B．must be descending sequence.
C．must have a minimum item at the head position.
D．must have a minimum item at the rear position.
sorting out17．When a recursive algorithm (递归算法) is transformed into a no recursive algorithm, a structure (      ) is generally used.
A．SeqList                            B．Stack           
C．Queue                              D．Binary Tree
18．A algorithm is referred to (      ).
A．a calculating method               
B．a sorting method
C．a sequential set of instructions to solve a problem
D．a searching method
19．A circular queue(循环队列) is full if (      ).
A．(rear+1)% Maxsize == front        B．front == rear
C．rear+1 == front                      D．(rear-1)% Maxsize == front
20．The difference between static sorting table(静态查表) and dynamic sorting table(动态查表) is (      ).
A．the difference in logical structure           
B．the difference in storage structure
C．the difference of data type
D．insertion and deletion only can be done in dynamic sorting table
TWO．Blank filling questions
1．A connected graph has     【1】      component(s).
2．In a complete binary tree,
the sequence number of node i’s parent ( if exist ) is         【2】       
the sequence number of node i’s left child ( if exist ) is       【3】     
the sequence number of node i’s right child ( if exist ) is       【4】       
3．    【5】    is the fastest known sorting algorithm in practice.
4．A full binary tree of a given height h(h>=1) has   【6】    nodes.
5．An undirected graph G has N vertices. The number of edges of a MST (最小生成树)of this graph is    【7】        .
6．Commonly used graph search methods are     【8】     and     【9】      .
7．Complete the one pass of quicksorting operations. (一趟快速排序算法)
int Partition ( RedType& R[ ], int low, int high )
{          R[0] = R[low] ; 
pivotkey = R[low].key;  // 枢轴 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。