(1) The Linked List is designed for conveniently b data item.
a. getting
b. inserting
c. finding
d.locating
(2) Assume a sequence list as 1,2,3,4,5,6 passes a stack, an impossible output sequence list Is
c .
a. 2,4,3,5,1,6
b.3,2,5,6,4,1
c.1,5,4,6,2,3
d.4,5,3,6,2,1
(3) A queue is a structure not implementing b .
a. first-in/first-out
b. first-in/last-out
c. last-in/last-out
d. first-come/first-serve
(4) Removing the data item at index i from a sequential list with n items, d items need to be shifted left one position.
a. n-i
b. n-i+1
c. i
d. n-i-1
(5) There is an algorithm with inserting an item to a ordered SeqList and still keeping the SeqList ordered. The computational efficiency of this inserting algorithm is c .
a. O(log2n)
b. O(1)
c. O(n)
d.(n2)
(6) The addresses which store Linked List d .
a. must be sequential
b. must be partly sequential
c. must be no sequential
d. can be sequential or discontiguous
(7) According the definition of Binary Tree, there will be b different Binary Trees with 5 nodes.
a. 6
b. 5
c. 4
d. 3
(8) In the following 4 Binary Trees, c is not the complete Binary Tree.
a b c d
(9) A Binary Tree will have a nodes on its level i at most.
a.2i
b. 2i
c.2i+1
d.2i-1
(10) If the Binary Tree T2 is transformed from the Tree T1, then the postorder of T1 is the
b of T2.
a. preorder
b. inorder
c. postorder
d. level order
(11) In the following sorting algorithm, c is an unstable algorithm.
a. the insertion sort
b. the bubble sort
c. quicksort
d. mergesort
(12) Assume there is a ordered list consisting of 100 data items, using binary search to find a special item, the maximum comparisons is d .
a. 25
b.1
c. 10
d.7
(13) The result from scanning a Binary Search Tree in inorder traversal is in c order.
a. descending or ascending
b. descending
c. ascending
d. out of order
(14) The d case is worst for quicksort.
a. the data which will be sorted is too larger.
b. there are many same item in the data which will be sorted .
c. the data will be sorted is out of order
d. the data will be sorted is already in a sequential order.
(15) In a Binary Tree with n nodes, there is a non-empty pointers.
a. n-1
b. n+1
c. 2n-1
d.2n+1
(16) In a undirected graph with n vertexs, the maximum edges is b .
a. n(n+1)/2
b. n(n-1)/2
c. n(n-1)
d.n2
(17) The priority queue is a structure implementing c .
a. inserting item only at the rear of the priority queue.
b. inserting item only at the front of the priority queue.
c. deleting item according to the priority of the item.
d. first in/first out
(18) The output from scanning a minimum heap with level traversal algorithm c .
a. must be an ascending sequence.
b. must be descending sequence
c. must have a minimum item at the head position.
d. must have a minimum item at the rear position.
(19) Assume the preorder of T is ABEGFCDH, the inorder of T is EGBFADHC, then the postorder of T will be a .
a. GEFBHDCA
b. EGFBDHCA
c. GEFBDHCA
d. GEBFDHCA
(20) When a recursive algorithm is transformed into a no recursive algorithm, a structure
b is generally used.
a. SeqList
b. Stack
c. Queue
d. Binary Tree
(1)Suppose 1,2,3,4 is the order which these elements push onto a stack. The sequence obtained is
(B)
A.4.1.2.3
B.3.2.4.1
C.3.4.1.2
D.4.3.1.2
(2)Suppose that a linear list contains n=31 nodes, the binary search is applied to the list, the maximum times in searching is (B)
A 4
B 5
C 25-1
D 24-1
(3)In the following sorting algorithms, which is unstable(A)
A Selection sort
B Merge sort
C Bubble sort
D Insertion sort
(4)Bubble sort is used for n nodes, the minimum number of comparisons is (A)
A n-1
B n
C n(n-1/2)
D n(n+1)/2
(5)How many binary trees in different forms can at most be built by three nodes?(B)
A 4
B 5
C 6
D 7
第二章线性表 一、顺序表和链表的优缺点 1.顺序表 定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低） 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.链式存储结构 定义：由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表，称为线性表的链式存储表示 优势： (1)能有效利用存储空间； 动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作； 插入或删除时只需要修改指针，而不需要元素移动。 劣势： (1)不能随机存取数据元素； (2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的 “位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 二、单链表中删除一个节点和插入一个节点的语句操作，p29 1.插入元素操作 算法基本思想：首先找到相应结点，然后修改相应指针。 假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为： s->next=p->next; p->next =s;
2.删除元素操作 算法基本思想:首先找到第i-1 个结点，然后修改相应指针。 删除b结点，其中，P指向a，指针修改语句为：p->next=p->next->next； 三、单链表的就地逆置习题集2.22 算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列 一、栈和队列的特性 1.特点 栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。 队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。 二、循环队列为空和满的判定方法，p63 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front
《数据结构》基本概念
基本概念 ?数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 ?数据元素 数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 ?数据项 数据项是构成数据元素的不可分割的最小单位。?数据对象 数据对象是具有相同性质的数据元素的集合，是数据的子集。 注意：在不产生混淆的情况下，将数据对象简称为数据。 ?数据结构 数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = (D, R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 ?数据的逻辑结构 数据的逻辑结构是指数据元素之间逻辑关系的整体。
根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵线性结构：数据元素之间存在着一对一的线性关系； ⑶树结构：数据元素之间存在着一对多的层次关系； ⑷图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。?数据的存储结构 数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 ?抽象数据类型 抽象数据类型是一个数据结构以及定义在该结构上
一、英语句子成分和英语句子结构讲解： （一）句子成分 1.主语（subject）: 句子说明的人或事物。 主语可以由名词、代词、数词、不定式、动名词、分词、主语从句和短语等来担任。 The sun rises in the east.（名词） He likes dancing. （代词） Twenty years is a short time in history. (数词) Seeing is believing. （动名词） To see is to believe. （不定式） What he needs is a book. （主语从句） It is very clear that the elephant is round and tall like a tree. （It形式主语，主语从句是真正主语） 找出下列句中的主语： Jane is good at playing the piano.（名词） She went out in a hurry.（代词） Four plus four is eight.（数词） To see is to believe.（不定式） Smoking is bad for health.（动名词） The young should respect the old.（名词化的形容词）What he has said is true. （句子） 2.谓语（predicate）: 说明主语的动作、状态和特征。 简单谓语:由动词或动词词组组成 I saw the flag on the top of the hill? He looked after two orphans. 复合谓语：由情态动词或助动词+动词; He can speak English well. She doesn’t seem to like dancing. 找出下列句中的谓语（注：只有动词才可作谓语。）： 1. We love China. 2. We have finished reading this book. 3. He can speak English. 4. She seems tired. 3.表语（predicative）: 系动词之后的成分，表示主语的性质、状态和特征。
数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。
数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计）物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表
示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。 队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号； 相等：串的值相等；空格串：由一个或多个空格组成的串，
【关键字】英语、情况、条件、会议、计划、主动、继续、健康、持续、保持、需要、方式、作用、结构、分析、衔接、引导、关心、主动性 句子成分 一．主语（subject）: 句子说明的人或事物。 1.请找出下列句子的主语并指出什么（词，短语或句子）可以充当主语。 The sun rises in the east. （名词） He likes dancing. （代词） Twenty years is a short time in history. (数词) Seeing is believing. （动名词） To see is to believe. （不定式） What he needs is a book. （主语从句） It is very clear that the elephant is round and tall like a tree. （It形式主语，主语从句是真正主语） 常见错误分析 2：动词及其短语在作句子的主语时，只能使用其to do 或doing 的形式。其中不定式强调具体的某一次的动作，-ing 强调经常发生的动作。 改错：1.play computer games does no good to us. 2.Have a walk in the street is her hobby. 3.Go home at once is his decision 4.Make more friends will do good to us. 5.I’m like computer very much. 6.The story was happening the year before last. 二．宾语： 1．动作的承受者-----动宾 请找出下列句子的宾语并指出什么可以充当宾语。 I like China. （名词） He hates you. （代词） How many do you need? We need two. （数词） I enjoy working with you. （动名词） I hope to see you again. （不定式） Did you write down what he said? （宾语从句） 2．介词后的名词、代词和动名词-----介宾 Are you afraid of the snake/me/fighting? 3．双宾语-----间宾（指人）和直宾（指物） He gave me a book yesterday. 常见错误分析 1：介词后跟宾语时，必须为：名词、代词、ing 或wh型的连接词引导的从句。 改错：①I am fond of play basketball. ②He’s cra zy about read story books. ③I am sorry for late. ④I felt terribly sad for absent from class. 2：动词及其短语在作句子的主语或宾语时，只能使用其to do 或doing 的形式。其中不定式强调具体的某一次的动作，-ing 强调经常发生的
/** *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环，
基本概念 数据 数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号 集合。 数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项 数据项是构成数据元素的不可分割的最小单位。 数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。 数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure = （D, R），其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴ 集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； ⑵ 线性结构：数据元素之间存在着一对一的线性关系； ⑶ 树结构：数据元素之间存在着一对多的层次关系； ⑷ 图结构：数据元素之间存在着多对多的任意关系。 注意：数据结构分为两类：线性结构和非线性结构。 数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。 抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。 算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法的特性 ⑴ 输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。 ⑵ 输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。 ⑶ 有穷性：一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都在有穷时间内完成。 ⑷ 确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。 ⑸ 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 线性表的定义 线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。 线性表的逻辑关系 在一个非空表L= (a i, a2, , a n)中，任意一对相邻的数据元素和a i之间(1< i < n)存在序偶 关系(a i-i，a i)，且a i-i称为a i的前驱，a i称为的后继。在这个序列中，a i无前驱，a n无后继，其它每个元素有且仅有一个前驱和一个后继。 顺序表的存储结构定义 用MaxSize 表示数组的长度,顺序表的存储结构定义如下： #define MaxSize i00 typedef struct { ElemType data[MaxSize]; // ElemType 表示不确定的数据类型 int length; //length 表示线性表的长度
学会分析英语句子（语法基础辅导讲义） 第一讲学会判断分析简单句 一、词类和句子成分的关系、动词概说与五种基本句型 1．语法学习和语法学习的方法 1)语法包括哪些内容？ 2)怎样学习语法？（死记活用） 关于英语词类的特点的思考题 2．十大词类中，哪种词类是英语中特有而汉语没有的？ 3．哪些词和名词有关系？ 4．动词有什么特征？动词分为几种类型？ 5．什么是不定式？它和谓语动词有什么区别？ 6．哪种词类和动词有关？为什么？ 二、什么是句子成分？有哪些句子成分？ 1.主谓宾定状补主干枝叶分清楚，哪些是主干？哪些是枝叶？ 2.什么是状语和定语？ 3. 什么是宾语补助语和主语补助语？ 英语语法分为句法和词法。 句法就是造句和运用句子的规则，句法是最基本的语法规则；词法就是词的使用规则，如动词时态、语态、助动词、情态动词、形容词和副词的用法等等。要造出一个正确的句子必须有词法和句法知识，比如要弄懂词类和句子成分的关系，比如形容词做定语，副词做装语；又比如代词所有格做定语；主格做主语；宾格做宾语，等等。 动词只能做谓语，十分重要。时态主要体现在动词上，动词做谓语，因此也就是要弄懂谓语的构成，不同的时态有不同的构成，时态有常用的时间状语，要彻底搞清楚。
一个句子必然有时态、语态。对谓语动词要弄清楚其时态和语态，才能进行肯定句、否定句和疑问句的转换。 语态体现在be 动词+ 过去分词上。不管什么语态的句子都有时态，不同时态的被动语态都有固定的结构。 句子必然有其由句子成分构成的句子结构。五种基本句型很重要，但是没有词类和句子成分的知识。例如不懂动词分为及物和不及物两种就不能懂得 主语+ 谓语+ 宾语; 主语+ 谓语+ 间接宾语+ 直接宾语; 主语+ 谓语+ 宾语+ 宾语补助语这三种句型 一个句子或者是简单句或者是并列句，或者是复合句。要弄清楚：是简单句、并列句还是复合句？是复合句，又有什么从句？ 每个句子的句子成分是怎么样的？如果不懂什么是宾语，那么就学不懂宾语从句；如果不懂什么是状语，那么就学不懂状语从句；如果不懂什么是定语，那么就学不懂定语从句；如果不懂什么是表语，那么就学不懂表语从句。 要弄清楚句子成分和结构，要学会从简单句、并列句、复合句三个方面分析句子,才能在阅读和造句时不犯错误。 所谓分析英语句子，就是从结构上分析判断它是简单句、并列句还是复合句？ 它们是由什么词类词组充当的？并列句有几个分句？是什么从句？这些句子不管主句还是从句又是怎样构成的？这是大结构大框架的分析。还有从局部如谓语的分析，什么时态？什么语态？词法知识都很重要。还有状语定语的分析也是局部分析。 词类和句子成分的关系 十大词类 要搞清楚句子成分必须搞清楚英语的词类，因为句子成分是由一个一个的词或词组充
空间数据结构 摘要：空间数据模型和空间数据结构是地理信息系统（GIS）课题的中心内容。本文对空间数据结构的定义、分类进行了一定的研究性的归纳与总结。 关键词：空间数据结构，矢量数据，栅格数据 引言 GIS中空间数据结构和空间数据模型是紧密相关的。数据模型的建立必须通过一定的数据结构，但两者之间也有非常大的区别。数据模型是一个总得概念，是人为概念化的真实，是对现实世界的提取，对现实世界的认识和选择。而数据结构指数据元素之间的相互关系，它是软件常规内涵，根据空间数据结构和数据模型的特点及其关系，可以建立空间数据库系统。 空间数据结构定义 空间数据结构是带有空间数据单元的集合。这些数据单元是数据的基本单 位，一个数据单元可以有几个数据项组成，数据单元之间存在某种联系叫做结构。 所以，研究空间数据结构，是指空间目标间的相互关系，包括几何和非几何的关 系，数据结构是数据模型的表述，数据结构往往通过一系列的图表和矩阵，以及 计算机码的数据记录来说明。 空间数据结构的分类 矢量数据结构 定义 矢量数据结构是基于矢量模型，利用欧几里得(EUCLID)几何学中的点、线、 面及其组合体来表示地理实体的空间分布，是通过记录坐标的方式，尽可能精确 地表示点线多边形等地理实体，自然地理实体的位置是用其在坐标参考系中的空 间位置来定义的，坐标空间设为连续，允许任意位置长度和面积的精确定义，其 特点是定位明显，属性隐含。 GIS采用的矢量数据结构模型，是将空间地质实体抽象成点、线、面三种几 何要素，矢量数据结构通过优化拓扑结构表达空间实体的相关关系，为空间数据 库建立基本框架。 矢量数据结构的特点 优点：数据按照点、线或多边形为单元进行组织，结构简单、直观、易实现 以实体为单位的运算和显示。 缺点：
定义：构成句子的各个部分叫做句子成分。句子成分有主要成分和次要成分； 主要成分：主语和谓语 次要成分：表语、宾语、定语、状语、补足语、同位语 I met my best friend Tom at the station yesterday . 主语谓语定语宾语同位语状语 ㈠主语（subject） 句子说明的人或事物 Jane is good at playing the piano.（名词） She went out in a hurry.（代词） Four plus four is eight.（数词） To see is to believe.（不定式） Smoking is bad for health.（动名词） The young should respect the old.（名词化的形容词） What he has said is true. （句子） 找出下列句中的主语：1、The sun rises in the east. 2、Twenty years is a short time in history. 3、The poor are now living in the shelter. 4、Seeing is believing. 5、To see is to believe.
6、He likes dancing. 7、What he needs is a book. 8、It is very clear that the elephant is round and tall like a tree. ㈡谓语 说明主语的动作、状态和特征 简单谓语:由动词或动词词组组成 I saw the flag on the top of the hill He looked after two orphans. 复合谓语：由情态动词或助动词+动词; He can speak English well. She doesn’t seem to like dancing. 找出下列句中的谓语（注：只有动词才可作谓语。）： 1. We love China. 2. We have finished reading this book. 3. He can speak English. 4. She seems tired. (三)宾语动作的对象或承受者——及物动词或介词的宾语Show your passport, please. （名词） She didn't say anything. （代词） How many do you want - I want two. （数词） They sent the injured to hospital. （名词化的形容词） They asked to see my passport. （不定式） I enjoy working with you. （动名词）
句子结构成份讲解及练习题 主语：就是一个句子述的对象，或是动作的执行者。它回答的是“谁”“什么”的问题。如：我看书。谁看书？ “我”。“我”就是这句子的主语。主语由名词或相当于名词的词充当。（如动词不定式，动名词，代词都可作主语，主语从句）主语（subject）: 句子说明的人或事物。 The sun rises in the east. （名词）He likes dancing. （代词） Twenty years is a short time in history. (数词) Seeing is believing. （动名词） To see is to believe. （不定式）What he needs is a book. （主语从句） It is very clear that the elephant is round and tall like a tree. （It形式主语，主语从句是真正主语） 谓语：说明主语是什么，干什么，怎么样。它回答的是主语“干什么，是什么”的问题。如上句中主语“我” 干什么？“看书”。“看书”就是谓语。一个句子，一般都可分成主、谓两大部分（祈使句是省主句）。再细分又可分成谓语（动词）、宾语，表语，补语（包括宾补和主补），定语，状语，同位语等。如第一例中谓语部分可划分成谓语（看）和宾语（书）。谓语部分中心词一定要是一个动词，要么是行为动词，要么是系动词，不同的动词构成不同的句子类型。句子的各种时态、人称和数的变化都在谓语动词上变。谓语（predicate）: 说明主语的动作、状态和特征。We study English. He is asleep. 宾语：指谓语动词所涉及的对象，由名、代、数，宾语从句等相当于名词的词句充当，但人称代词要用 宾格。如：还说上例。谓语动词是“看”，看什么？看“书”，“书”是动词“看”所涉及的对象，是“看”的宾语。需要说明的是：只有及物动词和介词或相当于及物动词和介词的短语才可带宾语。宾语：1）动作的承受者-----动宾 I like China. （名词）He hates you. （代词） How many do you need? We need two. （数词） We should help the old and the poor. I enjoy working with you. （动名词） I hope to see you again. （不定式）Did you write down what he said? （宾语从句） 2）介词后的名词、代词和动名词-----介宾 Are you afraid of the snake? Under the snow, there are many rocks. 3）双宾语-----间宾（指人）和直宾（指物） He gave me a book yesterday. Give the poor man some money. 表语：是和系动词紧密相连的。在述句中系动词后面的就是表语，这就是“主系表”结构。作表语的也是 名词性的词，也可以是从句。表语（predicative）: 系动词之后的成分，表示主语的性质、状态和特征。He is a teacher. （名词）Seventy-four! You don’t look it. （代词）Five and five is ten. （数词）He is asleep. （形容词） His father is in. （副词）The picture is on the wall. ( 介词短语) My watch is gone / missing / lost. （形容词化的分词） To wear a flower is to say “I’m poor, I can’t buy a ring. （不定式） The question is whether they will come. （表语从句） （常见的系动词有: be, sound（听起来）, look（看起来）, feel(摸起来，smell（闻起来）, taste（尝、吃起来）, remain（保持，仍是）, feel（感觉）... It sounds a good idea. It sound sounds strange. Her voice sounds sweet. Tom looks thin.
(1) The Linked List is designed for conveniently b data item. a. getting b. inserting c. finding d.locating (2) Assume a sequence list as 1,2,3,4,5,6 passes a stack, an impossible output sequence list Is c . a. 2,4,3,5,1,6 b.3,2,5,6,4,1 c.1,5,4,6,2,3 d.4,5,3,6,2,1 (3) A queue is a structure not implementing b . a. first-in/first-out b. first-in/last-out c. last-in/last-out d. first-come/first-serve (4) Removing the data item at index i from a sequential list with n items, d items need to be shifted left one position. a. n-i b. n-i+1 c. i d. n-i-1 (5) There is an algorithm with inserting an item to a ordered SeqList and still keeping the SeqList ordered. The computational efficiency of this inserting algorithm is c . a. O(log2n) b. O(1) c. O(n) d.(n2) (6) The addresses which store Linked List d . a. must be sequential b. must be partly sequential c. must be no sequential d. can be sequential or discontiguous (7) According the definition of Binary Tree, there will be b different Binary Trees with 5 nodes. a. 6 b. 5 c. 4 d. 3 (8) In the following 4 Binary Trees, c is not the complete Binary Tree. a b c d (9) A Binary Tree will have a nodes on its level i at most. a.2i b. 2i c.2i+1 d.2i-1 (10) If the Binary Tree T2 is transformed from the Tree T1, then the postorder of T1 is the b of T2. a. preorder b. inorder c. postorder d. level order (11) In the following sorting algorithm, c is an unstable algorithm. a. the insertion sort b. the bubble sort c. quicksort d. mergesort (12) Assume there is a ordered list consisting of 100 data items, using binary search to find a special item, the maximum comparisons is d . a. 25 b.1 c. 10 d.7 (13) The result from scanning a Binary Search Tree in inorder traversal is in c order. a. descending or ascending b. descending c. ascending d. out of order (14) The d case is worst for quicksort. a. the data which will be sorted is too larger. b. there are many same item in the data which will be sorted . c. the data will be sorted is out of order d. the data will be sorted is already in a sequential order. (15) In a Binary Tree with n nodes, there is a non-empty pointers. a. n-1 b. n+1 c. 2n-1 d.2n+1 (16) In a undirected graph with n vertexs, the maximum edges is b . a. n(n+1)/2 b. n(n-1)/2 c. n(n-1) d.n2 (17) The priority queue is a structure implementing c . a. inserting item only at the rear of the priority queue.
1、单选题（共 20 道试题，共 100 分。）得分：100 1. 把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A. 唯一的 2. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行 比较，将其放入已排序序列的正确位置上的方法，称为（）。 A. 希尔排序 C. 插入排序 3. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。 D. n的平方 4. 设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr (15)=4;addr (38)=5;addr (61)=6;addr (84)=7，如用二次探测再散列处理冲突，关键字为49的结点的地址 是（）。 D. 9 5. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 6. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的 一端的方法，称为（）。 A. 希尔排序 7. 用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴25，84，21，47，15，27，68，35，20；⑵20，15，21，25，47，27，68，35，84；⑶15，20，21，25，35，27，47，68，84；⑷15，20，21，25，27，35， 47，68，84。则所采用的排序方法是（）。 D. 快速排序 8. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。 A. k1 9. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输 出的顶点序列是（）。 A. 逆拓朴有序的
《空间数据结构基础》第四讲习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( √ ) 2、串是一种数据对象和操作都特殊的线性表。( √ ) 3、只包含空白字符的串称为空串。( × ) 4、稀疏矩阵压缩存储后，必会失去随机存取功能。( × ) 5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。( √ ) 6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。（×） 7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（×） 二、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。 A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG 3、串的长度是指（ B ） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 三、填空题 1、串是一种特殊的线性表，其特殊性表现在数据元素为字符，操作集也不同；两个串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。 2、设正文串长度为n，模式串长度为m，则串匹配的Brute－Force算法的时间复杂度为 O(m*n) ；KMP算法的时间复杂度为 O(m+n) 。 3、已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为 1340 。 四、综合题 1、KMP算法较Brute-Force算法有哪些改进? 【参考解答】
数据结构 一、单项选择题 1．数据的最小单位是_A___。 A．数据元素 B.记录 C.数据对象 D.数据项 2. 对于一个具有n个结点和e条边的无向图，若采用邻接表表 示，所有边链表中边结点的总数为__C__。 A. e/2 B.e C.2e D.n+e 3. 数组a[1..6,1..5] （无0行0列）以列序为主序顺序存储， a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是___A_。 A.1026 B.1040 C.1042 D.1046 4.某线性表常发生的操作为删除第一个数据元素和在最后一个 元素后添加新元素，采用__D__的存储结构，能使其存储效率和时间效率最高。 A．单链表B．仅用头指针的循环链表C．双向循环链表D．仅用尾指针的循环链表 5. 在一个单链表中，已知q所指向的结点是p指向的结点的直接 前驱结点，若在q所指向的结点和p指向的结点间插入s所指向的结点，则执行 C ___ 。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q; 6. 若循环队列使用C数组A[m]存放其数据元素，已知头指针 front指向队首元素，尾指针rear指向尾元素后的空单元，则当前队列中的元素个数为___A_。 A.(rear-front+m)%m B. rear-front+1 C. rear-front D. rear-front-1 7. 栈和队列的共同点是___C_。 A.先进先出 B. 后进先出 C.只允许在端点处插入和删除元素 D. 运算受限的线性表