第6章数据结构基础
【教学内容相关章节】
6.1栈和队列 6.2链表 6.3二叉树 6.4图
【教学目标】
（1）熟练掌握栈和队列及其实现；
（2）了解双向链表及其实现；
（3）掌握对比测试的方法；
（4）掌握随机数据生成方法；
（5）掌握完全二叉树的数组实现；
（6）了解动态内存分配和释放方法及其注意事项；
（7）掌握二叉树的链式表示法；
（8）掌握二叉树的先序、后序和中序遍历和层次遍历；
（9）掌握图的DFS及连通块计数；
（10）掌握图的BFS及最短路的输出；
（11）掌握拓扑排序算法；
（12）掌握欧拉回路算法。
【教学要求】
掌握栈和队列及其实现；掌握对比测试的方法；掌握随机数据生成方法；掌握完全二叉树的数组实现和链式表示法；掌握二叉树的先序、后序和中序遍历和层次遍历；掌握图的DFS和BFS遍历；掌握拓扑排序算法；掌握欧拉回路算法。
【教学内容提要】
本章介绍基础数据结构，包括线性表、二叉树和图。有两种特殊的线性表：栈和队列。对于树型结构主要讨论二叉树，还有二叉树的先序、中序和后序的遍历方式。对于图主要讨论图的DFS和BFS的遍历方法。这些内容是很多高级内容的基础。如果数据基础没有打好，很难设计正确、高效的算法。
【教学重点、难点】
教学重点：
（1）掌握栈和队列及其实现；
（2）掌握对比测试的方法；
（3）掌握随机数据生成方法；
（4）掌握完全二叉树的数组实现和链式表示法；
（5）掌握二叉树的先序、后序和中序遍历和层次遍历；
（6）掌握图的DFS和BFS遍历；
（7）掌握拓扑排序算法和欧拉回路算法。
教学难点：
（1）掌握完全二叉树的数组实现和链式表示法；
（2）掌握二叉树的先序、后序和中序遍历和层次遍历；
（3）掌握图的DFS和BFS遍历；
（4）掌握拓扑排序算法和欧拉回路算法。
【课时安排（共9学时）】
6.1栈和队列 6.2链表 6.3二叉树 6.4图
6.1 栈和队列
线性表是“所有元素排成一行”的数据结构。除了第一个元素之外，所有元素都有一个“前一个元素”；除了最后一个元素外，所有元素都有“后一个元素”。
线性结构是重要的算法和数据结构的基础。下面介绍两种特殊的线性表：栈和队列。
6.1.1 卡片游戏
桌上有叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1～n。当至少还剩两张牌时进行以下操作：把第一张牌扔掉，然后把新的第一张放一整叠牌的最后。输入n，输出每次扔掉的牌，以及最后剩下的牌。
样例输入：7
样例输出：1 3 5 7 4 2 6
【分析】
本题中牌像在排队。每次从排头拿到两个，其中第二个再次排到尾部。这种数据结构称为队列。在数据结构称为FIFO（First in First out，先进先出）表。
用一个数组queue来实现这个队列，可设两个指针front和rear。
完整的程序如下：
#include
const int MAXN = 50;
int queue[MAXN];
int main() {
int n, front, rear;
scanf("%d", &n);
for(int i = 0; i < n; i++) queue[i] = i+1; //初始化队列
front = 0; //队首元素的位置
rear = n; //队尾元素的后一个位置
while(front < rear) { //当队列非空
printf("%d ", queue[front++]); //输出并抛弃队首元素
queue[rear++] = queue[front++]; //队首元素转移到队尾
}
return 0;
}
注意：上面的程序有bug。如果在最后把rear的值打印出来，rear比n大。即在程序运行的后期，queue[rear++]=queue[front++]读写了非法内存。也可以采取将数组空间开大些，或采取一种称为循环队列的技术，重用已出队元素占用的空间。
C++提供了一种更加简单的处理方式——STL队列。下面是代码：
#include
#include
using namespace std;
queue
int main() {
int n, front, rear;
scanf("%d", &n);
for(int i = 0; i < n; i++) q.push(i+1); //初始化队列
while(!q.empty()) { //当队列非空
printf("%d ", q.front()); //打印队首元素
q.pop(); //抛弃队首元素
q.push(q.front()); //把队首元素加入队尾
q.pop(); //抛弃队首元素
}
return 0;
}
上面的程序的可读性大大增强了，体现在“queue”、“front”见名知义的命名，使用了C++ STL。除此之外，上面的代码还有两个附加的好处。首先，不需要事先知道n 的大小；其次，可以少用两个变量front和rear。减少魔术数（magic number）和变量个数都是提高代码可读性、减少错误可能性的重要手段。
说明：（1）在ACM竞赛中，需要用到数组、字符串、队列、堆栈、链表、平衡二叉检索树等数据结构和排序、搜索等算法，以提高程序的时间、空间运行效率，这些数据结构，如果需要手工来编写，那是相当麻烦的事情。
（2）ANSI C++中包含了一个C++ STL（Standard Template Library），即C++标准模板库，又称为C++泛型库，它在std命名空间中定义了常用的数据结构和算法，使用起来十分方便。
（3）C++ STL组件
STL组件三种类型的组件：容器、迭代器和算法，它们都支持泛型程序设计标准。
容器主要有两类：顺序容器和关联容器。顺序容器（vector、list、queue、string 等）一系列元素的有序集合。关联容器（set、multiset、map和mulimap）包含查找元素的键值。
迭代器的作用是遍历容器。
STL算法库包含四类算法：排序算法、不可变序算法、变序性算法和数值算法。
（4）queue队列容器
queue队列容器是一个先进先出（First In First Out，FIFO）线性存储表，元素的插入只能在队尾、元素的删除只能在队首。
使用queue需要声明头文件包含语句“#include
queue队列的操作有入队push()（即插入元素）、出队pop()（即删除元素）、读取队首元素front()、读取队尾元素back()、判断队列是否为空empty()和队列当前元素的数目size()。
下面给出一个程序来说明queue队列的使用方法。
#include
#include
using namespace std;
int main() {
//定义队列，元素类型是整型
queue
//入队，即插入元素
q.push(1);
q.push(2);
q.push(3);
q.push(9);
//返回队列元素数量
cout< //队列是否为空，是空，则返回逻辑真，否则返回逻辑假 cout< //读取队首元素 cout< //读取队尾元素 cout< //所有元素出列（删除所有元素） while(q.empty()!=true) { cout< //队首元素出队（删除队首元素） q.pop(); } //回车换行 cout< return 0; } 运行结果： 4 1 9 1 2 3 9 6.1.2 铁轨 某城市有一个火车站，铁轨铺设如图6-1所示。有n节车厢从A方向驶入车站，按进站顺序编号为1～n。你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A移入C，就不能再回到A了；一旦从C移入B，就不能回到C了。换句话说，在任意时刻，只有两种选择：A→C和C→B。 图6-1 铁轨 样例输入： 5 1 2 3 4 5 5 5 4 1 2 3 6 6 5 4 3 2 1 样例输出： Yes No Yes 【分析】 在中转站C中，车厢符合后进先出的原则，称为栈，即LIFO（Last In First Out）表。由于它只有一端生成，实现栈时只需要一个数组stack和栈顶指针（始终指向栈顶元素）。 完整的程序如下： #include const int MAXN = 1000 + 10; int n, target[MAXN]; int main() { while(scanf("%d", &n) == 1) { int stack[MAXN], top = 0; int A = 1, B = 1; for(int i = 1; i <= n; i++) scanf("%d", &target[i]); int ok = 1; while(B <= n) { if(A == target[B]){ A++; B++; } else if(top && stack[top] == target[B]){ top--; B++; } else if(A <= n) stack[++top] = A++; else { ok = 0; break; } } printf("%s\n", ok ? "Yes" : "No"); } return 0; } 说明：为了方便起见，使用的数组下标均从1开始。例如，target[1]是指目标序列中第一个车厢的编号，而stack[1]是栈底元素（这样，栈空当且仅当top=0）。 下面给出STL栈来实现的程序： #include #include using namespace std; const int MAXN = 1000 + 10; int n, target[MAXN]; int main() { while(scanf("%d", &n) == 1) { stack int A = 1, B = 1; for(int i = 1; i <= n; i++) scanf("%d", &target[i]); int ok = 1; while(B <= n) { if(A == target[B]){ A++; B++; } else if(!s.empty() && s.top() == target[B]){ s.pop(); B++; } else if(A <= n) s.push(A++); else { ok = 0; break; } } printf("%s\n", ok ? "Yes" : "No"); } return 0; } 说明：（1）stack栈容器是一种C++ STL中的容器，它是一个后进先出（Last In First Out，LIFO）的线性表，插入和删除元素都只能在表的一端进行。插入元素的一端称为栈顶（Stack Top），而另一端称为栈底（Stack Bottom）。插入元素称为入栈（Push），元素的删除则称为出栈（Pop）。 （2）要使用stack，必须声明头文件包含语句“#include Program Files\Microsoft Visual Studio\VC98\Include文件夹中。 （3）栈只提供入栈、出栈、栈顶元素访问和判断是否为空等几种方法。采用push()方法将元素入栈；采用pop()方法出栈；采用top()方法访问栈顶元素；采用empty()方 法判断栈是否为空，如果为空，则返回逻辑真，否则返回逻假。当然，可以采用size()方法返回当前栈中有几个元素。 下面的程序是对栈各种方法的示例： #include #include using namespace std; int main() { //定义栈s，其元素类型是整型 stack //元素入栈，即插入元素 s.push(1); s.push(2); s.push(3); s.push(9); //读取栈顶元素 cout< //返回栈元素数量 cout< //判断栈是否为空 cout< //所有元素出栈（删除所有元素） while(s.empty()!=true) { //栈非空 cout< s.pop(); //出栈（即删除栈顶元素） } //回车换行 cout< return 0; } 运行结果： 9 4 9 9 3 2 1 6.2 链表 在多数情况下，线性表都用它的顺序存储结构——数组很轻松实现，但对有些问题有时用它的链式存储结构——链表更好。 6.2.1 初步分析 例6-1 移动小球。 你有一些小球，从左到右依次编号为1,2,3,…,n，如图6-2所示。 图6-2 链表的初始状态 可以执行两种指令。其中，A X Y表法把小球X移动到小球Y左边，B X Y表示把小球X移动到小球Y右边。指令保证合法，即X不等于Y。 例如，在初始状态下执行A 1 4后，小球被移动小球4的左边，如图6-3所示。 图6-3 一次操作后的链表状态 如果再执行B 3 5，结点3将会移到5的右边，如图6-4的所示。 图6-4 两次操作后的链表状态 输入小球个数n，指令条数m和n条指令，从左到右输出最后的序列。注意，n可能高达500000，而m可能高达100000。 样例输入： 6 2 A 1 4 B 3 5 样例输出： 2 1 4 5 3 6 【分析】 各个小球在逻辑上是相邻的，因此可考虑把它们放在一个数组A中，所以完整的程序如下： #include const int MAXN = 1000; int n, A[MAXN]; int find(int X) { for(int i = 1; i <= n; i++) if(A[i] == X) return i; return 0; } void shift_circular_left(int a, int b) { int t = A[a]; for(int i = a; i < b; i++) A[i] = A[i+1]; A[b] = t; } void shift_circular_right(int a, int b) { int t = A[b]; for(int i = b; i > a; i--) A[i] = A[i-1]; A[a] = t; } int main() { int m, X, Y, p, q; char type[9]; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) //初始化数组 A[i] = i; for(int i = 0; i < m; i++) { scanf("%s%d%d", type, &X, &Y); p = find(X); //查找X和Y在数组中的位置 q = find(Y); if(type[0] == 'A') { if(q > p) shift_circular_left(p, q-1); //A[p]到A[q-1]往左循环移动 else shift_circular_right(q, p); //A[q]到A[p]往右循环移动 } else { if(q > p) shift_circular_left(p, q); //A[p]到A[q]往左循环移动 else shift_circular_right(q+1, p); //A[q+1]到A[p]往右循环移动 } } for(int i = 1; i <= n; i++) printf("%d ", A[i]); printf("\n"); return 0; } 对于上面的程序，当数据量很大时，代码是否会超时。一般来说，可以用两种方法判断：测试和分析。 计时测试的方法在前面已讲过，它的优点是原理简单、可操作性强，缺点在于必须事先程序写好——包括主程序和测试数据生成器。如果算法非常复杂，这是相当花时间的。 另一种方法是写程序之前进行算法分析，估算时间效率，这种方法在第8章会详细分析。不过现在可以直观分析一下：如果反复执行B 1 n和A 1 2，每次都移动几乎所有元素。元素个数和指令条数都那么大，移动总次数将是相当可观的。 6.2.2 链式结构 第二种方法是强调小球之间的相对顺序，而非绝对顺序。用left[i]和right[i]分别表示编号为i的小球左边和右边的小球编号（如果是0，表示不存在），则在移动过程中可以分成两个步骤：把X移出序列；把X重新插入序列。 第一步让left[X]和right[X]相互连接即可，如图6-5所示。注意，其他所有的left 和right都不会变化。 图6-5 在链表中删除结点 第二步类似。对于A指令，需要修改left[Y]的right值和Y的left值，如图6-6所示。 图6-6 在链表中插入结点（情况A） 而对于B指令，需要修改Y的right值和right[Y]的left的值，如图6-7所示。 图6-7 在链表中插入结点（情况B） 不管在哪种情况下，最后都需要修改X自己的left和right。对于特殊情况下，对于最左的小球X，它的left[X]的值为0，但可以假想最左的小球左边有一个编号为0的 虚拟的小球。那么对最右的小球的右边的虚拟小球编号为n+1。核心的代码如下：scanf("%s%d%d", type, &X, &Y); link(left[X], right[X]); if(type[0] == 'A') { link(left[Y], X); //这一行和下一行不能搞反 link(X, Y); } else { link(X, right[Y]); //这一行和下一行不能搞反 link(Y, X); } 函数link(X,Y)的作用是赋值right[X]=Y，然后left[Y]=X。 0 1 2 3 4 5 6 left right 完整的程序如下： #include const int MAXN = 1000; int n, left[MAXN], right[MAXN]; void link(int X, int Y) { right[X] = Y; left[Y] = X; } int main() { int m, X, Y; char type[9]; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { left[i] = i-1; right[i] = i+1; } for(int i = 0; i < m; i++) { scanf("%s%d%d", &type, &X, &Y); link(left[X], right[X]); if(type[0] == 'A') { link(left[Y], X); //这一行和下一行不能搞反 link(X, Y); } else { link(X, right[Y]); //这一行和下一行不能搞反 link(Y, X); } } for(int X = right[0]; X != n+1; X = right[X]) printf("%d ", X); printf("\n"); return 0; } 6.2.3 对比测试 对于写好的程序，可能会花费较长的时间进行调试，所以要具备一定的调试和测试能力。 测试的任务就是检查一份代码是否正确。如果找到了错误，最好还能提供一个让它错误的数据。有了错误数据之后，接下来的任务便是调试：找出出错的原因。如果找到了错，最好把它改对——至少对于刚才的错误数据能得到正确的结果。 改对一组数据之后，可能还有其他错误，因此需要进一步测试；即使以前曾经正确的数据，也可能因为多次改动之后反而变错了，需要再次调试。总之，在编码结束后，为确保程序的正确性，测试和调试往往要交替进行。 确保代码正确的方法是：再找一份完成同样功能的代码与之对比，用它来和这个新程序“对答案”（俗称对拍）。 对比测试首先需要数据，而且是大量数据。为此，需要编写数据生成器，完整的代码如下： #include #include #include int n = 100, m = 100000; double random() { //生成[0,1]之间的均匀随机数 return (double)rand() / RAND_MAX; } int random(int m) { //生成[0,m-1]之间的均匀随机数 return (int)(random() * (m-1) + 0.5); } int main() { srand(time(NULL)); //利用系统时间，初始化随机数种子 printf("%d %d\n", n, m); for(int i = 0; i < m; i++) { if(rand() % 2 == 0) printf("A"); else printf("B"); //随机指令种类 int X, Y; for(;;) { X = random(n)+1; Y = random(n)+1; if(X != Y) break; //只有X和Y不相等时才是合法的 } printf(" %d %d\n", X, Y); } return 0; } 核心函数是stdlib.h中的rand()，它生成一个闭区间[0,RAND_MAX]的均匀随机整数（均匀的含义是：该区间内每个整数被产生的概率相同），其中RAND_MAX至少为32767（215-1），在不同的环境下的值可能不同。严格地说，这个随机数是“伪随机数”，因为它也是由数学公式计算出来的。 6.2.4 随机数发生器 上面的程序使用了rand()函数和srand()函数，下面就这个两个函数进行说明。 1．rand()函数 rand()函数的主要功能是产生随机数。 （1）表头文件：#include （2）函数原型：int rand(void) （3）函数说明 rand（）函数的内部实现是线性同余法的，它不是真的随机数，只不过是因为其周期特别长，所以在一定的范围里可看成是随机的，rand()会返回一随机数，范围在0至RAND_MAX区间。在调用此函数产生随机数前，必须先利用srand()设好随机数种子，如果未设随机数种子，rand()在调用时会自动设随机数种子为1（即调用srand(1)），rand()产生的是假随机数字，每次执行是相同的，若要不同，以不同的值来初始化它，初始化函数是srand()。 （4）返回值 返回值是0至RAND_MAX之间的随机整数值，RAND_MAX的范围最少是32767之间（int），取双字节（16位数）。若用unsigned int双字节是65535，四字节是4294967295的整数范围，0～RAND_MAX每个数字被选中的机率是相同的。 提示6-1：stdlib.h中的rand()生成闭区间[0,RAND_MAX]内均匀分布的随机整数，其中RAND_MAX至少为32767。如果生成更大的随机整数，在精度要求不太高的情况下可以用rand()的结果“放大”得到。 说明：用“int x=1+rand()%n;”来生成[1,n]之间的随机数这种方法是不可取的， 比较好的做法是：j=1+(int)(n*rand()/(RAND_MAX+1.0));产生一个[1,n]之间的随机数。 2．srand()函数 srand()函数的功能是设置随机数种子。 （1）函数原型：void srand(unsigned int seed); （2）函数说明 srand()函数用来设置rand()产生随机数时的随机数种子。参数seed必须是整数，通常可以利用getpid()（即取目前进程的进程识别码）或time(NULL)的返回值来当做seed。time()函数的功能是返回从1970/01/01到现在的秒数。 如果每次seed都设相同值，rand()所产生的随机数值每次就会一样。由于每一次运行程序的时间是不同，time(NULL)函数的返回值也不同，即种子不同，所以产生的随机数也不同。 提示6-2：stdlib.h中的srand()函数初始化随机数种子。如果需要程序每次执行是使用一个不同的种子，可以用time.h中的time(NULL)为参数调用srand。一般来说，只在程序执行的开头调用一次srand。 “同一套随机数”可能是好事也可能是坏事。例如，若要反复测试程序对不同随机数据的响应，需要每次得到的随机数不同，就可用当前时间time(NULL)作为参数调用srand。如果程序是由操作系统自动批量执行的，可能因为每次运行时间过短，导致在相邻若干次执行时time的返回值全部相同，一个解决办法是在测试程序的主函数中设置一个循环，做足够多次测试后退出。 另一方面，如果发现某程序对于一组随机数据出错，就需要在测试时“重视”这组数据。这时，“每次相同的随机序”就显得十分重要了。注意，不同的编译器计算随机数的方法可能不同。如果是不同编译器编译出来的程序，即使是相同的参数调用srand()，也可能得到不同的随机序列。 最后，可以反复执行下面的操作：生成随机数据，分别执行两个程序，比较它们的结果。合理地使用操作系统提供的脚本功能，可以自动完成对比测试。 最后如果发现让两个程序答案不一致的数据，最好别急着对它进行调试。可以尝试着减少数据生成器中的n和m，试图找到一组尽量简单的错误数据。一般来说，数据越简单，越容易调试。如果发现只有很大的数据才会出错，通常意味着程序在处理极限数据方面有问题。对于这些技巧，平时要多积累。 6.3 二叉树 二叉树（Binary Tree）的递归定义如下：二叉树要么为空，要么由根结点（root）、左子树（left subtree）和右子树（right subtree）组成，而左子树和右子树分别是一棵二叉树。注意，在计算机中，树一般是“倒置”的——根在上，叶子在下。 6.3.1 小球下落 有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1,2,3,…,2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始全部关闭，当每次有小球落到一个开关上时，它的状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点，如图6-8所示。 图6-8 所有叶子深度相同的二叉树 一些小球从结点1处依次开始下落，最后一个小球将全落到哪里呢？输入叶子深度D 和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D≤20。输入最多包含1000组数据。 样例输入： 4 2 3 4 10 1 2 2 8 128 #《算法竞赛入门经典》勘误 关于勘误?下面的勘误很多来自于热心读者，再次向他们表示衷心的感谢！我并不清楚这些错误实际是在哪个版本中改正过来的，所以麻烦大家都看一下。 有发现新错误的欢迎大家在留言中指出，谢谢！ 一些一般性的问题?运算符?已经被废弃，请用min、max代替（代码仓库中的代码已更新，g++ 4.6.2下编译通过） 重大错误?p24. 最后一行，“然后让max=INF,而min=-INF”应该是“然后让max=-INF, 而min=INF”。 (感谢imxivid） p43. 最后，判断s[i..j]是否为回文串的方法也不难写出：int ok = 1; for(k = i; i<=j; i++)应该为for(k = i; k<=j; k++) (感谢imxivid） p45. 第七行和第九行i-j+1应为i+j+1。修改后： 1. { 2. for (j = 0; i - j >= 0 && i + j < m; j++) 3. { 4. if (s[i - j] != s[i + j]) break; 5. if (j*2+1 > max) { max = j*2+1; x = p[i - j]; y = p[i + j];} 6. } 7. for (j = 0; i - j >= 0 && i + j + 1 < m; j++) 8. { 9. if (s[i - j] != s[i + j + 1]) break; 10. if (j*2+2 > max) 11. {max = j*2+2; x = p[i - j]; y = p[i + j + 1]; } 12. } 13. }p53. 例题4-1. 组合数. 输入非负整数n和m，这里的n和m写反了。应是“输入非负整数m和n”。 p54. 举例中的m和n也写反了（真是个悲剧），且C(20,1)=20。 p71. 《周期串》代码的第8行，j++应为i++。 p72. 代码的第7行，“return”改为“break”以和其他地方一致。 p81. k为奇数和偶数的时候，分子和分母的顺序是不一样的。正确代码为： #include 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 数据结构与算法基础知识总结 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表示队列满 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 Data Structures and Algorithm 习题答案 Preface ii 1 Data Structures and Algorithms 1 2 Mathematical Preliminaries 5 3 Algorithm Analysis 17 4 Lists, Stacks, and Queues 23 5 Binary Trees 32 6 General Trees 40 7 Internal Sorting 46 8 File Processing and External Sorting 54 9Searching 58 10 Indexing 64 11 Graphs 69 12 Lists and Arrays Revisited 76 13 Advanced Tree Structures 82 i ii Contents 14 Analysis Techniques 88 15 Limits to Computation 94 Preface Contained herein are the solutions to all exercises from the textbook A Practical Introduction to Data Structures and Algorithm Analysis, 2nd edition. For most of the problems requiring an algorithm I have given actual code. In a few cases I have presented pseudocode. Please be aware that the code presented in this manual has not actually been compiled and tested. While I believe the algorithms to be essentially correct, there may be errors in syntax as well as semantics. Most importantly, these solutions provide a guide to the instructor as to the intended answer, rather than usable programs. 第一章习题1-1 #include 习题1-3 #include 习题1-5 #include 大师兄教你如何过华为机试 宝典1—内功心法 大华为这个大数据时代土豪金海量式的招聘又要开始了！！！ 近期听说大华为的校招机试马上就要开始了，由于华为软件岗位的招聘只有技术面跟机试是与技术有关的内容，所以机试的地位非常重要。对于机试，除了长期积累的软件基本功以外，还有很多可以短期训练的东西，类似于考试之前的突击，可以迅速提高机试成绩，就像在我西电大杨老师考前最后一堂课一定要去，那个重点就是考点阿。 这篇机试葵花宝典的内容是针对华为软件类上机准备的，如果你认真看了本宝典,如果你是真正通过自己能力考上西电的话,想不过都难。同样想拿高级题的同学，请移步 https://www.doczj.com/doc/509515189.html,/land/或者https://www.doczj.com/doc/509515189.html,，刷上200道题，机试不想拿满分都难。 对于机试，首先应该调整好自己的心态，不要觉得写程序很难，机试题很难，也不要去考虑，万一机试考到自己不会的内容怎么办，要相信，机试题永远是考察每个人的基础，基础是不会考的很偏的，会有人恰好做过某个题而做出来那个题，但不会有人恰好没做过一个题而做不出来那个题。 机试之前，应该做的准备有： 1、买一本《算法竞赛入门经典》，这本书不同于普通的算法或者编程语言的书籍，这 本书既讲语言，又讲算法，由浅入深，讲的很好，能看完前几章并且把例题都做 会，想通过机试就很简单了 2、调整好心态，时刻告诉自己，哪些小错误是自己以前经常犯的，最好用笔记本记录 下来，写每道题前再看一遍，如果遇到代码调不出来了，先想想自己是否犯过以 前那些错误。还有就是，看了题目以后，先仔细想清楚细节，在纸上写清楚自己 需要用到的变量，以及代码的基本框架，不要急于动手去写代码 3、不要惧怕任何一道看起来很难的题目，有不会的就去问身边会的人，让别人给自己 讲清楚 4、心中默念10遍C++跟C除了多了两个加号其实没有区别，会C就能上手C++ 5、大量的练习是必要且有效的 6、看完这篇宝典，预过机试、必练此功。 在这里推荐一个帖子，是机试归来的学长写的，写的很不错，里面的例题在后面的攻略 信息学奥赛（NOIP）必看经典书目汇总！ 小编整理汇总了一下大神们极力推荐的复习资料！（欢迎大家查漏补缺） 基础篇 1、《全国青少年信息学奥林匹克分区联赛初赛培训教材》（推荐指数：4颗星） 曹文，吴涛编著，知识点大杂烩，部分内容由学生撰写，但是对初赛知识点的覆盖还是做得相当不错的。语言是pascal的。 2、谭浩强老先生写的《C语言程序设计（第三版）》（推荐指数：5颗星） 针对零基础学C语言的筒子，这本书是必推的。 3、《骗分导论》（推荐指数：5颗星） 参加NOIP必看之经典 4、《全国信息学奥林匹克联赛培训教程（一）》（推荐指数：5颗星） 传说中的黄书。吴文虎，王建德著，系统地介绍了计算机的基础知识和利用Pascal语言进行程序设计的方法 5、《全国青少年信息学奥林匹克联赛模拟训练试卷精选》 王建德著，传说中的红书。 6、《算法竞赛入门经典》（推荐指数：5颗星） 刘汝佳著，算法必看经典。 7、《算法竞赛入门经典:训练指南》（推荐指数：5颗星） 刘汝佳著，《算法竞赛入门经典》的重要补充 提高篇 1、《算法导论》（推荐指数：5颗星） 这是OI学习的必备教材。 2、《算法艺术与信息学竞赛》（推荐指数：5颗星） 刘汝佳著，传说中的黑书。 3、《学习指导》（推荐指数：5颗星） 刘汝佳著，《算法艺术与信息学竞赛》的辅导书。（PS：仅可在网上搜到，格式为PDF）。 4、《奥赛经典》（推荐指数：5颗星） 有难度，但是很厚重。 5、《2016版高中信息学竞赛历年真题解析红宝书》（推荐指数：5颗星） 历年真题，这是绝对不能遗失的存在。必须要做！ 三、各种在线题库 1、题库方面首推USACO（美国的赛题），usaco写完了一等基本上就没有问题，如果悟性好的话甚至能在NOI取得不错的成绩. 2、除此之外Vijos也是一个不错的题库，有很多中文题. 3、国内广受NOIP级别选手喜欢的国内OJ（Tyvj、CodeVs、洛谷、RQNOJ） 4、BJOZ拥有上千道省选级别及以上的题目资源，但有一部分题目需要购买权限才能访问。 5、UOZ 举办NOIP难度的UER和省选难度的UR。赛题质量极高，命题人大多为现役集训队选手。 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 目录： 1、数据结构 2、算法的设计原则 3、总结 正文： 本系列博客我们将学习数据结构和算法，为什么要学习数据结构和算法，这里我举个简单的例子。 编程好比是一辆汽车，而数据结构和算法是汽车内部的变速箱。一个开车的人不懂变速箱的原理也是能开车的，同理一个不懂数据结构和算法的人也能编程。但是如果一个开车的人懂变速箱的原理，比如降低速度来获得更大的牵引力，或者通过降低牵引力来获得更快的行驶速度。那么爬坡时使用1档，便可以获得更大的牵引力；下坡时便使用低档限制车的行驶速度。回到编程而言，比如将一个班级的学生名字要临时存储在内存中，你会选择什么数据结构来存储，数组还是ArrayList，或者HashSet，或者别的数据结构。如果不懂数据结构的，可能随便选择一个容器来存储，也能完成所有的功能，但是后期如果随着学生数据量的增多，随便选择的数据结构肯定会存在性能问题，而一个懂数据结构和算法的人，在实际编程中会选择适当的数据结构来解决相应的问题，会极大的提高程序的性能。 1、数据结构 数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 一、数据结构的基本功能 ①、如何插入一条新的数据项 ②、如何寻找某一特定的数据项 ③、如何删除某一特定的数据项 ④、如何迭代的访问各个数据项，以便进行显示或其他操作 二、常用的数据结构 这几种结构优缺点如下：先有个大概印象，后面会详细讲解！！！ 算法简单来说就是解决问题的步骤。 在Java中，算法通常都是由类的方法来实现的。前面的数据结构，比如链表为啥插入、删除快，而查找慢，平衡的二叉树插入、删除、查找都快，这都是实现这些数据结构的算法所造成的。后面我们讲的各种排序实现也是算法范畴的重要领域。 424-Integer Inquiry One of the first users of BIT's new supercomputer was Chip Diller.He extended his exploration of powers of3to go from0 to333and he explored taking various sums of those numbers. ``This supercomputer is great,''remarked Chip.``I only wish Timothy were here to see these results.''(Chip moved to a new apartment,once one became available on the third floor of the Lemon Sky apartments on Third Street.) Input The input will consist of at most100lines of text,each of which contains a single VeryLongInteger.Each VeryLongInteger will be100or fewer characters in length,and will only contain digits(no VeryLongInteger will be negative). The final input line will contain a single zero on a line by itself. Output Your program should output the sum of the VeryLongIntegers given in the input. Sample Input 123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 Sample Output 370370367037037036703703703670 10106–Product The Problem The problem is to multiply two integers X,Y.(0<=X,Y<10250) The Input The input will consist of a set of pairs of lines.Each line in pair contains one multiplyer. The Output For each input pair of lines the output line should consist one integer the product. Sample Input 12 12 2 222222222222222222222222 Sample Output 144 444444444444444444444444 465–Overflow Write a program that reads an expression consisting of two non-negative integer and an operator.Determine if either integer or the result of the expression is too large to be represented as a``normal''signed integer(type integer if you are working Pascal,type int if you are working in C). Input An unspecified number of lines.Each line will contain an integer,one of the two operators+or*,and another integer. Output For each line of input,print the input followed by0-3lines containing as many of these three messages as are appropriate: ``first number too big'',``second number too big'',``result too big''. Sample Input 300+3 9999999999999999999999+11 Sample Output 300+3 9999999999999999999999+11 first number too big 广西科技大学2015 —2016 学年第 1 学期课程考核试题试卷 考核课程数据结构与算法（ B 卷）考核班级物联网141 学生数36 印数40 考核方式闭卷考核时间120 分钟 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案。每小题1分，共33分） 1、算法是（）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 2、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第8个元素的存储地址是（）。 A. 102 B. 104 C. 106 D. 108 3、在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i+1 4、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。 A. p指向头结点 B. p指向尾结点 C. p的直接后继是头结点 D. p的直接后继是尾结点 5、在以下的叙述中，正确的是（）。 A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构 6、在一个单链表中，已知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; 7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。 A. p->next=q; q->prior=p; p->next->prior=q; q->next=q; B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D. q->next=p->next; q->prior=p; p->next=q; p->next=q; 8、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。 A. p=p->next; B. p->next=p->next->next; C. p->next=p; D.p=p->next->next; 9、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 10、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。 A. O(1) B. O(n) C. O(m) D. O(m+n) 11、线性表的顺序存储结构是一种（）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 12、循环链表的主要优点是（）。 A. 不再需要头指针 B. 已知某结点位置后能容易找到其直接前驱 C. 在进行插入、删除运算时能保证链表不断开 D. 在表中任一结点出发都能扫描整个链表 13、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。 数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构 《数据结构与算法》模拟试卷五 一、名词解释（5*3=15分） 数据结构完全二叉数 AOE网队列拓扑排序 二、填空题（1*16=16分） 1.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为 ______。 2.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点 的条件是______。 3.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出 栈序列中第30个元素为______。 4.一种抽象数据类型包括______和______两个部分。 5.线性表的链式存储方式中，每个结点包括两个域，分别是______和______ 。 6.在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为 空的条件分别为单链表中______ 和 ______ 。 7.在一棵二叉树中，度为0的结点的个数是10，则度为2的结点个数是_________ 8.一个有n个结点的二叉树的深度最大为___________，最小为__________ 9.n个定点的连通图至少有_______条边。 10.二分查找的存储结构仅限于________，且是__________ 11.在对一组记录(54，38，96，72，60，15，60，45，83)进行直接插入排序时， 当把第6个记录60插入到有序表时，为寻找插入位置需比较________次。 三、选择题（1*10=10分） 1.在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点， 则执行 _______。 A、HL=p; p->next=HL; B、p->next=HL; HL=p; C、p->next=HL; p=HL; D、p->next=HL->next; HL->nxet=p; 2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n+1）时， 需要从前向后依次移动_______个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个顺序队列中，队首指针指向队首元素的_______位置。 A、当前 B、后一个 C、前一个 D、后面 4.计算递归函数如不用递归过程通常借助的数据结构是____。 A、线性表 B、双向队列 C、树 D、栈 5.如果T2是由有序树T转换来的二叉树，则T中结点的后序排列是T2结点的 ____。 A、先序排列 B、中序排列 C、后序排列 D、层序排列 6.栈的插入和删除操作在_____进行。蓝书刘汝佳算法竞赛入门经典勘误
数据结构与算法习题及答案
数据结构与算法基础知识总结
数据结构与算法分析习题与参考答案
数据结构与算法复习题10(C语言版)
数据结构与算法分析 C++版答案
最新算法竞赛入门经典各章(第二版)前4章课后习题答案电子教案
大师兄教你如何过华为机试
(完整)信息学奥赛(NOIP)必看经典书目汇总,推荐文档
数据结构与算法试题
数据结构与算法分析
BIG NUMBER 算法竞赛入门经典 刘汝佳
数据结构与算法试卷(B卷)
数据结构与算法基础
数据结构与算法模拟试卷五
相关主题
文本预览