关键词不能为空

当前您在: 主页 > 英语 >

数据结构例题解析(1)

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-01-25 09:10
tags:

-

2021年1月25日发(作者:恶实)

I Single Choice(10 points)
1. (

a

)For the following program fragment the running time(Big-Oh) is










.
i = 0;
s = 0;
while(s <( 5*n*n + 2))
{



i++;









s = s + i;
}
a. O(n)






b. O(n
2
)








c. O(n
1/2
)






d. O(n
3
)

2. (

c

)Which is non-linear data structure_____.
a. queue















c. tree








d. sequence list

3.(

b

)The worst-time for removing an element from a sequence list

(Big-Oh) is








.


a. O(1)






b. O(n)








c. O(n
2
)






d. O(n
3
)

4.(

d
)In
a
circular
queue
we
can
distinguish(


)
empty
queues
from
full
queues
by










.
a. using a gap in the array

b. incrementing queue positions by 2 instead of 1

g a count of the number of elements

d. a and c

5.

(

b

)A recursive function can cause an infinite sequence of function calls if








.
a.

the problem size is halved at each step

b.

the termination condition is missing

c.

no useful incremental computation is done in each step

d.

the problem size is positive



6

(

c


)The full binary tree with height 4 has













nodes.



a. 15












b. 16











c.31













d.32

7. (

b


)Searching in an unsorted list can be made faster by using










.
a.

binary search

b.

a sentinel
(哨兵)

at the end of the list

c.

linked list to store the elements

d.

a and c

8.



b

Suppose there are 3 edges in an undirected graph G,

If we represent graph G with a
adjacency matrix, How many “1”s are there in the matrix?

a. 3












b. 6











c. 1















d. 9
9.
(

d
)
Construct
a
Huffman
tree
by
four
leaf
whose
weights
are
9,
2,
5,
7
respectively.
The
weighted path length

is___________.
a. 29












b. 37










c. 46













d.44
10. Consider the following weighted graph.



Consider Dijkstra’s algorithm on this graph t
o find the shortest paths with
s
as a starting vertex.
Which are the first four vertices extracted from the priority queue by the algorithm (listed in the
order they are extracted) ?




a.
s
,
y
,
t
,
x







b.
s
,
y
,
x
,
z









c.
s
,
t
,
y
,
x










d.
s
,
y
,
x
,
t


Fig. 1
11. Here is an array of ten integers:
5 3 8 9 1 7 0 2 6 4
Suppose we partition this array using quicksort's partition function and using 5 for the pivot.
Which shows the array after partition finishes:
a. 5 3 4 2 1 0 7 9 6 8
b. 0 3 4 2 1 5 7 9 6 8
c. 3 1 0 2 4 5 8 9 6 7
d. 3 1 0 2 4 5 8 9 7 6
e. None of the above


II Fill in Blank (10 points)
1.

For the following program fragment the running time(Big-Oh) is



O(n2)



.




for ( int i = 0; i < n; i++ )








for ( int j = 0; j < =i; j++)

















s;













//s
为某种基本操作

2.
We
store
a

4
symmetric
matrix
A
into
an
array
B
with
row
major
order,
Store
the
lower
triangle only. the index of element a[2][3] in B is








6











.
3


We can use 3 vector type to store value and

















of non-zero elements in a
sparse matrix.
4. A______stack______ is a list where removal and addition occur at the same end . Frequently
known a LIFO (Last-In-First-Out) structure.

5.

T( n ) = 2T( n/2 )+ cn, T(n)=O(logn)

T(n) = T( n-1)+cn,



T( n ) = O(_____n_____)
6.
There
is
a
binary
tree
whose
elements
are
characters.
Preorder
list
of
the
binary
tree
is
“ABECDFGHIJ”
and
inorder
list
of
the
binary
tree
is
“EBCDAFHIGJ”.
Postorder
traversal
sequence of the binary tree is



EDCBIHJGFA




.


7

There are







(n+1)/2









leaf nodes in a full binary tree with n nodes.
8

When
the
input
has
been
sorted
,the
running
time
of
insertion
sort(Big-Oh)
is






O(n)






.
9

We sort the seq uence

43

02

80

48< br>,
26

57

15

73
21

24

66

with shell sort for
increment 3, the result is ______


(15 02 21 24 26 57 43 66 80 48 73)










_ .
10

In
a
circular
queue,

front”
and

rear”

are
the
front
pointer
and
rear
pointer
respectively.

Queue size is “maxsize”. When insert an element in the queue, rear
= __ (rear+1)%maxsize__




11. A _________________B

_____________________ is an example of a search tree which is
multiway (allows more than two children).
12. A tree in which every node is no smaller than its children is termed _____
大顶堆
______.

III

Application of Algorithms


35 points



G shown in Fig 2 is a directed graph, please describe G with adjacency matrix and write
the orders of breadth first traversal and depth first traversal.

B
C
A
D
E















Fig.2


A B C D E

A 0 1 0 1 0
B 0 0 1 1 0
C 0 0 0 0 1
D 0 0 0 0 1
E 0 0 0 0 0
Dft:ABCED
Bft:ABDCE
2

The sequence of input keys is shown below:









19

1

23

14
55

20

84

27

68
11

10

17
A fixed table size of 19 and a hash function H(key)=key%13

with linear probing(
线性探测
), fill
the table below and compute the average length of successful search.




3. Show the results of inserting 53,17,78,09,45,65,87 each , one at a time, in a initially empty max
heap
(大根堆)







4. write the sequence of preorder,postorder traversals and add inorder threads in the tree.



A
B
D
E
C
F














Fig. 3
5. Build a Huffman tree and

determine Huffman code when the probability distribution(
概率分

) over the 8 alphabets ( c1, c2, c3, c4, c5, c6, c7, c8 ) is (0.05, 0.25, 0.03, 0.06, 0.10, 0.11, 0.36,
0.04

6. Graph G shown in Fig 4 is a directed graph, please describe G with adjacency list and write
topological ordering.
















Fig. 4


IV
Fill in blank of algorithms.


15


1


Here is single source shortest path algorithm Dijkstra. Fill in blank of the algorithm.
class Graph {

private:




float Edge[NumVertices][NumVertices];





float dist[NumVertices];
//
最短路径长度数组






int path[NumVertices];

//
最短路径数组






int S[NumVertices];
public:




void ShortestPath ( int,

int );




int choose ( int );
};

void Graph :: ShortestPath ( int n,

int v ){
//
在具有

n
个顶点的带权有向图中
,
各边上权值由
Edge[i][j]
给出。建立一个数组
:
dist[j],
0
?
j < n, //
保存从顶点

v
到顶点

j
的最短路径长度
,
同时用数组
path[j], 0
?
j < n,
存放求到

//
最短路径顶点集





//
图的类定义






的最短路径。




for ( int i = 0; i < n; i++) {








S[i] = 0;

















dist[i] = Edge[v][i];




//dist
数组初始化









if ( i != v && dist[i] < MAXNUM) path[i] = v;








else path[i] = -1;



}
S[v] = 1;


dist[v] = 0;
//
顶点
v
加入顶点集合





//
选择当前不在集合
S
中具有最短路径的顶点
u


for ( i = 0; i <




n





; i++ ) {





float min = MAXNUM;

int u = v;





for ( int j = 0; j < n; j++ )






if ( !S[j] &&






dist[j] < min










)










{ u = j;


min = dist[j]; }








S[u] = 1;
















//
将顶点
u
加入集合
S








for ( int w = 0; w < n; w++ )



//
修改










if ( !S[w] && Edge[u][w] < MAXNUM &&

dis[w] > (min+Edge[u][w])

) {







dist[w] =






min + Edge[u][w]







;








path[w] = u;



}



}








//path
数组初始化


}

3

Consider
the
following
function
to
balance
symbols
stored
in
string
exp
that
includes
parentheses
(圆括号)

and Fill in blank.
#include
Using namespace std;
int matching(string &exp) {
//exp is a pointer to a string to check


int state = 1,i=0;



char e;




stack s;


while ( i<() && state )






switch (exp[i]) {









case '(':






















(exp[i])














;



















i++;















break;

case ')':













if (


!() && ()==

(
































) {













();

i++; }

































else















state = 0;










//an error occurs














break;








default:












i++; break;



}




//end of while



if (

state && ()




























)

return 1;






else

return 0;


V Programming


30



1. Write efficient functions (and give their Big-Oh running times)that take a pointer to a binary
tree root T and compute:


The number of leaves of T
typedef struct BiTNode


{ TElemType data;





struct BiTNode

*lchild,*rchild;




} BiTNode , *BiTree;



2.
Write
a
method
called
maximumDegree

of
an
undirectedh
graph

that
returns
the
maximum
degree
of
any
vertex
in
the
graph.
The
graph
is
stored
with
adjacency
matrix.
Write
the
definition
of
the
graph.
implement
the
function.
Analyze
space
complexity and time complexity of your function.


3.
Write
a
function
with
linked
list
that
inserts
a
number
into
a
sorted
linked
list.
Firstly, you should write a function creates a list that like this:
L={3,5,8,12,32,48}
and then insert 25 into this list.






答案解析
0-0
,仅供参考,若有不同意 见请联系
QQ767954870

_



选择题:
1-5:ACBDB 6-11:CBBDDE
1
、知识点:复杂度分析,必考




思路:复 杂度主要计算算法的步数,可以看出,当前循环执行的步数与
i
的值是相等的,所
以可 列
1+2+..+i=(5*n*n+2)
,复杂度的计算忽略常数
, (1+i)*i/2=(5*n*n+2), i ~ O(n)
2
、知识点:
non- linear

linear
的区别

3
、知识点:复杂度分析
+
线性序列

-


-


-


-


-


-


-


-



本文更新与2021-01-25 09:10,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565033.html

数据结构例题解析(1)的相关文章