数据结构简答题和论述题
1、试描述数据结构和抽象数据类型的概念与程序设计语⾔中数据类型概念的区别。
【解答】数据结构是指相互之间存在⼀定关系的数据元素的集合。 ⽽
抽象数据类型是指⼀个数据结构以及定义在该结构上的⼀组操作。 程序设计语⾔中的数据类型是⼀个值的集合和定义在这个值集上⼀组操作的总称。抽象数据类型可以看成是对数据类型的⼀种抽象。
串：是零个或多个字符组成的有限序列。
串是⼀种特殊的线性表，它的每个结点仅由⼀个字符组成。
空串 ：长度为零的串，它不包含任何字符。
空⽩串 ：仅由⼀个或多个空格组成的串
⼦串 ：串中任意个连续字符组成的⼦序列称为该串的⼦串。
串变量和串常量
通常在程序中使⽤的串可分为：串变量和串常量。
（1）串变量 ：串变量和其它类型的变量⼀样，其取值是可以改变的。
（2）串常量 ：串常量和整常数、实常数⼀样，在程序中只能被引⽤但不能改变其值。即只能读不能写。
（1）树形图表⽰： 树形图表⽰是树结构的主要表⽰⽅法。
（2）树的其他表⽰法
① 嵌套集合表⽰法：是⽤集合的包含关系来描述树结构。
② 凹⼊表表⽰法：类似于书的⽬录
③ ⼴义表表⽰法：⽤⼴义表的形式表⽰的。上图 (a)树的⼴义表表⽰法如下：
（A（B（E，F（I，J））， C，D（G，H）））
1．中序遍历的递归算法定义：
若⼆叉树⾮空，则依次执⾏如下操作：
(1)遍历左⼦树； (2)访问根结点； (3)遍历右⼦树。
2．先序遍历的递归算法定义：
若⼆叉树⾮空，则依次执⾏如下操作：
(1) 访问根结点； (2) 遍历左⼦树； (3) 遍历右⼦树。
3．后序遍历得递归算法定义：
若⼆叉树⾮空，则依次执⾏如下操作：
(1)遍历左⼦树； (2)遍历右⼦树； (3)访问根结点。
2、链表具有的特点是
B 插⼊、删除不需要移动元素
C 不必事先估计存储空间
D 所需空间与线性表长度成正⽐
顺序队列
（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
（2） 顺序队列的表⽰
①和顺序表⼀样顺序队列⽤⼀个向量空间存放当前队列中的元素。
②由于队列的队头和队尾的位置是变化的，设置两个指针 front 和 rear 分别指⽰队头元素和队尾元素在向量空间中的位置，它们的初值在队
列初始化时均应置为 0。
顺序队列的基本操作
①⼊队时：将新元素插⼊ rear 所指的位置，然后将 rear 加 1。
②出队时：删去 front 所指的元素然后将 front 加 1 并返回被删元素。
注意 ：①当头尾指针相等时，队列为空。
②在⾮空队列⾥，队头指针始终指向队头元素，尾指针始终指向队尾元素的下⼀位置。
顺序队列中的溢出现象
① "下溢 "现象 ：当队列为空时，做出队运算产⽣的溢出现象。 “下溢 ”是正常现象，常⽤作程序控制转移的条件。
② "真上溢 "现象 ：当队列满时，做进栈运算产⽣空间溢出的现象。 “真上溢 ”是⼀种出错状态，应设法避免。
③ "假上溢 "现象 ：由于⼊队和出队操作中，头尾指针只增加不减⼩，致使被删元素的空间永远⽆法重新利⽤。
3、请说明顺序表和单链表各有何优缺点，并分析下列情况下，采⽤何种存储结构更好些。
⑴ 若线性表的总长度基本稳定，且很少进⾏插⼊和删除操作，但要
求以最快的速度存取线性表中的元素。
⑵ 如果 n 个线性表同时并存，并且在处理过程中各表的长度会动态
发⽣变化。
⑶ 描述⼀个城市的设计和规划。
串变量和串常量的区别
顺序表的优点：
① ⽆需为表⽰表中元素之间的逻辑关系⽽增加额外的存储空间；
② 可以快速地存取表中任⼀位置的元素（即随机存取） 。
顺序表的缺点：
① 插⼊和删除操作需移动⼤量元素；
② 表的容量难以确定；③ 造成存储空间的“碎⽚” 。
单链表的优点：
① 不必事先知道线性表的长度；
② 插⼊和删除元素时只需修改指针，不⽤移动元素。单
链表的缺点：
① 指针的结构性开销；
② 存取表中任意元素不⽅便，只能进⾏顺序存取。
4、设单链表以⾮递减有序排列，设计算法实现在单链表中删去值相同的多余结点。
【解答】从头到尾扫描单链表， 若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下：
5、在单链表中， 除了头结点以外， 任⼀结点的存储位置由 （ 其前趋结点的指针域）指⽰。
6、当线性表采⽤顺序存储结构时，其主要特点是（ 逻辑结构中相邻的结点在存储结构中仍相邻）。
7、在双链表中，每个结点设置了两个指针域，其中⼀个指向（ 前驱）结点，另⼀个指向（ 后继）结点。
8、设有⼀个空栈，栈顶指针为 1000H，现有输⼊序列为 1、2、3、4、5， 经过 push，push，pop，push，pop，push，push 后，输出序列是（ 23），栈顶指针为（1003H ）。
9、 栈通常采⽤的两种存储结构是 （顺序存储结构和链接存储结构（或顺序栈和链栈） ）；
其判定栈空的条件分别是 （栈顶指针 top= -1 和 top=NULL，栈顶指针 ），
判定栈满的条件分别是（ top 等于数组的长度和内存⽆可⽤空间）。
10、（栈）可作为实现递归函数调⽤的⼀种数据结构。
【分析】递归函数的调⽤和返回正好符合后进先出性。
11、表达式 a*(b+c)-d 的后缀表达式是（ abc+*d-）。
【分析】将中缀表达式变为后缀表达式有⼀个技巧： 将操作数依次写下来，再将算符插在它的两个操作数的后⾯。
12、和队列是两种特殊的线性表，栈的操作特性是（ 后进先出，先进先出），队列的操作特性是（对插⼊和删除操作限定的位置不同 ），栈和队列的主要区别
13、循环队列的引⼊是为了克服（假溢出 ）。
14、数组 Q[n] ⽤来表⽰⼀个循环队列， front 为队头元素的前⼀个位置，rear 为队尾元素的位置，计算队列中元素个数的公式为（（rear-front+n ）% n）。
【分析】也可以是（ rear-front ）% n，但 rear-front 的结果可能是
负整数，⽽对⼀个负整数求模，其结果在不同的编译器环境下可能会有所不同。
15、⽤循环链表表⽰的队列长度为 n，若只设头指针，则出队和⼊队的时间复杂度分别是（Ｏ (1) ）和（Ｏ(n) ）。
【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；⼊队即是在终端结点的后⾯插⼊⼀个结点，这需要从头指针开始查终端结点的地址。
16、 串是⼀种特殊的线性表，其特殊性体现在（数据元素的类型是⼀个字符 ）。
17、 两个串相等的充分必要条件是（ 长度相同且对应位置的字符相等）。
【分析】例如 “abc” ≠"abc " ，“abc” ≠"bca" 。
18、 若⼀个栈的输⼊序列是 1，2，3，, ， n，输出序列的第⼀个元素是 n，则第 i 个输出元素是（n-i+1 ）。
19、⼀个栈的⼊栈序列是 1，2，3，4，5，则栈的不可能的输出序列是（ 43512）。
【分析】此题有⼀个技巧： 在输出序列中任意元素后⾯不能出现⽐该元素⼩并且是升序（指的是元素的序号）的两个元素。
20、设计⼀个判别表达式中左右括号是否配对的算法，采⽤（栈 ）数据结构最佳
【分析】每个右括号与它前⾯的最后⼀个没有匹配的左括号配对， 因此具有后进先出性。
21、在解决计算机主机与打印机之间速度不匹配问题时通常设置⼀个打印缓冲区，该缓冲区应该是⼀个（队列 ）
22、举例说明顺序队列的“假溢出”现象。
【解答】假设有⼀个顺序队列，如图 3-6 所⽰，队尾指针 rear=4 ，队头指针 front=1 ，如果再有元素⼊队，就会产⽣“上溢”，此时
的“上溢”⼜称为“假溢出” ，因为队列并不是真的溢出了，存储队列的数组中还有 2 个存储单元空闲，其下标分别为 0 和 1。23、空串和空格串有何区别？串中的空格符有何意义？空串在串处理
中有何作⽤？
【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可⽤来分隔⼀般的字符，便于⼈们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的⼦串。
24、如果进栈序列为 A、B、C、D，则可能的出栈序列是什么？
答：共 14 种，分别是：ABCD ，ABDC ，ACBD ，ACDB ，ADCB ，BACD，BADC ，BCAD ，BCDA ，BDCA ，CBAD ，CBDA ，CDBA ，DCBA
25、简述队列和栈这两种数据结构的相同点和不同点。
【解答】相同点：它们都是插⼊和删除操作的位置受限制的线性表。不同点：栈是限定仅在表尾进⾏插⼊和删除的线性表， 是后进先出的线性表，⽽队列是限定在表的⼀端进⾏插⼊，在另⼀端进⾏删除的线性表，是先进先出的线性表。
26、利⽤两个栈 S1和 S2 模拟⼀个队列，如何利⽤栈的运算实现队列的插⼊和删除操作，请简述算法思想。
【解答】利⽤两个栈 S1和 S2模拟⼀个队列， 当需要向队列中插⼊⼀个元素时，⽤ S1来存放已输⼊的元素，即通过向栈 S1 执⾏⼊栈操作来实现；当需要从队列中删除元素时，则将 S1中元素全部送⼊到 S2中，再从 S2中删除栈顶元素，最后再将 S2中元素全部送⼊到 S1中；判断队空的条件是：栈 S1和 S2同时为空。
27、设计算法把⼀个⼗进制整数转换为⼆⾄九进制之间的任⼀进制
数输出。
【解答】算法基于原理： N=(N div d) ×d + N mod d （div 为整除
运算， mod为求余运算）。
28、⼀棵具有 n 个结点的⼆叉树采⽤顺序存储结构，编写算法对该⼆
叉树进⾏前序遍历。
【解答】按照题⽬要求，设置⼀个⼯作栈以完成对该树的⾮递归算法，
思路如下：
① 每访问⼀个结点，将此结点压栈，查看此结点是否有左⼦树，若
有，访问左⼦树，重复执⾏该过程直到
左⼦树为空。
② 从栈弹出⼀个结点，如果此结点有右⼦树，访问右⼦树执⾏步骤
①，否则重复执⾏步骤②。
具体算法如下：
29、以孩⼦兄弟表⽰法做存储结构，求树中结点 x 的第 i 个孩⼦。
【解答】先在链表中进⾏遍历，在遍历过程中查值等于 x 的结点，
然后由此结点的最左孩⼦域 firstchild
到值为 x 结点的第⼀个孩⼦，再沿右兄弟域 rightsib 到值为 x
结点的第 i 个孩⼦并返回指向这个孩⼦的
指针。
树的孩⼦兄弟表⽰法中的结点结构定义如下：
template
struct TNode
{
T data;
TNode *firstchild, *rightsib;
};
具体算法如下：
30、试出分别满⾜下列条件的所有⼆叉树：
⑴ 前序序列和中序序列相同。
⑵ 中序序列和后序序列相同。
⑶ 前序序列和后序序列相同。
【解答】 ⑴ 空⼆叉树、只有⼀个根结点的⼆叉树和右斜树。
⑵ 空⼆叉树、只有⼀个根结点的⼆叉树和左斜树。
⑶ 空⼆叉树、只有⼀个根结点的⼆叉树
31、以孩⼦兄弟表⽰法作为存储结构，编写算法求树的深度。
【解答】采⽤递归算法实现。若树为空树，则其深度为 0，否则其深
度等于第⼀棵⼦树的深度 +1和兄弟⼦
树的深度中的较⼤者。具体算法如下：
32、设计算法，判断⼀棵⼆叉树是否为完全⼆叉树。
【解答】根据完全⼆叉树的定义可知，对完全⼆叉树按照从上到下、
从左到右的次序（即层序）遍历应该
满⾜：
⑴ 若某结点没有左孩⼦，则其⼀定没有右孩⼦；
⑵ 若某结点⽆右孩⼦，则其所有后继结点⼀定⽆孩⼦。
若有⼀结点不满⾜其中任意⼀条，则该⼆叉树就⼀定不是完全⼆叉
树。因此可采⽤按层次遍历⼆叉树的⽅
法依次对每个结点进⾏判断是否满⾜上述两个条件。 为此，需设两个
标志变量 BJ和 CM，其中 BJ表⽰已扫
描过的结点是否均有左右孩⼦， CM存放局部判断结果及最后的结果。
具体算法如下：
33、n 个顶点的⽆向图，采⽤邻接表存储，回答下列问题 ?
⑴ 图中有多少条边？
⑵ 任意两个顶点 i 和 j 是否有边相连？
⑶ 任意⼀个顶点的度是多少 ?
【解答】
⑴ 边表中的结点个数之和除以 2。
⑵ 第 i 个边表中是否含有结点 j 。
⑶ 该顶点所对应的边表中所含结点个数。
34、n 个顶点的⽆向图，采⽤邻接矩阵存储，回答下列问题：
⑴ 图中有多少条边？
⑵ 任意两个顶点 i 和 j 是否有边相连？
⑶ 任意⼀个顶点的度是多少？
【解答】
⑴ 邻接矩阵中⾮零元素个数的总和除以 2。
⑵ 当邻接矩阵 A中 A[i][j]=1 （或 A[j][i]=1 ）时，表⽰两顶点之间
有边相连。
⑶ 计算邻接矩阵上该顶点对应的⾏上⾮零元素的个数。
35、证明：⽣成树中最长路径的起点和终点的度均为１。
【解答】⽤反证法证明。
设 v1, v2, , , vk 是⽣成树的⼀条最长路径，其中， v1 为起点， vk
为终点。若 vk 的度为 2，取 vk 的另⼀个
邻接点 v，由于⽣成树中⽆回路，所以， v 在最长路径上，显然 v1,
v2, , , vk , v 的路径最长，与假设⽭盾。
所以⽣成树中最长路径的终点的度为 1。
同理可证起点 v1 的度不能⼤于 1，只能为 1。
36、已知⼀个连通图如图 6-6 所⽰，试给出图的邻接矩阵和邻接表存
储⽰意图，若从顶点 v1 出发对该图进
⾏遍历，分别给出⼀个按深度优先遍历和⼴度优先遍历的顶点序列。
【解答】邻接矩阵表⽰如下：
深度优先遍历序列为： v1 v2 v3 v5 v4 v6
⼴度优先遍历序列为： v1 v2 v4 v6 v3 v5
邻接表表⽰如下：
37、已知⽆向图 G的邻接表如图 6-10 所⽰，分别写出从顶点 1 出发
的深度遍历和⼴度遍历序列，并画出相
应的⽣成树。
【解答】深度优先遍历序列为： 1，2，3，4，5，6
对应的⽣成树为：
⼴度优先遍历序列为： 1，2，4，3，5，6
对应的⽣成树为：
38、试述顺序存储和链式存储的区别及各⾃的优缺点。
答：数组占⽤连续的内存空间，链表不要求结点的空间连续。
1）插⼊与删除操作： 由于数组在插⼊与删除数据时需移动⼤量的数据元素，⽽链表只需要改变⼀些指针的链接，因此，链表⽐数组易于实现数据的插⼊和删除操作。
2）内存空间的占⽤情况：因链表多了⼀个指针域，故较浪费空间，因此，在空间占⽤⽅⾯，数组优于链表。
3）数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取⽅式，⽽数组元素的访问是通过数组下标来实现的，是随机存取⽅式，因此，在数据存取⽅⾯，数组优于链表。数据的合并与分离：链表优于数组，因为只需要改变指针的指向
39、java堆和栈的区别：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。