计算机应用基础数据结构部分试题及答案(2)

计算机应用基础数据结构部分试题及答案（Computer application

basic data structure part questions and answers） Some things, knowing that is wrong, but also to adhere to, because not reconciled; some people, knowing that love is also to give up, because there is no end; sometimes, knowing that there is no road, but still forward, because used to.

Computer application basic data structure part questions and answers

1. choice questions:

1. the complexity of the time complexity of the following program segments is (

For (i=1; i<=n; i++)

For (j=1; j<=i; j++)

For (k=1; k<=j; k++) X=x+1;

A., O (1), B.O (n), C., O (N2), D.O (N3)

2., in the data structure, the data structure can be logically divided into ()

A. dynamic structure and static structure, B. compact structure and non compact structure

C. linear structure and nonlinear structure, D. internal structure and external structure

3. data structures include four basic types: set, linear, tree, and graph structures.

A. storage structure, B. logic structure, C. basic operation, D. algorithm description

4. data () include search, insert, delete, update and sort, etc..

A. storage structure, B. logic structure, C. basic operation, D. algorithm description

5. the storage structure of data includes four basic types of sequence, link, hash, and ().

A. linear B. array, C. set, D. index

6., the following () is the best time complexity, i.e., the shortest execution time.

A., O (n), B.O (logn), C., O (nlogn), D.O (N2)

7. the complexity of the time complexity of the following program segment is ()

For (int i=0; i

For (int j=0; j

A[i][j]=i*j;

A., O (M2), B.O (N2), C., O (m*n), D.O (m+n)

8. () is not the basic feature of the algorithm.

A. correctness, B. length is limited, C. within the specified time to complete D. certainty

9. the input sequence of a stack is 1, 2, 3, 4, 5, and the following sequence is the output sequence of the stack.

A. 31245, B.41325, C.23415, D.14253

10., in the N node with two nodes, the number of chains is empty, and the number of fields is ().

A., n-1, B., 2N-1, C., n+1, D., 2n+1

1-5, D, C, B, C, D,, B, C, C, C, C

11. known complete two fork tree has 30 nodes, then the whole two fork tree has () 1 degrees of node.

A. 0, B. 1, C. 2, D. are not sure

12. depth two K full tree, at least () node.

A., 2k-1, B., 2k-2, C., 2k-1, D., 2k-2

13. depth two K full tree, at most () nodes.

A., 2k-1, B., 2k-2, C., 2k-1, D., 2k-2

14. direct insertion sort of a set of records (54, 38, 96, 23, 15, 60, 72, 45, 83, 60). When seventh records are inserted into an ordered table, comparisons (Times) are needed to find the insertion position.

A. 1, B. 2, C. 3, D. 4

15. bisearch ordered table (6, 15, 30, 37, 65, 68, 70, 72, 89, 99, 37) if required in order to find elements, and the elements in the table (compare).

A. 65, 15, 37, B. 68, 30, 37, C. 65, 15, 30, D. 65,, 15, 30, 37

16. a length linear table storage order of the N, to the I elements (1 I n+1) to insert a new element, need from behind the front turn after the shift (elements).

A., n-i, B., n-i+1, C., n-i-1, D., I

17., as shown in the 4 two fork tree, () is not exactly two fork tree.

(A) (B) (C) (D);

18. for the length of an ordered list stored in order of 18,

if the use of binary search, to find the fifteenth elements of the search length ().

A. 3 B. 4 C. 5 D.6

19., there are 10000 unordered elements, and you want to pick out the first 10 largest elements at the fastest speed. You'd better choose () the ranking method.

A. heap sort, B. quick sort, C. bubble sort, D. insert sort

20. computer algorithms refer to ().

A. computing method, B. sorting method, C., solve the problem of ordered sequence, D. scheduling method

11-15, B, C, A, C, D,, B, C, A, B, A

21. a stack of sequences 1, 2, 3, 4, then its unlikely output sequence is ().

A. 1, 2, 3, 4, B., 4, 3, 2, 1, C., 1, 3, 4, 2, D. 4,,, 1, 2, 3

22. for any tree with two branches, if its junction number is N0, and the knot number of 2 is N2, then N0= ().

A., N2-1, B., N2+1, C., N2, D., N2-2

C. (Front) - 1% (n = = rear D. (Front + 1)% (n = = rear

45.树中所有结点的度等于所有结点数加 ()

A.0 D.2. C. 1

46.在一棵树中, 每个结点最多有 个前驱结点 ().

A.0 B.1 C.2 d.任意多个

47.在一棵度为3的树中, 度为3的结点数为2个, 度为2的结点数为1个 度为1的结点点数为2个 则度为0的结点数为 个 (,,).

A.3. B.4 C.5 D.6

48.在一棵二叉树上第5层的结点数最多为 ()

A.16 B.15 C.8 D.32

49.在一棵具有n个结点的二叉树的第i层上, 最多具有 个结点 ().

A.2i 2I + 1 b. C. 2I D 2n - 1.

50.一颗具有35个结点的完全二叉树的深度为 ()

A.6 a D.8 B.7

41 - 45 B B D B C 46 - 50 c a b d

51.在一棵完全二叉树中, 若编号为i的结点存在右孩子, 则右孩子

结点的编号为 ()

A.2i b.2i-1 c.2i d.2i + 1 + 2

52.设高度为h的二叉树上只有度为0和度为2的结点, 则此类二叉树中所包含的结点数至少为 ()

A.2h b.2h-1 c.2h D.H + 1 + 1

53.按照二叉树的定义,

A two fork tree with 3 nodes; has () a state.

A.5 B.4 C.3 D.30

54. if the probability of finding each element is equal, the average search length of any element is found on the order table of length n

A.n, B.n+1, C. (n-1), /2, D. (n+1) /2

55., the sequential search method is suitable for storing linear tables with (linear) structure.

A. hash stores B., sequential storage, or link storage

C. compressed storage, D. index storage

56. for the sequential storage order table (5, 12, 20, 26, 37, 42, 46, 50, 64), if the use of binary search, find the search length (element 26)

A.2 B.3 C.4 D.5

57. on the linear scale bisearch, linear table (must)

A. is stored sequentially

B. is stored by link

C. is stored sequentially, and nodes are sorted in keyword order

D. is stored by linking, and nodes are sorted in keyword order

58. using a binary search method to find the length of a linear list is n, the average length of each element (for)

A., O (N2), B., O (nlogn), C., O (n), D., O (logn)

59. in the process of direct insertion of n elements, you need to go through ().

A,.N, B.n+1, C.n-1, D.2n

60. direct insertion of n elements, sorting time complexity is ()

A., O (1), B., O (N2), C., O (n), D., O (nlog2n)

51-55, C, B, A, D, B,, C, B, C, D, C

61. in the process of quick sorting of n elements, it is best

to do () a trip.

A., N, B., n/2, C., logn, D., 2n

62. in the process of bubbling n elements, you need at least () to complete.

A. 1, B., N, C., n-1, D., n/2

63., in the process of quick sorting of n elements, the average time complexity is

A., O (1), B., O (logn), C., O (N2), D., O (nlogn)

In the 64. sorting method, the method in which the elements in the sorted sequence are sequentially removed and compared to the elements in the sorted sequence (initially empty) is put into the correct position of the sorted sequence

A. insert sort B., bubble sort C., Hill sort, D. select sort

65. when sorting a linear table (25, 84, 21, 47, 15,, 27, 68, 35, 20), the sequence of elements changes as follows:

(1) 25, 84, 21, 47, 15,, 27, 68, 35, 20

(2) 20, 15, 21, 25, 47,, 27, 68, 35, 84

(3) 15, 20, 21, 25, 35,, 27, 47, 68, 84

(4) 15, 20, 21, 25, 27,, 35, 47, 68, 84

The sorting method used is ().

A. select sort, B., Hill sort, C. insert sort, D. quick sort

66. fast sorting of the following four sequences, each with the first element as the benchmark for the first division, then in the division process, the number of mobile elements required to have the largest number of sequences is ().

A. 1, 3, 5, 7, 9, B., 5, 7,, 9, 1, 3

C. 5, 3, 1, 7, 9, D., 9, 7,, 5, 3, 1

67., if a simple selection of n elements is sorted, the time complexity required to find the minimum element is the time required for any sort of sorting

A., O (1), B., O (logn), C., O (n), D., O (N2)

68., if the n elements are sorted by heap, a total (or) sieve operation is needed in the process of sorting each order by the initial heap.

A., n+1, B., n/2, C., N, D., n-1

In the 69. sorting method, the method of selecting elements in the sequence that never sorted and placing it in a sorted sequence (initially empty) is called ().

A., Hill sort, B. bubble sort, C. insert sort, D. select sort

70. the key words for a group are (45, 80, 55, 40, 42),

85) the initial heap created by heap sorting is ().

A. (80, 45, 55, 40, 42, 85), B. (85, 80, 55,, 40, 42, 45)

C. (85, 80, 55, 45, 42, 40), D. (85, 55, 80,, 42, 45, 40)

61-65, C, A, D, A, D,, B, B, C, D, D

71. if the n elements are directly inserted into the sorting, the number of elements in the ordered table is () before the I sort procedure is performed.

A. 1, B.i-1, C.i, D., i+1

72. in the process of bubbling the n elements, the first trip requires at most (or) a comparison between the adjacent elements.

A., n+1, B., n/2, C., N, D., n-1

73. if the order of an element is basically ordered, then the sorting is faster.

A. heap sort, B. quick sort, C. direct insertion sort, D. direct selection sorting

74., a quick ranking method is most detrimental to its strengths in () cases.

The amount of data A. is sorting is too large, and B. contains multiple values in the sorted data

The data ordered by C. is basically in order and the number of data to be sorted by D. is odd

In the 75. sorting method, the whole unordered sequence is divided into several small sub sequences and the insertion sorting method is called.

A. Hill sort, B. bubble sort, C. direct insertion sort, D. direct selection sorting

76. direct insertion sort method to sort the following 4 tables from comparison is the least number of ().

A. (94, 32, 40, 90,, 80, 46, 21, 69)

Some things, knowing that is wrong, but also to adhere to, because not reconciled; some people, knowing that love is also to give up, because there is no end; sometimes, knowing that there is no road, but still forward, because used to.

B. (21, 32, 46, 40,, 80, 69, 90, 94)

C. (32, 40, 21, 46,, 69, 94, 90, 80)

D. (90, 69, 80, 46,, 21, 32, 94, 40)

77. a set of key records (46, 79, 56, 38, 40, 84), using a quick

sorting method, is based on the first record as a benchmark.

A. (38, 40, 46, 56, 84, 79)

B. (40, 38, 46, 79, 84, 56)

C. (40, 38, 46, 56, 84, 79)

D. (40, 38, 46, 84, 79, 56)

78. if the sequence of elements (7, 2, 5, 8, 1, 11) of heap sort, and the use of a small heap, from the initial data of the initial heap (for).

A. (1, 2, 5, 7, 11, 8)

B. (1, 2, 5, 8, 11, 7)

C. (1, 5, 2, 7, 11, 8)

D. (1, 5, 2, 8, 7, 11)

79. as shown, the preorder traversal sequence of the two fork tree is ().

A. EGFACDB

B. EAGCFBD

C. EACBDGF

D. EGACDFB

80., it is known that the preorder traversal sequence of a certain two tree is DACBE, and the ordered sequence is DEBAC, and its preorder traversal sequence is (). A. ACBED B. DEABC C. DECAB D. EDBAC

71-75, C, D, C, C, A,, B, D, C, B, C

81., it is known that the preorder traversal sequence of a two fork tree is ABDEFGC, and the ordered sequence is DEBGFAC, and the corresponding two fork tree is (). 81-85 B

2. fill in the blanks

1. the logical structure of data structure and data including _____, ______, ______, ________ four types.

The storage structure and the physical structure of the 2. data including _____, ______, ______, four basic types of ________.

3. data structure is _____ research data, the relationship

between _____ and them, and the corresponding _____ structure definition, design corresponding _____, and ensure that the new structure is obtained through these operations is _____ type structure.

4. an algorithm should have _____, _____,

_____, _____, the five characteristics of _____.

5. the time complexity of an algorithm is how the algorithm contains _____, it is a relative measure of the running time of the algorithm, the space complexity of an algorithm is that the algorithm for temporary occupation in the operation process of the _____ size.

6. time complexity of an algorithm is usually expressed by its _____ form, when a time complexity of the algorithm and the scale of the problem is independent of the size of N, is expressed as _____; proportional to, said to _____; a logarithmic relationship, said to _____; a square, the table shows _____.

7._____ is a set of symbols that describe the number and characters of an object, and all inputs that can be processed into a computer and processed by a computer program. _____ is the basic unit of data, sometimes this unit is composed of a plurality of _____. In this case, it is also called _____ records, is the smallest unit of data, and the linear form of a collection of records for _____.

8. a collection of data structures, K, and his two - element

relationship, R:

K={a, B, C, D, e, F, G, h}

R={, , , , }, f>, ,

The data structure has a _____ structure.

9. a collection of data structures, K, and his two - element relationship, R:

K={a, B, C, D, e, F, G, h}

R={, , , , }, e>, ,

The data structure has a _____ structure.

10. a collection of data structures, K, and his two - element relationship, R:

K={1,2,3,4,5,6}

R={(1,2), (2,3), (2,4), (3,4), (3,5), (3,6), (4,5), (4,6)}

The data structure has a _____ structure.

1. sets, linear structure, tree structure, graphic structure (mesh structure)

2. sequentially stored, chained, stored, hashed, indexed

3., physical structure, logical structure (the order of the two can be reversed), operations, algorithms, the original

4., poverty, certainty, feasibility, input and output

5. statement execution times, storage space

6. orders of magnitude, O (1), O (n), O (logn) and O (N2)

7. data, data elements, data items, data items, files

8. linear structure

9. tree structure

10. graphic structure (mesh structure)

11. if the linear table often need to insert and delete operations, it is best to use _____ storage structure, if often need to search operation of the linear table, it is best to use _____ storage structure.

12. access to a linear table of elements with a given value of time complexity in the order of _____.

13. for a length n of the sequence table, the time complexity of insert header elements for _____, at the end of the table, insert the time complexity of the elements _____.

14. in a single linked list node pointer P points to insert a pointer to the Q node, the _____ value assigned to q->next, and

then the _____ value assigned to p->next.

15. in a single chain table P point to the node before inserting a pointer, s point to the node, you can perform the following operations:

(1) s->next=_____;

(2) p->next= s;

(3) t= p->data;

(4) p->data=_____;

(5) s->data=_____;

The 16. assumption to the first node in the list of the single table pointer for the head, to the single list header, insert the new node pointer P points, the first implementation of _____ assignment, then performs _____ assignment.

17. in a single linked list delete pointer P points node successor node, need to _____ the value assigned to the p->next pointer domain.

18., in a single chain table, delete the pointer P point to the node, you should perform the operation:

Q=p->next;

P->data= p->next->data;

P->next=_____;

Free (Q);

In the 19. _____ list, either by setting a head pointer can be determined by setting it a tail pointer, i.e. by a head pointer or the tail pointer can access to each node in the linked list. Twenty

When a pointer is inserted before a node pointed to by a P in a bidirectional cyclic list with a header, the following operations can be performed when the s points to the node:

(1) s->data= element;

(2) s ->prior=_____;

(3) p->prior->next=s;

(4) s->next=_____;

(5) p->prior=_____;

11. chain, order 12.O (n)

13.O (n) and O (1)

14.p->next, q

15.p->next, s->data, t

16.p->next=, head, head=p

17.p->next->next

18.p->next->next

19. cycle

Some things, knowing that is wrong, but also to adhere to, because not reconciled; some people, knowing that love is also to give up, because there is no end; sometimes, knowing that there is no road, but still forward, because used to.

20.p->prior, P, s

21. pointers in a two-way linked list pointed to by P node before inserting a new node, its time complexity is in the order of _______.

22. linear table length refers to _______.

23. in the linear order of the table storage, the logical relationship between elements is determined by _______, in linear form a chain store, the logical relationship between elements is determined by _______.

24. according to each node chain storage structure of linear

table contains a number of pointers, the list can be divided into _______ and _______.

25. linear tables, stacks and queues are _______ for stack structure, only in the _______ insert and delete elements; to insert elements in the queue can only delete elements in ______ _______.

The 26. is provided with an empty stack, the existing input sequence 1, 2, 3, 4, 5, push, pop, after push, push, pop, push, push, the output sequence corresponding to the _______.

27. elements 1, 2, 3, 4, 5 in turn into the stack, if the output sequence 34251, sequence of operations should be carried out for push (S, 1), push (S, 2), ______, pop (S), push (S, 4), pop (S), ______, ______, pop (S), pop (S).

Circular queue 28. has N storage unit in a medium, when the queue is full with ______ elements.

29. have a tree, as shown, answer the following questions:

(1) the root of this tree is ();

(2) the leaf node of this tree is ()

(3) the degree of node C is (), and the degree of the tree is ()

(4) the children of node C are ()

(5) the parent of node C is ()

30. for an N node of two binary tree, the minimum depth of it may have to ______, the maximum depth is ______. 21.O (1)

22. the number of data elements contained in a linear table

23. the value of the physical storage address and pointer

24. single linked list, double linked list

25. linear, stack top, team tail, team head 26.2, 3

27.push (S, 3), pop (S) and push (S, 5) 28.n-1

29. (1) A (2) B, E, G, D (3) 2,3 (4) E, F (5) A

30.[log2n]+1, n

The total number of nodes and 31. a depth of K over the two fork tree for ______, the minimum depth of tree nodes in the total number of complete binary tree of two K for ______, maximum ______.

32. by a, B, C three nodes of two binary tree, a total of ______

different structure.

33. for a tree with n nodes of the tree, the tree of all nodes and the degree to ______.

In 34. a two binary tree, assuming that the nodes of degree 2 is 5, the nodes of degree 1 to 6, while the leaf nodes for a ______.

35. assuming a two binary tree sequence stored in

one-dimensional array a, but let the number 1 of the nodes in the a[0] element, so that the number 2 of the nodes in the a[1] element, the other is analogy, numbered I nodes of the left child node corresponding to the array index ______, corresponding to the right child ______.

36., a n node of the two tree completely from the root node of this layer, each layer of the node from left to right in the order of storage in the array A[1

N], set up a node position in the array of I (1 i n), his father is the position of the nodes is _______.

37. of the two fork tree depth is h, and only 0 degrees and 2 nodes, the two tree contains nodes up to _______.

38. assume a set of records (46,79,56,38,40,84), in the process of bubble sort to sort the results for the first time _______.

39. assume a set of records (46,79,56,38,40,80), the process of quick sort, a total of ______ times ranking.

40. assume a set of records (46,79,56,38,40,80), with its quick sort, it is the first time after the division of the ______.

31.2k-1, 2k-1, 2k-1

Thirty-two point five 33.n-1

Thirty-four point six

35.2i-1, 2I

36.[i/2] (take integer part) 37.2h-1

38.46,56,38,40,79,84

Thirty-nine point three

40.[40,38], 46, [56,79,80]

41. of n records in the ordered list of binary search, compare the number of the largest is ______.

The storage structure of 42. binary search method is limited to ______, and orderly.

43. in a single list, to delete a specified node, the node must

find ______.

Four kinds of the basic operation of the linear table 44. are inserted and deleted, search and ______ operation.

45. circular single linked list and main different non circular single linked list is circular single linked list tail pointer ______, rather than circular single linked list tail pointer ______.

46. access to single node in the linked list, must be followed along ______.

47. in the double linked list, each node has two pointers, one point to another point ______ ______.

48. in a doubly linked list, delete the pointer points to the P node, the need for p->next->prior domain pointer assignment for ______.

49. let head be a circular linked list L head node, the L is empty table is ______.

50. stack called ______ queue table, also known as ______ table. 41.log2n

42. sequential storage structure

43. precursor node

44. sort

45. points to the chain header node, pointing empty

46. pointer field or next domain

47. predecessor node, successor node

48.p->prior

49.head->next=head

50. first in first out, first in first out

The 51. assumption back into the stack and stack operation respectively expressed in S and X, the input sequence a, B, C, D, e after a series of stack operation SSXSXSSXXX, the output sequence is obtained ______.

52. in a one-dimensional array of a[n] stack, the stack contains the minimum number of elements for ______, up to ______.

53. in a length of N in the sequence table to delete the first I elements (0 i n-1), need to move forward ______ elements.

54. a data structure in computer (map) called ______.

55. in the linear structure and tree structure, between the precursor node and successor node there are ______ and ______ contact.

51.b, C, e, D, a 52, n-1 53.n-i

54. storage structure of data

55., one to one, one to many

56. every time out an element from the disorder in the child table, and then inserted into the ordered proper position in the table, this is called the _______ Ranking Ranking Method; each from unordered list selected one of the largest or smallest element, it is switched to an ordered list, this method is called ________ sorting.

57. as shown in the two binary tree traversal sequence is ____________.

56. insert, select

57.A, B, C, D, E, G, F

Some things, knowing that is wrong, but also to adhere to, because not reconciled; some people, knowing that love is also to give up, because there is no end; sometimes, knowing that there is no road, but still forward, because used to.

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