数据结构英文考试

数据结构 1 一． 考试常用的 Algorithm 算法。Primitive 基本的 consume 消费 stack 栈 principle 原则 Recursive 递归 linear 线性的 dynamic 动态的 binary二进制的 thread 线索 Traversal 遍历 node 结点 inorder 中序 posorder 后序 preorder 前序 Graph 图 undirected 无向图 element 数字 remove 删除 middle 中间 Adjacent 邻接 maintain 维持 pointer 指针 circular 循环 implement 实现 Bubble 冒泡 insertion 插入 address 地址 二、考试内容 1、What is an algorithm?什么是算法？ an algorithm is a well-defined list of steps for solving a particular problem. 2、What is data structure? 什么是数据结构？ What does the primitive data structure include? 基础的数据结构包括什么？ What does the non primitive data structure include?非基础的数据结构包括什么？ (1)The data structrue is the logical or mathematical model of a particular organization of date (data may be organized in many ways) （2）Primitive data：int, float, char; (3) non primitive data: linear (arrays , list) nonlinear( graphs , tree) 3、What is a stack?什么是栈？What principle does it work on?它的工作原理是什么？ （1）A stack is linear data structure in which items may be added or removed only at one end, called the TOP of the stack. （2）last in first out. 4、What is a queue? 什么是队列？What principle does it work on?它的工作原理是什么？ （1）a queue is a linear list of elements in which deletions can take place only at one end，called the front，and insertions can take place only at the other end，called the rear. （2）first in first out. 5、What is recursion? 什么是递归？Does a recursive program is one which defines in terms of itself?在程序中是否调用自身？ （1）Recursion is a programming tool that is one of the most powerful for beginning students of programming; （2） yes. 6、What is a tree?什么是树？What is a binary tree? 什么是二叉树？ What is tree traversal? 什么是树的遍历？How to create and traverse the tree in inorder, preorder and postorder?先序，中序，后序是如何让遍历的？ （1）Tree is a connected Graph without any cycle;it is non-linear data structure . （2）Binary Tree: A binary tree T is defined as a finite set of elements, called nodes, such that: either （3）According to the path of every node visit tree, and just visit once a) T is empty (null tree) or b) T contains a special node called the root of T and the remaining nodes of T form an ordered pair of disjoint binary trees T1 (left subtree) and T2 (right subtree) preorder:1、process the root R.2、traverse the left subtree of R in preorder.3、traverse the right subtree of R in preorder. inorder：1、traverse the left subtree of R in inorder.2、process the root R.3、traverse the right subtree of R in inorder. postorder：1、traverse the left subtree of R in postorder.2、traverse the right subtree of R in 数据结构 2 postorder.3、process the root R. 7、what is insertion sort? How to implement it?（什么是插入排序？怎样实现？） （1）Sorting takes place by inserting a particular element at the appropriate position,that’s why the name insertion sorting （2） #include void main() { int a[10], n, temp, i,j; clrscr(); printf("how many numbers\n"); scanf("%d",&n); printf("input the numbers\n"); for (i=0; iwhile (temp < a[j] && j >=0) { a[j+1]=a[j]; j=j-1; } a[j+1]=temp; } printf("\n te asceding order is \n"); for (i=0; i < n; ++i) printf("%d\t", a[i]); }

8、what is bubble sort? How to implement it?（什么是冒泡排序？怎样实现？) （1）As always in the sorting process decimal put forward, put back large numbers, which is equivalent to the increase in bubble （2） #include void main() { int x[10], i,n,temp,j; printf(" how manu number you want to input\n"); scanf("%d",&n); for(i=0; i<=n-1; ++i) scanf("%d",&x[i]); for (i=0; i < (n-1); ++i) for (j=0; j < (n-(i+1)); j++) if (x[j] > x[j+1]) { temp=x[j]; x[j]=x[j+1]; x[j+1]=temp; } printf("sorted array is \n"); for(i=0; i<=n-1; ++i) printf("%d\t",x[i]); }

9、what is graph? What is directed graph and undirected graph?（图是什么？什么是有向图和无向图？） (1)a graph is depicted in diagrammatic form as a set of dots (for the points,vertices or nodes)joined by curves(for the lines or edges) (2)directed graph: A graph with directed edges Undirectied graph: A graph with only undirected edges 10、what is ascending priority queue and descending priority queue?（什么是优先队列的升序和降序？） (1) ascending priority queue elements can be inserted in any order, but while deleting an