第五章 数据结构与算法基础
第五章数据结构与算法基础
5.1 数据结构与算法的概念
随着计算机科学与技术的发展，计算机技术已渗透到国民经济的各行各业和人们日常生活的方方面面。计算机已不仅用于数值计算，而更多地用于非数值计算，其加工处理的对象从纯粹的数值数据发展到字符、文字、表格、声音、图形、图像等各种复杂的具有一定结构的数据。为了更有效地处理各种数据，开发出高清晰、高效率、高可靠的软件，就必须对处理数据的特性、数据间的关系以及数据在计算机中的表示与操作进行深入的研究。这就是“数据结构”这门学科形成和发展的背景。
5.1.1 数据结构基本概念
数据（data）是指计算机可以保存和处理的信息。
数据元素（data element）是构成数据的基本单位，在计算机程序中通常作为一个整体进行处理。一个数据元素可以由一个或多个数据项组成。数据元素也称为元素、结点（node）或记录（record）。
数据项（data item）是指数据中不可分割的、含有独立意义的最小单位，也称字段（field）或域。
【例5－1】实现对某高校的教职工档案进行管理，设每位教职工档案内容包括工号、姓名、性别、年龄、职称等，则每位教职工的工号、姓名、性别、年龄、职称等各项就是数据项，每位教职工的所有数据项就构成一数据元素。
显然，如果没有将属于同一个人的有关数据项集中构成一数据元素、数据元素之间没有按照一定的规则组织起来，则对这些数据的操作将是十分困难的甚至是无法实现的。
数据结构是研究数据及数据元素之间关系及其操作实现算法的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。
1.数据的逻辑结构
数据的逻辑结构就是数据元素之间的逻辑关系。可表示为：
Data_Structure =(D，R)
其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。
根据数据元素之间关系的不同特性，数据结构可分为线性数据结构和非线性数据结构。
（1）线性结构的逻辑特征是除第一个结点和最后一个结点外，其他所有结点都有且只有一个直接前趋和一个直接后继结点。
（2）非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。
2.数据的存储结构
数据的逻辑结构是面向应用问题的，是从用户角度看到的数据的结构。数据必须在计算机内存储，数据的存储结构(storage structure)是研究数据元素和数据元素之间的关系如何在计算机中表示，是逻辑数据的存储映像，它是面向计算机的。
实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。通常，数据在存储器中的存储有四种基本的映像方法。
（1）顺序存储结构（Sequential Storage Structure）：把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，它主要用于线性数据结构，非线性的数据结构也可以通过某种线性化
的方法来实现顺序存储。
（2）链式存储结构（Linked Storage Structure）：链式存储结构把逻辑上相邻的两个元素存放在物理上不一定相邻的存储单元中，结点间的逻辑关系是由附加的指针字段表示的。链式存储结构的特点就是将存放每个数据元素的结点分为两部分：一部分存放数据元素(称为数据域)；另一部分存放指示存储地址的指针(称为指针域)，借助指针表示数据元素之间的关系。
（3）索引存储结构（Index Storage Structure）：在存储结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能惟一标识一个结点的数据项，地址则指向结点信息的存储位置。
（4）散列存储结构：根据结点的关键字值计算出该结点的存储地址。即在数据元素与其在存储器上的存储位置之间建立一个映像关系F，根据关键字值和映像关系F就可以得到它的存储地址，即D=F(E)，E是要存放的数据元素的关键字值，D是该数据元素的存储位置。哈希表是散列存储结构中最常用的一种方法。
3．数据的运算
数据的运算是定义在数据逻辑结构上的操作，每种数据结构都有一个运算的集合。常用的运算有检索、插入、删除、更新、排序等。运算的具体实现要在对应的存储结构上进行。
5.1.2 算法
研究数据结构的目的在于获得好的算法设计。
1.算法及其特征
算法(algorithm)是对某一问题求解步骤的一种描述，它具有以下五个特征：
（1）输入(input)：算法有零个或多个输入。
（2）输出(output)：算法执行结束后，至少有一个输出。
（3）确定性(definiteness)：算法的每一步都有确切的定义，没有二义性。
（4）可执行性(effectiveness)：算法的每一步都是可操作的。
（5）有穷性(finiteness)：算法必须在执行有穷步之后结束。
2.算法的描述
描述一个算法有多种方法，常用的描述方法有自然语言、伪码、流程图、类–PASCAL 语言、C语言等。本章使用C语言作为描述算法的工具。
3.算法的性能标准
算法的性能主要有以下几个标准：
（1）正确性(correctness)：算法的执行结果应与预先规定的功能和性能相符合。
（2）简明性(simplicity)：一个算法应当思路清晰，易于阅读、理解与交流，便于调试、修改和扩充。
（3）健壮性(robustness)：一个好的算法不但在输入正确的情况下能得到正确的输出，而且在输入不合法数据时，也应能做适当处理（如给予输出提示信息），不至于引起严重后果。
（4）效率(effeciency)：一个好的算法应尽量缩短运行时间，尽量少地占用存储空间，即有高的时间效率和空间效率。
5.1.3 算法分析
评价一个算法的优劣，除了正确性、简明性和健壮性外，算法的时空效率是极其重要的。算法分析的目的在于通过对算法执行时间和占用空间的分析，寻求算法的优化。因此，算法分析主要就是分析算法的时间复杂度和空间复杂度。
时间复杂度：依据算法编制成程序后，在计算机上运行时所消耗的时间。
空间复杂度：依据算法编制成程序后，在计算机执行过程中所需要的最大存储空间。 1. 时间复杂度
一个算法的时间复杂度是指随着问题规模的变化，算法运行时间的变化情况，它是被处理问题规模的函数。时间复杂度一般都采用渐近时间复杂度表示。
定义：设f(n)和g(n)是定义在正整数n 上的正函数，如果存在两个正常数c 和n 0，使得当n ≥n 0时，有f(n)≤cg(n)，则记作f(n)=O(g(n))。
大O(bit-Oh notation)记号用以表达一个算法运行时间的上界。当一个算法具有O(g(n))的运行时间时，是指该算法在计算机上的实际运行时间不会超过g(n)的一个常数倍。
使用大O 记号表示的算法的时间复杂度，称为算法的渐近时间复杂度(asymptotic complexity)。
定理：如果f(n)=a m n m
+a m －1n
m －1
+…+a 1n+a 0是m 次多项式，则f(n)=O(n m
)。
证明：取n 0=1，当n ≥n 0时，有 f(n)= a m n m
+a m －1n
m －1
+…+a 1n+a 0 ≤|a m |n m +|a m －1|n
m －1
+…+|a 1|n+|a 0|
≤(|a m |+|a m －1|/n+…+|a 1|/n
m －1
+ |a 0|/n m )n m
≤(|a m |+|a m －1|+…+|a 1|+|a 0|)n m
取c=|a m |+|a m －1|+…+|a 1|+|a 0|，得f(n) ≤c n m
=O(n m
)，定理得证。
【例5－2】下面算法实现求一个数组元素的累加和，计算该算法的时间复杂度。 int sum(int list[],int n) { /* 执行次数 */ int sum=0.0; for (int i=0; i 时间复杂度为：(n+1)+n+1=2n+2，记为： O(n) 【例5－3】下面过程实现两矩阵乘法，计算该过程的时间复杂度。 /*执行次数*/ for(i=0; i */ for(k=0; k (n+1) */ c[i][j]+=a[i][k]*b[k][j]; /* =n 3 */ } 时间复杂度为：n+1+n(n+1)+ n 2 + n 2 (n+1) + n 3=2 n 3 +3 n 2 +2n+1 记为： O(n 3 ) 从例5－2和例5－3可看出，可以通过算法中重复执行次数最多的语句的频度来估算算 法的时间复杂度。 常见的渐近时间复杂度以及大小关系如下： O(1)＜O(log 2 n)＜O(n)＜O(nlog 2 n)＜O(n2)＜O(n3)＜O(2n) 。 2. 空间复杂度 一个算法的实现所占用的存储空间主要包括：指令、常数、变量所占用的存储空间；输入数据所占用的存储空间；算法执行时必需的辅助空间。前两种空间是计算机运行时所必须的。通常，把算法在执行时所需的辅助空间的大小作为分析算法空间复杂度的依据。 与算法时间复杂度的表示一致，也用辅助空间大小的数量级来表示算法的空间复杂度，仍然记为：O(x)。常见的几种空间复杂度有：O(1)，O(n)，O(n2)，O(n3)等。 事实上，一个问题的算法实现，时间复杂度和空间复杂度往往是相互矛盾的，要降低算法的执行时间就要以使用更多的空间为代价，要节省空间就可能要以增加算法的执行时间作为代价，两者很难兼顾。因此，只能根据具体情况有所侧重。同时，还必须注意算法的清晰性。除非在一些特殊场合，否则，在现代程序设计中，并不提倡一味强调算法的效率而牺牲算法的清晰性。 5.2 线性表 5.2.1 线性表的定义及操作 线性表(Linear-list)是n(n≥0)个数据元素的有限序列。 记为：(a 1, a 2 , ..., a n-1 ., a n ) 其中元素个数n称为表的长度，n = 0时，称此线性表为空表。 表元素又称为结点，其内容可以是一个简单类型的数据，也可以是一复杂结构的数据，如可以是一整数，也可以是表示一个人的档案信息。但在同一个线性表中的元素，其数据类型是完全一样的。 线性表中各元素在表中的位置确定了它们在表中的先后次序。若n≥1，则a 1 为第一元 素，a n 为最后一个元素。元素a i-1 先于a i ，称a i-1 为a i 的前驱，a i 为a i-1 的后继；并且第一个 元素a 1无前趋，最后一个元素a n 无后继，其它元素a i (1 i-1 和一个直接后继a i+1 。 【例5－4】由26个大写英文字母组成的线性表：(A，B，C，...，Z) 【例5－5】根据【例5－1】中教职工档案信息组成的线性表： 线性表的基本操作主要有： (1) Initiate(L) 初始化线性表L，设置为空表。 (2) Length(L) 求线性表的表长。 (3) Get(L，i) 取线性表中的第i个元素。 (4) Location(L，x) 确定数据元素x在表中的位置。 (5) Insert(L，i，x) 在线性表中第i个元素之后(或之前)插入一个新元素x。 (6) Delete(L，i) 删除线性表中的第i个元素。 (7) Empty(L) 判断线性表是否为空。 (8) Clear(L) 将已知的线性表清理为空表。 线性表的操作还有：对有序表的插入和删除；按某种要求重排线性表中各元素的顺序；按某个特定值查找线性表中的元素；两个线性表的合并等。 5.2.2 线性表的顺序存储结构 线性表的顺序存储结构就是将线性表的元素按其逻辑次序依次存放在一组地址连续的存储单元里，简称顺序表。 由于线性表的所有数据元素的数据类型完全一样，因此每个元素在存储器中占用的空间大小相同，假设线性表第一个元素存放的地址为LOC(a 1)，每个元素占用的空间大小为L 个字节，则元素a i 的存放地址为： LOC(a i )＝LOC(a 1)＋L*(i －1) 可见，只要确定了顺序表的起始地址，顺序表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。 通常可用一结构体来描述顺序表： #define MAXLEN 200 /*数据元素个数的最大值*/ typedef int ElemType ； /*可根据需要定义为其它数据类型*/ typedef struct { ElemType elem[MAXLEN]； /*数组域*/ int length ； /*表长域*/ } Sqlist ； /*结构体类型名*/ 结构体里的ElemType 代表数据元素的类型，它可以是一简单数据类型（如表示一个整型数）,也可以是用于表示多个数据项的结构类型（如个人档案信息）。elem 是一维数组名，用于存放表中各数据元素。MAXLEN 代表数组的容量，应根据问题的规模设置，并留有一定的余量。length 是线性表的长度，用于存放表中数据元素的实际个数。Sqlist 是typedef 定义的结构体类型名，在此之后可以用它说明结构体变量，用于描述一实际顺序表。 例如：Sqlist s ； 说明s 是结构体类型的变量，用于存放一实际顺序表。下面算法的线性表顺序存储结构均以此结构表示。 1．元素的插入算法 已知顺序表 (a 1，a 2，…，a i-1，a i ，…，a n )，要在第i 个位置插入一个元素x ，使线性表变为(a 1，a 2，…，a i-1，x ，a i ，…，a n )。其算法思路是： (1) 将第n 至第i 个元素逐个后移一个存储位置，腾出第i 个位置空间； (2) 将x 插入到第i 个位置； (3) 线性表的长度加1。 【算法5－1】 int insert(Sqlist *v, int i, ElemType x) /*将元素x 插入到线性表v 中的第i 个位置，若插入成功，则返回1；否则，返回0*/ { int j; if ((i<1) || (i>v->length+1) || (v->length== MAXLEN)) { printf(" Error ！\n"); /*插入位置出错或线性表已满*/ return 0; } for (j=v->length-1; j>=i-1; j--) /*将第n 至第i 个元素逐个后移一个存储位置*/ v->elem[j+1]=v->elem[j]; v->elem[i-1]=x; /*插入元素x */ v->length =v->length+1; /*线性表长度加1*/ return 1; } 2．元素的删除算法。 已知顺序表 (a 1，a 2，…，a i-1，a i ，a i+1，…，a n )，要删除第i 个元素a i ，线性表变为(a 1，a 2，…，a i-1，a i+1，…，a n )。其算法思路是： (1) 将第i+1至第n 个位置上的元素依次向前移动一个存储单位； (2) 将线性表的长度减1。 【算法5－2】 int delete(Sqlist *v, int i) /*将线性表v 中的第i 个元素删除，若删除成功，则返回1；否则，返回0*/ { int j; if ((i<1) || (i > v->length)) { printf("" Error ！\n""); /*要删除的元素不存在*/ return 0; } for (j=i; j<= v->length-1; j++) /*将第i+1至第n 个元素逐个前移一个存储位置*/ v->elem[j-1]=v->elem[j]; v->length--; /* 线性表长度减1 */ return 1; } 可见，在顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其算法时间主要耗费在元素的移动上，而移动元素的个数取决于插入或删除元素的位置。 假设p i 是在第i 个元素之前插入一个元素的概率, 而此时移动元素的次数是(n-i+1)。插入位置i 的取值范围是[1，n+1]，则在长度为n 的线性表中插入一个元素时所需移动元素次数的平均值为： 假设q i 是删除第i 个元素的概率，而此时移动元素的次数是(n-i)。删除位置i 的取值范 围是[1，n]，则在长度为n 的线性表中删除一个元素时所需移动元素次数的平均值为： 如果在线性表的任何位置插入或删除元素的概率相等，即 则： 1n 1p i +=n 1q i =2n 1)i (n 1n 1E 1n 1i in = +-+=∑ +=∑=-= -= n 1 i de 2 1 n i)(n n 1E ∑ =-=n 1i i de i) (n q E 1)i (n p E 1 n 1i i in +-=∑ += 其算法的时间复杂度均为O(n)。 5.2.3 线性表的链式存储结构 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也是相邻的。因此，可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。其缺点是： （1）在做插入或删除操作时，需移动大量元素（平均要移动一半的元素），效率较低； （2）在给长度变化较大的线性表预先分配空间时，必须按最大空间分配，使存储空间不能得到充分利用； （3）必须连续存放； （4）表的容量难以扩充，实际应用中可能出现容量不足的情况。 一般情况下，线性表的顺序存储结构适合于表中元素变动较少的线性表，否则，则应使用链式存储结构。 1．单链表 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以是连续的，也可以是不连续的。这样，逻辑上相邻的元素在物理位置上就不一定是相邻的，为了能正确反映元素的逻辑顺序，就必须在存储每个元素的同时，存储其直接后继元素的存储位置。这时，存放数据元素的结点至少应包括两个域，一个域存放该元素的数据，称为数据域(data)；另一个域存放后继结点在存储器中的地址，称为指针域或链域(next)。这种链式分配的存储结构称为链表。数据元素的结点结构如下： typedef int ElemType ； typedef struct node{ ElemType data; /*数据域，可以是其他基本数据类型或构造类型*/ struct node *next; } NODE; 一般情况下，链表中每个结点可以包含若干个数据域和指针域。若每个结点中只有一个指针域，则称此链表为线性链表或单链表，否则被称为多链表。 【例5－6】设有线性表：(mouse, cattle, tiger, rabbit, snake)，用不带头结点链表表示如图5.1所示，用带头结点链表表示如图5.2所示。 图5.1 线性表的链式存储结构 图5.2 带头结点线性表的链式存储结构 在逻辑状态示意图5.1中，结点的指针域用箭头指示，用于表示线性链表结点间的相邻关系。逻辑结构的表示非常形象、清晰。在此单链表中，head 是指向单链表中第一个结点的指针，我们称之为头指针；最后一个元素snake 所在结点不存在后继结点，因而其指针域为―空‖(用NULL 或 ∧ 表示) 。 可见，用单链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个数据元素其存储的物理位置不要求相邻， 因此，这种存储结构为非顺序映像或链式映像。在使用中，我们只关心数据元素的逻辑次序而不必关心它的真正存储地址。 head head 为了简化链表的算法，通常在单链表第一个元素所在的结点之前附设一个结点，即头结点。头结点的指针域用于存储第一个元素所在结点的位置；数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息。若线性表为空表，则头结点的指针域为―空‖。以下算法中均使用带头结点的链表。 2．单链表的运算 （1）单链表的建立 【算法5－3】 NODE *creatlink( ) { NODE *head, *p, *s; int num; s = (NODE *)malloc(sizeof(NODE)); s -> next = NULL; head = s, p = s; scanf("%d", &num); while (num!=0) { s = (NODE *)malloc(sizeof(NODE)); s -> data = num; p -> next = s; p = s; scanf("%d", &num); } p -> next = NULL; return head; } 标准函数malloc(sizeof(NODE)) 是从可利用空间表中申请存储一新结点所需的内存空间，返回该结点的首地址，若内存空间不足，则其返回值为0，故为了提高程序的健壮性，最好申请后加以判断后再做处理。 算法中用输入为0时做为结束标志，应用中应根据实际情况确定合适的结束标志。 “算法5－3”采用“尾插入”法，即将新结点插入到链表的最后一个元素后，也可采用“前插入”法，即将新结点插入到链表的第一个元素前，请读者自行编写。 （2）单链表的查找 链表存储结构不是一种随机存取结构，要查找单链表中的一个结点，必须从头指针出发，沿结点的指针域逐个往后查找，直到找到要查找的结点为止。 【算法5－4】 NODE * Location(NODE *head, ElemType x) /*在头指针head中查找数据元素x的位置，若查到，返回其位置，否则，返回NULL */ { NODE *p; p = head -> next; while (( p!= NULL) && (p -> data != x )) p = p -> next; return p; } （3）单链表的插入 设有线性表(a 1，a 2，...，a i-1，a i ，...，a n )，用带头结点的单链表存储，头指针为head ，要求在线性表中第i 个元素a i 之前插入一个值为x 的元素。 算法思路：将指针p 指向元素a i 的前驱结点a i-1，生成一个数据域为x 的新结点s ，修改结点p 和结点s 的指针域，将x 插在a i-1与a i 之间。即s->next = p->next ；p->next = s 。插入结点s 后单链表的逻辑状态如图5.3所示。 图5.3 在带头结点单链表中插入值为x 的元素 【算法5－5】 void insert(NODE *head, int i, ElemType x) { NODE *p, *s; int j=0; p = head; while (( p != NULL) && (j < i-1)) /*使p 指向第i-1个结点*/ { p = p -> next; j++; } if ((p == NULL) || (j > i-1)) printf( ''i 值不合法 \n''); else { s = (NODE *)malloc(sizeof(NODE)); s -> data = x; s -> next = p -> next; p -> next = s; } } （4） 单链表的删除 设有线性表(a 1，a 2，...，a i-1，a i ，...，a n )，将结点a i 从链表中删除。 算法思路：将指针p 指向元素a i 的前驱结点a i-1，然后改变链接，即只要将待删除结点的指针域内容赋予p 结点的指针域即可。 图5.4 在单链表中删除第i个结点 【算法5－6】 void delete(NODE *head, int i) { NODE *p, *s; int j=0; p = head; while (( p->next != NULL) && (j < i-1)) { p = p -> next; j++; } if ((p == NULL) || (j > i-1)) printf( ''i值不合法\n''); else { s = p -> next; p -> next = s -> next; free(s); } } 标准函数free(s)将s指向的结点归还给可利用空间表。 3. 循环链表和双向链表 （1）循环链表 将最后一个结点的指针域指向头结点的链表称为循环链表。从循环链表中任一结点出发均可找到表中其它任一结点。为使运算方便，循环链表一般也都设表头结点。 （2）双向链表 在每个结点上除数据域data外，设置二个指针域，其中一个指针域prior指向其前趋结点，另一个指针域next指向其后继结点，就得到双向链表。 双向链表通常也可设置头结点，也可将双向链表的头结点和尾结点链接起来组成双向循环链表。 在双向链表中，可从任一结点出发，分别可往前或往后查找其他任一接点。与单链表相比，双向链表的插入与删除等操作更加简单，当然，双向链表增加了一个指向前趋结点的指针域，即增加了存储空间的开销。 设p是指向链表中任一结点的指针，则有： p->next->prior = p->prior->next = p （a ）插入。在双向链表中第i 个结点前插入元素x 。 思路：搜索插入位置，找到第i 个结点用指针p 指示，然后申请新结点s 并改变链接。 图5.5 双向链表的插入 插入时相关操作序列为： ① s->data = x; ② s->prior = p->prior; ③ s->next = p; ④ (p->prior)->next = s; ⑤ p->prior = s 。 （b ）删除。在链表中删除第i 个结点。 思路：找到删除位置p ，然后改变链接，最后释放被删结点p 。 删除时相关操作序列为： (p->prior)->next = p->next; (p->next)->prior = p->prior; 4. 应用举例 【例5－7】 设计算法：求头指针为head 的单链表中的结点数目。 int length(NODE *head) { NODE *p; int i=0; p = head-> next; /*指向第一个结点*/ while ( p != NULL ) { p = p -> next; i++; } return i; } 【例5－8】设计算法：将一个带头结点的单链表A 分解为两个带头结点的单链表A 和B ，使得A 表中含有原表中序号为奇数的元素，B 表中含有原表中序号为偶数的元素，且保持其相对顺序。 void disA(NODE *A, NODE **B) { NODE *r, *p, *q; …… *B = (NODE *)malloc(sizeof(NODE)); r = *B; p = A->next; while ((p!=NULL) && (p->next!=NULL)) { q = p->next; p->next = q->next; r->next = q; r = q; p = p->next; } r->next = NULL; p->next = NULL; } 5.3 栈 1．栈的定义及其操作 栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。其中允许进行插入和删除操作的一端称为栈顶(top)，而表中固定的一端称为栈底(bottom)。栈中元素个数为零时称为空栈。例如，线性表s为： s=(a 0，a 1 ，…，a n ) 当我们把它看作栈来使用时，可以描述为图5.6所示的形式。其中，a 1是栈底元素，a n 是栈顶元素，入栈是指插入数据元素，出栈是指删除数据元素。 图5.6 栈的结构图 从图5.6中可以看出，进栈是把数据元素放在栈顶，即最后进栈的数据元素在栈顶，而出栈是把栈顶的数据元素删除。因此，对于栈来说，最后进栈的数据元素最先出栈，故把栈称为后进先出(LIFO-Last In First Out) 或先进后出(FILO-First In Last Out)的数据结构。 在中断系统、子程序调用等场合都离不开栈。 栈的基本操作有： (1) initstack(s) 初始化空栈s。 (2) empty(s) 判定s是否为空栈。 (3) push(s，x) 进栈操作，将数据元素x插入到栈S的栈顶。 (4) pop(s) 出栈操作，若栈s不是空栈，则取出栈顶元素。 2．栈的表示和实现 栈是线性表的一种特例，因此，表示线性表的方法同样适用于栈。 （1）栈的顺序存储结构——顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设置指针Top 指示栈顶元素的当前位置。空栈的栈顶指针值为-1。设用数组datatype elements[MAXSIZE]表示栈，则对非空栈，elements [0]为最早进入栈的元素，elements [top]为最迟进入栈的元素，即栈顶元素。 当top= MAXSIZE-1时，表示栈满，此时若有元素入栈则产生栈的―上溢‖(overflow)；反之，top= -1表示栈空，若此时再进行作出栈操作，则将发生―下溢‖(underflow)。 栈的顺序存储结构定义为： #define MAXSIZE 200 /*栈中数据元素个数的最大可能值*/ typedef int ElemType ； typedef struct{ ElemType elem[MAXSIZE]； int top； } stack； 其中，MAXSIZE是栈的容量，ElemType 是栈中数据元素的数据类型（如可为int 型或其它类型），top指示当前栈顶位置，栈底位置为0。 1）置空栈：将栈进行初始化，将栈顶指针top初始化为–1。 【算法5－7】 void initstack (stack *s) /* 建立一个空栈s */ { s=(stack *)malloc(sizeof(stack)); s->top= -1； } 2）判栈空：在进行出栈操作时，应先判断栈是否为空。 【算法5－8】 int empty(stack *s) /* s是否为空栈，若是返回1，否则返回0 */ { if (s->top == -1) return (1)； else return (0)； } 3）进栈：将数据元素x压入栈顶。 【算法5－9】 int push (stack *s, ElemType x) /*压栈，若成功返回1，否则返回0 */ { if (s->top == MAXSIZE-1) { printf ("Stack Overflow\n")；/* 上溢*/ return (0)； } s->top++； s->elem[s->top]=x； return (1)； } 4）出栈：首先判断栈是否为空，若空则表示出栈失败，返回0；否则返回1。 【算法5－10】 int pop(stack *s , ElemType *x) /*x 存放出栈的数据元素*/ { if (empty(s)) { printf ("Stack Underflow\n")； /* 下溢 */ return (0)； } *x= s->elem[s->top]; s->top--; return (1); } (2) 栈的链式存储结构——链栈 对于顺序栈来说，其最大缺点是：栈的容量不易确定，在实际应用中可能导致浪费存储空间，也可能导致栈的容量不足，产生上溢现象。采用链式存储结构可较好解决顺序栈存在的问题，当然，这也使栈中的每个元素增加一个指针域，操作也复杂一些。 栈的链式存储结构结点类型同单链表相同，其算法读者可参照单链表和顺序栈的有关内容自行编写。 5.4 队列 1．队列的定义及其操作 队列(Queue)也是一种特殊的线性表。它只允许在表的一端进行插入操作，而在另一端进行删除操作。允许删除操作的一端称为队头(Front)，允许插入操作的一端称为队尾(Rear)。 在队列中，先进入的成员总是先离开队列，后进入的成员总是后离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称为FIFO 表。 在键盘的输入、操作系统中的批处理调度等场合都需要建立队列。 当队列中没有元素时称为空队列。在空队列中依次加入元素a 1, a 2, … , a n 之后，a 1是队头元素，a n 是队尾元素。显然出队的次序也只能是a 1, a 2, …, a n , 也就是说队列的改变是依先进先出的原则进行的。图5.7是队列的示意图。 图5.7 队列的结构图 队列的基本操作有： （1）iniqueue(sq) 置sq 为一个空队列。 （2）empty(sq) 判断队列sq 是否为空队列。 （3）enqueue(sq, x) 将元素x 插入队列sq 的队尾, 称为入队。 （4）dequeue(sq) 取出队列sq 的队头元素，简称为出队。 2．队列的表示和实现 a 1 a 2 a 3 a n … 队头 front 队尾 rear 出队 入队 队列也是线性表的一种特例，因此，表示线性表的方法同样适用于队列。 （1）队列的顺序存储结构——顺序队列 队列的顺序存储结构称为顺序队列。顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也必须用一个数组来存放当前队列中的元素。由于队列的队头和队尾的位置均是变化的，因而需要设置两个指针，分别指示当前队头元素和队尾元素在数组中的位置。队列的顺序存储结构定义为： #define MAXSIZE 200 /*队列中数据元素个数的最大可能值*/ typedef int ElemType; typedef struct { ElemType elem[MAXSIZE]; int front ，rear; } seqqueue; 为使操作方便，通常规定头指针front 总是指向当前队头元素的前一个位置，尾指针rear 指向当前队尾元素的位置。初始时，队列的头、尾指针指向数组空间下界的前一个位置，在此设置为–1。若不考虑溢出，则入队运算可描述为： sq->rear++; /* 尾指针加1 */ sq->data[sq->rear]=x; /* x 入队 */ 出队运算可描述为： sq->front++; /* 头指针加1 */ 图5.8说明了在顺序队列中进行出队和入队运算时队列中的数据元素及其头、尾指针的变化情况。 图5.8 顺序队列运算时的头、尾指针变化情况 当E 元素入队后，sq->rear=4，入队操作已无法继续进行，但事实上队列中尚有3个空位，这种情况称为“假溢出”。为解决这一问题，可以在每次出队时将整个队列中的元素向前移动一个位置，也可以在发生“假溢时”将整个队列中的元素向前移动直至头指针为–1，但这两种方法都会引起大量元素的移动，所以在实际应用中极少采用。通常的解决方法是让队列的头尾相连，构成一个环型队列，如图5.9所示。当进行入队操作时，sq->rear 按顺时针方向前进一个位置，出队操作时，sq->front 按顺时针方向前进一个位置；当sq->rear 、sq->front 的值为MAXSIZE-1时，若此时再进行加1操作，则将其值设置为0。 4 3 2 1 0 sq -> rear ＝－1 sq -> front ＝－1 4 3 2 1 0 sq -> rear ＝2 sq -> front ＝－1 4 3 2 1 0 sq -> rear ＝2 sq -> front ＝2 4 3 2 1 0 sq -> rear ＝4 sq -> front ＝2 ( a ) 空队( b ) ABC 相继入( d ) DE 相继入( c ) ABC 相继出 图5.9 循环队列 循环队列中队空和队满时，队头指针和队满指针都会碰到一起，为了区别队列空与满的二种状态，一般约定：若sq->rear==sq->front ，队列为空，不能进行出队操作；若(sq->rear+1)%MAXSIZE==sq->front ，队列为满，不能进行入队操作。 在循环队列上实现的基本操作如下： 1) 置空队 【算法5－11】 void iniqueue(seqqueue *sq) / * 置队列sq 为空队 */ { sq=( seqqueue *)malloc(sizeof(seqqueue)); sq->front=0; sq->rear=0; } 2) 判断队空 【算法5－12】 int empty (seqqueue * sq) /* 判别队列sq 是否为空，若为空，返回1，否则返回0 */ { if (sq->rear= =sq->front) return (1); else return (0) ; } 3) 入队 【算法5－13】 int enqueue (seqqueue * sq, ElemType x) /* 将新元素x 插入队列sq 的队尾 */ { if (sq->front==(sq->rear+1)％ MAXSIZE) { printf ("queue is full"); return (0); } /* 队满溢出 */ sq->rear=(sq->rear+1)％MAXSIZE ; sq->elem[sq->rear]=x; return (1); } 4) 出队 【算法5－14】 front sq → int * dequeue (seqqueue * sq, ElemType *x) /* 删除队列sq的头元素，成功返回1，失败返回0，并返回该元素*/ { if (empty(sq)) { printf ("queue is empty"); return 0;} /* 队空*/ sq->front=(sq->front+1) % MAXSIZE; *x= sq->elem[sq->front]; return (1); } (2) 队列的链式存储结构——链队 对于顺序队来说，其缺点与顺序栈类似：队列的容量不易确定，在实际应用中可能导致浪费存储空间，也可能导致队列的容量不足，产生溢出现象。采用链式存储结构可较好解决顺序队列存在的问题。 队列的链式存储结构结点类型同单链表相同，其算法读者可参照单链表和顺序队的有关内容自行编写。 5.5 树与二叉树 5.5.1 树的基本概念 在计算机科学中，树型结构是一种应用广泛的非线性数据结构，它很类似自然界中的树，它为计算机应用中出现的具有层次关系或分支关系的数据提供了一种理想的表示方式。 树的定义如下： 树(Tree)是n(n≥0)个结点的有限集合。当n=0时称为空树，否则在任一非空树中： (1) 有且仅有一个被称根（root）的结点； (2) 当n＞1时，除根结点以外的其余结点可分为m(m＞0)个互不相交的集合T1，T2，…，Tm，且其中每一个集合本身又是一棵树，并称其为根的子树(SubTree)。 这是一个递归定义，即在树的定义中又用到了树，它显示了树的特性。即一棵树是由根及若干子树构成的，而子树又可由更小的子树构成。 在树中，除根结点没有前趋结点外，其余结点有且只有一个前趋结点，各结点可有多个后继结点或没有后继结点。 图5.10 树的示意图 图5.10是一棵由11个结点组成的树，其中A为根结点，其余结点分成二个互不相交的子集：T1={B，D，E，I}，T2={C，F，G，H，J，K}，T1、T2是根A的子树。T1又可分成二个互不相交的子集T11={D，I}，T12={E}，它们是B的子树；T2分成三个互不相交的子集T21={F，J，K}，T22={G}，T23={H}，它们是C的子树。 以图5.10的树为例，下面给出与树有关的基本概念。 孩子(child)：某结点子树的根称为该结点的孩子结点。 双亲(parent)：一个结点是它的那些子树的根的双亲结点。 兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如B是结点D和E的双亲结点，D和E是B结点的孩子结点，D、E互为兄弟结点。 结点的度：一个结点拥有的子树数目。如A结点的度为2，它有二个子树T1和T2；C 结点的度为3；I、E、J、K、G和H等结点的度为0，它们没有子树。 叶子结点：度为零的结点称叶子或终端结点。I、E、J、K、G和H等结点都为叶子结点。 分支结点：度不为零的结点称分支结点。B、C、D、F等为分支结点。 树的度：一棵树上所有结点的度的最大值为该树的度。图5.10的树的度为3。 边：树中两个结点的有序对 结点的层次：规定根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。 树的深度：一棵树中，结点的最大层次值就是树的深度。图5.10的树的深度为4。 有序树：树T中各子树T1，T2，…，Tn的相对次序是有意义的，则称T为有序树。在有序树中，改变了子树的相对次序就变成了另一棵树。 森林：森林是m(m≥0)棵互不相交的树的集合。 5.5.2 二叉树及其存储表示 1．二叉树的定义 一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。 图5.11是一棵二叉树，A为二叉树的根，以B为根的子树为A的左子树，以C为根的子树为A 图5.11 二叉树 根据二叉树的定义，图5.12列出了二叉树的所有可能的五种形态。图中，（1）为空二叉树；（2）为只有一个根结点的二叉树；（3）是具有左、右子树的二叉树；（4）是只有左子树的二叉树；（5）是只有右子树的二叉树。 （1） （2） （3） （4） （5） 图5.12 二叉树及其五种形态 二叉树具有两个主要特点： (1) 每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。 (2) 二叉树的子树有左、右之分，其次序不能任意颠倒。 如果一棵二叉树的深度为k ，并且含有2k –1个结点，则称此二叉树为满二叉树。如图5.13所示。满二叉树的特点是每一层都具有最大结点个数。 图5.13 满二叉树 对满二叉树的结点进行连续编号：从根结点起，自上而下逐层从左到右给每个结点编一个从1开始的顺序号。 对深度为k ，有n 个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中的编号从1到n 的结点一一对应时，称之为完全二叉树。如图5.14所示。 完全二叉树的特点： (1) 叶子只可能在层次最大的两层上出现。 (2) 最下面一层的结点都集中在该层最左边的若干位置上。 满二叉树是完全二叉树，而完全二叉树未必是满二叉树。 图5.14 完全二叉树 2．二叉树的性质 性质1：二叉树第i 层的结点数最多有2i-1 (i ≥1)个。 层次i 第i 层最多结点数 1 20 =1 2 21 =2 3 22 =4 ┇ ┇ k 2k?1 此性质读者可自行用数学归纳法证明。 性质2：深度为k 的二叉树中结点总数最多有2k –1个。 由性质1可见，深度为k 的二叉树的最大结点数为： = 2k ?1 性质3： 对任何一棵二叉树T ，如果其终端结点数为n 0，度为2的结点数为n 2，则n 0=n 2+1。 证明： (1) 设n 1为二叉树中度为1的结点数，n 为二叉树中总的结点数，则: n = n 0 + n 1 + n 2 (2) 设B 为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结点都有一个分支进入，所以 B = n-1 即 n = B+1 又，度为0的结点不产生分支，度为1的结点产生1个分支，度为2的结点产生2个分支，所以 B = n 1 + 2n 2 于是得： n = n 1 + 2n 2 + 1 (3) 由(1)和(2)得： n 0 + n 1 + n 2 = n 1 + 2n 2 + 1 故 n 0 = n 2 + 1 性质4：具有n 个结点的完全二叉树的深度为： +1 ∑=-k 1 i 1i 2 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 Java数据结构和算法 一、数组于简单排序 (1) 二、栈与队列 (4) 三、链表 (7) 四、递归 (22) 五、哈希表 (25) 六、高级排序 (25) 七、二叉树 (25) 八、红—黑树 (26) 九、堆 (36) 十、带权图 (39) 一、数组于简单排序 数组 数组（array）是相同类型变量的集合，可以使用共同的名字引用它。数组可被定义为任何类型，可以是一维或多维。数组中的一个特别要素是通过下标来访问它。数组提供了一种将有联系的信息分组的便利方法。 一维数组 一维数组（one-dimensional array ）实质上是相同类型变量列表。要创建一个数组，你必须首先定义数组变量所需的类型。通用的一维数组的声明格式是：type var-name[ ]; 获得一个数组需要2步。第一步，你必须定义变量所需的类型。第二步，你必须使用运算符new来为数组所要存储的数据分配内存，并把它们分配给数组变量。这样Java 中的数组被动态地分配。如果动态分配的概念对你陌生，别担心，它将在本书的后面详细讨论。 数组的初始化（array initializer ）就是包括在花括号之内用逗号分开的表达式的列表。逗号分开了数组元素的值。Java 会自动地分配一个足够大的空间来保存你指定的初始化元素的个数，而不必使用运算符new。 Java 严格地检查以保证你不会意外地去存储或引用在数组范围以外的值。Java 的运行系统会检查以确保所有的数组下标都在正确的范围以内（在这方面， Java 与C/C++ 从根本上不同，C/C++ 不提供运行边界检查）。 多维数组 在Java 中，多维数组（multidimensional arrays ）实际上是数组的数组。你可能期望，这些数组形式上和行动上和一般的多维数组一样。然而，你将看到，有一些微妙的差别。定义多维数组变量要将每个维数放在它们各自的方括号中。例如，下面语句定义了一个名为twoD 的二维数组变量。 int twoD[][] = new int[4][5]; 简单排序 简单排序中包括了：冒泡排序、选择排序、插入排序； 1.冒泡排序的思想： 假设有N个数据需要排序，则从第0个数开始，依次比较第0和第1个数据，如果第0个大于第1个则两者交换，否则什么动作都不做，继续比较第1个第2个…，这样依次类推，直至所有数据都“冒泡”到数据顶上。 冒泡排序的的java代码： Public void bubbleSort() { int in,out; for(out=nElems-1;out>0;out--) for(in=0;in 《数据结构与算法设计》 实验报告 ——实验二 学院：自动化学院 班级： 学号： ： 一、实验目的 按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。 二、实验容 简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： ①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 ②输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取 整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 概要设计 1、宏定义 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 2、基本函数： （1）void InitStack_char(SqStack *S) //char型栈初始化 （2）void InitStack_int(sqStack *S) //int型栈初始化 （3）void Push_char(SqStack *S,char ch) //char型元素进栈 （4）void Push_int(sqStack *S,int num) //int型元素进栈 （5）char GetTop_char(SqStack *S) //取char型栈顶元素 （6）int GetTop_int(sqStack *S) //取int型栈顶元素 （7）Status In(char c) //判断是否为运算符，若是运算符则返回，否则返回 （8）char Precede(char a,char b) //判断两运算符的先后次序 （9）Status Pop_char(SqStack *S,char &x) //char型栈出栈 （10）Status Pop_int(sqStack *S,int &x) //int型栈出栈 （11）int Operate(int a,char theta,int b) //计算a和b运算结果 3、流程图 习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相 西安科技大学 2013年硕士研究生入学考试试题A ───────────────────────────────── 科目编号：824 科目名称： 数据结构与算法设计 考生须知： 1、 答案必须写在答题纸上，写在试题或草稿纸上不给分。 2、 答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。 3、 答题必须写清题号，字迹要清楚，卷面要保持整洁。 4、 试题要随答题纸一起交回。 一、单项选择题（每小题2分，共30分） （1）并归排序的时间复杂度是（ ）。 A ．O(n 2) B ．O(nlog 2n) C ．O(n) D ．O(log 2n) （2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（ ）存储结构最节省时间。 A ．单链表 B ．单循环链表 C ．带尾指针的单循环链表 D ．带头结点的双循环链表 （3）散列文件是一种（ ）。 A ．顺序文件 B ．索引文件 C ．链接文件 D ．计算机寻址文件 （4）常用于函数调用的数据结构是（ ）。 A ．栈 B ．队列 C ．数组 D ．链表 （5）两个矩阵sn ms B A ,相乘的时间复杂度是（ ）。 A ．O(n 2) B ．O(s 2) C ．O(msn) D ．O(mn) （6）图的广度优先搜索遍历使用的数据结构是（ ）。 A ．栈 B ．队列 C ．集合 D ．树 （7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（ ）。 A ．直接前驱 B ．直接后继 C ．开始结点 D ．终端结点 （8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间复杂度是（ ）。 A ．O(n 2) B ．O(1) C ．O(n) D ．O(log 2n) （9）在链队列中执行入队操作，（ ）。 A ．需判断队是否为空 B ．限定在链表头p 进行 C ．需判断队是否为满 D ．限定在链表尾p 进行 （10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（ ）。 A ．（70，83，62，95） B ．（70，62，83，95） 数据结构与算法课程设计报告 题目 两两相连的房间问题： 一所奇怪的房子，这所房子里有n个房间，每个房间里有一些门通向别的房间，可是这些门十分奇怪，它们只能从房间a开向房间b，也就是说，一扇从a开向b的门是不能让一个人从b房间走到a房间的。你能计算一下任意两个房间之间都互相相通吗？ 问题分析 此程序需要完成如下要求：在这所房子里，从任意一个房间开始，按照开门的方向，均能够找到一个合适的路线，使得一个人能够不重复的到达其他的每一个房间，所以，需以每一个房间都为一次起始点来走向其他的房间，以此来判断这所房子里的任意两个房间之间是否互相相通。 实现本程序需要解决以下问题： 1.如何表示每一个房间，即存储房间的信息，并且还要确定这所房子里的各个房间的位置。 2.各个房间之间的门，以及门是从哪个房间开向哪个房间的该如何表示和存储的。 3.从某一个房间开始，如何走到其他各个房间，即如何对房间进行遍历。 4.为了在遍历过程中，不重复的遍历每一个房间，该如何标记已被遍历过的房间，从而只 访问未走过的房间。 5.最后通过什么的遍历方式才能判断各个房间之间是否互相相通。 数据结构的选择和概要设计 通过对题目要求的理解，我们可以用图来表示这所房子，而房子中的各个房间就相当于图中的各个结点，由于房间的门是有方向的，一扇从a开向b的门是不能让一个人从b房间走到a 房间的，从而可知该图为有向图，那么门就相当于有向图中的弧，从一个门开向另一个门即代表有向图中弧的起始点和终止点。 对于图的存储，我采用邻接表的形式来存储，并将每一个房间进行编号，对于邻接表，则需要定义一个邻接表结点类型、邻接表表头结点类型，通过表头与结点的连接而将有向图中弧的信息存储起来。那么人从任意一个房间走向另一个房间，即相当于有向图中从一个结点按照弧的信息访问其他的结点，可以采用深度优先搜索遍历。如果从每一个结点以起始点开始一次遍历就都能访问到其他结点的话则说明有向图是连通图，即该房子里的各个房间能够互相相通。定义一个全局的整形变量flag，如果是连通图的话则flag=1，否则flag=0。 程序实现的流程图如下： 《数据结构与算法》期末复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 一、填空题（每空2分，共20分） 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为（ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） ????? ?????????=n n n n a a a a a a A ,2,1,2,21,21,1 《数据结构与算法分析》课程设计教学任务书 一、课程设计的目的 数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 二、课程设计的基本要求 1. 独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 2. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 3. 按照课程设计的具体要求建立功能模块，每个模块要求按照如下几个内容认真完成： a）需求分析： 在该部分中叙述，每个模块的功能要求 b）概要设计： 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义） c）详细设计： 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组程序，每个功能模块采用不同的函数实现） 源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释 d）调试分析： 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些，问题如何解决？），算法的改进设想 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容 4. 实现的结果必须进行检查和演示，程序源代码和程序的说明文件必须上交，作为考核内容的一部分。（上交时每人交一份，文件夹的取名规则为：“学号姓名”，如“09201199王五”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收 ?．算法分析 2.1.?标 ·了解为何算法分析的重要性 ·能够??“O ”表?法来描述算法执?时间 ·了解在Python 列表和字典类型中通?操作??“O ”表?法表?的执?时间 ·了解Python 数据类型的具体实现对算法分析的影响 ·了解如何对简单的Python 程序进?执?时间检测 2.2.什么是算法分析 计算机初学者经常将??的程序与他?的?较。你也可能注意到了电脑程序常常看起来很相似，尤其是那些简单的程序。?个有趣的问题出现了，当两个看起来不同的程序解决相同的问题时，?个程序会优于另?个吗？ 为了回答这个问题，我们需要记住的是，程序和它所代表的基本算法有着重要差别。在第?章中我们说到，算法是问题解决的通?的分步的指令的聚合。这是?种能解决任何问题实例的?法，?如给定?个特定的输?，算法能产?期望的结果。从另???看，?个程序是?某种编程语?编码后的算法。同?算法通过不同的程序员采?不同的编程语?能产?很多程序。 为进?步探究这种差异，请阅读接下来展?的函数。这个函数解决了?个我们熟知的问题，计算前n 个整数的和。其中的算法使?了?个初始值为0的累加变量的概念。解决?案是遍历这n 个整数，逐个累加到累加变量。 代码2.1前n 个正整数求和（active1 ） 现在看下?的foo函数。可能第?眼看上去?较奇怪，但是进?步观察你会发现，这个函数所实现的功能与之前代码2.1中的函数基本相同。看不太懂的原因是糟糕的编码。我们没有使?好的变量命名来增加可读性，并且在累加过程中使?了多余的赋值语句。 回到前?我们提出的问题：是否?个程序会优于另?个？答案取决于你??的标准。如果你关?可读性，那么sum_of_n函数肯定?foo函数更好。实际上，在你的编程?门课程上你可能见过很多这样的例?，因为这些课程的?标之?就是帮助你编写更具可读性的程 代码2.2 另?种前n个正整数求和（ac ve2） def foo(tom): fred=0 for bill in range(1,tom+1): barney = bill fred = fred + barney return fred print (foo(10)) 序。然?，在这门课程中，我们主要感兴趣的是算法本?的特性。（我们当然希望你可以继续努?写出更具可读性的代码。） 算法分析主要就是从计算资源的消耗的?度来评判和?较算法。我们想要分析两种算法并且指出哪种更好，主要考虑的是哪?种可以更?效地利?计算资源。或者占?更少的资源。从这个?度，上述两个函数实际上是基本相同的，它们都采?了?样的算法来解决累加求和问题。 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 常用的大数据结构与算法 在学习了解这些数据结构和算法之前，引用一位前辈的话： “我们不需要你能不参考任何资料，实现红黑树；我们需要的是你能在实践当中，选择恰当的数据结构完成程序开发；在必要的时候，能在已有的数据结构基础上进行适当改进，满足工程需要。但要做到这一点，你需要掌握基础的算法和数据结构，你需要理解并应用一些高级数据结构和算法的思想。因此，在程序员这条道路上，你要想走得更远，你需要活用各种数据结构，你需要吸收知名算法的一些思想，而不是死记硬背算法本身。” 那么，工程实践当中，最常用的算法和数据结构有哪些？ 以下是Google工程师Arjun Nayini在Quora给出的答案，得到了绝大多数人的赞同。 最常用的算法 1.图搜索算法(BFS,DFS) 2.排序算法 3.通用的动态规划算法 4.匹配算法和网络流算法 5.正则表达式和字符串匹配算法 最常用的数据结构 1.图，尤其是树结构特别重要 2.Maps结构 3.Heap结构 4.Stacks/Queues结构 5.Tries树 其他一些相对比较常用的数据算法还有：贪心算法、Prim’s / Kruskal’s算法、Dijkstra’s 最短路径算法等等。 怎么样才能活用各种数据结构？ 你能很清楚的知道什么时候用hash表，什么时候用堆或者红黑色？在什么应用场景下，能用红黑色来代替hash表么？要做到这些，你需要理解红黑树、堆、hash表各有什么特性，彼此优缺点等，否则你不可能知道什么时候该用什么数据结构。 常言道： 程序=算法＋数据结构 程序≈数据结构 小编希望这些算法的掌握能够帮助大家拓宽握数据结构和算法的视野，提高算法设计和动手编程的能力。 第一章绪论 一．选择题 1．数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 2．算法分析的目的是①C，算法分析的两个主要方面是②A。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B) A．逻辑结构B．顺序存储结构 C．链表存储结构D．以上都不对 4．数据结构中，在逻辑上可以把数据结构分成：( C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（A ）。 A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 6．数据结构研究的内容是（D ）。 A．数据的逻辑结构B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面 7．链式存储的存储结构所占存储空间（A ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 8．一个正确的算法应该具有5 个特性，除输入、输出特性外，另外3 个特性是（A ）。 A．确定性、可行性、有穷性B．易读性、确定性、有效性C．有穷性、稳定性、确定性D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（A）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 10．算法分析的主要任务是（C ）。 A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系 二．解答 设有一数据的逻辑结构为：B=(D, S)，其中： D={d1, d2, …, d9} S={ 北方民族大学课程设 计 课程名称: 数据结构与算法 院(部)名称:信息与计算科学学院 组长姓名学号 同组人员姓名 指导教师姓名:纪峰 设计时间:2010.6.7----2009.6.27 一、《数据结构与算法》课程设计参考题目 （一）参考题目一（每位同学选作一个,同组人员不得重复） 1、编写函数实现顺序表的建立、查找、插入、删除运算。 2、编写函数分别实现单链表的建立、查找、插入、删除、逆置算法。 3、编写函数实现双向链表的建立、插入、删除算法。 4、编写函数实现顺序栈的进栈、退栈、取栈顶的算法。 5、编写函数实现链栈的进栈、退栈、取栈顶的算法。 6、编写函数实现双向顺序栈的判空、进栈、出栈算法。 7、编写函数实现循环队列的判队空、取队头元素、入队、出队算法。 8、编写函数实现链环队列的判队空、取队头节点、入队、出队算法。 9、编写函数实现串的，求串长、连接、求字串、插入、删除等运算。 10、分别实现顺序串和链串的模式匹配运算。 11、实现二叉树的建立，前序递归遍历和非递归遍历算法。 12、实现二叉树的建立，中序递归遍历和非递归遍历算法。 13、实现二叉树的建立，后序递归遍历和非递归遍历算法。 14、实现二叉树的中序线索化，查找*p结点中序下的前驱和后继结点。 15、分别以临接表和邻接矩阵作为存储就够实现图的深度优先搜索和广度优先搜索算法。 16、利用线性探测处理冲突的方法实现散列表的查找和插入算法。 (二)参考题目二（每三人一组，任选三个题目完成） 1.运动会分数统计（限1 人完成） 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分， 3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有合理的提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 1、线性表的各种基本操作在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。( × ) 2、一个有向图的邻接表和逆邻接表中表结点的个数一定相等。( × ) 3、先序遍历森林和先序遍历与该森林相对应的二叉树，其结果不同。( √ ) 4、不使用递归，也可实现二叉树的先序、中序和后序遍历。( √ ) 5、散列法存储的基本思想是由关键字的值决定数据的存储地址。( √ ) 6、采用折半查找法对有序表进行查找总是比采用顺序查找法对其进行查找要快。( √ ) 7、在任何情况下，快速排序方法的时间性能总是最优的。( × ) 8. 二维数组是其数据元素为线性表的线性表。( × ) 9. 拓扑排序是一种内部排序方法。( × ) 10．数据的物理结构是指数据在计算机内实际的存储形式。( × ) 11、数据元素是数据的最小单位。( × ) 12、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( √ ) 13、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × ) 14、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( × ) 15、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 16、所谓取广义表的表尾就是返回广义表中最后一个元素。( × ) 17、完全二叉树中，若一个结点没有左孩子，则它必是树叶。( √ ) 18. 二叉树只能用二叉链表表示。( × ) 19．在二叉树的第i层上至少有2i-1个结点(i>=1)( × ) 20．度为二的树就是二叉树。( × ) 21. 有e条边的无向图，在邻接表中有e个结点。( × ) 22. 有向图的邻接矩阵是对称的。( × ) 23．任何无向图都存在生成树。( × ) 24. 不同的求最小生成树的方法最后得到的生成树是相同的. ( × ) 25. 有环图也能进行拓扑排序。( × ) 26. 关键路径是AOE网中从源点到终点的最长路径。( √ ) 27．内排序要求数据一定要以顺序方式存储。( × ) 28．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。( × ) 29．直接选择排序算法在最好情况下的时间复杂度为O（N）。( × ) 30．在待排数据基本有序的情况下，快速排序效果最好。( × ) 31．快速排序总比选择排序快。( √ ) 二．单选题（） 1. 单循环链表的主要优点是( D )。 A.不再需要头指针 B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入，删除运算时，能更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 2. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( D )存储方式最节省时间。 A．顺序表B．单链表C．双链表D．单循环链表 3. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 4. 以下数据结构中哪一个是非线性结构？( D ) A. 队列 B. 栈 C. 线性表 D. 二叉树 5. 图的深度优先遍历算法类似于二叉树的( A )，广度优先遍历算法类似于二叉树的( D )。 A．先序遍历B．中序遍历C．后序遍历D．层次遍历 6. 若广义表A满足Head(A)==Tail(A)，则A为( B )。 A. ( ) B. (( )) C. (( ),( )) D. (( ),( ),( )) 7. 下列二叉树中，( A )可用于实现符号的不等长高效编码。 [试题分类]：数据结构与算法 1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。 A.操作 B.存储映像 C.关系 D.数据元素 答案:C 题型:单选题 知识点:1.2 基本概念和术语 难度:1 2.一般而言，最适合描述算法的语言是( )。 A.自然语言 B.计算机程序语言 C.介于自然语言和程序设计语言之间的伪语言 D.数学公式 答案:C 题型:单选题 知识点:1.4 算法和算法分析 难度:1 3．在下列序列中，不是线性表的是( )。 A. (‘a’,‘b’) B. (a, b) C. (‘AB’,‘CD’) D. (‘a’, b) 答案:D 题型:单选题 知识点:2.1 线性表的类型定义 难度:2 4.对于顺序表的优缺点，以下说法错误的是( )。 A.插入和删除操作较方便 B.可以方便地随机存取表中的任一结点 C.无需为表示结点间的逻辑关系而增加额外的存储空间 D.由于顺序表要求占用连续的空间，存储分配只能预先进行 题型:单选题 知识点:2.2线性表的顺序表示和实现 难度:2 5.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 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; 题型:单选题 知识点:2.3线性表的链式表示和实现 难度:2 6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。 A.单链表 B.带头结点的单链表 C.单循环链表 绪论单元测试 1 【判断题】(2分) 数据结构主要研究内存中数据组织和数据处理方法。 A. 错 B. 对 正确 本题总得分2分 2 【多选题】(2分) 数据结构与算法课程的学习目标是（）。 A. 理解并掌握典型数据结构及七本运算的实现算法。 B. 提高计算思维能力 C. 能利用所学数据结构和算法知识解决实际问题。 D. 具备基本的算法设计与分析能力。 3 【多选题】(2分) 数据结构课程的学习重点是（） A. 掌握各种数据结构的逻辑特性 B. 掌握基本的算法分析方法。 C. 掌握各种数据结构的存储结构的设计与实现。 D. 掌握基本的算法设计方法 第一章测试 1 【多选题】(3分) 算法分析主要分析的是算法的（） A. 空间复杂性 B. 时间复杂性 C. 正确性 D. 可读性 2 【判断题】(2分) 数据结构是数据对象与对象中数据元素之间关系的集合。 A. 错 B. 对 3 【判断题】(2分) 数据元素是数据的最小单位。 A. 错 B. 对 4 【判断题】(2分) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 A. 对 B. 错 5 【判断题】(3分) 算法和程序没有区别，所以在数据结构中二者是通用的。 A. 错 B. 对 6 【单选题】(3分) 数据结构中，与所使用的计算机无关的是数据的（）结构 A. 存储 B. 物理与存储 C. 逻辑 D. 物理 7 【单选题】(3分) 算法分析的目的是（） A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 8 【单选题】(3分) 设x,y,n为正整数，下列程序片段的渐进时间复杂度是（）x=1；y=1； while（x+y<=n）{ if（x>y）y++； elsex++；} A. O(n2) B. O(log2n) C. O(n) D. O((2/3)n) 9 【多选题】(3分) 在数据结构中，从逻辑上可以把数据结构分成（）数据结构与算法基础知识总结
Java数据结构和算法
数据结构与算法设计实验
数据结构与算法第1章参考答案
824数据结构与算法设计A
大数据结构与算法课程设计程序及报告材料
数据结构与算法C语言版期末复习题
【精选资料】北京交通大学数据结构与算法期末考试参考答案
天津科技大学数据结构与算法课程设计
《数据结构与算法 Python精品课程》第二章：算法分析
数据结构与算法设计知识点
常用的大数据结构与算法
数据结构与算法习题库(考前必备)
数据结构和算法课程设计题目
数据结构与算法设计期末复习资料
数据结构与算法
智慧树知道网课《数据结构与算法》课后章节测试满分答案