数据结构C++版试题.doc

数据结构试题一
一、单项选择题（每小题3分，共30分）
1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。
A、不确定 B、2n C、2n+1 D、2n-1
2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。
A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，cd，da]ff[eb，gc，ha]
3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。
A、单链表 B、双链表 C、单循环链表 D、顺序表
4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。
A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序
5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。
A、空或只有一个结点 B、高度等于其结点数
C、任意结点无左孩子 D、任意结点无右孩子
6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的 是（ ）。
A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序
7、快速排序算法在最好情况下的时间复杂度为（ ）。
A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)
8、已知数据表 A中每个元素距其最终位置不远，则采用（ ）排序算法最 省时间。
A、堆排序 B、插入排序 C、直接选择排序 D、快序排序
9、带权有向图G用邻接矩阵 A存储，则顶点 i的入度为 A中（ ）。
A、第 i行非∞的元素之和 B、第 i列非∞的元素之和
C、第 i行非∞且非 0的元素之和 D、第 i列非∞且非 0的元素之和
10、在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比 较次数的数量级为（ ）。
A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)
二、判断题 （认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，共10分）
1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问该图的每个顶点。 ( )
2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。 ( )
3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 ( )
4、图G的最小生成树的代价一定小于其他生成树的代价。 ( )
5、已知一棵树的先序序列和后序序列，一定能构造出该树。 ( )
6、对一个堆按层次遍历，不一定能得到一个有序序列。 ( )
7、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT 中的结点也一定是叶子结点。 ( )
8、不管 ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Push(x,S) 的耗时均为 O(n)。 ( )
9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入 上去，一定能得到原来的二叉排序树。 ( )
10、快速排序是排序算法中最快的一种。 ( )
三、填空题（每小题2分，共20分）
1、在双向循环表中，在 p所指的结点之后插入指针 f所指的结点，其操作为 ：
___ ______=p;f→next=p→next;_____=f; p→next=f。
2、在有序表 A[1…20]中，采用二分查找算法查找元素值等于 A[12]的元素，所比较过的元素的下标依次为__________。
3、若某串的长度小于一个常数，则采用_________存储方式最节省空间。
4、在有 n个顶点的有向图中，每个顶点的度最大可达_________。
5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为 __________。
6、设键值序列为{K1，K2，…，Kn},用筛选法建堆则必须从第_______个元 素开始筛选。
7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_________。
8、直接选择排序算法在最好情况下所作的交换元素的次数为___ _____。
9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行_______比赛。
10、下列排序算法中， 占用辅助空间最多的是_________( 堆排序， 希尔排序， 快速排序，归并排序)。
四、简答题（每题10分，共60分）
1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？
2、设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表中，请回答以下问题：
（1）设计一个适合该散列表的散列函数。
（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多少？
3、对 n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问
（1）图中有多少条边？
（2）任意两个顶点 i和 j是否有边相连？
（3）任意一个顶点的度是多少？
4、已知下面二叉排序树的各结点的值依次为1…9，请标出各结点的值。

5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同形态有哪些？
数据结构试题1参考答案
一、1——5：DADAB 6——10：CCBDD
二、1——5：ⅹ√ⅹⅹ√ 6——10：√ⅹⅹⅹⅹ
三、 1、①f→prior， ②p→next→prior 2、10 15 12 3、顺序压缩 4、2(n-1) 5、129 6、n/2的最小整数 7、(p→lchild==NULL)&&(p→rchild==NULL)
8、0 9、n(n-1) 10、归并排序
四、1、 答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。双链表 的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。
2、答案：（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余 数法的模，则可得其散列函数为h(k)=k%11。
（2）若用线性探测法解决冲突，则可构造出散列表如下：

13
14
35

17
29

153

0 1 2 3 4 5 6 7 8 9 10
11
此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表为：

3、 答案：（1）无向图的邻接矩阵所有数值之和除以2，为边数。有向图邻接矩阵各行 数值之和为总边数。邻接表表示无向图内部顶点个数除以 2，有向图内部顶 点个数。
（2）无向图中 I 行和 J 列的交叉点的值是否为 1。有向图 I 行 J 列交叉点或 I列和 J行交叉点的值为1。
（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数 值之和。
4答案：

5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。
具有3个结点的二叉树的形态为：5种形态，有左右之分。

数据结构试题2
一、单项选择题（每小题3分，共30分）
1、下列排序算法中，（ ）排序在每趟结束后，不一定能选出一个元素放到其排好序的最终位置上。
A、选择 B、冒泡 C、归并 D、堆
2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表
3、串的长度是（ ）。
A、串中不同字符的个数 B、串中不同字母的个数
C、串中所含字符的个数且字符个数大于 0 D、串中所含字符的个数
4、有一个散列表，表长度 m为 100，采用除余法构造散列函数，即 H(k)=k%P,(P 小于等于 m)，为使散列函数有较好的性能，P 的选择应是（ ）。
A、99 B、97 C、91 D、93
5、在包括 n个键值的二叉排序树中查找一个键值，其平均比较的量级为（ ）。
A、O(n) B、O(logn) C、O(nlogn) D、O(n)
6、对有14个元素的有序表 A[1…14]作二分查找，查找A[4]时的被比较元素依次为（ ）。
A、A[1]，A[2]，A[3]，A[4] B、A[1]，A[14]，A[7]，A[4]
C、A[7]，A[3]，A[5]，A[4] D、A[7]，A[5]，A[3]，A[4]
7、具有65个结点的完全二叉树其深度为（ ）。
A、8 B、7 C、6 D、5
8、带权有向图G用邻接矩阵 A存储，则顶点 i的入度等于 A中（ ）。
A、第 i行非无穷元素之和 B、第 i列非无穷元素之和
C、第 i行非零且非无穷元素个数 D、第 i列非零且非无穷元素个数
9、队列操作的原则是（ ）。
A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除
10、若表R在排列前已按元素键值递增顺序排序，采用（ ）的比较次数少。
A、直接插入排序 B、快速排序 C、归并排序 D、选择排序
二、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１ 分，共１０分） 1、在栈空的情况下，不能做退栈运算，否则产生下溢。 （ ）
2、在快速排序算法中，取待排序的 n个记录中的第一个的键值为基准，将所有记 录分为两组，读记录就排在这两组的中间，这也是该记录的最终位置。 （ ）
3、在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使 用二分查找方法。 （ ）
4、设有键值序列（k1，k2，…，kn），当 i>n/2时，任何一个序列（k1，k2，…，kn）一定是堆。 （ ）
5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度h。 （ ）
6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。 （ ）
7、双循环链表中，任一结点的前驱指针均为不空。 （ ）
8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复 杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。 （ ）
9、如果有向图 G=(V，E)的拓扑序列不唯一，则图中必有两条弧<vi,vj>和<vj,vi> 存在。（ ）
10、矩阵压缩存储的方法是用三元组表存储矩阵元素。 （ ）
三、填空题（每小题2分，共20分）
1、设 sq[1…maxsize]为一个顺序存储的栈，变量 top 指示栈顶元素的位置。作进栈操作时，必须判别____。如要把栈顶元素取到 x中，需执行语句__ ___。
2、设一个二叉树共有50个叶结点（终端结点），则共有_______个度为2的结点。
3、在单链表中，若要在指针p所指结点(data，next)后插入指针s所指结点，则需要执行下列两条语句：s→next=p→next;_________。
4、3个结点可构成_________棵不同形状的树。
5、利用直接选择排序算法对 n个记录进行排序，最坏情况下，记录交换的次数为 _______
6、如果含 n个顶点的图是一个环，则它有_________棵生成树。
7、如果要将序列{50，16，23，68，94，70，73}建成堆，则只需把 16 与______ 相互交换即可。
8、在一棵高度为 h 的平衡二叉树中，最少含有_________个结点，最多含有 2 h -1 个结点。
9、假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中，其中 B[0]存储矩阵中第1个元素a11，则B[31]中存放的元素是___________。
10、在单链表上难以实现的排序方法有___________和堆排序。
四、简答题（每题10分，共60分）
1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指 针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？
2、 一项工程由P1、 P2、 …、 P6六项子工程组成， 这些工程之间有下列关系： P1<P2， P3<P6，P4<P3，P2<P6，P4<P5，P1<P3，P5<P6，符号“<”表示“优于”关系，例如 P2<P6，表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。
3、设散列表长度为 14，散列函数 H(x)=∟ 2 / i」，其中 i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug， Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：
（1）构造散列表。
（2）求出在等概率情况下，查找成功的平均查找长度。
4、设下图所示的二叉树是由森林转化而成的，试将它还原为森林。

5、何为队列的“假溢出”现象？如何解决？
6、分析以下程序段中语句x=x+y的执行次数。
x=0; y=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
x=x+y;
数据结构试题2答案
一、1——5：CDDBB 6——10：CBDAA
二、1——5：√√√ⅹⅹ 6——10：ⅹ√ⅹⅹⅹ
三、1、① 栈是否满（或top=maxsize） ②x=sq[top] 2、49 3、p→next=s;
4、2 5、n-1 6、n 7、50 8、h 9、A82 10、快速排序
四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表的删除时间复杂度为O(1)，单循环链表删除p结点的时间复杂度为O(n)。
2、答案：可给出有向图表示各子工程间的关系按照入度为零的结点先访问的原则，访问各个结点即可。
找出3个可能的施工顺序如下：
P1，P2，P3，P4，P5，P6
P1，P4，P2，P3，P5，P6
P4，P5，P1，P2，P3，P6
3、答案：（1）：

（2）ASL=（1*7+2*4+3*1）/12=5。
4、答案：

5、答案：队列的“假溢出”现象是指用数组实现的顺序队列中，对尾指针已达到数组的下标上界产生上溢而对头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间首尾相连。

数据结构试题3
一、单项选择题（每小题3分，共30分）
1、假设有 n个关键字，它们具有相同的Hash 函数值，用线性探测法把这 n个关键字存入到Hash地址空间中要做（ ）次探测。
A、n2 B、n(n+1) C、n(n+1)/2 D、n(n-1)/2
2、若有一个栈的输入序列是 1，2，3，…，n 输出序列的第一个元素是 n，则第 i 个输出元素是（ ）。
A、n-i B、n-i-1 C、n-i+1 D、不确定
3、在一棵度为3的树中，度为 3的结点数为 2 个，度为2的结点数为 1个，度为1 的结点树为2个，那么度为 0的结点数为（ ）。
A、4 B、5 C、6 D、7
4、在一个具有 n个结点的无向完全图中，包含有（ ）条边。
A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n2
5、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，需（ ）次比较可检索成功。
A、 1 B、2 C、3 D、4
6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（ ）。
A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接选择排序
7、已知 8 个元素（34，76，45，18，36，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（ ）。
A、4 B、5 C、6 D、7
8、设有一个10阶的对称矩阵 A，采用压缩存储方式以行序为主存储，a00为第一个元素， 其存储地址为0，每个元素占有 1个存储地址空间，则a85的地址为 （ ）。
A、13 B、33 C、17 D、32
9、设关键字序列为：3，7，6，9，8，1，4，5，2。进行排序的最小交换次数为（ ）。
A、6 B、7 C、8 D、20
10、给定权的集合{15，3，14，2，6，9，16，17}，所构造出的哈夫曼树的带
权路径长度为（ ）。
A、129 B、219 C、189 D、229
二、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分， 共１０分）
1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 （ ）
2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。 （ ）
3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。 （ ）
4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突
的方法两个方面。 （ ）
5、因为算法和程序没有区别，所以在数据结构中二者是通用的。 （ ）
6、进栈操作 push(x,s)作用于链接栈时，无须判满。 （ ）
7、稳定排序算法是最好的。 （ ）
8、二叉搜索树的左、右子树都是二叉搜索树。 （ ）
9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。 （ ）
10、表中的每一个元素都有一个前驱和后继元素。 （ ）
三、填空题（每小题2分，共20分）
1、在散列表(Hash)查找中，评判一个散列函数优劣的两个主要条件是_______和________。
2、设根结点处在第一层，那么具有 n 个结点的完全二叉树，其高度为_____。
3、快速排序方法的最坏时间复杂度为______，平均时间复杂度为___。
4、给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为_________。
5、设图 G 的顶点数为 n，边数为 e，各顶点的度数为 D(Vi)，则e=________。
6、将5个不同的数据进行排序，至少需要比较_____次，至多需要比较_______次。
7、二分折半查找的查找速度一般比顺序查找的速度快，设有100个元素，用二分折半查找时，最大比较次数是____，最小比较次数是_____。
8、由 a，b，c3 个结点构成的二叉树，共有_________种不同的结构。
9、在一棵高度为 h 的平衡二叉树中，至少含有________个结点，最多含有 2 h -1 个结点。
10、在一个单链表中删除*p 结点，应执行如下操作 ：
q=p→next;
p→data=p→next→data;
p→next=________;
free(q);
四、简答题（每题10分，共60分）
1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？
2、假设用于通讯的电文仅有 8 个字母组成，字母在电文中出现的频率分别为：7， 19，2，6，32，3，21，10。试用这8个频率值构造哈夫曼树，并画出该哈夫曼所对应的森林。
3、已知一个长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec）：
（1）构造最价二叉排序树；
(2)试求在等概率情况下对此二叉排序树进行折半检索时检索成功的平均长度。
4、对于下图，试给出：

（1）每个顶点的入度和出度； （2）邻接矩阵；
（3）逆邻接表； （4）强连通分量；
5、快速排序、插入排序、自然两路归并排序、堆排序，哪一种排序方法所需的辅助空间最大？请简单说明。
1、 。
数据结构试题3答案
一、1——5：CCCAB 6——10：DCBAD
二、1——5：ⅹ√√√ⅹ 6——10：√ⅹ√ⅹⅹ
三、1、① 值均匀分布于表空间以减少冲突 ② 函数尽可能简单以方便计算
2、logn的最小整数+1 3、①O(n 2 ) ②O(nlogn)
4、(31 38 44 56 75 80 55 63) 或(80 75 55 56 63 44 31 38)
5、0.5*D(Vi)之和(i…n) 6、①4 ②10
7、①7 ②1 8、5 9、h 10、p→next→next
四、1、答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。
2、答案： （哈夫曼树有多种形态，不是唯一的。 ）
（1）哈夫曼树为：

（2）哈夫曼树所对应的森林为：

3、答案：（1）

（2）在等概率情况下检索成功的平均检索长度：
ASL=（1*1+2*2+3*4+4*4+5*1）/12=38/12=19/6
2、 答案：（1）各个顶点的入度和出度如下：
顶点：1 2 3 4 5 6
入度：2 2 1 3 2 1
出度：1 2 3 0 3 2
（2）邻接矩阵为： （3）逆邻接表为：

（4）、强连通分量有如下3个：

5、答案：快速排序需要的辅助空间与辅助栈的深度有关，平均情况下为O(logn),最坏情况下需要 O(n)；插入排序和堆排序只需要一个元素大小的辅助空间在元素交换时用,为O(1)；而自然两路归并排序需和待排序数组同样大小的辅助空间，为O(n)，所以自然两路归并排序所需的辅助空间最大，快速排序次之，插入排序和堆排序最小。

数据结构试题4
一、单项选择题（每小题3分，共30分）
1．一般情况下将递归算法转换为等价的非递归算法应设置_____. ( )
[A] 堆栈 [B] 队列 [C] 数组 [D] 堆栈或队列
2．设队列的输入序列是1、2、3、4，则只有_____是其出队序列。 ( )
[A] 1234 [B] 2134 [C] 1432 [D] 4312
3．C语言中要保存10个字符的字符串,至少需要声明大小为___的一维数组。 ( )
[A] 10 [B] 。 [A] F(0)=0 [B] F(1)=1 [C] F(0)=1 [D] F(n)=n
4．若一棵哈夫曼树有20个度为2的结点，则它共有_____个叶结点。 ( )
[A] 19 [B] 21 [C] 23 [D] 25
5．如果T2是由有序树T转换而来的二叉树，那么T中结点的后根序列就是
T2中结点的________。 （ ）
[A] 先根序列 [B] 中根序列 [C] 后根序列 [D] 层次序列
6. 有向图中所有顶点的入度之和等于所有顶点的出度之和的____倍。 ( )
[A] 1 [B] 2 [C] 1/2 [D] 不一定
7．递归函数F(n)=F(n-1)+n+1(n>1)的递归出口是_____. ( )
[A]F(0)=0 [B]F(1)=1 [C]F(0)=1 [D]F(n)=n
8．在下列算法中，______算法可能出现以下情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 ( )
[A] 堆排序 [B] 冒泡排序 [C] 插入排序 [D] 快速排序
9．在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为____。 ( )
[A] O(1) [B] O(log2n) [C] O(n2) [D] O(n)
10．具有四层结点AVL树至少有_______个结点。 ( )
[A] 10 [B] 9 [C] 8 [D] 7
二、填空题（每小题2分，共20分）
1.在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着的__________、__________和_____________的联系。
2．在线性表的单链接存储中，指向下一结点的指针为next。若一个元素所在结点的地址为p，则其后继结点的地址为____________，若假定p为一个数组a中的下标，则其后继结点的下标为___________。
3. 栈又称为______________表，队列又称为____________表。
4. 后缀表达式“4 5 + 3 * 2 4 + * ”的值为____________。
5. 一棵深度为5的满二叉树中的结点数为______个,一棵深度为3的满四叉树中的结点数为_________个。
6. 对于一棵含有40个结点的理想平衡树,它的高度为___________。
7. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做________排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做________排序。
8. 当从一个小根堆中删除一个元素时，需要把_________元素填补到________位置，然后再按条件把它逐层________调整。
9. 对于一个具有n个顶点的图,若采用邻接矩阵表示，则矩阵大小为_________。
10. 向一棵 B—树插入元素的过程中，若最终引起树根结点的分裂，则新树的高度比原树增________；从一棵 B—树删除元素的过程中，若最终引起树根结点的合并，则新树的高度比原树减__________。
三、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题 １分,共１０分）
1.给出不同输入序列建造二叉排序树，一定得到不同二叉排序树 。 ( )
2.有向图的邻接表和逆邻接表中的结点数一定相同。 ( )
3.图G的拓扑序列唯一，则其弧数必为 n-1(其中n为G的顶点数)。 ( )
4.在索引顺序文件中插入新的记录时，必须复制整个文件。 ( )
5.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。 ( )
6.对n个记录进行冒泡排序，在最坏情况下所需要的时间是O(n2)。 ( )
7. 在线性结构中，每个结点都有一个直接前驱和一个直接后继。 ( )
8.AVL树的任何子树都是AVL树。 ( )
9. B＋树既适于随机检索，也适于顺序检索。 ( )
10.两个字符串相等的充要条件是两个串包含的字符相同。 ( )
四、简答题（每题10分，共60分）
1. 说明数组和链表的区别，各有何优缺点？
2. 已知序列（17，18，60，40，7，32，73，65，85），请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。
3．邻接矩阵表示图时，若图中有1000个顶点，500条边，则形成的邻接矩阵有多少个元素？有多少个非零元素？是否为稀疏矩阵？
4．简述二叉排序树的概念，并按给定的输入序列：
25、13、15、31、7、20、37
构造一棵二叉排序树。
5．一棵二叉树的前序、对称序和和后序序列分别如下，其中有一部分未显示出来，试求空格处内容，并画出该二叉树对应的森林。
前 序：__B__F__ICEH__G
对称序：D__KFIA__EJC__
后 序: __K__FBHJ__G__A
6．有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的huffman编码。
五、算法设计题（每题15分，共30分）
说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。
1．已知长度为n的线性表A采用顺序存储结构，写一算法，删除该线性表中所有值为 item的数据元素，并给出算法的时间复杂度。
2．设计一个算法，统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所有顶点的度。
数据结构试题4答案
一、1. A 2.A 3. B 4. B 5. B 6.A 7. B 8. C 9. D 10.D
二、1. 1:1 1:N M:N （或者 一对一 1对多 多对多）
2. p->next a[p].next 3. 后进先出 先进先出 4. 162
5. 31 21 6. 6 7. 交换 二路归并（或归并）
8. 堆尾 堆顶 向下 9. n2 10. 1 1
三、1．X 2.√ 3. √ 4. X 5. X 6.√ 7.X 8.√ 9.X 10.X
四、答案：区别：数组占用连续的内存空间，链表不要求结点的空间连续。
各有何优缺点：（1） 插入和删除操作。数组插入和删除需移动数据元素，链表插入和删除不移动数据元素，链表比数组易于实现插入和删除操作；
（2） 在空间占用方面，数组优于链表；
（3） 在数据存取方面，数组是随机存取方式，而链表是顺序存取方式。
2.答案：采用起泡排序法排序的各趟结果如下：
初 始：17，18，60，40，07，32，73，65，85
第一趟：17，18，40，07，32，60，65，73，85
第二趟：17，18，07，32，40，60，65，73，85
第三趟：17，07，18，32，40，60，65，73，85
第四趟：07，17，18，32，40，60，65，73，85
第五趟：07，17，18，32，40，60，65，73，85
第五趟无元素交换，排序结束。
3．答案：邻接矩阵有1 000 000个元素。
对于有向图，有500个非零元素；对于无向图，有1 000个非零元素。
此邻接矩阵是稀疏矩阵。
4．答案：如果一棵二叉树的每个结点对应于一个关键码，且每个结点的左子树中所有结点的关键码值都小于该结点的关键码值，而右子树中所有结点的关键码值都大于该结点的关键码值，称此二叉树为二叉排序树。

5．答案：前 序:A B D F K I C E H J G
对称序:D B K F I A H E