数据结构英文考试.doc

数据结构一 考试常用的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) orb) 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 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,thats why the name insertion sorting（2）7 #include void main() int a10, n, temp, i,j; clrscr(); printf(how many numbersn); scanf(%d,&n); printf(input the numbersn); for (i=0; in; +i) scanf(%d,&ai); for(i=1; in; +i) temp=ai; j=i-1; while (temp =0) aj+1=aj; j=j-1; aj+1=temp; printf(n te asceding order is n); for (i=0; i n; +i) printf(%dt, ai); 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 x10, i,n,temp,j; printf( how manu number you want to inputn); scanf(%d,&n);for(i=0; i=n-1; +i) scanf(%d,&xi);for (i=0; i (n-1); +i) for (j=0; j xj+1) temp=xj; xj=xj+1; xj+1=temp; printf(sorted array is n); for(i=0; i=n-1; +i) printf(%dt,xi);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 edgesUndirectied graph: A graph with only undirected edges10、what is ascending priority queue and descending priority queue?（什么是优先队列的升序和降序？） (1) ascending priority queue elements can be inserted in any order, but while deleting an element from the queue, remove only the smallest element first; (2) decending priority queue elements can be inserted in any order, but while deleting an element from the queue, only the largest element is deleted;11、DeQueue and dqueue(双端队列与双队列的区别） (1)DeQueue:double ended queue-a linear list in which elements can be added or removed at either end but not middle. (2)dqueue:double queue-Deposit can only be restricted to one side but can be removed either end of both ends.12、what is circular queue?什么是循环队列？what is the difference between the circular queue and linear queue? 循环队列和线性队列的有什么不同？how to implement it?如何实现它？（1）circular queue is in an ordinary queue as and when the items is inserted the rear pointer is incremented.（2）Circular queue is in an ordinary queue;but linear queue is a linear list of elements.13、what is the difference between iterative program and recursive program?循环程序和递归程序的不同是什么？Iteration:Process of executing the statements repeatedly.反复执行过程中的语句any function can be solved usingiterative process.more efficient in terms of memory utilization and speed of execution.更高效的内存利用率和执行速度方面 No compactness. 不紧密的recursive program:Defines in terms of itself.14、What is thread binary tree?什么是线索二叉树？what is the working of it?它是基于什么工作的？（1）Threaded binary trees use the null points to go back up the tree, a tree can be threaded for an inorder traversal.（2）A left thread points to the predecessor in an inorder traversal.A right thread points to the successor in an inorder traversal.15、What is linked list?什么是链表？ A linked list is a linear collection of data elements called nodes where the linear order is given by means of pointers. The first part contains information of element and the second part called link field or next pointer field contains address of next node in list.16、What is a good program?什么是好程序？ Run correctly Run efficiently (min-time) Be easy to read and understand Be easy to debug and modify17、 What is pointer?什么是指针？A pointer is an address of another variable.A pointer variable stores(holds) a memory address.Pointer is a strength of C三、程序题：Queue.c(队列)#include struct queue int front, rear; int items5; ;void qinsert(struct queue *, int); void qdisplay(struct queue *);void main() struct queue q; int ch, ele; q.front=0; q.rear= -1; clrscr(); while(1) printf(n queue operationsn); printf(1. INSERTn); printf(2. REMOVEn); printf(3 DISPLAYn); printf(4 EXITn); printf(enter your choicen); scanf(%d,&ch); switch(ch) case 1: printf(input the valuen); scanf(%d,&ele); qinsert(&q,ele); break;case 2: printf(remove operationn); ele=qremove(&q); if (ele != -1) printf(element remvoed is %dn, ele); break; case 3: printf(Queue contents are n); qdisplay(&q); break; case 4: exit(1); default : printf(invalid choicen); void qinsert(struct queue *qptr, int ele) if (qptr-rear = 4) printf(n queue overflown); else qptr-items+(qptr-rear) =ele; int qremove(struct queue *qptr) if (empty(qptr) printf(n queue underflow); return(-1); else return(qptr-items(qptr-front)+); int empty(struct queue *qptr) if (qptr-rear front) return(1); else return(0); void qdisplay(struct queue *qptr) int i; printf(n); if (empty(qptr) printf(QUEUE EMPTYn); else for (i=qptr-front; i rear; +i) printf(%dt, qptr-itemsi); printf(n); Cirqueue.c(循环队列)#include #include #define SIZE 5struct queue int front, rear; int items SIZE; int count; ;void qinsert(struct queue *, int); void qdisplay (struct queue *); int qfull(struct queue *qptr) return(qptr-count = SIZE) ? 1: 0); int qempty(struct queue *qptr) return(qptr-count = 0) ? 1:0); void qinsert(struct queue *qptr, int item) if (qfull(qptr) printf(queue overflown); return; qptr-rear = (qptr-rear+1) % SIZE; qptr-itemsqptr-rear=item; (qptr-count)+; int qremove(struct queue *qptr) int item; if (qempty(qptr) printf(queue underflown); return; printf(element removed is %d, qptr-itemsqptr-front); qptr-front=(qptr-front + 1) % SIZE; (qptr-count)-; return; void qdisplay(struct queue *qptr) int i,j; i=qptr-front; if (qempty(qptr) printf(Queue Emptyn); return; for (j=1; jcount; j+) printf(%dt, qptr-itemsi); i = (i+1) % SIZE; void main() int ch,item; struct queue q; clrscr(); q.front=0; q.rear=-1; q.count=0;while(1) printf(n 1. Insertn); printf(2. Deleten); printf(3. Displayn); printf(4 Exitn);printf(enter your choicen); scanf(%d,&ch); switch(ch) case 1: printf(enter the element to be insertedn); scanf(%d, &item); qinsert(&q, item); break; case 2: qremove(&q); break; case 3 : qdisplay(&q); break; case 4: exit(); break; default: printf(Invalid choicen); Tree.c(树)#include #include struct node int info; struct node *left; struct node *right; ;typedef struct node node;node *root=NULL;node *getnode() node *p; p=(node *) malloc(sizeof(node); return(p); void insert()int data;node *ptr, *prev, *p;printf(n enter a data to insertn);scanf(%d, &data);ptr=root;while (ptr!=NULL & ptr-info!=data)if (ptr-info right; else prev=ptr;ptr=ptr-left; if (ptr != NULL)printf(n Duplicate value is not allowed);elsep=getnode();p-info= data;p-left=p-right=NULL;if (prev-info info);prev-right=p;elseprintf(n inserted at LEFT of %d, prev-info);prev-left=p;void inorder(node *p) if (p!=NULL) inorder(p-left); printf(t%d, p-info); inorder(p-right); void preorder(node *p) if (p!=NULL) printf(t%d, p-info); preorder(p-left); preorder(p-right); void postorder(node *p) if (p!=NULL) postorder(p-left); postorder(p-right); printf(t%d, p-info);void main()int ele,ch;clrscr();printf(enter an element to insert at Root );scanf(%d, &ele);root=getnode();root-info=ele;root-left=root-right=NULL;while (1)printf(n 1 Insert);printf(n 2 Inorder);printf(n 3 Preorder);printf(n 4 Postorder);printf(n 5 Exit);printf(n Enter your choice);scanf(%d,