nexoncn.com

文档资料共享网 文档搜索专家

文档资料共享网 文档搜索专家

15th session of the preliminary round of the Olympic tournament national youth Informatics question

(Increase the group two hours to finish the Pascal language)

● Answers of all que

stions are asked to write in the answer sheet of paper, write papers on paper shall be null and void ●

I. choice questions (a total of 10 questions, each question 1.5 points, a total of 15 points. For each item, there is one and only one correct answer. )

1.On Turing machine which of the following statements is correct: A). Turing machine is the world's first electronic computer. B) due to the heavy use of tape, Turing machine runs very slowly. C) Turing machine is a theoretical calculation model. D) English Turing invented the Turing machine, to crack password for the German army in the second world war played an important role. 2.On BIOS 2, which of the following statements is correct: A).the BIOS is short for computer basic input/output system software. B).BIOS contains the keyboard, mouse, sound card, graphics, interfaces, and other commonly used input drivers. C).BIOS will generally be completed operating system vendors to develop. D).BIOS can provide copies of files, copy, delete, and file management features such as directory maintenance. 3, well-known ASCII encoding for the capital letter a 65 (decimal), the hex-ASCII encoding for the capital letter j: A) .48 B). 49 C).50 D). none of the above 4, 16-bit word length system environment, a 16-bit signed integer binary complement of 1,.11,111,111,110,11e,+15. Its corresponding decimal integer should be: A).19 B). -19 C). 18 D).-18 5, a contains n branching nodes (non-leaf nodes) non-empty full k-ary tree, k>=1, which is the number of leaf nodes:

A) .NK+1 B). NK-1 C). (k+1) n-1 D. (k-1) n+1 6. The expression a* (b+c)-d Postfix expression is: A) .abcd*+- B) .abc+*d- C) .abc*+d- D).-+*ABCD 7, optimal prefix codes, also known as Huffman coding. This combination of encoding is characterized by more frequent use of unique encoding of the element to the shorter, to make communication more efficient. The following coding prefix coding combination which set is not legitimate. A) .(00,01,10,11) B). (0,1,00,11) C). (0,10,110,111) D). (1,01,000,001) 8, and quickly sort average situation and worst situation Xia of algorithm time complex degrees respectively for: A). average situation o (nlog2n), worst situation o (N2). B). average situation o (n), worst situation o (N2). C) .average situation o (n), worst situation o (nlog2n). D). average situation o ( Log2n), worst case o (N2). 9, The left figure shows a weighted undirected graph, vertices V0 Prim algorithm for finding minimum spanning trees. Turn sequence of vertices added to the minimum spanning tree of the vertices collection: A). V0, V1, V2, V3, V5, V4 B) .V0, V1, V5, V4, V3, V3 C) .V1, V2, V3, V0, V5, V4, D). V1, V2, V3, V0, V4, V5 10, official website of the National Informatics Olympic participation in contests of informatics teachers provide students with relevant information and resources, National Informatics Olympic official website URL is: A). http://www.noi.com/ B). http://www.noi.org/ C) .http://www.noi.cn/ D). http://www.xinxixue.com/

II. indefinite multiple choice questions (10 items, Each question 1.5 points, a total of 15 points. Not less than 1 for each item, the number of correct answers. More or less not selected).

1.On CPU, which of the following is true: A).CPU-called the CPU (central processing unit). B).CPU can run directly to machine language. C).CPU by Intel Corporation invented the first. D).Under the same clock speed, 32-bit CPU 1 time times faster than a 16-bit CPU

to run. 2, on the following computer memory which is correct: A).random access memory (RAM) means that when a program is run, each memory location is assigned to a program of random and uncertain. B)..General personal computer can only deposit/access at the same time a specific memory module. C..Computer memory is strictly speaking, including main memory (memory), cache (cache) and register (register) consists of three sections. D).1MB usually refers to the memory size of 1024*1024 bytes of memory. 3, on which operating system the following are correct: A).multi-tasking operating system dedicated to multi-core or multiple CPU architecture computer systems management. B).Under the management of the operating system, a complete program to run in part can be stored in memory in the process. C).Time sharing system allows multiple users to share a host of computing power, to ensure the timely response of each user typically has a time slice round robin strategy. D).In order to facilitate application development at the top, the operating system is free open source. 4, on the computer network, following what is correct: A).there are many layer network protocol is mainly due to the implementation of new technologies need to be compatible with the old. B). Standard next-generation IPv6 Internet use IPv5 standard upgrades and additions. C).TCP/IP is the foundation of the Internet Protocol Suite, contains the TCP and IP communication network and transport layer protocols. D)..Each network hosts on the Internet typically need to use a unique IP address, or a fixed domain name to indicate its address must be registered. 5,On HTML which of the following is true: A).the full name of the HTML hypertext markup language, achieve unity of text, graphics, sound, and video encoding. B).Description of HTML pages containing not only the content of information, definition of Web pages will also contain formatting information. C).A hyperlink on a Web page only links to external network resources, links between the pages of this website realized by the label. D). Click on a hyperlink on a Web page are essentially implicit in the is the links, as a Uniform Resource Locator (URL) request network resources or services. 6, if the right adjacency matrix of the graph g 3 vertices with an array stored as {{0,1,1},{1,0,1},{0,1,0}} assumes a specific store vertices in the following order: V1,v2,v3 on the map, the following statement which is correct: A) the graph is a directed graph. B) this figure is strongly connected. C) all vertices of the graph into degrees and minus and equals 1 for all vertices. D) starting from the v1 by depth-first traversal of the vertex sequence after

sequence of vertices and breadth is the same. 7, with tail pointer (CList linked list pointers point to the end nodes) non-empty cycle of each node in a singly linked list to next field points to the next node. Assumes that there is already more than 2 nodes. Which of the following is true: A). If p points to a new node is inserted, insert an element at the head of the sequence of statements is: p^.next:=CList^.next; clist^.next:= p; B) If p points to a new node is inserted, inserts an element at the tail of the sequence of statements is: p^.next:=CList; clist^.next:= p; C) head statement that deletes a node in the sequence is: p:=CList^.next; clist^.next:= clist^.next^.next; dispose(p); D) at the end, delete a node sequence of statements is: p:= clist; clist:= clist ^.next; dispose(p); 8, list the address range 0-10, the hash function h (k) =K mod 11. Opening address by linear probing method of handling conflict, 26,25,72,38,8,18,59 and keyword sequence stored in the hash table, deposited in a Hashtable does not determine the order of these elements. Assumes that zhiqian bulk list for empty, is element 59 kept in bulk list in the of may address has: A). 5 B). 7 C). 9 D). 10 9, and sort algorithm is stability of mean is key code same of records sort before and after relative location not occurred change, following which sort algorithm is stability of: A). insert sort B). base sort C). merging sort D). bubbling sort 10, and in participate in NOI series race process in the, following which behavior is was strictly prohibited of: A).carry writing tool, watches and not has communications B).Gong Electronic dictionary can enter the stadium. C).By hand in the online test calculates the likely answer and direct output the answer in a program to obtain the score. By searching the Internet to solve problems. D).Submit program starts multiple processes in order to improve efficiency in the implementation of the program.

.III. problem solving (2 items every 5 min, total 10 points)

1. topological sorting is the all the vertices in a directed acyclic graph g into a linear sequence, makes any pair of vertices u and v in the graph, if <u,v>the whereabouts of e (G), the u in linear sequences appear before v, such a linear sequence of topological sequence. As a directed acyclic graph below, topological sort, on its vertices do all possible topologies sequence number is _________.

2

5 6

8

1

4 7 9

3

2. a national coin denominations 1, 7, 72, and 73 for a total of four kinds, if you want to pay with cash 10,015 worth of goods, assuming an infinite number of coins and the seller and allow the change, then the transaction process requires at least _________ coins in circulation.

IV. reading procedures write results (all 4 questions, each question 8, a total of 32 points)

1． var a, b: integer; function work(a, b: integer): integer; begin if a mod b <> 0 then work := work(b, a mod b) else work := b; end; begin read(a, b); writeln(work(a, b)); end. input: 123 output: _________ 2． var

a, b: array[0..3] of integer; i, j, tmp: integer; begin for i := 0 to 3 do read(b[i]); for i := 0 to 3 do begin a[i] := 0; for j := 0 to i do begin inc(a[i], b[j]); inc(b[a[i] mod 4], a[j]); end; end; tmp := 1; for i := 0 to 3 do begin a[i] := a[i] mod 10; b[i] := b[i] mod 10; tmp := tmp * (a[i] + b[i]); end; writeln(tmp); end. Input: 2 3 5 7 output: _______________ 3． const y = 2009; maxn = 50;

var

n, i, j, s: longint; c: array[0..maxn, 0..maxn] of longint;

begin s := 0; read(n); c[0, 0] := 1; for i := 1 to n do begin c[i, 0] := 1; for j := 1 to i - 1 do c[i, j] := c[i-1, j-1] + c[i-1, j]; c[i, i] := 1; end; for i := 0 to n do s := (s + c[n, i]) mod y; write(s); end.

input：17 output：

4． var n, m, i, j, k, p: integer; a, b: array[0..100] of integer; begin read(n, m); a[0] := n; i := 0; p := 0; k := 0; repeat for j := 0 to i - 1 do if a[i] = a[j] then begin p := 1; k := j; break; end; if p <> 0 then break; b[i] := a[i] div m; a[i+1] := (a[i] mod m) * 10;

inc(i); until a[i] = 0; write(b[0], '.'); for j := 1 to k - 1 do write(b[j]); if p <> 0 then write('('); for j := k to i - 1 do write(b[j]); if p <> 0 then write(')'); writeln; end.

Input: 5 output: _________

V. improvement program (the first 5, each 2 min 6 empty after, every 3 minutes, a total of 28 points)

1. (Maximum continuous) given a series (not more than 100 the number of elements), the series element is a negative integer, positive integer, 0. You can find a series in a row in the series, making the child contains all of the elements in the sequence, and the maximum, and a maximum under the premise of the series contain a maximum number of elements and output the maximum and as well as the number of child elements in the series in a row. When such as series,

as 4,-5,3,2,4, output and 9; Series 1 2 0 7 8 o'clock, output 16 and 7. var a: array[1..100] of integer; n, i, ans, len, tmp, beg: integer;

begin read(n); for i := 1 to n do read(a[i]); tmp := 0; ans := 0; len := 0; beg := 0 ;

for i := 1 to n do begin if tmp + a[i] > ans then begin ans := tmp + a[i]; len := i - beg; end else if ( tmp+a[i]=ans ) and (i - beg > len) then

len := i - beg;

if tmp + a[i] begin beg := i tmp := 0; end else

<0

then

;

tmp：=ans+tmp____ end; writeln(ans, ' ', len); end.

;

2.

(looking

for

arithmetic

progressions)

number

of

arithmetic progressions of length equal (each number in the sequence is 0~59), set length is l, to disrupt the order of summation of all numbers together. Now give you those upset number, ask the original, l maximum for how much? read a number n (1<=n<=60), and then read into n number, representative after the upset. Output maximum possible length l arithmetic progressions. var hash: array[0..60] of integer; n, x, ans, maxnum, i: integer;

function work(now: integer): boolean; var ok: boolean;

first, second, delta, i: integer; begin while (( inc(now); if now > maxnum then begin work := true; exit; end; first := now; for second := first to maxnum do if hash[second] > 0 then begin delta := ② ; ③ > maxnum then ① ) and (hash[now]=0)) do

if first + delta * break; if delta = 0 then ok := ( else begin ok := true; ④

)

for i := 0 to ans - 1 do

ok := end; if ok then begin

⑤

and (hash[first+delta*i]>0);

for i := 0 to ans - 1 do dec(hash[first+delta*i]); if work(first) then begin work := true; exit; end; for i := 0 to ans - 1 do inc(hash[first+delta*i]); end; end; work := false; end;

begin fillchar(hash, sizeof(hash), 0); read(n); maxnum := 0;

for i := 1 to n do begin read(x); inc(hash[x]); if x > maxnum then maxnum := x; end; for ans := n downto 1 do if (n mod ans = 0) and begin writeln(ans); break; end; end. ⑥ then

更多相关文档:

更多相关标签:

noip提高组初赛试题 | noip提高组初赛试题 c | noip2015提高组初赛 | noip2016提高组初赛 | noip2016初赛试题 | noip2012提高组初赛 | noip初赛试题 | noip2013提高组初赛 | 文档资料共享网 nexoncn.com
copyright ©right 2010-2020。

文档资料共享网内容来自网络，如有侵犯请联系客服。email:zhit325@126.com