专升本数据结构考前必看
1．名词解释：栈和队列
栈是只允许在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出（L IF O）表。
队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最先插入队的元素最先离开（删除），故队列也常称先进先出（F IF O）表。
2. 假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。
（1）试指出判别给定序列是否合法的一般规则。
（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。
【答案】（1）通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。（2）可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于合法序列BAC，我们使用SSXXSX操作序列。
3. 如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和13542 6，请说明为什么不能或如何才能得到。
【答案】输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。
4. 简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
【答案】设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear 时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。
5. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；
（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。
【答案】（1）4132 （2）4213 （3）4231
1．描述以下概念的区别：空格串与空串。
【答案】空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。
2．设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。
【答案】
（1）s1和s2均为空串；
（2）两串之一为空串；
（3）两串串值相等（即两串长度相等且对应位置上的字符相同）。
（4）两串中一个串长是另一个串长（包括串长为1仅有一个字符的情况）的数倍，而且长串就好象是由数个短串经过连接操作得到的。
5.4应用题
1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？
【答案】设数组元素A[i][j]存放在起始地址为Loc （i, j ）的存储单元中。
∵ Loc （2, 2 ）= Loc （0, 0 ）+ 2 * n + 2 = 644 + 2 * n + 2 = 676.
∴ n = （676 - 2 - 644 ）/ 2 = 15
∴ Loc （3, 3 ）= Loc （0, 0 ）+ 3 * 15 + 3 = 644 + 45 + 3 = 692.
2．设有一个n?n的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B 中，称之为对称矩阵A的压缩存储方式。试问：
（1）存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？
（2）若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素a ij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。
【答案】
（1）数组B共有1＋2 + 3 +?????? + n= （n+1 ）*n / 2个元素。
（2）只存下三角部分时，若i ≥ j，则数组元素A[i][j]前面有i-1行（1~i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，??????，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为：
1 +
2 + ?????? + （i-1）+ j = （i-1）*i / 2 + j
若i < j，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第（j-1）*j / 2 + i位置中找到。
如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为：
当i ≥ j时，= i*（i+1）/ 2 + j
当i < j时，= j*（j+1）/ 2 + i
3．利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：（1）L1（apple, pear, banana, orange）
（2）L2（（apple, pear）, （banana, orange））
（3）L3（（（apple）, （pear）, （bananA）, （orange）））
（4）L4（（（（apple）））, （（pear））, （bananA）, orange）
（5）L5（（（（apple）, pear）, bananA）, orange）
【答案】
（1）Head （Tail （Tail （L1）））
（2）Head （Head （Tail （L2）））
（3）Head （Head （Tail （Tail （Head （L3）））））
（4）Head （Head （Tail （Tail （L4））））
（5）Head （Tail （Head（L5）））
1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
【答案】树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树惟一表示，并可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有3：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。
2．若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作：
（1）寻找某个结点双亲；（2）寻找某个结点的子女；
请问应该用何种结构来存储该二叉树？
【答案】用顺序存储结构存储n个结点的完全二叉树。编号为i的结点，其双亲编号是?i/2?(i=1时无双亲)，其左子女是2i(若2i≤n，否则i无左子女)，右子女是2i+1(若2i+1≤n，否则无右子女)。
3．求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【答案】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是?n/2?，这是最后一个分支结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是?n/2?+1。
4．试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如先序abc，后序bca，中序bac。
【答案】先序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。5．试找出满足下列条件的二叉树：
1）先序序列与后序序列相同； 2）中序序列与后序序列相同； 3）先序序列与中序序列相同； 4）中序序列与层次序列相同；
【答案】先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根”，根据以上原则，解答如下：
1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 （3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 （4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树 6．已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK 和LGHDIEBJKFCA （1）给出这棵二叉树；（2）转换为对应的森林。
【答案】
7．一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。
【答案】先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使先序序列与后序序列相反，图示如下：
8．假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG 。请画出该二叉树，并将其转换为对应的森林。
【答案】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分：左子树和右子树。若左子树不空，层次序列中第二个结点为左子树的根；若右子树为空，则层次序列中第三个结点为右子树的根。对右子树也作类似的分析。层次序列的特点是，从左到右每个结点或是当前情况下子树的根或是叶子。
9．已知一个森林的先序序列和后序序列如下，请构造出该森林。 先序序列：ABCDEFGHIJKLMNO 后序序列：CDEBFHIJGAMLONK
【答案】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。
（2）题图
E A B L D G H
I J F C K I
A D E
B F
C G H E C A B
D I G
H F A C B H J D F
G K L E I
（1）题图
F A
E
B D
C
J
H
G I
K O
N L M
10．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A 【答案】
11．设有正文AADBAACACCDACACAAD ，字符集为A ，B ，C ，D ，设计一套二进制编码，使得上述正文的编码最短。
【答案】字符A ，B ，C ，D 出现的次数为9，1，5，3。其哈夫曼编码如下：A:1，B:000，C:01，D:001。
AOE 网的性质
（1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
（2）只有在进入某点的各有向边所代表的活动都已结束，该顶点所代表的时事件才能发生。
整个工程只有一个开始点，一个结束点。
AOV 网
A B C
E D
G
I H F J
K 1 3
5
9 0 0 0 1
1
1
用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网。
在网中，若从顶点i到顶点j有一条有向路径，则i是j 的前驱
AOV网是一种有向无环图。
强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图。1．设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={
分析：作该题的关键是弄清楚以下两点
（1）边集E中
（2）强连通图是任意两顶点间都存在路径的有向图。
【答案】该有向图是强连通图，表示如下：
2．画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。
【答案】
【解析】因为在有n个顶点的无向完全图中，每一个顶点与其它任一顶点都有一条边相连，所以每一个顶点有n-1条边与其他顶点相连，则n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。
3．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：
（1）图中有多少条边?
（2）任意两个顶点i和j是否有边相连?
（3）任意一个顶点的度是多少?
【答案】
（1）无向图的邻接矩阵是对称的，故它的边数应是上三角或下三角的非0元个数。
（2）邻接矩阵中如果第i行第j列的元素非0则表示顶点i与顶点j相连。
（3）任意一个顶点vi的度是第i行或第i列上非0元的个数。
4．熟悉图的存储结构，画出下面有向图的邻接矩阵、邻接表、逆邻接表、十字链表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。
【答案】邻接矩阵如下：邻接表如下：
逆邻接表如下：十字链表如下：
深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF
5．已知下面是某无向图的邻接表，画出该无向图，并分别给出从A出发的深度优先搜索生成树和广度优先搜索生成树。
【解析】作该题的关键是弄清楚邻接表的概念，理解深度优先搜索和广度优先搜索的全过程以及二者的区别。
【答案】该无向图如下所示：
深度优先搜索生成树为：广度优先搜索生成树为：
6．请分别用Prim算法和Kruskal
算法构造以下网络的最小生成树，并求出该树的代价。
【解析】Prim算法的操作步骤：首先从一个只有一个顶点的集合开始，通过加入与其中顶点相关联的最小代价的边来扩充顶点集，直到所有顶点都在一个集合中。
【答案】
0 1 0 1 0 0
0 0 1 0 1
0 0 0 0 0 0
1
0 1 0 0 1
【解析】Kruscal算法的操作步骤：首先将n个顶点看成n个互不连通的分量，从边集中找最小代价的边，如果落在不同连通分量上，则将其加入最小生成树，直到所有顶点都在同一连通分量上。
【答案】
7．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。
【解析】求关键路径首先求关键活动，关键活动a i的求解过程如下
（1）求事件的最早发生时间ve(j), 最晚发生时间vl(j);
（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0);
（3）计算e(i),l(i)：设a i由弧
e(i)=ve(j)
l(i)=vl(k)-dut(
（4）找出e(i)-l(i)=0的活动既是关键活动。
【答案】
顶点ve vl 活动 e l l-e
V0 0 0
v1 2 2
v2 4 5
v3 10 10
v4 7 7
v5 9 a0 0 0 0
a1 0 4 4
a2 0 1 1
a3 2 9 7
a4 2 2 0
a5 4 5
10 v6 14
14 1 a6 7 7 0 a7 7 10 3 a8
4 5 1 a9 10 10
a10 9 10 1
关键路径为：a0->a4->a6->a9
8． 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。
【解析】解题关键是弄清拓扑排序的步骤
（1）在AOV 网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465
9．给定带权有向图G 和源点v1,利用迪杰斯特拉（Dijkstra ）算法求从v1到其余各顶点的最短路径。
【解析】求解该题的关键是掌握迪杰斯特拉（Dijkstra ）算法的设计原理----从一个顶点v 到另一顶点v k 的最短路径或者是(v,v k )或者是(v,v j ,v k ),它的长度或者是从v 到v k 弧上的权值，或者是D[j]与v j 到v k 弧上的权值之和，其中D[j]是已经找到的从v 到v j 的最短路径。 【答案】S 是已找到最短路径的终点的集合。
终点 从v1到各终点的
D 值和最短路径的求解 i=2 i=3
i=4 i=5 i=6
v2 5 (v1,v2) 5 (v1,v2)
v3 4 (v1,v3)
v4 32767 32767 32767 9 (v1,v2,v5,v4)
v5 32767 32767 6 (v1,v2,v5)
v6 32767 32767 12 (v1,v2,v6) 9 (v1,v2,v5,v6) 9
(v1,v2,v5,v6)
vj v3 v2 v5 v4 v6 S {v1,v3} {v1,v2} {v1,v2,v5} {v1,v2,v5,v4} {v1,v2,v5,v6}
10．利用Floyd 算法求下图中各对顶点之间的路径。
【解析】Floyd 算法是依次添加顶点来修改相应路径，也就是说,若（vi ，．．．，vk ）和(vk ，．．．，vj)分别是从
vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，．．．vk，．．．，vj）和已经得到的从vi到vj且中间顶点序号不大于k-１的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。经过n次比较后必求得vi到vj的最短路径，依次，可求得各对顶点间的最短路径。求解的关键是求解如下的一个n阶方阵序列：
D(＿1)，D(0)，D(1)，．．．，D(k)，D(n＿1)
其中
D(＿1)[i][j]=G．arcs[i][j]
D(k)=Min{D(k-1)[i][j]，D(k-1)[i][k]+D(k-1)[k][j]} 0≤k≤n-1
【答案】
D(-1)D(0)D(1)D(2)
D
0 1 2 0 1 2 0 1 2 0 1 2
0 0 1 7 0 1 7 0 1 4 0 1 4
1 ∞0 3 ∞0 3 ∞0 3 1
2 0 3
2 9 ∞0 9 10 0 9 10 0 9 10 0
P(-1)P(0)P(1)P (2)
P
0 1 2 0 1 2 0 1 2 0 1 2
0 AC AB AC AB AC ACB AC ACB
1 CB CB CB CBA CB
2 BA BA BAC BA BAC BA BAC
每对顶点之间的最短路径及长度总结如下：
顶点A到顶点C最短路径为：A->C，长度为：１
顶点A到顶点B最短路径为：A->C->B，长度为：4
顶点C到顶点A最短路径为：C->B->A，长度为：12
顶点C到顶点B最短路径为：C->B，长度为：3
顶点B到顶点A最短路径为：B->A，长度为：9
顶点B到顶点C最短路径为：B->A->C，长度为：10
8.4应用题
1．顺序查找时间为O(n)，二分法查找时间为O(log2n)，散列法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃?
【答案】不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。
2．对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?
【答案】n-1次
【解析】设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。
3．若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：
（1）查找不成功，即表中无关键字等于给定值K的记录；
（2）查找成功，即表中有关键字等于给定值K的记录。
【答案】
（1）不成功时需要n+1 次比较
（2）成功时平均为(n+1)/2次
【解析】有序表和无序表顺序查找时，都需要进行n+1次比较才能确定查找失败。因此平均查找长度都为n+1。查找成功时，平均查找长度都为(n+1)/2，有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。
4．设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。
【答案】
（1）查找a 的过程如下(圆括号表示当前比较的关键字)，经过三次比较，查找成功。
（2）g 的查找过程如下，一次比较成功。
[a b c d e f (g) h i j k p q ] （3）n 的查找过程如下， 经过四次比较，查找失败。 5．为什么有序的单
链表不能进行折半查找?
【答案】因
为链表无法进行随机访问，如
果要访问链表的中
间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 6．构造有12个元素的二分查找的判定树，并求解下列问题： （1）各元素的查找长度最大是多少？
（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？ （3）查找第5个元素依次要比较哪些元素？ 【答案】12个元素的判断树如下图所示：
（1）最大查找长度是树的深度4。
（2）查找长度为1的元素有1个，为第6个，查找长度为2的元素有2个，为第3个和第9个，查找长度为3的元素有4个，为第1、4、7、11个，查找长度为4的元素有5个，为第2、5、8、10、12个。
（3）查找第五个元素依次比较6，3，4，5。
7．以数据集合{1,2,3,4,5,6}的不同序列为输入，构造4棵高度为4的二叉排序树。 【答案】
图1 图2
下标
1 2 3 4 5 6 7 8 9 10 11 12 13 区间 第一次比较 a b c d e f (g) h i j k p q [a..q] 第二次比较 a b (c ） d e f g h i j k p q [a..f] 第三次比较
(a ）
b
c
d
e
f
g
h
i
j
k
p
q
[a..b]
下标 1 2 3 4 5 6 7 8 9 10 11 12 13 区间 第一次比较 a b c d e f (g) h i j k p q [a..q] 第二次比较 a b c d e f g h i (j) k p q [h..q] 第三次比较 a b c d e f g h i j k (p) q [k..q] 第四次比较 a b c d e f g h i j (k) p q [k] 6 5 3 9 12 2 4 11 7 1 8 10 1 6 5 3
2 4 4
3 1 6 2 5
图3 图4
8．直接在二叉排序树中查找关键码K 与从中序遍历输出的有序序列中用二分查找法查找关键码K ，其数据比较次数是否相同？
【答案】不相同。
【解析】因为二分查找得到的判定树和二叉排序树的形状不一定相同。 9．已知一棵二叉排序树如下：
（1）假如删除关键字28，画出新二叉树。 （2）若查找56，需和哪些关键字比较。 【答案】
（1）删除元素28后，需修改二叉排序树的形态，可用结点28左子树上最大的结点代替它如图（1），也可用其右子树上最小的结点代替它，如图（2）。
图（1） 图（2）
（2）若要查找56，需和38、49、55、56进行4次比较。
10．设散列函数为h(key)=key%101，解决冲突的方法为线性探测，表中用"-1"表示空单元。
38 35 28 49 56 22 34 55 47 17 48 50 38 35 22 49 56 34 55 47 17 48 50 38 34 49 56
22 35 55 47 17 48 50 2 1 4 6 5 3 2 1 59 6
3 4
0 1 2 3 202 304 507
（1）若删去散列表HT 中的304（即令HT[1]=-1）之后，在表HT 中查找707将会发生什么？
（2）若将删去的表项标记为"-2"，查找时探测到"-2"继续向前搜索，探测到"-1"时终止搜索。请问用这种方法删去304后能否正确地查找到707？
【答案】 （1）查找707时，首先根据散列函数计算得出该元素应在散列表中的0单元，但是在0单元没有找到，因此将向下一单元探测，结果发现该单元是-1(为空单元)，所以结束查找，这将导致707无法找到。
（2）如果改用"-2"作为删除标记，则可以正确找到707所在的结点。
11．已知散列表的地址区间为0～11，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。
【答案】构造散列表如下（每个元素的查找长度标注在该元素的下方）。
等概率情况下成功时的平均查找长度为（1×5＋2＋3＋4＋5）/9＝19/9
12．设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。
【答案】
在等概率情况下成功的平均查找长度为： (1*5+2*2+3*1+4*1)/9=16/9
13．假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。
【答案】
序号 1 2 3 4 5 6 7 8 9
10 元素值 32 75 29 63 48 94 25 46 18 70 初始地址 6 10 3 11 9 3 12 7 5 5 最终地址 6 10 3 11 9 4 12 7 5 8
构造的散列表如下：
在等概率情况下成功的平均查找长度为(1*7+2*5+3*1+4*1)/14=24/14
14．散列表的地址区间为0～15，散列函数为H(key)=key%13。设有一组关键字{19,01,23,14,55,20,84}, 采用线性探测法解决冲突，依次存放在散列表中。问：
0 1 2 3 4 5 6 7
29 94 18 32 46
（1）元素84存放在散列表中的地址是多少？
（2）搜索元素84需要的比较次数是多少？
【答案】构造的散列表如下：
0 1 2 3 4 5 6 7 8 9
1 14 55 19 20 84
（1）元素84存放在散列表中的地址是8。
（2）搜索元素84需要的比较3次。
9.4应用题
1．什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?
【答案】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。
外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。
假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字，若采用某种排序方法后，使得这些具有相同关键字的记录在排序前后相对次序依然保持不变，则认为该排序方法是稳定的，否则就认为排序方法是不稳定的。
2．冒泡排序算法是否稳定？为什么？
【答案】冒泡排序算法是稳定的。因为依据该排序算法的基本思想，排序过程只比较相邻两个记录的关键字，若交换记录也只在相邻二个记录之间进行，从而可知在交换过程中不会出现跨越多个记录的情形。即使是相邻两个记录关键字相同时，经过比较也不会产生相邻记录的交换。所以冒泡排序法不会改变相同关键字记录的相对次序，故是稳定的。
3．在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？
【答案】如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如：
初始关键字：59 45 10 90
第一趟排序：45 10 59 90
第二趟排序：10 45 59 90
其中45在第一趟排序中移向了与最终位置相反的方向。但在快速排序中不会出现这种情况，因为在每趟排序中，比基准元素大的都交换到右边，而比基准元素小的都交换到左边。
4．设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。
（1）直接插入排序（2）希尔排序（增量为5,2,1）
（3）起泡排序（4）快速排序
（5）基数排序（6）堆排序
【答案】
（1）直接插入排序
（2）希尔排序(增量为5,2,1)
（3）起泡排序
（4）快速排序
（5）基数排序
按最低位分配
收集
按最高位分配
收集
（6）堆排序
第一步，形成初始的最大堆(略)，第二步，做堆排序。
初始排列，不是最大堆形成初始最大堆交换0#与9# 对象
从0# 到8# 重新形成堆交换0# 与8# 对象从0# 到7# 重新形成堆
交换0# 与7# 对象从0# 到6# 重新形成堆交换0# 与6# 对象
从0# 到5# 重新形成堆交换0# 与5# 对象从0# 到4# 重新形成堆
交换0# 与4# 对象从0# 到3# 重新形成堆交换0# 与3# 对象
从0# 到2# 重新形成堆交换0# 与2# 对象从0# 到1# 重新形成堆
交换0# 与1# 对象从0# 到1# 重新形成堆，得到结果
5．试构造对5个整数元素进行排序，最多只用7次比较的算法思想。
【答案】设5个元素分别用a，b，c，d，e表示，取a与b，c与d进行比较，若a>b，c>d（也可能是a
6．对一个具有7个记录的文件进行快速排序，请问：
（1）在最好情况下需进行多少次比较？并给出一个最好情况初始排列的实例。
（2）在最坏情况下需进行多少次比较？为什么？并给出此时的实例。
【答案】
（1）在最好情况下，由于快速排序是一个划分子区间的排序，每次划分最好能得到两个长度相等的子表，
设表的长度为n=2k-1，显然有，第一遍划分得到两个长度均为n/2的子表。第二遍划分得到4个长
度均为n/4的子表，以此类推，总共进行k=log
2
(n+1)遍划分，各子表的长度均为1时，此时排序结束。
由于n=7,k=3，在最好情况下，第一遍经过6次，可找到一个其基准是正中间的元素，第二遍分别对两个子表（此时长度为3）进行排序，各需要2次，这样就可将整个数据序列排序完毕，从而知7个数据的最好情况下需进行10次比较。如：4，7，5，6，3，1，2。
（2）在最坏情况下，若每次划分时用的基准，它的关键字值是当前记录中最大（或最小值），那么每次划分只能得到左子表（或右子表），子表长度只比原表减少了一个。因此，若初始排列的记录是按关键字递增或递减的，而所得的结果须为递减或递增排列的，此时快速排序就退化为与冒泡排序相似，而且时间复杂度为O(n2)，此时反而不快了。对于n=7的数据序列，显然最坏情况下的比较次数为21。例如：7，6，5，4，3，2，1。
7．如果某个文件经内排序得到80个初始归并段，试问：
（1）若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？
（2）如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？
【答案】
（1）设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = ?log
k m? = ?log
k
80? = 3得：
k3≥80。由此解得k≥3，即应取的归并路数至少为3。
（2）设多路归并的归并路数为k ，需要k 个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = ?log k m ? = ?log 1480? = 2。即至少需2趟归并可完成排序。若限定这个趟数，由S = ?log k 80? = 2，有80≤k 2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。
专升本试题(数据结构)
(A )数据的逻辑结构 (B )数据的存储结构 《数据结构》专升本考试试题 (2015 年 3 月) (C )数据的逻辑结构和存储结构 12.算法分析的两个主要方面是( (A )空间复杂度和时间复杂度 (C )可读性和文档性 (D )数据的逻辑结构、存储结构及其基本操作 )o (B )正确性和简单性 (D )数据复杂性和程序复杂性 一、单项选择题(本大题共 20小题，每小题2分，共40分) 1 ?对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为( (A) 正确性 (B) 可行性 ( C) 健壮性 2 ?设S 为C 语言的语句,计算机执行下面算法时， for(i=n-1 ； i>=0 ； i--) for(j=0 ; jn ext==head (B ) p-> next==NULL (C ) p==NULL (D ) p==head 16. 一个栈的输入序列为： a ，b ，c ，d ，e ，则栈的不可能输出的序列是( )o (A ) a,b,c,d,e (B ) d,e,c,b,a (C ) d,c,e,a,b (D ) e,d,c,b,a 17.设SUBSTR(S,i,k)是求S 中从第i 个字符开始的连续k 个字符组成的子串的操作，则对 5 ?深度为k 的完全二叉树，其叶子结点必在第( (A ) k-1 (B ) k (C ) k-1 和 k (D ) 6?具有60个结点的二叉树，其叶子结点有12个， (A ) 11 ( B ) 13 (C ) 48 ( D 37 利于删除操作 利于随机访问 )层上。 1至k 则度为1的结点数为( 7.图的Depth-First Search(DFS) 遍历思想实际上是二叉树( (A )先序 (B )中序 (C )后序 (D )层序 8 .在下列链队列Q 中，元素a 出队的操作序列为( )遍历方法的推广。 S= ' Beijing&Nanjing '，SUBSTR(S,4,5)=( ) (A )‘iji ng ' (B )' jing& ' (C )' ingNa ' (D ) 'ing&N ' 18.广义表((a),a) 的表尾是( )o (A ) a (B ) (a) (C )() (D ) ((a)) 19. 在一棵具有5层的满二叉树中结点总数为( )o (A ) 31 (B ) 32 (C ) 33 (D ) 16 20. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )o (A )完全图 (B )连通图 (C )有回路 (D ) —棵树 二、填空题(本大题共20个空，每空2分，共40分) Q (A ) (B ) (C ) (D ) p=Q.fr ont->n ext; p->n ext= Q.front->n ext; p=Q.fr ont->n ext; Q.front->n ext=p->n ext; p=Q.rear- >n ext; p->n ext= Q.rear- >n ext; p=Q->n ext; Q->n ext=p->n ext; 1 .逻辑结构决定了算法的 ____________ ，而存储结构决定了算法的 _____________ o 2. _______________________ 栈和队列都是一种 ______________________ 的线性表，栈 和删除只能在 ______________ 进行。 3. 线性表(a 1,a 2,…,a n )的顺序存储结构中，设每个单元的长度为L,元素a i 的存储地址LOC 4. 已知一双向链表如下(指针域名为next 和prior): 9. Huffman 树的带权路径长度WP 等于( (A )除根结点之外的所有结点权值之和 (C )各叶子结点的带权路径长度之和 )域存储后继结点的地址。 (C ) rchild (D ) root )o 10?线索二叉链表是利用( (A ) Ichild (B ) data 11 ?研究数据结构就是研究( (B ) (D ) ) 所有结点权值之和 根结点的值 现将p 所指的结点插入到x 和y 结点之间，其操作步骤为： ________________________ 5 . n 个结点无向完全图的的边数为 ________________________ ， n 个结点的生成树的边 为 ____________________ o
数据结构期末考试复习笔记
判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点
山东07年专升本考试数据结构模拟试题.
山东:07年专升本考试数据结构模拟试题1 一、填空题:(每小题2分,共10分 1. 设有数据结构(D,R,其中 D 是数据元素的有限集,R 是的有限集。 2. 深度为 k 的二叉树其结点数至多有个。 3. 栈是一种特殊的线性表,它允许在表的一端进行操作。 4. 通常象交通、道路问题的数学模型是一种称为的数据结构。 5. 哈希表是一种查找表,可以根据哈希函数直接获得。 二、单项选择题:(每小题2分,共10分 对于下列各题,在备选答案中选出一个正确的,并将其编号填在“”位置上。 1. 若线性表最常用的操作是存取第 i 个元素及其前驱元素的值,则采用存储方式最节省运算时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 2. 下列排序算法中,算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。。 A. 直选择排序 B. 冒泡排序
C. 归并排序 D. 堆排序 3. 队列的操作原则是。 A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删除 4. 在具有 n 个结点的二叉链表中,非空的链域个数为。 A. n-1 B. n C. n+1 D. 不确定 5. 对具有 n 个元素的有序查找表采用折半查找算法查找一个键值,其最坏比较次数的数量级为。 A. O(log2n B. O(n C. O(nlog2n D. O(n2 三、判断题:(每小题2分,共10分
判断下列各题是否正确,若正确,在题后的括号内填“T”,否则填“F”。 1. 在栈为空的情况下不能作出栈处理,否则,将产生下溢出。( 2. 如果有向图 G=(V, E 的拓扑序列唯一,则图中必定仅有一个顶点的入度为0、一个顶点的出度为0。( 3. 在大根堆中,必定满足每个结点的键值大于其左右子树中所有结点的键值。( 4. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。( 5. 在索引顺序表中,对索引表既可采用顺序查找,也可采用二分查找。( 四、解答下列各题:(每题10分,共40分 1. 已知线性表 L 采用带头结点的的单向循环链表表示,试给出它的存储结构类型描述及相应的示意图。。 2. 已知一棵二叉树的先序、中序和后序序列如下所示,请填写各序列中空格处的结点,并画出该二叉树的二叉链表存储结构示意图。 先序序列是:_ B _ F _ I C E H _ G;中序序列是:D _ K F I A _ E J C _ ; 后序序列是:_ K _ F B H J _ G _ A 3. 已知数据表为(48,70,33,65,24,56,12,92,86,22,a 写出采用快速排序算法进行排序时第一趟快速划分的详细过程及结果;b 写出按基数排序思想对最低位进行一次分配和收集的结果。 4. 对图1所示的带权无向图,写出它的邻接矩阵和深度优先搜索序列,并按克鲁斯卡算法求其最小生成树(写出求解的详细过程示意图。 图1 带权无向图 五、算法设计题:(前两题必做,每题15分,共30分;第三题为附加题,选做,10分
郝斌数据结构自学笔记--知识点+程序源代码
郝斌数据结构自学笔记 --知识点+程序源代码 By-HZM 1_什么叫做数据结构 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。 ~ 数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作 2_衡量算法的标准 算法 解题的方法和步骤 ~ 衡量算法的标准 1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性 3_数据结构的特点 【 数据结构的地位 数据结构是软件中最核心的课程 程序=数据的存储+数据的操作+可以被计算机执行的语言 4_预备知识_指针_1 5_预备知识_指针_2 * 指针的重要性： 指针是C语言的灵魂 定义：
地址： 地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】 CPU=====地址线，控制线，数据线=====内存 指针： … 指针就是地址，地址就是指针。 指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。 分类： 1.基本类型的指针 2.指针和数组的关系 ? 变量并不一定连续分配，随机分配内存。 内存： 内存是多字节组成的线性一维存储空间。 内存的基本划分单位是字节。 每个字节含有8位，每一位存放1个0或1个1. 内存和编号是一一对应的。 （ 软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。 NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。 2）局部变量只在本函数内部使用。 如何通过被调函数修改主调函数中普通变量的值。 1）实参为相关变量的地址； < 2）形参为以该变量的类型为类型的指针变量； 3）在被调函数中通过 *形参变量名的形式的形式就可以修改主函数。 CASE 1 #include<> int main(void) { |
数据结构专升本模拟题及答案
作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2. 链表不具有的特点是（） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A．2 B．3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D．rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。 A．连接B．求子串 C．模式匹配D．判子串 9、设串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))的结果是（）。
数据结构复习笔记
数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------
专升本试题数据结构
《数据结构》专升本考试试题 (2015年3月) 一、单项选择题(本大题共20小题,每小题2分,共40分) 1.对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为( )。 (A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性 2.设S为C语言的语句,计算机执行下面算法时,算法的时间复杂度为( )。 for(i=n-1;i>=0;i--) for(j=0;j
数据结构专升本习题集
第一章概论 选择题 1.要求同一逻辑结构的所有数据元素具有相同的特性,这意味着___ A.数据元素具有同样的特点 B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致 C.每个数据元素都同一样式 D.数据元素所包含的数据项的个数要相等 2.数据结构是一门研究非数值计算的程序设计问题中计算机的_____以及它们之间的关系和运算等的学科 A.操作对象 B.计算方法 C.逻辑存储 D.数据映像 3.数据结构被形容地定义为（D，R），其中D是_____的有限集合，R是D上的关系有限集合． A.算法 B.数据元素 C.数据操作 D.逻辑结构 4.在数据结构中,从逻辑上可以把数据结构分为_____ A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表的顺序存储结构是一种____的存储结构，线性表的链式存储结构是一种顺序存取的存储结构． A.随机存取 B.顺序存取 C.索引存取 D.Hash存取 6.算法分析的目的是_____ A.找出数据结构图的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 7.计算机算法指的是解决某一问题的有限运算序列,它必须具备输入、输出和____等五个特征。 A.可行性、可移值性和可扩充性 B可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 8.线性表若采用顺序存储结构，要求内存中可用存储单元的地址_____。 A.必须是连续的 B.部分必须是连续的
C.一定是不连续的 D.连续不连续都可以 9.在以下的叙述中,正确的是______. A.线性表的线性存储结构优于链式存储结构 B.二维数组是它的每个数据元素为一个线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10.根据数据元素之间关系的不同特性,以下四类基本的逻辑结构反映了四类基本的数据组织形式,其中解释错误的是____ A.集合中任何两个结点之间都有逻辑关系但组织形式松散 B.线性结构中结点按逻辑关系依次排列形成一条"锁链" C.树形结构具有分支、层次特性，其形态有点像自然界中的树 D.图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 11.以下说法正确的是_____ A.数据元素是数据的最小单位 B.数据项是数据的基本单位 C.数据结构是带有结构的各数据项的集合 D.数据结构是带有结构的数据元素的集合 12．计算机算法指的是解决问题的有限运算序列，它必具备输入、输出和_____等五个特性． A.正确 B．可行性、确定性和有穷性
数据结构学习总结
数据结构学习总结 经过一学期的学习，我对数据结构有了我自己的认识。一开始，我以为它和C语言和C++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生
专升本《数据结构》_试卷_答案
专升本《数据结构》 一、（共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 .标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 .标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 .标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 .标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 .标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 .标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h .标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 .标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分） A.循环队列 B.双向链表 C.哈希表 D.数组 .标准答案：D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分） A.O(1) B.O(log n) C.O(n) D.O(n2) .标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分） A.k B.k-1 C.2k D.k+1 .标准答案：D 15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分） A.abcd B.dcba C.acbd D.dbca .标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分） A.n(n-1) B.n(n-1)/2 C.2n D.n-1 .标准答案：D 18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分） A.队列 B.树 C.栈 D.集合 .标准答案：A
专升本考试试题分析包括英语高数数据结构考试原题
第一章英语；英语整体上看试卷一共分为六道大题，一是单项选择题；试题分析；一单项选择：20’；ishelpfulinlookingforajo；A.certificateB.grad eC.re；A.senseB.savingC.imforma；A.momentB.pointC.heartD.；4.Mymebysa yingthatIcould；A.discou 第一章英语 英语整体上看试卷一共分为六道大题，一是单项选择题共计20道20分；二是完型填空10道10分；三是阅读，分三个篇章，每个篇章5道选择，各2分，总计30分；四是用词的适当形式填空，10道10分；五是翻译(汉译英)，5道2 0分；六是写作10分；总计100分。 试题分析 一单项选择：20’ is helpful in looking for a job，but it doesn’t mean a job. A.certificate B.grade C.record D.debt A.sense B.saving C.imformation https://www.wendangku.net/doc/8d9037715.html,fort A.moment B.point C.heart D.face 4.My me by saying that I could win in the speech contest ,so I to ok part in it. A.discouraged B.encouraged C.courage D.asked 5.His new book to the top as the bestseller.
A.rocketed B.raised C.stayed D.reached 6.The president was invited to address the audience at the openin g Of the Olympic Games. A.ceremony B.speech C.meeting D.celebration 7.In some western is that blank cats will bring misforture to peo ple. A.superstar B.superpower C.superstitious D.superstition 8.The the cup from the table with any guest’s knowledge . A.reminded B.reduced C.refused D.removed A.looks B.sets C.symbolizes D.Seeks 10.Although we are of the same age,we height and weight. 11.Some soldiers are very his orders strictly. A.loyalty B.loyal C.faithfulness D.faith （损坏）. A.What B.whatever C.who D.whoever 13.All of those the peace conference were asked to sign their nam es on piece of cloth. A.attended B.preseted C.went D. was
数据结构(专升本)
数据结构(专升本) 单选题 1. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是序列的是_____。(5分) (A) 2 3 4 1 5(B) 5 4 1 3 2(C) 23 1 4 5(D) 1 5 4 3 2标准答案 是：B 2. 设一个栈的输入序列是1，2，3，4，5,则下列序列中， 是栈的合法输出序列的是_____。(5分) (A) 51 2 3 4(B) 4 5 1 3 2(C) 43 1 2 5(D) 3 2 1 5 4标准答案 是：D 3. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中， 不可能是它的输出序列的是_____。(5分) (A) a，c，b，d(B) b, c，d，a(C) c,d，b,a(D) d, c，a，b标 准答案是：D 4. 设abcdef以所给的次序进栈，若在进栈操作时，允许 退栈操作,则下面得不到的序列为_____。(5分) (A) fedcba(B) bcafed(C) dcefba(D) cabdef标准答案是：D 5. 输入序列为ABC，可以变为CBA时，经过的栈操作为 _____(5分) (A) push,pop,push,pop,push,pop(B) push,push,push,pop,pop,pop (C) push,push,pop,pop,push,pop(D) push,pop,push,push,pop,pop标准答案是：B 6. 表达式a*(b+c)-d的后缀表达式是_____。(5分) (A) abcd*+-(B) abc+*d-(C) abc*+d-(D) -+*abcd标准答案是： B 7. 设计一个判别表达式中左，右括号是否配对出现的算 法，采用_____数据结构最佳。(5分) (A) 线性表的顺序存储结构(B) 队列(C) 线性表的链式存 储结构(D) 栈标准答案是：D 8. 用链接方式存储的队列，在进行删除运算时_____。(5 分) (A) 仅修改头指针(B) 仅修改尾指针(C) 头、尾指针都要修 改(D) 头、尾指针可能都要修改标准答案是：D 9. 用不带头结点的单链表存储队列时,其队头指针指向队 头结点,其队尾指针指向队尾结点，则在进行删除操作时 (A) 仅修改队头指针(B) 仅修改队尾指针(C) 队头、队尾指 针都要修改(D) 队头,队尾指针都可能要修改 标准答案是：D 10. 循环队列A[0..m-1]存放其元素值，用front和rear分 别表示队头和队尾，则当前队列中的元素数是_____。(5 分) (A) (rear-front+m)%m(B) rear-front+1(C) rear-front-1(D) rear-front标准答案是：A 11. 栈和队列的共同点是_____。(5分) (A) 都是先进先出(B) 都是先进后出(C) 只允许在端点处插入和删除元素(D) 没有共同点标准答案是：C 12. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是_____。(5分) (A) 6(B) 4(C) 3(D) 2标准答案是：C 13. 下面关于串的的叙述中，哪一个是不正确的？_____(5分) (A) 串是字符的有限序列(B) 空串是由空格构成的串(C) 模式匹配是串的一种重要运算 (D) 串既可以采用顺序存储，也可以采用链式存储 标准答案是：B 14. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为_____。(5分) (A) 求子串(B) 联接(C) 匹配(D) 求串长 标准答案是：C 15. 已知串S=‘aaab’,其Next数组值为_____。(5分) (A) -10 1 2(B) 0 0 1 2(C) 01 2 0(D) 0 1 0 0标准答案是：A 16. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是_____。(5分) (A) 1175(B) 1180(C) 1205(D) 1210标准答案是：A 17.设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为_____。(5分) (A) （i-1）*n+j(B) （i-1）*n+j-1(C) i*（j-1）(D) j*m+i-1标准答案是：A 18. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是_____。(5分) (A) 60(B) 66(C) 18000(D) 33标准答案是：B 19. 数组A[0..4,-1..-3,5..7]中含有元素的个数_____。(5分) (A) 55(B) 45(C) 36(D) 16标准答案是：B 20. 对稀疏矩阵进行压缩存储目的是_____。(5分) (A) 便于进行矩阵运算(B) 便于输入和输出(C) 节省存储空间(D) 降低运算的时间复杂度标准答案是：C 单选题 1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____存储方式最节省运算时间。(5分) (A) 单链表(B) 仅有头指针的单循环链表(C) 双链表(D) 仅有尾指针的单循环链表标准答案是：D 2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一 个新元素的算法的时间复杂度为______ (1<=i<=n+1)。(5分)
数据结构专升本模拟题及参考答案
东北农业大学网络教育学院 数据结构专升本作业题 作业题（一） 一、单项选择题 1. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1; A．O(1) B．O(n) C．O(n2) D．O(n3) 4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A．2 B．3 C．4 D．6 5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A．98 B．100 C．102 D．106 6、判定一个栈s（最多元素为m0）为空的条件是（）。 A．s-〉top! =0 B．s-〉top= =0 C．s-〉top! =m0 D．s-〉top= =m0 7、循环队列用数组A[m]（下标从0到m-1）存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 A．（rear-front+m）%m B．rear-front+1 C．rear-front-1 D． rear-front 8、设有两个串S1与S2，求串S2在S1中首次出现位置的运算称作（）。 A．连接 B．求子串 C．模式匹配 D．判子串
数据结构复习笔记
第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。
- 最全最新版专升本《数据结构》试题答案
- 数据结构专升本复习
- 专升本试题数据结构
- 最新云南省()专升本十套数据结构(试题及答案)资料
- 专升本数据结构考前必看
- 数据结构专升本模拟题及参考答案
- 专升本《数据结构》
- 数据结构(专升本)
- 专升本试题(数据结构)教学文案
- 专升本十套-数据结构(试题及答案)
- 专升本试题(数据结构)83586
- 数据结构专升本习题集
- 最新专升本《数据结构》_试卷_答案
- 专升本试题(数据结构)
- 数据结构专升本模拟试题及参考答案
- 数据结构模拟题(专升本)含答案
- 专升本十套数据结构试题及答案
- 数据结构专升本模拟题及参考答案
- 数据结构模拟题(专升本)含答案
- 最全版专升本《数据结构》试题答案