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．inrting
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 quence list as 6，5，4，3，2，1 is pushed in a stack, an impossible output quence list is ( ).
A．3，4，6，5，2，1 B．4，5，3，1，2，6
sodasC．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 inrting an item to a ordered SeqList(顺序链表) and still keeping the SeqList ordered. The computational efficiency of this inrting algorithm is ( ).
A．Otouristy(log2n) B．O(1)
C．O(n) D．O(n2)
8．The address which store Linked List ( ).
A．must be quential B．must be partly quential
C．must be no quential D．can be quential 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 Bstrong的反义词．32
C．16 D．10
11．In the following sorting algorithm, ( ) is an unstable algorithm.
A．the inrtion sort(插入排序) B．the bubble sort(气泡法排序)
C．quicksort(快速排序) D．mergesort(归并排序)
12．Assume that there is an ordered list consisting of 100 data items, using binary arch(二分法查找) to find a special item, the maximum comparisons is ( ).
itchA．25 B．1
C．10 D．7
金酸梅奖提名13．The result from scanning a Binary Search Tree (二叉排序树) in inorder traversal is in
tips( ) 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 quence.
B．must be descending quence.
C．must have a minimum item at the head position.
D．must have a minimum item at the rear position.
17．When a recursive algorithm (递归算法) is transformed into a no recursive algorithm, a structure ( ) is generally ud.
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 quential t of instructions to solve a problem
D．a arching 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．inrtion 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 quence number of node i’s parent ( if exist ) is 【2】
the quence number of node i’s left child ( if exist ) is 【3】
the quence 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 ud graph arch methods are 【8】 and 【9】 benchmark是什么意思.
7．Complete the one pass of quicksorting operations. (一趟快速排序算法)
int Partition ( RedType& R[ ], int low, int high )
{ R[0] = R[low] ;
pivotkey = R[low].key; // 枢轴
