Today from 2:30pm - 4:30pm is the preliminary round of the Informatics Olympiad.
Because I'm waiting for the C language paper to come out, there is nothing to do now, so I'll take the pascal language has come out of the multiple-choice questions and problem solving part, and analyze it, because the C language is also the same topic. If you are interested, you can take a look at it, your own answer, welcome to explore.
The multiple choice and problem solving questions for the popularization and improvement groups.
The 15th National Junior Informatics Olympiad League Preliminary Competition Questions
(Popular Group Pascal Language Two hours to complete)
●● All the answers to the questions are required to be written on the answer sheet, and are not valid if they are written on the test sheet ●●
I. Multiple Choice Questions (***20 questions, 1.5 points each, *** counts for 30 points. Each question has one and only one correct answer.)
1. Which of the following statements about the Turing machine is true:
A) The Turing machine was the world's earliest electronic computer
B) Due to the extensive use of magnetic tape operation, the Turing machine ran slowly.
C) The Turing machine was invented by the Englishman Turing and played an important role in breaking German codes in World War II.
D) The Turing machine is only a theoretical model of computation.
Analysis Choice D
A The earliest computer was the ENIAC B The Turing machine was a model of a computer that did not have the speed to run, let alone operate on tape
C The Turing machine was a theory developed by the Englishman Alan Turing,
Alan Turing himself played an important role in breaking the German code system in World War II, not the Turing machine.
2. Which of the following statements is true about computer memory:
A) Random memory (RAM) means that when a program is run, the memory location specifically allocated to the program is random and indeterminate each time.
B) 1MB of memory usually means 1024*1024 bytes in size.
C) Computer memory technically consists of three parts: main memory, cache, and registers.
D) Generally the data in memory can be retained for more than 2 hours even in case of power failure.
Choose B 1MB=1024KB=1024*1024B
In A, RAM is not randomly located, but is accessible at any time. The term "random access" means that when a message in memory is read or written, the time it takes is independent of the location of that message.
The physical implementation of the cache and registers in C is integrated into the CPU, and they do not belong to any of the five main parts of the von Neumann system.
D in 2 seconds can not be retained Immediately lost
3. Which of the following statements about BIOS is correct:
A) BIOS is an acronym for Basic Input Output System Software for computers.
B) BIOS contains drivers for commonly used input and output devices such as keyboards, mice, sound cards, graphics cards, and printers.
C) BIOS is usually developed by the operating system vendor.
D) BIOS can provide various file management functions such as file copy, duplication, deletion, and directory maintenance.
Analyze choice A Actually bios=Basic Input Output System. but there is a controversy about whether it is software or not!
In B, the BIOS only stores some basic information about system startup, the drivers for these devices are not stored.
BIOS in C is usually produced by a separate chip manufacturer, the most famous are all three in Taiwan.
In D, the firmware BIOS simply these functions.
4. The following statement is true about CPUs:
A) CPUs are known as central processing units (or CPUs).
B) CPUs can run assembly language directly.
C) A 32-bit CPU runs twice as fast as a 16-bit CPU at the same main frequency.
D) CPUs were first invented by Intel.
Analysis Choice A CPU=Central Processing Unit
In item B, CPUs can only execute machine instructions, which is binary code
In item C, the number of bits can only indicate the length of the word processed, and the hardware instructions of the system in which it is located are different, so it is difficult to say who is faster
In item D, Intel was the first to invented the microprocessor, and the CPU is realized by the electronic tube, transistor before it.
5. Which of the following statements is true about ASCII:
A) ASCII is the unique code for all keys on a keyboard.
B) An ASCII code can be stored using one byte of memory space.
C) The latest extension of the ASCII encoding scheme includes encodings for Chinese characters and other European languages.
D) ASCII was developed and popularized by the British.
Analysis Choice B The ASCII code is stored in one byte, eight-bit binary 0 to 127 encoding.
Item A, there is no correspondence with the keyboard
Item C, the extended ASCII code uses two bytes, and the Chinese character code is not the content of the extended ASCII.
Item D, American Standard Code for Information Interchange, U.S.
6, the following software is not a computer operating system:
A) Windows B) Linux C) OS/2 D) WPS
Analysis of the choice of D WPS=Word Processing System (Kingsoft's word processing system)
B is the open source Linux system C is Apple's system
7. Which of the following statements about the Internet is true:
A) The IPv6 standard used in the new generation of the Internet is an upgrade and supplement to the IPv5 standard.
B) Incoming hosts on the Internet no longer need an IP address if they have a domain name.
C) The base protocol of the Internet is the TCP/IP protocol.
D) All downloadable software and data resources on the Internet are legally available for free.
Analysis Choice C The protocols that underlie the primary Internet are TCP/IP, TCP is the file transfer protocol at the transport layer, and IP is the inter-network protocol at the network layer.
IPv6 in A is an upgrade of IPv4
IP is required in B. Domain names are for good memory
Piracy is illegal in D.
8. Which of the following statements about the HTML language is correct:
A) HTML achieves a uniform encoding of text, graphics, sound and even video information.
B) HTML is known as Hypertext Markup Language.
C) Flash animations, which are widely used online, are written in HTML.
D) HTML is also a high-level programming language.
Analysis Choice B HTML (HyperText Mark-up Language), or HyperText Mark-up Language, is the main language that makes up web documents.
A Text, graphics, sound, and video all have their own coding and are not standardized.
C in Flash is made by specialized software Adobe Flash software.
D is a markup language, which can be said to be similar to scripting, not a high-level programming language.
9. Which of the following statements is true about programming languages:
A) A program with comments will generally run slower than the same program without comments.
B) Programs developed in high-level languages cannot be used on low-level hardware systems (e.g., automated machine tools) or low-end cell phones.
C) High-level languages are easier to port across platforms than low-level languages.
D) None of the above statements are true.
Analysis Choice C This option has appeared in previous questions. Characteristics of High-Level Languages
A Comments are ignored during compilation and do not affect program operation
B High-Level Languages can be used with the underlying hardware, and after compilation, they generate object code that can be executed on the hardware system
10. It is known that the ASCII code for the uppercase A is 65 (decimal), then the decimal ASCII code for the uppercase letter J is:
A) 71 B) 72 C) 73 D) None of the above
Analysis Choice D 64+9=74
11, The octal number corresponding to the decimal decimal 125.125 is
A) 100.1 B) 175.175 C) 175.1 D) 100.175
Analysis Choice C
The integer part is divided by 8 to take the remainder, and the result is written in reverse order The decimal part is multiplied by 8 to take the integer, and the result is written in positive order.
12. There are six elements FEDCBA sequentially fed into a stack from left to right, and some elements are popped off the stack during the feed. Ask which of the following could not be a legal out-of-stack sequence?
A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF
Analysis Choice C
Note that the order of entry into the stack is F to A
When CD is out of the stack, the top of the stack is E, and F cannot come out of the stack, so C is not legal.
13. The suffix expression of expression a*(b+c)-d is
A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd
Analyze Choice B
The main question is about traversal of the tree, and it is important to understand the prefix, mid-suffix and suffix expressions.
Construct a binary tree with operands as leaf nodes and operators as non-leaf nodes. Traversing in middle order gives you the midfix expression.
14, A non-empty binary tree containing n branch nodes (non-leaf nodes) has at most the following number of leaf nodes:
A) 2n + 1 B) 2n - 1 C) n - 1 D) n + 1
Analyze Choice D
Cauchy's property of a binary tree: N0 = N2 + 1 i.e., one more leaf node than the number of binary nodes.
15. The worst case algorithmic complexity of quick sort is:
A) O (log2n) B) O (n) C) O (nlog2n) D) O (n2)
Analyze the choice of D Worst case time complexity, each time the selection is made with the number that is closest to the edge.
16. Another sequential table consisting of 4000 integers is used to locate an element using binary lookup, assuming that the elements of the table have been arranged in ascending order. Then it takes at most a few comparisons to determine if the element sought exists:
A) 11 times B) 12 times C) 13 times D) 14 times
Analysis Choice B
2^11-1=2047 2^12-1=4095 2047<4000<4095 Therefore the height of the tree is 12
17, Sorting algorithm is stable means that the relative positions of records with the same keycode before and after sorting do not change, which of the following sorting algorithms is unstable:
A) Bubble Sort B) Insertion Sort C) Merge Sort D) Rapid Sort
Analysis Choice D
Rapid Sort causes the data to swap left and right positions
Other sorts can be programmed with care of the boundary conditions. Stability can be achieved by paying attention to boundary conditions.
18. A directed graph of n vertices is known. If the graph is strongly connected (paths exist from all vertices to other vertices), what is the minimum number of directed edges in the graph?
A) n B) n + 1 C) n - 1 D) n* (n - 1)
Analysis Choice A
Forms a directed circle (ring), with all nodes on top of it.
19. The official website of the National Olympiad in Informatics provides relevant information and resources for teachers and students involved in informatics competitions, the URL of the official website of the National Olympiad in Informatics is:
A) / D) /
D) /
Analyze Choice C Official website
II. Indeterminate Choice Questions (***10 questions of 1.5 marks each, *** counting for 15 marks, with not less than 1 correct answer for each question. no marks will be awarded for multiple or lesser choices).
1, about the CPU which of the following statements are correct:
A) CPU is known as the central processing unit (or central processing unit).
B) CPUs can run machine language directly.
C) The CPU was first invented by Intel.
D) A 32-bit CPU runs twice as fast as a 16-bit CPU at the same main frequency.
Analysis of choice AB
C, Intel first invented the microprocessor, and the CPU before the implementation of it by the electronic tube, transistor D, the number of bits can only indicate the word length of processing, where the system hardware instructions are different, the speed is difficult to say who is faster
2, about the computer memory which of the following statements are correct:
A ) Random memory (RAM) means that when the program is running, each time the memory location specifically allocated to the program is random and indeterminate.
B) A typical personal computer can only store/fetch one specific memory cell at a time.
C) Computer memory technically consists of three parts: main memory, cache, and registers.
D) 1MB of memory is usually 1024*1024 bytes in size.
Analysis choice BD is generally a unit of bytes operated serially. 1MB=1024KB=1024*1024B
RAM in A is not randomly located, but is accessed at any time, and the term "random access" refers to the fact that when a message in memory is read or written, the time it takes to do so is different from the time it takes for that message to be read or written. This is called "random access", which means that when a message is read or written in memory, the time it takes to do so is independent of where the message is located.
The physical implementation of the cache and registers in C is integrated into the CPU, and they do not belong to any of the five main parts of the von Neumann system.
3. Which of the following statements about operating systems is true:
A. Multitasking operating systems are dedicated to the management of computer systems with multiple cores or multiple CPU architectures.
B. Under the management of an operating system, a complete program can be partially stored in memory during operation.
C. A time-sharing system allows multiple users to *** enjoy the computing power of a single host computer, and a time-slice rotation scheduling strategy is often used to ensure that each user receives a timely response.
D. Operating systems are free and open source in order to facilitate the development of upper-level applications.
Analyze Choice BC
A Multitasking systems can be single CPU constructs, and ordinary PCs are multitasking.
D Operating systems are not all free and open source
4. Which of the following statements are true about computer networks:
A) The main reason why network protocols have many layers is that new technologies need to be compatible with older implementations of past solutions.
B) The IPv6 standard used in the next generation of the Internet is an upgrade and supplement to the IPv5 standard.
C) TCP/IP is the basic protocol cluster of the Internet and contains network and transport layer communication protocols such as TCP and IP.
D) Each incoming host on the Internet is usually required to use a unique IP address, or else it must register a fixed domain name to identify its address.
Analyze Choice C
A Network protocols are layered not for compatibility, but according to the network layering model.
B The new IPv6 is an upgrade from IPv4.
D Even if you register a domain name, you still have to have an IP address.
5. Which of the following statements about HTML is true:
A) HTML, known as HyperText Markup Language, realizes the unified encoding of text, graphics, sound, and even video information.
B)HTML contains not only a description of the content of a Web page, but also a definition of the format of the page.
C)Hyperlinks on web pages can only point to external web resources, and links between pages on this site are realized by setting tags.
D) Clicking on a hyperlink on a Web page is essentially requesting a Web resource or Web service by following the Uniform Resource Locator (URL) implied by the link.
Analysis Choice BD
A None of them are uniformly encoded
C Hyperlinks can also be used on the pages of this Web site
6. If the adjacency matrix of an unweighted graph G of 3 vertices is stored in an array as {{0, 1, 1}{1, 0, 1}{0, 1, 0}}, assuming that the vertices are, in order, in the concrete storage: v1, v2, v3 With respect to this graph. Which of the following statements are true:
A) The graph is a directed graph.
B) The graph is strongly connected.
C) The sum of the in-degrees of all vertices minus the sum of the out-degrees of all vertices of the graph is equal to 1.
D) The sequence of vertices traversed by a depth-first traversal starting from v1 is the same as the breadth-first sequence of vertices.
Analyzing the choice ABD
You can draw this directed graph, the matrix is stored asymmetric, so it is a directed graph.
C The sum of the in-degrees is equal to the box of out-degrees.
7. Each node in a non-empty circular singly linked table with a tail pointer (the chain table pointer clist points to the tail node) points to the next node with a pointer to the next field. Assume that there are already more than 2 nodes in it. Which of the following statements are true:
A) If p points to a new node to be inserted, the sequence of statements to insert an element at the head is:
p^.next:=clist^.next;clist^.next:=p;
B) If p points to a new node to be inserted, the sequence of statements to insert an element at the tail is The sequence is:
p^.next:=clist;clist^.next:=p;
C) The sequence of statements to delete a node at the head is:
p:=clist^.next;clist^.next:=clist^.next^.next;dispose(p);
D) The sequence of statements to delete a node at the end is:
p:=clist;clist:=clist^.next;dispose(p);
Analyzing the choice AC
B should be p^.next:=clist^.next;clist^.next:=p;.
D in order to loop to find the last element of the tail pointer in order to delete
8, hash table address interval is 0-10, hash function is H(K) = K mod 11. open address method of linear probing method to deal with the conflict, and will be the keyword sequence of 26, 25, 72, 38, 8, 18, 59 is stored into the hash table, the elements are deposited into the hash table of the The order of these elements into the hash table is not determined. Assuming that the hash table was previously empty, the possible addresses of the elements 59 stored in the hash table are:
A) 5 B) 7 C) 9 D) 10
Analyzing the choice of ABCD Hash Functions for Conflict Avoidance
Calculate the hash value of each of the 26 25 72 38 8 18 59
5 4 6 5 8 7 4
So that it is possible that 5's Order: 25, 59 ......
Order of 7: 25, 26, 38, 59 ......
Order of 9: 25, 26, 38, 18, 59... ...
Order of 10: ......59
The above order is not unique.
9, sorting algorithms are stable means that the relative position of the records before and after the sorting of the same key code does not change, which of the following sorting algorithms are stable:
A) Insertion Sort B) Base Sort C) Subtractive Merge Sort D) Bubbling Sort
Analyze the choice of ABCD
In the programming of the implementation, as long as the boundaries of the control are good to reach the stable sorting.
10. Which of the following behaviors are strictly prohibited during participation in the NOI series of competitions:
A) Bringing writing instruments, watches, and electronic dictionaries that do not have a communication function into the arena.
B) Obtaining marks by manually calculating the possible answers in an online test and outputting the answers directly in the program.
C) Obtaining solutions by searching the Internet.
D) Starting multiple processes in a submitted program to increase the efficiency of its execution.
Analysis Choice BCD
All of them are considered disciplinary violations. a is sometimes OK. The test here is NOI, not NOIP.
III. Problem Solving (***2 questions, 5 points per blank, *** counts for 10 points)
1. Topological ordering is the process of arranging all the vertices in a directed acyclic graph G into a linear sequence such that if any pair of vertices u and v in the graph, if <u, v> ∈ E(G), then u occurs before v in the linear sequence, and such a linear sequence becomes a topological sequence. The following directed acyclic graph with a topological ordering of its vertices gives the number of all possible topological sequences as ______.
Analysis 432
Just use permutations and combinations to determine the order of 12346, then insert 7 into the interior to have two positions to choose from, and then 6 positions to choose from when you insert 5. Finally, when you put 89, consider two cases: 89 together, with 8 positions to choose; 89 not together, with 8 positions to choose 2.
C(2,1) × C(6,1) × [C(8,1) + C(8,2)] = 2 × 6 × (8 + 28) = 432
2, a certain country's coins have a denomination of 1, 7, 7 ^ 2, 7 ^ 3 * * * * counting the four kinds of coins, if you want to use cash to pay for the goods of 10015 yuan, assuming that the buyer and seller of the various types of money in infinite number and allow change, then At least ______ coins need to be in circulation during the transaction.
Analysis 35
10015 is reduced to a decimal number of 41125, which is normally 4 x 7 + 1 = 29 sheets of 7^3 denomination, 1 sheet of 7^2 denomination, 2 sheets of 7 denomination, and 5 sheets of 1 denomination.
Because it can be infinite and in change, and requires a minimum number in circulation. This takes the number a, which is greater than or equal to 4 on the 7-digit scale, and replaces it with a zeroed 7-a, which minimizes it.
Here 29, 1, 2, 5 in only 5 is greater than 4, so use a large amount, and 7-5 to find the zero method of calculation. This gives a total of 29+1+2+(1+7-5)=35 sheets.
Because it is doing C, so read the program and perfect the part is not analyzed. Oh~~