数据结构简答题打印版.doc
《数据结构简答题打印版.doc》由会员分享，可在线阅读，更多相关《数据结构简答题打印版.doc（9页珍藏版）》请在冰点文库上搜索。
数据结构简答题
1.1简述下列术语：
数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：
数据是对客观事物的符号表示。
在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。
是对一般数据类型的扩展。
1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：
抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。
一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。
抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。
在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.7在程序设计中，可采用下列三种方法实现输出和输入：
（1）通过scanf和printf语句；
（2）通过函数的参数显式传递；
（3）通过全局变量隐式传递。
试讨论这三种方法的优缺点。
解：
（1）用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
（2）通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
（3）通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。
2.1描述以下三个概念的区别：
头指针，头结点，首元结点（第一个元素结点）。
解：
头指针是指向链表中第一个结点的指针。
首元结点是指链表中存储第一个数据元素的结点。
头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。
它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2填空题。
解：
（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
（2）顺序表中逻辑上相邻的元素的物理位置必定紧邻。
单链表中逻辑上相邻的元素的物理位置不一定紧邻。
（3）在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
（4）在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3在什么情况下用顺序表比链表好？
解：
当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。
3.2简述栈和线性表的差别。
解：
线性表是具有相同特性的数据元素的一个有限序列。
栈是限定仅在表尾进行插入或删除操作的线性表。
3.11简述队列和堆栈这两种数据类型的相同点和差异处。
解：
栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
4.1解：
空格串是指一个或多个空格字符（ASCII码为20H）组成的串，而空串中没有任何字符。
4.2解：
串赋值（StrAssign）、串比较（StrCompare）、求串长（StrLength）、串连接（Concat）、求子串（SubString）这五种基本操作构成串类型的最小操作子集。
6.2一棵度为2的树与一棵二叉树有何区别？
解：
二叉树是颗有序树，但度为2的树则未必有序。
三、简答题
1.描述以下三个概念的区别：
头指针，头结点，表头结点。
1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。
若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。
2.线性表的两种存储结构各有哪些优缺点？
2．线性表具有两种存储结构即顺序存储结构和链接存储结构。
线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：
而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。
3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？
为什么？
3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：
这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。
4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？
试说明理由。
4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。
因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。
5.在单循环链表中设置尾指针比设置头指针好吗？
为什么?
5．设尾指针比设头指针好。
尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O
（1）。
若用头指针来表示该链表，则查找终端结点的时间为O（n）。
6.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
6．共有14种可能的出栈序列，即为：
ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA
7.什么是队列的上溢现象？
一般有几种解决方法，试简述之。
7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。
当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。
对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。
（2）要避免出现“假溢出”现象可用以下方法解决：
第一种：
采用移动元素的方法。
每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。
第二种：
每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种：
采用循环队列方式。
将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。
8.下述算法的功能是什么?
LinkList*Demo（LinkList*L）
{//L是无头结点的单链表
LinkList*q,*p;
if（L&&L->next）
{q=L;L=L->next;p=L;
while（p->next）
p=p->next;
p->next=q;q->next=NULL;
}
return（L）;
}
8．该算法的功能是：
将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
四、应用题
1.已知一棵树边的集合为{，，，，，，，，，，，，}，请画出这棵树，并回答下列问题：
（1）哪个是根结点？
（2）哪些是叶子结点？
（3）哪个是结点g的双亲？
（4）哪些是结点g的祖先？
（5）哪些是结点g的孩子？
（6）哪些是结点e的孩子？
（7）哪些是结点e的兄弟？
哪些是结点f的兄弟？
（8）结点b和n的层次号分别是什么？
（9）树的深度是多少？
（10）以结点c为根的子树深度是多少？
1.解答：
a
b
c
d
e
g
f
h
i
m
n
j
k
i
图5-15
根据给定的边确定的树如图5-15所示。
其中根结点为a；
叶子结点有：
d、m、n、j、k、f、l；
c是结点g的双亲；
a、c是结点g的祖先；
j、k是结点g的孩子；
m、n是结点e的子孙；
e是结点d的兄弟；
g、h是结点f的兄弟；
结点b和n的层次号分别是2和5；
树的深度为5。
2.一棵度为2的树与一棵二叉树有何区别。
2.解答：
度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。
3.试分别画出具有3个结点的树和二叉树的所有不同形态？
3.解答：
略
4.已知用一维数组存放的一棵完全二叉树：
ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。
4.解答：
先序序列：
ABDHIEJKCFLG
中序序列：
HDIBJEKALFCG
后序序列：
HIDJKEBLFGCA
5.一棵深度为H的满k叉树有如下性质：
第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：
（1）各层的结点数目是多少？
（2）编号为n的结点的父结点如果存在，编号是多少？
（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？
（4）编号为n的结点有右兄弟的条件是什么？
其右兄弟的编号是多少？
5.解答：
（1）第i层上的结点数目是mi-1。
（2）编号为n的结点的父结点如果存在，编号是（（n-2）/m）+1。
（3）编号为n的结点的第i个孩子结点如果存在，编号是（n-1）*m+i+1。
（4）编号为n的结点有右兄弟的条件是（n-1）%m≠0。
其右兄弟的编号是n+1。
6.找出所有满足下列条件的二叉树：
（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；
（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；
（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；
6.解答：
（1）先序序列和中序序列相同的二叉树为：
空树或者任一结点均无左孩子的非空二叉树；
（2）中序序列和后序序列相同的二叉树为：
空树或者任一结点均无右孩子的非空二叉树；
（3）先序序列和后序序列相同的二叉树为：
空树或仅有一个结点的二叉树。
7.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。
7.解答：
后序序列：
ACDBGJKIHFE
8.假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。
8.解答：
先序序列：
ABCDGEIHFJK
9.给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。
9.解答：
先根遍历：
ABCDEFGHIJKLMNO
后根遍历：
BDEFCAHJIGKNOML
森林转换成二叉树如图5-16所示。
10．给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。
10.解答：
构造而成的哈夫曼树如图5-17所示。
A
B
D
E
F
C
G
H
J
I
K
N
O
M
L
图5-14
【例6-5】一个带权无向图的最小生成树是否一定唯一？
在什么情况下构造出的最小生成树可能不唯一？
解：
一个带权无向图的最小生成树不一定是唯一的。
从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
三、应用题
1.已知一个顺序存储的有序表为（15,26,34,39,45,56,58,63,74,76），试画出对应的折半查找判定树，求出其平均查找长度。
1.折半查找判定树如图7-3所示，平均查找长度等于29/10。
图7-3中的结点与有序表中元素的对应关系如下表所示。
图7-3
10
9
4
5
6
7
8
1
2
3
1
2
3
4
5
6
7
8
9
10
15
26
34
39
45
56
58
63
74
76
2.假定一个线性表为（38,52,25,74,68,16,30,54,90,72），画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。
图7-4
38
52
25
16
74
30
68
90
54
72
2.二叉排序树如图7-4所示，平均查找长度等于32/10。
3.假定一个待哈希存储的线性表为（32,75,29,63,48,94,25,46,18,70），哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。
元素32752963489425461870
初始哈希地址
最终哈希地址
0123456789101112
哈希表
3.H（K）=K%13平均查找长度为14/10，其余解答如下。
元素32752963489425461870
初始哈希地址6103119312755
最终哈希地址6103119412758
0123456789101112
哈希表29941832467048756325
4.假定一个待哈希存储的线性表为（32,75,29,63,48,94,25,36,18,70,49,80），哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。
4.H（K）=K%11，哈希表如图7-5所示，平均查找长度17/12。
图7-5
0
∧
三、简答题
2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？
答：
简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。
数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
3.简述线性结构与非线性结构的不同点。
答：
线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。
四、简答题
1.【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。
在什么情况下用顺序表比链表好？
答：
①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：
存储密度大（＝1？
），存储空间利用率高。
缺点：
插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：
插入或删除元素时很方便，使用灵活。
缺点：
存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2.【严题集2.1①】描述以下三个概念的区别：
头指针、头结点、首元结点（第一个元素结点）。
在单链表中设置头结点的作用是什么？
答：
首元结点是指链表中存储线性表中第一个数据元素a1的结点。
为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。
若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。
否则表示空表的链表的头指针为空。
这三个概念对单链表、双向链表和循环链表均适用。
是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
头结点
head
à
data
link
头指针首元结点
简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？
那还得另配一个头指针！
！
！
）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
四、简答题（每小题4分，共20分）
1.【严题集3.2①和3.11①】说明线性表、栈与队的异同点。
刘答：
相同点：
都是线性结构，都是逻辑结构的概念。
都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：
①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。
4.【统考书P604-13】顺序队的“假溢出”是怎样产生的？
如何知道循环队列是空还是满？
答：
一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
设置一个布尔变量以区别队满还是队空；
浪费一个元素的空间，用于区别队满还是队空。
使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是：
f=rear队满标志是：
f=（r+1）%N
2.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？
为什么？
答：
不一定。
时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。
仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。
四、简答题（每小题4分，共20分）
【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？
答：
度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。
即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
三、简答题（每小题4分，共16分）
1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？
用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：
不适合！
虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。
例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
3.【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?
如果要求时间复杂度更小,你采用什么方法？
此方法的时间复杂度是多少?
答：
查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。
要想降低时间复杂度，可以改用Hash查找法。
此方法对表内每个元素的比较次数都是O
（1）。
四、分析题（每小题6分，共24分）
1.【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：
判定树应当描述每次查找的位置：
5
8
1369
4710
2.【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。
答：
12
17
2111621
4913
验算方法：
用中序遍历应得到排序结果：
2,4,7,9,11,12,13,16,17，21
升级会员 