2021数据结构英文试卷A及答案

1、北京交通大学软件学院20212021学年第一学期期末考试试题Data Structure and Algorithm Design(A)Class:Student Number: Name:TeacherNo、IIIIIIIVVVITotalMarkI、Single-Choice(20 points)1、The height of a bi nary tree that contains 1023 eleme nts is at most(1) and at least ( 2)、A. 1022B.1023 C. 1024D.9E.10F.112、If the seque nee of pus

2、h ing eleme nts into a stack is a,b,c, which output seque nee is impossible?( ).A.abcB.bcaC.cbaD.cab3、How many minimum-cost spanning trees are there for an undirected connected graph with n vertices and e edges?()A、 must be only one B、 n-1C、n-eD、 notsure4、When using the adjace ncy matrix A to repres

3、e nt a un directed graph with n no desand e edges, the degree of the node vi can be computed by formula ()、B、丿 i /2 C、 e /2ntiAUJJ +?AiJD、5、In the worst case, time complexity of quicksort will be degraded to ()、A.O( n)B.O( n2)C.O( nlog n)6、In order to find a specific key in an ordered list with 100

4、keys using binary searchalgorithm, the maximum times of comparis ons is ()、A、25B、 10C、1D、 77、Con sider the follow ing pseudo-code, which in dicates part of a sta ndard binary tree algorithm、print( node ) print data;if( there is a left child ) print( left child );if( there is a right child ) print( r

5、ight child );Which of the follow ing is the sta ndard n ame for this algorithm?()A、 Ino rder traversalB、 Preorder traversalC、 Postorder traversal D、 Bi nary search8、Which is not the property of a B-tree of order m? ()A、The root node has m subtree at mostB、All leaf no des are at the same level、C、The

6、keys in every node are ordered、D、All leaf no des are conn ected by links、9、Suppose that we have 1000 distinet integers, which are in the range from 0 to 50、If using Radix Sort accord ing to the Least Signi fica nt Digit first, () bucketsare n eeded to con structed、A、10B、50C、51D、1000An swer table for

7、 Questi on I(write your an swers of Questi on I here)1(1)1(2)23456789BEDDABDBDAII、 Fill in the blank (2points * 5)An swer table for II (Please write your an swers 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 travers

8、al algorithm for a normal tree、2、Here is a hash table, whose size is 18, hash ing function is H1(key)=key%17 (% here is the modulus operator), and which usesLin ear Prob ing strategy to cope with the collisi ons and in serts 26, 25, 72, 38, 8, 18, 59 into the hash table in turn、 The address of 59 is

9、、3、Given a key sequenee 2,5,3, please write its ascending orderedsequenee after being sorted using heap sort、 (Note 5=,just 5 is before in original sequenee) 、 Please distinguish 5and 、4、If a 2-dimensions matrix Amn is stored in an 1-D array withrow-major mapp ing, the n the address of eleme nt Aij

10、relative to A00 is5、If the in-order and pre-order series of the no des in a binary tree are 1,2,3,4,5 and 1,2'：3,4,5 respectively, the postorder seque nee shouldbe、III、(40 points)1、(8 poin ts) Suppose there is a stri ng abcadececdcdeeededthat comprises the characters a, b, c, d and e、 We may enc

11、ode the symbols using variable-length codes in order to make the length of string the shortest 、 Please draw the Huffma n tree used to en code the characters, calculate the weighted path length for the Huffman tree and write the code for each character(1) Draw the Huffman tree (3 poi nts)(2) Calcula

12、te the weighted path len gth for the Huffma n 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、(1) A

13、n example list for quick sort and the sorting procedure using quick sort、(4 poi nts)(4, 2,3) (2 poin ts)sorting procedureThe first pass: 3,2, ,4 (1point)The seco nd pass: ,2,3,4 (1po int)(2) An example list for select ion sort and the sorting procedure usingselect ion sort、(4 poin ts)(2,3,1) (1 poi

14、nts)sorting procedureThe first pass:1,3,2 (1point)The seco nd pass: 1,3,2 (1po int)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 (distribut ing and collect ing) of sorting using radix sort method、 not necessary t

15、o write queue front and rear pointer if queue is null、(1) The first pass (3 poi nts)p-331-13犷236- 268 一 13-33 713 S1st pa» of distributing accordi to the Lea$t digitfll331ilf6* 16 6_*236- if 6f71 笫-337 r7fl«268138 i8lTtpasi of collectingp331166236-*367->137- 337268138(2) The sec ond pas

16、s (3 poin ts)p331-*166->256->367-* 137357651582ad pass of distributing according to the middle digitf3T33iT236137T337T138t3恥"367t268i】62皿 pass of collectingp ->331-*236 ->137->337->138 "63672 闘(3) The third pass (2 points)p- 331- 236 f 137- 337 -*138 1- 36- 2683 pasi of d

17、istributing according tc tbe moit signifkut digifl137-*138166rl(I2H236->268 *-t2t3 -33 L ->337 ->367 r3J3rd pas& of collectingpT 13713$T“J236T25gf 33337367It is in ascending order*4、(6 poin ts)There are n 1 no des of degree 1,n2 no des of degree 2,nmno des of degree m in a tree of degre

18、e m,how many leaf no des there are in the tree? Please give formula and prove your conclusion、Answer:because every node except root has one branch linked, so totalno des are equal to total bran ches plus one, there are n bran ches in node of(2poi nts)degree nformula such as (2po ints)%斗iq斗卄!“-S i*iv

19、 +11= i r(2poi nts)5、(10 points) Show the result of inserting 63, 37, 48, 100, 54, 64, 27, 108, 99,42 into(a) an empty binary search tree(2 poin ts)(b) an initially empty A VL tree(4 points)(c) an in itially empty B-tree of order 3(4 poin ts)An swer:(1) binary search tree(2 points)(2)AVL (4 poi nts)

20、 B-tree (4poi nts)IV、(10 points) Please fill in the blanks in the program which reverses asingly 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、#defi ne list_i ni t_size100#defi ne n 10#defi ne lensizeof(struct no de)typedef struct node int num;

21、struct node *n ext; Ino de,*li nk;link llist;static int a=1,2,3,4,5,6,7,8,9,10;void creat(l ink *list)/create a singly linked list for key sequence stored in array a int i=0;lnode *p,*q;q=(struct no de*)malloc(le n);q_>n um=ai;*list=q;while (i< n-1) p=(struct no de*)malloc(le n);i=i+1;(1;q=p;p

22、_>n ext=O;void reverseList(l ink *h)/ reverse the singly lin ked list In ode *p,*q, *r;p=*h;r=0;while (p)q=p;(3) ;(4); r = q;(5);main ()In ode *l;creat(&l);reverseList (&I);An swer:(1) _ p->num=ail;(2) _ q_>next=p;(3) _ p=p_>next;(4) _ q->next =r;(5) 亠 V、(10 points)Please read

23、 the following code, write the functions of programs and write output of the program、#include<stdio、h>#include "malloc、h"#define n 6static char ch n='a','b','c','d','e','f;static intan n=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

24、,0,0,1, 0,0,1,1,1,0; typedef struct node/* 邻接表中的边结点 */struct node *next; EdgeNode; int adjvex;typedef struct vnode char vertex;/* 邻接表中的顶点结点 */EdgeNode *firstedge; VertexNoden;typedef structint datan; CirQueue; int front,rear;CirQueue *Q;int pathn,sum=0;int visitedn;VertexNode G;,建无向网的邻接表表示 */Gi 、 fi

25、rstedge=0; void createALGraph() /* 根据邻接矩阵 int i,j; EdgeNode *s;for(i=0; i<n; i+) Gi 、 vertex=chi;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;

26、 i+) s=Gi 、 firstedge;printf(" %c : ",Gi 、 vertex); while(s) printf(" %c",Gs->adjvex 、 vertex);s=s->next;printf("n");int ShortestPath(int u,int v) /* 求 u 与 v 之间经过的分支数最少的路径 */ int k,pren,spathn,count=0,found=0;EdgeNode * p;if(u=v) printf("errorn"); return

27、 0;Q=(CirQueue*)malloc(sizeof(CirQueue);Q->front=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&q