重庆大学 数据结构 课程样卷2 |
|
|
变压器风扇开课学院： 计算机学院 课程号： 18001035 | 考试日期： |
| 考试时间： 120 分钟 |
题 号 | 一 | 二 | 三 | 四 | 五 | 六 | 七 | 八 | 九 | 十 | 总 分 |
得 分 | | | | | | | 文具盒生产过程 | | | | |
| | | | | | | | | | | | | |
一． Single choice
1． The linear list (a1, a2, ... an), which is in Sequential Storage, when we delete any node, the average number of moving nodes ( ).
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
2． Which is wrong among the following statements ( ).
A. Data element is the basic unit of the data
B. Data element is the smallest unit of the data
C. Data can be composed of a number of data elements
移动管式喷砂机
D. Data items can be composed of a number of data elements
3． To insert a data element in a linear structure data conveniently, the best data structure is ( ).
消音片A. Sequential storage B. Linked storage
C.Index storage D. Hash storage
4． If insert a new node into the doubly linked list which the number of nodes is n, the measurement level of time complexity is ( ).
A.O(1) B. O(n) C. O(nlog2n) D. O(n2)
5． In virtue of a child’s Brother linked lists as a tree, if we want to find the fifth child of the node x, as long as finding the first child of x, and then ( ).
A. pointer scans 5 nodes continuously from the child domain
B. pointer scans 4 nodes continously from the child domain
C. pointer scans 5 nodes continously from the brother domain
D. pointer scans 4 nodes continously from the brother domain
6． The character of Tree structure is: a node can have( )
A. More than one direct pre-trend
B. More than one direct successors
C. More than one pre-trend
D. A successor
7． 蛋白糖基化Assume that there are 13 numbers, they form a Huffman tree, calculate the number of nodes on this Huffman tree ( ).
A. 13 B. 12 C. 26 D. 25
8． A spanning tree of the undirected connected graph is a ( ) which contains the whole vertices of this connected graph.
A. Minimal connected subgraph B. Minimal subgraph
C. Significantly connected sub-graph D. Significantly sub-graph
9． Which is wrong in the following statements ( ).
A. Each vertex is only visited once during the graph traversal.
B. There are two methods, Depth-First Search and Breadth-First Search, to traverse a graph.
C. Depth-First Search of a graph isn’t fit to a directed graph
D. Depth-first search of a graph is a recursive process
10． In sequential search algorithm of static table, if we set up a sentry at the head of a list, the right way to find the element is ( )
A. Looking for the data element from the first element to the back
B. Looking for the data element from the second element to the back
C. Looking for the data element from the (n+1)th element to the front
D. I t is nothing to do with the search for order
11． In order to find the number 85 in an ordered list (18,20,25,34,48,62,74,85), how many times do we need to compare( )
A.Once B. Twice C. 3 times D. 4 times
12． Assume that the length of Hash table is m=14, Hash function H(key) = key % 11. There have been 4 nodes in the table, and their addresses are: 4,5,6,7. Other addresses are NULL. In virtue of quadratic probing re-hash to deal with conflict, calculate the address of node whose keyword is 9 ( ).
A. 8 B. 3 C. 5 D. 9
13． 过氧化锰Using Quicksort to sort the following four sequences, and choose the first element as the benchmark to divide. During the first division, in the following sequences which need to move the most times ( )
A. 70,75,82,90,23,16,10,68
B. 70,75,68,23,10,16,90,82
C. 82,75,70,16,10,90,68,23
D. 23,10,16,70,82,75,68,90
14． There are 10000 elements in a sequence, the best way to get the very smallest 10 elements in the sequence is ( ).
A. Quicksort B. Heapsort C. Insertion sort D. Merge sort
15． If the sequence is almost in order, take compare times of key code and move times of key code into account, the best way to sort is( )
A. Merge sort B. Insertion sort C. Straight selection sort D. Quicksort
二． Fill the blanks
1． In order to insert a new node s after the node which pointer q points to in a circular doubly linked list, we need to execute the following statements:
s->prior=q; s->next=q->next; _____________________; q->next=s;
2． In the doubly linked list, if d is a pointer points to a node in the list, then:
d->next->__________=d->prior->__________=__________;
3． Stack can be considered as an operation restricted linked list ,one end that can insert and remove is called _____________。
4． In threaded binary tree, a node which is pointed by t has no left sub-tree, the necessary and sufficient conditions for is _____________。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议