《数据结构样卷3.docx》由会员分享，可在线阅读，更多相关《数据结构样卷3.docx（9页珍藏版）》请在三一办公上搜索。
1、数据结构样卷3重庆大学试卷 教务处07版 第 1 页 共 3 页 重庆大学 数据结构 课程样卷3 开课学院： 计算机学院 课程号： 18001035 考试日期： 6 The inorder sequence of a binary tree is ABCDEFG, and its postorder sequence is BDCAFGE, so its pre-order sequence is ( ) A. EGFACDB B. EACBDGF C. EAGCFBD D. EGAFCDB 7 A Huffman tree with n leaf nodes, its total numbe
2、r of nodes is ( ) A. n-1 B. n+1 C. 2n-1 D. 2n+1 8 In an adjacency list of undirected graph with n vertexes and e edges, 命题人：组题 名姓 密 弊号学作 绝 拒 、 纪 考 肃 严 级、年信 守 实封 诚 、 争 竞 平班、公业专 线 院学考试方式：考试时间： 120 分钟 题 号 一 二 三 四 五 六 七 八 九 十 总 分 得 分 一、 Single choice 1 Merge two ordered list, both of them contain n elem
3、ents, the least times of comparison is ( ). A. n B. 2n-1 C. 2n D. n-1 2 Sequential stored linear list with the length of 1000, if we insert an element into any position, the possibility is equal, when we insert a new element, the average number of removing elements is ( ). A. 1000 B. 1001 C. 500 D.
4、499 3 Assume that the initial status of stack S and queue Q are both NULL, push elements e1,e2,e3,e4,e5,e6 into the stack S one by one, an element pops from stack, then enter into queue Q. If the sequence which the six elements in the dequeue is e2,e4,e6,e5,e3,e1, the capacity of stack S is at least
5、 ( ). A. 6 B. 4 C. 3 D. 2 4 Two-dimensional array A 10 . 20,5 . 10 stores in line sequence, each element occupies 4 storage location, and the memory address of A10,5 is 1000, then the address of A20,9 is ( ). A. 1212 B. 1256 C. 1368 D. 1364 5 A tree with degree 3, it has 2 nodes with the degree 3, o
6、ne node with the degree 2, and 2 nodes with the degree 1, so the number of nodes with degree 0 is ( ). A. 4. B. 5. C. 6. D. 7 the number of edge node is ( ). A. n B. ne C. e D. 2e 9 The degree (sum of in-degree and out-degree) of a directed graph is k1, and the number of out-degree is k2. Therefore,
7、 in its adjacency list, the number of edge nodes in this singly linked list is ( ). A. k1 B. k2 C. k1-k2 D. k1+k2 10 If the graph has n vertexes is a circle, so it has ( ) spanning tree. A. n B. 2n C. n-1 D.n+1 11 When look up a sequential list with the length 3, the possibility that we find the fir
8、st element is 1/2, and the possibility that we find the second element is 1/3, the possibility that we find the third element is 1/6, so the average searching length to search any element (find it successfully and the sentry is at the end of the list) is ( ) A. 5/3 B.2 C. 7/3 D.4/3 12 There is an or
9、dered list 3,5,7,8,11,15,17,22,23,27,29,33, by binary search to search 27, so the number of comparison is ( ) A. 2 B. 3 C. 4 D. 5 13 Sort the following keyword sequences by using Quicksort, and the slowest one is ( ) A. 19,23,3,15,7,21,28 B. 23,21,28,15,19,3,7 C. 19,7,15,28,23,21,3 D. 3,7,15,19,21,2
10、3,28 14 Heapsort needs additional storage complexity is ( ) A. O(n) B. O(nlog22n) C. O(n) D. O(1) 15 If we sort an array within the time complexity of O(nlog2n), needing sort it stably, the way that we can choose is ( ) A. Merge sort B. Direct insertion sort C. Heap sort D. Quicksort 二、 Fill the bla
11、nks 1. Assume that the structure of the nodes in doubly circular linked list is (data,llink,rlink), without a head node in the list, if we want 人：审题人： 命题时间： 教务处制重庆大学试卷 教务处07版 第 2 页 共 3 页 2. 3. 4. to insert the node which pointer s points after the node pointer p points, then execute as the following
12、 statements: ; ; _ _; ; Both stack and queue are _linear structure. The four leaf nodes with the weight 9,2,5,7 form a Huffman tree, its weighted path length is _. In order to ensure that an undirected graph with six vertexes is 2. The following is AOE network: (1) How much time does it take to comp
13、lete the whole project? (2) Find out all of the critical path.(9 points) 3. Assume that a set of keywords is 1，12，5，8，3，10，7，13，97,try to complete the following questions:(9 points) (1) Choose the keywords in sequence to build a binary sort tree Bt; connected, need at least _ edges. 5. An n-vertex d
14、irected graph, if the sum of all vertices out-degree is s, then the sum of all vertices degree is_ _. 6. The Depth-First traversal of a graph is similar to the binary tree_ traversal; the Breadth-first graph traversal algorithm is similar to the binary tree _traversal. 7. A connected graph with n ve
15、rtexes and e edges has _ edges of its spanning tree. 8. The time complexity of binary searching is _; if there are 100 elements, the maximum number of comparisons by binary searching is _. 9. Sort n elements by merge sort, the requiring auxiliary space is _. 10. Sort a linear list with 8 elements by
16、 Quicksort, at the best, the comparison time is _. 三、 Application 1. Begin from the vertex A, seek the minimum spanning tree by using Prim algorithms V1a3=3V3a7=5V5a11=8V8a58=4a12=21a6=V04aa6=4V6aaa15=32=617=3=98aV2a5=3V4a10=5V7a14=9V9 (2) Draw the structure of the tree after deleting node “12” from
17、 the binary tree Bt. 4. The keyword sequence is 503,87,512,61,908,170,897,275,653,462, using radix sorting method to sort them in ascending order, try to write every trip results of sort. 四、 Algorithm 1. The following algorithm execute on a singly linked list without head node, try to analyze and wr
18、ite its function.(5 points) void function(LinkNode *head) LinkNode *p,*q,*r; p=head; q=p-next; while(q!=NULL) r=q-next; q-next=p; p=q; q=r; head-next=NULL; head=p; 2. Design an algorithm to divide a singly linked list A with a head 重庆大学试卷 教务处07版 第 3 页 共 3 页 pointer a into two singly linked list A an
19、d B, whose head pointers are a and b, respectively. On the condition that linked list A has all elements of odd serial number in the previous linked list A and linked list B has all elements of even serial number in the previous linked list A, in addition, the relative order of the original linked list are maintained.(7 points) 3. The type of binary tree is defined as follows: typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode, *BiTree; Please design an algorithm to count how many leaf nodes the binary tree have.
