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

北 京 交 通 大 学 软 件 学 院

2012―2013学年第一学期期末考试试题

Data Structure and Algorithm Design(A)

Class: ____Student Number: _____Name: ________ Teacher________ No. Mark I II III IV V VI Total I. Single-Choice(20 points)

1. The height of a binary tree that contains 1023 elements is at most ( 1 ) and at least ( 2 ).

A． 1022 B．1023 C． 1024 D．9 E．10 F．11

2. If the sequence of pushing elements into a stack is a,b,c, which output sequence is impossible?（ ）．

A．abc B．bca C．cba D．cab

3.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-1 C. n-e D. not sure

4. When using the adjacency matrix A to represent a undirected graph with n nodes and e edges, the degree of the node vi can be computed by formula ( ).

A.

B.

/2 C. e /2 D.

5. 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

algorithm, the maximum times of comparisons is ( ). A. 25 B.10 C. 1 D.7

7. 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 following is the standard name for this algorithm? ( ) A. Inorder traversal B. Preorder traversal C. Postorder traversal D. Binary search

8.Which is not the property of a B-tree of order m? ( )

A. The root node has m subtree at most B. All leaf nodes are at the same level.

C. The keys in every node are ordered. D. All 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, ( ) buckets are needed to constructed.

A. 10 B. 50 C. 51 D. 1000

Answer table for Question I (write your answers of Question I here) 1(1) B 1(2) E 2 D 3 D 4 A 5 B 6 D 7 B 8 D 9 A

II. Fill in the blank (2points * 5)

Answer table for II (Please write your answers of II here) 1 preorder 2 11 2 2，3，⑤，5 3 i*n+j 4 5,4,3,2,1 1. The strategy of depth-first searching algorithm for a graph is similar to that of___ _ traversal algorithm for a normal tree. 2. Here is a hash table, whose size is 18, hashing function is

H1(key)=key (% 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 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 A[m][n] is stored in an 1-D array with row-major mapping, then the address of element A[i][j] relative to A[0][0] is ___ ____ 5. If the in-order and pre-order 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 __________.

III. (40 points)

1. (8 points) Suppose there is a string abcadececdcdeeeded that comprises the characters a, b, c, d and e. We may encode the symbols using variable-length codes in 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.

(1) Draw the Huffman tree (3 points)

a:2, b:1, c:4, d:5 , e: 6

(3 points)

(2) Calculate the weighted 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) 错一个扣一分，扣光为止

a 100 b 101 c 11 d 01 e 00 2. (8 points) Please respectively give two unsorted lists whose length are 4 to illustrate that quick sort and selection sort are unstable.

(1) An example list for quick sort and the sorting procedure using quick

sort. (4 points)

（4, 2, ②, 3）-------------------------- (2 points) sorting procedure

The first pass: 3,2, ②,4 -------------------------（1point） The second pass: ②,2,3,4 -----------------------（1point）

(2) An example list for selection sort and the sorting procedure using

selection sort. (4 points)

（2，②，3，1）-------------------------- (1 points) sorting procedure

The first 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 pointer if queue is null. (1) The first pass (3 points)

(2) The second pass (3 points)

(3) The third pass (2 points)

4.（6 points）There are n1 nodes of degree 1，n2 nodes of degree 2，…，nm nodes of degree m in a tree of degree m，how many leaf nodes there are in the tree? Please give formula and prove your conclusion.

Answer：because every node except root has one branch linked, so total nodes are equal to total branches plus one, there are n branches in node of degree n （2points） formula such as （2points）

（2points）

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 points） (b) an initially empty AVL tree（4 points）

(c) an initially empty B-tree of order 3（4 points） Answer：

(1) binary search tree（2 points） 63 100 37

108 27 64 48

99 54 42

（2）AVL （4 points）

(3) B-tree （4points）

IV. (10 points) Please 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 llist;

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=a[i]; *list=q; while (i

{ p=(struct node*)malloc(len); i=i+1; （1） ; （2） ; q=p; }

p->next=0; }

void reverseList(link *h) // reverse the singly linked list { lnode *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=a[i];____ (2) __ q->next=p;_______ (3) __ p=p->next;_________ (4) __ q->next =r;________ (5) _ _*h=q;_________

V.（10 points）Please read the following code, write the functions of programs and write

output of the program.

#include #include \#define n 6

static char ch[n]={'a','b','c','d','e','f'};

static int a[n][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,0,0,1, 0,0,1,1,1,0};

typedef struct node /*邻接表中的边结点*/

{ int adjvex; struct node *next; } EdgeNode;

typedef struct vnode /*邻接表中的顶点结点*/

{ char vertex; EdgeNode *firstedge; } VertexNode[n];

typedef struct

{ int front,rear; int data[n]; } CirQueue; CirQueue *Q;

int path[n],sum=0; int visited[n]; VertexNode G;

void createALGraph() /*根据邻接矩阵，建无向网的邻接表表示*/ {int i,j; EdgeNode *s;

for(i=0; i

{ G[i].vertex=ch[i]; G[i].firstedge=0; }

for(i=0; i

{ s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j; s->next=G[i].firstedge; G[i].firstedge=s; } } } }

void print()

{ int i; EdgeNode *s; for (i=0; i

printf(\ %c : \ while(s)

{ printf(\ %c\ s=s->next; }

printf(\ } }

int ShortestPath(int u,int v)/* 求u和v之间经过的分支数最少的路径*/ { int k,pre[n],spath[n],count=0,found=0; EdgeNode * p;

if(u==v) { printf(\ Q=(CirQueue*)malloc(sizeof(CirQueue)); Q->front=Q->rear=0;

for(k=0;kdata[Q->rear++]=u; while(!found && Q->front!=Q->rear) { k=Q->data[Q->front++]; p=G[k].firstedge; while(p && !found)

{ if(visited[p->adjvex]==0) { pre[p->adjvex]=k; if(p->adjvex==v) {found=1; break;} visited[p->adjvex]=1;

Q->data[Q->rear++]=p->adjvex;

} p=p->next; } }

if(found)

{ printf(\ \

spath[count++]=v; k=pre[v]; while(k!=u) {spath[count++]=k; k=pre[k];} spath[count]=u;

for(k=count;k>=0;k--) printf(\ \ printf(\ return 1; }

else{printf(\ return 0;} }

main() { int i,j;

createALGraph(); print();

for(i=0;i

Answer:

（1）function of createALGraph

Create linked adjacency list based on adjacency matrix

--------------------------------------- (2 points)

（2）function of the whole program

Find the shortest path which includes the minimum number of branches among all paths from u to v. ---------------------- (3 points)

（3）output of the program. ------------------------------- (1+4=5 points)

VI. (10 points) Please describe the children-sibling link of a tree in C Language. Write a function to calculate the depth of a normal tree. (10 points) Answer：

Typedef struct CSNode （2分）

{ char data;

struct CSNode *fch, *nsib; } CSNode, *CSTree;

int TreeDepth(CSTree T)

{ if(!T) return 0; （2分）

else { h1 = TreeDepth( T->fch ); （2分）

h2 = TreeDepth( T->nsib); （2分） if(h1+1> h2) return(h1+1)

else return(h2); （2分）

}

}

（1）function of createALGraph

Create linked adjacency list based on adjacency matrix

--------------------------------------- (2 points)

（2）function of the whole program

Find the shortest path which includes the minimum number of branches among all paths from u to v. ---------------------- (3 points)

（3）output of the program. ------------------------------- (1+4=5 points)

VI. (10 points) Please describe the children-sibling link of a tree in C Language. Write a function to calculate the depth of a normal tree. (10 points) Answer：

Typedef struct CSNode （2分）

{ char data;

struct CSNode *fch, *nsib; } CSNode, *CSTree;

int TreeDepth(CSTree T)

{ if(!T) return 0; （2分）

else { h1 = TreeDepth( T->fch ); （2分）

h2 = TreeDepth( T->nsib); （2分） if(h1+1> h2) return(h1+1)

else return(h2); （2分）

}

}

本文来源：https://www.bwwdw.com/article/1ao2.html