2012數(shù)據(jù)結(jié)構(gòu)英文試卷A及答案

1、北京交通大學(xué)軟件學(xué)院20122013學(xué)年第一學(xué)期期末考試試題Data Structure and Algorithm Design(A)Class:Student Number: Name:TeacherNo、IIIIIIIVVVITotalMarkI、 Single-Choice(20 points)1、 The height of a binary tree that contains 1023 elements is at most(1 ) and at least ( 2 卜A. 1022B.1023 C. 1024D.9E.10F.112、 If the sequence of pu

2、shing elements into a stack is a,b,c, which output sequence is impossible?( ).A.abcB.bcaC.cbaD.cab3、How many minimum-cost spanning trees are there for an undirected connectedgraph with n vertices and e edges?()A、 must be only one B、n-1C、 n-eD、 notsure4、When using the adjacency matrix A to represent

3、a undirected graph with n nodesand e edges, the degree of the node vi can be computed by formula ( 卜nn/2 C、e /2 D、1l5、 In the worst case, time complexity of quicksort will be degraded to ( 卜A.O(n)B.O(n2)C.O(nlogn)6、 In order to find a specific key in an ordered list with 100 keys using binary search

4、 algorithm, the maximum times of comparisons is ( 卜 A、25B、10C、1D、77、 Consider the following pseudo-code, which indicates part of a standard binary tree algorithm、print( node ) print data;if( there is a left child ) print( left child );if( there is a right child ) print( right child );Which of the fo

5、llowing is the standard name for this algorithm?()A、Inorder traversalB、Preorder traversalC、Postorder traversalD、 Binary search8、Which is not the property of a B-tree of order m? ()A、 The root node has m subtree at mostB、 All leaf nodes are at the same level、C、 The keys in every node are ordered、D、 A

6、ll leaf nodes are connected by links、9、Suppose that we have 1000 distinct integers, which are in the range from 0 to 50、 If using Radix Sort according to the Least Significant Digit first, () bucketsare needed to constructed、A、 10B、50C、 51D、1000Answer table for Question I (write your answers of Ques

7、tion I here)1(1)1(2)23456789BEDDABDBDAII、 Fill in the blank (2points * 5)Answer table for II (Please write your answers of II here)12234preorder112,3,5i*n+j5,4,3,2,11、 The strategy of depth-first searching algorithm for a graph is similar tothat of traversal algorithm for a normal tree、2、 Here is a

8、hash table, whose size is 18, hashing function is H1(key尸key%17 (% here is the modulus operator), and which uses Linear Probing strategy to cope with the collisions and inserts 26, 25, 72, 38, 8,18, 59 into the hash table in turn、 The address of 59 is、3、 Given a key sequence 2,5，,3, please write its

9、 ascending ordered sequence after being sorted using heap sort、 (Note 5=，just 5 is before in original sequence) 、 Please distinguish 5 and 、4、 If a 2-dimensions matrix Amn is stored in an 1-D array with row-major mapping, then the address of element Aij relative to A00 is5、 If the in-order and pre-o

10、rder series of the nodes in a binary tree are 1,2,3,4,5“ and 1,2：3,4,5" respectively, the postorder sequence should be、111、 (40 points)1、(8 points) Suppose there is a string abcadececdcdeeededthat comprises the characters a, b, c, d and e、 We may encode the symbols using variable-length codes i

11、n order to make the length of string the shortest、 Please draw the Huffman tree used to encode the characters, calculate the weighted path length for the Huffman tree and write the code for each character Draw the Huffman tree (3 points) a:2, b:1, c:4, d:5 , e: 6(3 points)(2) Calculate the weighted

12、path length for the Huffman tree (2 points)WPL(T尸 6 2+5 2+2 3+1 3+4 2 =39(3) write the code for each character、(3 points)錯一個扣一分，扣光為止abcde12、(8 points) Please respectively give two unsorted lists whose length are 4 to illustrate that quick sort and selection sort are unstable、 An example list for qui

13、ck sort and the sorting procedure using quicksort、(4 points)(4, 2,，3) (2 points)sorting procedureThe first pass: 3,2, ，4 (1point)The second pass: ，2,3,4 (1point)(2) An example list for selection sort and the sorting procedure usingselection sort、(4 points)(2,3,1) (1 points)sorting procedureThe first

14、 pass: 1,，3,2 (1point)The second pass: 1,，3,2 (1point)The third pass: 1,，2, 3 (1point)3、(8 points) Given the key sequence (331, 166, 367, 236, 268, 137, 337,138), Please give the procedure (distributing and collecting) of sorting using radix sort method、 not necessary to write queue front and rear p

15、ointer if queue is null、(1) The first pass (3 points)pf 3 31 166 f 36"- 2268 - IT- 33 7 - 13 S1st pa» of distributing accordi to the Lea$t digitII1T31T1" 6t1G6T230- if 6f73V- 137 -337 r7fl«268138 一dlpass of collectingp-331 - 166 736T367Tly7T 337T268 T38(2) The second pass (3 poin

16、ts)p7331Tl 66- 236T367tI37T337T268Tl3 區(qū)2ad pass of distributing according to the middle digit心一31 -236- 137337138皿f6-l6 J367 2681 2 pass of collectingp -331-236 ->137->337->138 T66T367T268(3) The third pass (2 points)p-*331-*236 t137-Q37 -*138 >166-36號一>2683" pa5!)vrdhtribuiii ac

17、cording tc iht uiu)t Mgniricaut digifl>137-138>166rl仃2-236T268 Jl2iI3 -33 L ->337 ->367 r3J3rd pa。of collectingp - 137Tl38-16J236T26J3337767It is in ascending order*4、(6 points)There are n 1 nodes of degree 1,r2 nodes of degree 2,，nmnodes of degree m in a tree of degree m,how many leaf n

18、odes there are in the tree? Please give formula and prove your conclusion、Answer:because every node except root has one branch linked, so total(2points)nodes are equal to total branches plus one, there are n branches in node ofdegree nformula such as (2points)%斗叫斗4%京9+1，哈a 1尸現(xiàn)t(2points)5、 (10 points

19、) Show the result of inserting 63, 37, 48, 100, 54, 64, 27, 108, 99,42 into(a) an empty binary search tree(2 points)(b) an initially empty A VL tree(4 points)(c) an initially empty B-tree of order 3(4 points)Answer: binary search tree(2 points)(2)AVL (4 points)(3) B-tree (4points)IV、 (10 points) Ple

20、ase fill in the blanks in the program which reverses a singly linked list、 For example, 1,2,3,4,5,6,7,8,9,10 will become 10,9,8,7,6,5,4,3,2,1 after being reversed、 #define list_init_size 100#define n 10#define len sizeof(struct node)typedef struct node int num; struct node *next; lnode,*link;link ll

21、ist;static int a尸1,2,3,4,5,6,7,8,9,10;void creat(link *list)/create a singly linked list for key sequence stored in array a int i=0;lnode *p,*q;q=(struct node*)malloc(len);q->num=ai; *list=q;while (i<n-1) p=(struct node*)malloc(len);i=i+1;(1;(2 q=p;p->next=0;void reverseList(link *h)/ rever

22、se the singly linked list Inode *p,*q, *r; p=*h;r=0;while (p)q=p;(3) ;(4); r = q; (5); main()lnode *l; creat(&l); reverseList(&l);Answer:(1) _ p->num=ai;(2) _ q->next=p;(3) _ p=p->next;(4) _ q->next =r;(5) _*h=qV、(10 points)Please read the following code, write the functions of p

23、rograms and write output of the program、#include<stdio、h>#include "malloc、h"#define n 6static char chn='a','b','c','d','e','f;static int ann=0,1,1,0,0,0,1,0,0,1,1,0,1,0,0,1,0,1,0,1,1,0,0,1,0,1,0,0,0,1,0,0,1,1,1,0;typedef struct node /* 鄰接表中

24、的邊結(jié)點(diǎn)*/ int adjvex;struct node *next; EdgeNode;typedef struct vnode /*鄰接表中的頂點(diǎn)結(jié)點(diǎn)*/ char vertex; EdgeNode *firstedge; VertexNoden;typedef struct int front,rear; int datan; CirQueue;CirQueue *Q;int pathn,sum=0; int visitedn; VertexNode G;void createALGraph() /*根據(jù)鄰接矩陣,建無向網(wǎng)的鄰接表表示*/int i,j; EdgeNode *s;for

25、(i=0; i<n; i+) Gi 、 vertex=chi;Gi 、 firstedge=0; for(i=0; i<n; i+) for(j=0; j<n; j+) if (aij=1) s=(EdgeNode*)malloc(sizeof(EdgeNode);s->adjvex=j; s->next=Gi 、 firstedge;Gi 、 firstedge=s;void print() int i; EdgeNode *s;for (i=0; i<n; i+) s=Gi 、 firstedge;printf(" %c :",Gi

26、、 vertex);while(s) printf(" %c",Gs->adjvex 、 vertex);s=s->next;printf("n");int ShortestPath(int u,int v) /* 求 u 與 v 之間經(jīng)過的分支數(shù)最少的路徑*/ int k,pren,spathn,count=0,found=0;EdgeNode * p;if(u=v) printf("errorn"); return 0; Q=(CirQueue*)malloc(sizeof(CirQueue);Q->front=

27、Q->rear=0;for(k=0;k<n;k+) visitedk=0; prek=-1;visitedu=1; Q->dataQ->rear+=u;while(!found && Q->front!=Q->rear) k=Q->dataQ->front+;p=Gk 、 firstedge;while(p && !found) if(visitedp->adjvex=0) prep->adjvex=k;if(p->adjvex=v) found=1; break;visitedp->adjvex=1;Q->dataQ->rear+=p->adjvex;p=p->next;if(found) printf("found: ");spathcount+=v; k=prev;while(k!=u) spathcount+=k; k=prek; spathcount=u;for(k=count;k>=0;k-)printf("%d ", spathk);printf("n"); return 1;elseprintf("There is no pa