当前位置：搜档网 › 数据结构试卷(手动组卷)

数据结构试卷(手动组卷)

题目部分，(卷面共有78题,523.0分,各大题标有题量和总分)

一、简答题(78小题,共523.0分)

(5分)[1]堆排序是否是一种稳定的排序方法？为什么？

(10分)[2]简要叙述B(有些教材称为B-树)与B+ 树的区别

(8分)[3]在多关键字排序时，LSD和MSD两种方法的特点是什么？

(4分)[4]快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？

(3分)[5]在内排序算法中，待排序的数据已基本有序时，花费时间反而最多的排序方法是哪种？

(5分)[6]快速排序的最大递归深度是多少？最小递归深度是多少？

(7分)[7]在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？

(6分)[8]外排序中为何采用k-路（k>2）合并而不用2-路合并？这种技术用于内排序有意义吗？为什么？

(7分)[9]以归并算法为例，比较内排序和外排序的不同，说明外排序如何提高操作效率。(5分)[10]设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。(6分)[11]快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？

(8分)[12] 在堆排序、快速排序和合并排序中：

(1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？

(3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？

(8分)[13]简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。

(6分)[14]以下概念的区别：拓扑排序与冒泡排序。

(5分)[15]在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？

(7分)[16]对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？

(4分)[17]八皇后问题的最大递归深度是多少？

(4分)[18]如果一棵Huffman树T有0n个叶子结点，那么，树T有多少个结点？

(3分)[19]什么是循环队列？

(8分)[20]简述数组与字符串属于线性表的理由。

(4分)[21]试叙述一维数组与有序表的异同。

(5分)[22]用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？

(8分)[23]在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?

(8分)[24]常用的存储表示方法有哪几种?

(4分)[25]KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?

(4分)[26]两个字符串相等的充要条件是什么？

(3分)[27]两个串相等的充分必要条件是什么？

(2分)[28]串的两种最基本的存储方式是什么？

(5分)[29]试叙述一维数组与有序表的异同。

(6分)[30]在什么条件下，MSD 基数排序比LSD 基数排序效率更高？

(5分)[31]在顺序表中插入和删除一个结点需平均移动多少个结点？具体移动次数取决于哪几个因素？

(6分)[32]为什么有序的单链表不能进行折半查找?

(6分)[33]何时选用顺序表、何时选用链表作为线性表的存储结构为宜？

简述线性表的相互许存储与链接存储的空间分配方式、存储结构特性和主要优缺点。 (8分)[34]循环队列的优点是什么? 如何判别它的空和满?

(6分)[35]链栈中为何不设置头结点?

(4分)[36]试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？ (5分)[37]算法的时间复杂度仅与问题的规模相关吗?

(7分)[38]常用的存储表示方法有哪几种?

(8分)[39]试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 (16分)[40]简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

(6分)[41]试问对于下列各种排序方法，哪些是稳定的？哪些是不稳定的？

（1）直接插入排序；（2）希尔排序；（3）快速排序；

（4）堆排序；（5）归并排序；（6）基数排序。

(8分)[42]试问：对初始状态如下（长度为n ）的各序列进行直接插入排序时，至多需进行多少次关键字间的比较（要求排序后的序列按关键字自小至大顺序有序）？

（1）关键字（自小至大）顺序有序；（key 1

（2）关键字（自大至小）逆序有序；（key 2>key 2>…>key n ）

（3）序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序：

(key 1

（4）前半个序列中的关键字顺序有序，后半个序列中的关键字逆序有序：

(key 1…>key n )

(4分)[43]简述栈和线性表的差别。

(7分)[44]对于循环向量中的循环队列，写出求队列长度的公式。

(5分)[45]简述队列和栈这两种数据类型的相同点和差异处。

(7分)[46]一个长度为n 的序列，若去掉其中少数k 个记录后，序列是按关键字有序的，则称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。

(6分)[47] 试问：按锦标赛排序的思想，决出八名运动员之间的名次排列，至少需编排多少场次的比赛（应考虑最坏的情况）？

(7分)[48]不难看出，对长度为n 的记录序列进行快速排序时，所需进行的比较次数依赖于这n 个元素的初始排列。试问：当n 为7时，在最好情况下需进行多少次比较？请说明理由。

(6分)[49]假设我们把n 个元素的序列{a 1, a 2, …, a n }中满足条件ak<}{max 1l k

l a <≤的元素a k 称为“逆序元素”。若在一个无序序列有一对元素a i >a j (i

(10分)[50]如果某个文件经内排序得到80个初始归并段，试问

(1) 若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？

(2) 如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？

(6分)[51]在什么条件下，MSD基数排序比LSD基数排序效率更高？

(12分)[52]希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。(15分)[53]奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。

(1) 这种排序方法结束的条件是什么？

(2) 写出奇偶交换排序的算法。

(3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？

(6分)[54]在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?

(15分)[55]线性表可用顺序表或链表存储。试问：

(1) 两种存储表示各有哪些主要优缺点?

(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？

(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？

(10分)[56]如果待排序的排序码序列已经按非递减次序有序排列，试证明函数QuickSort( )的计算时间将下降到O(n2)。

(7分)[57]在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？

(9分)[58]什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的?

(8分)[59]在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O(log2n)。

(7分)[60]数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？

(8分)[61]什么是数据结构? 有关数据结构的讨论涉及哪三个方面?

(8分)[62]什么是数据? 它与信息是什么关系?

(6分)[63]为什么在单循环链表中设置尾指针比设置头指针更好?

(9分)[64]在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?

(6分)[65]何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

(6分)[66]试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

(12分)[67]在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次排序码比较。

(6分)[68]若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？

（1）查找不成功，即表中没有关键字等于给定值K 的记录；

（2）查找成功，且表中只有一个关键字等于给定值K 的记录；

（3）查找成功，且表中有若干个关键字等于给定值K 的记录，一次查找要求找出所有记录。此时的平均查找长度应考虑找到所有记录时所用的比较次数。

(5分)[69]在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

(10分)[70]给出12个初始归并段，其长度分别为30, 44, 8, 6, 3, 20, 60, 18, 9, 62, 68, 85。现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL 。

(8分)[71]特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？ (6分)[72] 试叙述一维数组与有序表的异同。

(5分)[73]什么是广义表？请简述广义表和线性表的主要区别。

(6分)[74]数组，广义表与线性表之间有什么样的关系？

(5分)[75]简述广义表属于线性结构的理由。

(6分)[76]描述以下概念的区别：空格串与空串。

(4分)[77]如果两个串含有相等的字符，能否说它们相等？

(7分)[78]什么是前缀编码？举例说明如何利用二叉树来设计二进制的前缀编码。

====================答案====================

答案部分，(卷面共有78题,523.0分,各大题标有题量和总分)

一、简答题(78小题,共523.0分)

(5分)[1][答案]

堆排序不是一种稳定的排序方法。因为在堆调整的过程中，关键字进行比较和交换的所走路线是沿着根结点到叶子结点，因此对于相同的关键字就可能存在后面的先被变换到前面。例

如对于初始大J 顶堆(2，1，1 )，第一遍堆调整为(1

,1)(2),因而堆排序不是稳定的。 (10分)[2][答案]

B 树是一种平衡的多路查找树，通常用在文件系统中。B_树的定义为：

一棵m 阶的B_树，或为空树，或为满足下列特性的m 叉树：

(1)树中每个结点至多有m 棵子树。

(2)若根结点不是叶于结点，则至少有两棵子树。

(3 除根之外的所有非终端结点至少有[m/2]棵子树。

(4)所有的非终端结点中包含下列信息数据：

(n ，0,1,122,,...,n n A K A K A K A )0,1,1221,,...,n n

i A K A K A K A K -

其中：i K (i=1，2，…，n)为关健字，且指针1i K -所指子树中所有结点的关键字均小于i K (i=1，2，…，n)，n A 所指子树中所有结点的关键字均大于n K ，n([m/2 ]≤n ≤m-1)为关键字的个数（或n+l 为子树个数)。

(5)所有的叶结点都出现在同一层次上，并且不带信息(可看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)，

B+树是B-树的种变形树，常用于文件系统中：它与B_树的差异在于

（1）有n棵子树的结点中含有n个关键字。

（2)所有的叶结点中包含了全部关键字的信息以及指向含这些关键字记录的指针，且叶子结点本身关键字的大小由小到大的顺序进行链接。

(3)所有的非终端结点可以看成是索引部分，结点中仅含有其子树(根结点)中的最大(或最小)关键字。

(8分)[3][答案]

最高位优先（MSD）法：先对最高位关键字K0进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的K0值，然后，分别就每个子序列对关键字K1进行排序，按K1值不同再分成若干更小的子序列，……，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。

最低位优先（LSD）法：先对最低位关键字Kd-1进行排序，然后对高一级关键字Kd-2进行排序，依次重复，直至对最高位关键字K0排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，但对Ki (0<=i

(4分)[4][答案]

不是。因为当序列已有序时，快速排序将退化成冒泡排序，时间复杂度为O(n2)。当待排序序列无序，使每次划分完成后，枢轴两侧子文件长度相当，此时快速排序性能最好。

(3分)[5][答案]

快速排序。

(5分)[6][答案]

设待排序记录的个数为n，则快速排序的最小递归深度为?log2n?+1，最大递归深度n。

(7分)[7][答案]

这种看法不对。本题的叙述与稳定性的定义无关，不能据此来判断排序中的稳定性。例如5,4,1,2,3在第一趟冒泡排序后得到4,1,2,3,5。其中4 向前移动，与其最终位置相反。但冒泡排序是稳定排序。快速排序中无这种现象。

(6分)[8][答案]

外排序用k-路归并(k>2)是因为k越小，归并趟数越多，读写外存次数越多，时间效率越低，故，一般应大于最少的2路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。

(7分)[9][答案]

内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。因为归并的趟数s=?logkm?,其中，m是归并段个数，k是归并路数。增大k和减少m都可减少归并趟数。应用中通过败者树进行多（k）路平衡归并和置换-选择排序减少m，来提高外部排序的效率。

(5分)[10][答案]

对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序。

(6分)[11][答案]

平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排序、堆排序、希尔排序。

(8分)[12][答案]

(1)堆排序，快速排序，归并排序(2)归并排序(3)快速排序(4)堆排序

(8分)[13][答案]

直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i] ，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。

简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1<=i

二路并归排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到?n/2?个长度为2的有序序列，再进行两两归并，得到?n/4?个长度为4的有序序列。如此重复，经过?log2n?趟归并，最终得到一个长度为n 的有序序列。最坏时间复杂度和平均时间复杂度都是0(nlog2n)，空间复杂度是O(n)，是稳定排序。

(6分)[14][答案]

拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与顶点连接的弧来确定顶点序列；冒泡排序是借助交换思想通过比较相邻结点关键字大小进行排序的算法。

(5分)[15][答案]

这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。

(7分)[16][答案]

从节省存储空间考虑：先选堆排序，再选快速排序，最后选择归并排序；从排序结果的稳定性考虑：选择归并排序。堆排序和快速排序都是不稳定排序；从平均情况下排序最快考虑：先选择快速排序。

(4分)[17][答案]

八皇后问题是利用回溯法求解，而回溯法的一个很重要的特点就是：空间需求为O(从开始结点起最长路径的长度)。因此，八皇后问题的最大递归深度是8。

(4分)[18][答案]

因为Huffman树没有度为1的结点，所以树T有20n-1个结点

(3分)[19][答案]

用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。

(8分)[20][答案]

数组可以看成是线性表的扩展，也即此时线性表中的数据元素本身也是个数据结构，对n 维数组来说，可以看作具有n个数据元素的线性表，而每一个数据元素本身又是一个数据结构，即由n-1维的数组构成。依此类推，也即，对于n维数组中的每一个元素来说都受到n

个关系(n维)的约束，在每个关系(每一维)中，数据元素都有一个直接后继(除去最后一个元素)和一个直接前驱(除去最前一个元素)因此，这n个(n维)关系中的任一关系，就其单个关系而言，仍是线性关系。

串是取值范围受到限制的线性表，即只能取字符集合中的字符。因此，串仍然是线性表

(4分)[21][答案]

一维数组是一种特殊的线性表结构，它与有序表的差异在于该结构中不存在元素值之间的递增或递减关系

(5分)[22][答案]

用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。

(8分)[23][答案]

可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。

(8分)[24][答案]

（1）顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。

（2）链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。

（3）索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。（4）散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

(4分)[25][答案]

KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。

(4分)[26][答案]

两个串相等当且仅当这两个串的值相等，即只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等

(3分)[27][答案]

两个串的长度相等且对应位置的字符相同。

(2分)[28][答案]

顺序存储方式和链接存储方式。

(5分)[29][答案]

一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。

(6分)[30][答案]

由于高位优先的MSD方法是递归的方法，就一般情况来说，不像低位优先的LSD方法那样直观自然，而且实现的效率较低。但如果待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采用MSD方法比LSD方法的效率要高。

(5分)[31][答案]

在顺序表中插入和删除一个结点需平均移动表中近一半的结点。如果表长n,则插入运算时元素的平均移动次数为n/2；删除运算的平均移动次数为n-1/2。具体的取决于表长n和位置i。

(6分)[32][答案]

因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

(6分)[33][答案]

顺序表的最大优点是可随机访问，因此，如果对线性表经常进行查找、排序

等运算，则宜采用顺序表作为存储结构。

链表的最大优点是便于插入和删除(它不需要移动元素，只需要修改指针)。因此，如果对线性表经常进行插、删运算，则宜采用链表作为存储结构。

(8分)[34][答案]

循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

(6分)[35][答案]

链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

(4分)[36][答案]

简单来说，数据结构定义了一组按某些关系结合在一起的数据元素；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作；而程序设计语言中的数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

(5分)[37][答案]

不是,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

(7分)[38][答案]

常用的存储表示方法有四种:

顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。

索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

散列存储方法：根据结点的关键字直接计算该结点的存储地址。

(8分)[39][答案]

例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数

组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们从高级语言的层次讨论这个问题。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

(16分)[40][答案]

数据：指能够被计算机识别、存储和加工处理的信息载体。

数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

逻辑结构：指各数据元素之间的逻辑关系。

存储结构：就是数据的逻辑结构用计算机语言的实现。

线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。

非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。

(6分)[41][答案]

（1）（5）（6）是稳定的排序方法；（2）（3）（4）是不稳定的排序方法。

(8分)[42][答案]

(1)n-1

(2)n(n-1)/2

(3)n-1+∑=2

/1n i i

(4)n/2-

∑+=n

n i i 12/ (4分)[43][答案]

栈是操作受限的线性表，栈的插入和删除操作都只能在栈顶端进行，因而相应的称为“入栈”和“出栈”。

(7分)[44][答案]

公式如下(设采用第二种方法，front 指向真正的队首元素，rear 指向真正队尾后一位置，向量空间大小：QueueSize

Queuelen=(QueueSize+rear-front)%QueueSize

(5分)[45][答案]

队列和栈都是操作受限的线性表，都属于线性表的逻辑结构。区别在于，队列的插入是在对尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行。

(7分)[46][答案]

对近似有序的序列可用直接插入排序法，其时间复杂度为O(kn)，当k 远远小于n 且n 很大

时，将比快速排序更有效。而起泡排序和简单选择排序的时间复杂度均为O(n 2)，和k 无关。

(6分)[47][答案]

至少需编排17场比赛。

(7分)[48][答案]

快速排序最好成绩的情况是指，排序所需的“关键字间的比较次数”和“记录的移动次数”最少的情况，在n 为7的情况下，至少需进行2趟排序。

(6分)[49][答案]

只要考虑序列中位于a i和a j之间的元素a k(ia i>a j时，有可能使a i由非逆元素变为逆序元素，但整个序列的“逆序对”不变。

(10分)[50][答案]

(1) 设归并路数为k，初始归并段个数m = 80，根据归并趟数计算公式S = ?logkm? = ?logk80?= 3得：k3≥80。由此解得k≥3，即应取的归并路数至少为3。

(2) 设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k +1 = 15，因此k = 14，可做14路归并。由S = ?logkm? = ?log1480? = 2。即至少需2趟归并可完成排序。

若限定这个趟数，由S = ?logk80? = 2，有80≤k2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。

(6分)[51][答案]

(12分)[52][答案]

(1) 希尔排序{ 512 275 275* 061 } 增量为2

{ 275* 061 512 275 } 增量为1

{ 061 275* 275 512 }

(2) 直接选择排序{ 275 275* 512 061 } i = 1

{ 061 275* 512 275 } i = 2

{ 061 275* 512 275 } i = 3

{ 061 275* 275 512 }

(3) 快速排序{ 512 275 275* }

{ 275* 275 512 }

(4) 堆排序{ 275 275* 061 170 } 已经是最大堆，交换275与170

{ 170 275* 061 275 } 对前3个调整

{ 275* 170 061 275 } 前3个最大堆，交换275*与061

{ 061 170 275* 275 } 对前2个调整

{ 170 061 275* 275 } 前2个最大堆，交换170与061

{ 061 170 275* 275 }

(15分)[53][答案]

(1) 设有一个布尔变量exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描后是否有过交换。若exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；若exchange = 0，表示刚才没有交换，可以结束排序。

(2) 奇偶排序的算法

template void dataList :: odd-evenSort ( ) {

int i, exchange;

do {

exchange = 0;

for ( i = 1; i < CurrentSize; i += 2 ) //扫描所有奇数项

if ( Vector[i] > Vector[i+1] ) { //相邻两项比较, 发生逆序

exchange = 1; //作交换标记

swap ( Vector[i], Vector[i+1] ); //交换

}

for ( i = 0; i < CurrentSize; i += 2 ) //扫描所有偶数项

if ( Vector[i] > Vector[i+1] ) { //相邻两项比较, 发生逆序

exchange = 1; //作交换标记

swap ( Vector[i], Vector[i+1] ); //交换

}

} while ( exchange != 0 );

}

(3) 设待排序对象序列中总共有n个对象。序列中各个对象的序号从0开始。则当所有待排序对象序列中的对象按排序码从大到小初始排列时，执行m = ?(n+1)/2?趟奇偶排序。当所有待排序对象序列中的对象按排序码从小到大初始排列时，执行1趟奇偶排序。

在一趟奇偶排序过程中，对所有奇数项扫描一遍，排序码比较?(n-1)/2?次；对所有偶数项扫描一遍，排序码比较?n/2?次。所以每趟奇偶排序两遍扫描的结果，排序码总比较次数为?(n-1)/2? + ?n/2? = n-1。

(6分)[54][答案]

(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。

链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。

(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。

如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。

如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。

(10分)[56][答案]

【证明】

若待排序的n个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为

T(n)。当以第一个对象作为基准对象时，应用一次划分算法Partition，通过n-1次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有n-1个对象的非递减有序序列。对于这样的递归QuickSort( )算法，其时间代价为

T(n) = (n-1) + T(n-1)

= (n-1) + {( n-2) + T(n-2) }

= (n-1) + (n-2) + {(n-3) + T(n-3) }

= ……

= (n-1) + (n-2) + (n-3) + …+ { 2 + T(1) }

= (n-1) + (n-2) + (n-3) + …+ 2 + 1

= n(n-1)/2 = O(n2)

(7分)[57][答案]

如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如，

57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动

6 5

7 40 3

8 11 13 34 48 75 7 1

9 9 如19向相反方向移动

6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动

6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动

6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动

6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动

6 7 9 11 13 19 57 40 38 34 48 75

6 7 9 11 13 19 34 57 40 38 48 75

(9分)[58][答案]

内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。

不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“>(或<)”改写成“≥(或≤)”，也可能造成不稳定。

(8分)[59][答案]

由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两个子序列的长度相等，则所需栈的深度为

S(n) = 1 + S(n/2) == 1 + { 1 + S(n/4) } = 2 + S(n/4)= 2 + { 1 + S(n/8) } = 3 + S(n/8)= ……

= log2n + S(1) = log2n (假设1个对象的序列所用递归栈的深度为0)

如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递归栈中，再对较短的子序列进行排序，可用表示最坏情况的大O表示法表示。此时其递归栈的深度不一定正好是log2n，其最坏情况为O(log2n)。

(7分)[60][答案]

线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一

个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构

非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。

(8分)[61][答案]

数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。

有关数据结构的讨论一般涉及以下三方面的内容：

①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；

②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；

③施加于该数据结构上的操作。

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。

(8分)[62][答案]

什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。

(6分)[63][答案]

尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。

(9分)[64][答案]

分别讨论三种链表的情况。

⑴单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。⑵双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。

⑶单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。

(6分)[65][答案]

在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：

⑴基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

⑵基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

(6分)[66][答案]

开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。

链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。

头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。

(12分)[67][答案]

template void datalist :: count_sort ( ) {

//initList是待排序表，resultList是结果表

int i, j;

int *c = new datalist ; // c是存放计数排序结果的临时表for ( i = 0; i < CurrentSize; i++ ) Vector[i].count = 0; //初始化，计数值都为0

for ( i = 0; i < CurrentSize-1; i++ )

for ( j = i+1; j < CurrentSize; j++ )

if ( Vector[j].key < Vector[i].key ) Vector[i].count++;

else Vector[j].count++; //统计

for ( i = 0; i < CurrentSize; i++ ) //在c->Vector[ ]中各就各位

c->Vector[ Vector[i].count ] = Vector[i];

for ( i = 0; i < CurrentSize; i++ ) Vector[i] = c->Vector[i]; //结果复制回当前表对象中

delete c;

}

(6分)[68][答案]

（1）相同；（2）相同；（3）不相同。

(5分)[69][答案]

结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。

(10分)[70][答案]

设初始归并段个数n = 12，外归并路数k = 4，计算(n-1) % (k-1) = 11 % 3 = 2 ≠0，必须补k-2-1 = 1个长度为0的空归并段，才能构造k路归并树。此时，归并树的内结点应有(n-1+1)/(k-1) = 12/3 = 4个。

WPL = (3+6+8)*3 + (9+18+20+30+44+60+62)*2 + (68+85)*1 = 51 + 486 + 153 = 690

(8分)[71][答案]

特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t<

(6分)[72][答案]

一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。

(5分)[73][答案]

线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。广义表中的元素可以是原子，也可以是子表

(6分)[74][答案]

数组是具有相同性质的数据元素的集合，同时每个元素又有唯一下标限定，可以说数组是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n-1维数组的一个线性表。而广义表与线性表的关系，

(5分)[75][答案]

广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个成为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。

(6分)[76][答案]

空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。

(4分)[77][答案]

仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

(7分)[78][答案]

前缀码是一编码不是任何其它编码前缀的编码。例如，0和01就不是前缀码，因为编码0是编码01的前缀。仅从编码来看，0和01 是前缀码，但因历史的原因，它不被称为前缀码，而是把一编码不是另一编码前缀的编码称为前缀码。

利用二叉树可以构造前缀码，例如，以A，B，C，D为叶子可构成二叉树，将左分枝解释为0，右分枝解释成1，从根结点到叶子结点的0、1串就是叶子的前缀码。用哈夫曼树可构造出最优二叉树，使编码长度最短。

2010年数据结构期中考试试卷及答案

《数据结构》期中试卷（2009级） 2010-2011学年第一学期姓名：学号：成绩：一、选择题：（每小题2分，共20分） 1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 A．8 B. 62.5 C. 62 D. 7 3. 已知广义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原子项e的运算是：( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则入队时的操作为（）。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A．p->llink=q； q->rlink=p；p->llink->rlink=q；q->llink=q； B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink； C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q； 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 利用二叉链表存储树时，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

数据结构期中考试试题答案c语言版本

数据结构期中考试试题答案一、单选题（每小题2分，共8分） 1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.在一个带附加表头的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 D 。 A.HL=p;p->next=HL; B.p->next=HL;HL=p; C.p->next=HL;p=HL; D.p->next=HL->next;HL ->next=p; 3．若让元素A，B，C，D依次入栈，则出栈次序不可能出现 D 种情况。 A.D,C,B,A B.A,D,C,B C.B,A,D,C D.D,A,B,C 4．从一个顺序队列删除元素时，首先需要 B 。 A.前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素二、填空题（每空1分，共32分） 1．数据的逻辑结构分为集合、线性、树型、图形四种。 2.函数重载要求参数个数、参数类型或参数次序有所不同。 3．在带附加表头的循环双向链表中，表头附加结点的左指针域指向最后一个结点，最后一个结点的右指针域指向表头附加结点。

4．在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为 HL->next==NULL 和 HL==HL->next 。 5．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next=a[1].next 、a[1].next=i 。 6．在由数组a中元素结点构成的单链表中，删除下标为i的结点的后继结点并将被删除结点的下标赋给i时，所进行的操作（需要用一个临时变量p）描述为 p=a[i].next 和 a[i].next=a[p].next;i=p 。 7．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向列号相同的下一个结点，right指针域指向行号相同的下一个结点。 8．一个广义表中的元素分为单元素和表元素两类。 9．广义表A=((a,(b,(),c),((d),e)))的长度为 1 ，深度为 4 。 10．向一个顺序栈插入一个元素时，首先应 top++ ，然后再将待插入元素放入栈顶位置。 11．对于队列，应在队尾进行插入，在队首进行删除。 12．中缀表达式2+7/(4-1)所对应的后缀表达式为 2 7 4 1 - / + @ 。 13．后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为 3 。 14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为 a ，孩子结点为 f ，树的深度为 4 。三、运算题（每小题8分，共24分） 1．假定线性表L=（33,69,78,22,44,88）,i=3,x=34,y=22,则对L进行下列一组操作` ListEmpty(L); false GetElem(L,i); 78

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

《数据结构》期末考试试卷

广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 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. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i

数据结构期末考试题及答案

数据结构期末考试题及答案、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位

B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性和输出的关系 C. 分析算法的效率以求改进档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。

数据结构期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ c）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（d ）。 for(i=n-1；i>=0；i--) for(j=0；jnext; p->next= Q.front->next; （B）、p=Q.front->next; Q.front->next=p->next; （C）、p=Q.rear->next; p->next= Q.rear->next; （D）、p=Q->next; Q->next=p->next; 9． Huffman树的带权路径长度WPL等于（ c ）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值

数据结构复习资料,java数据结构期末考试

第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析：如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长

数据结构(c语言版)期末考试复习试题

《数据结构与算法》（c语言版）期末考复习题一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位

B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序

数据结构期末考试试题A卷(完成,不知对不对)

第 1 页，共 11 页任课教师签名：命题教师签名：系主任签名：主管院长签名：湛江师范学院2007年－2008学年度第1学期期末考试试题A 卷 (考试时间:120分钟) 考试科目：数据结构请将所有答案填写在答题卡上，交卷时请将所有试卷上交一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; inext==L C L->next==p D p->next==NULL 4．4个元素进S 栈的顺序是A 、B 、C 、D ，进行两次Pop(S,x)操作后，栈顶元素的值是（ B ）。 A A B B C C D D 5．经过下列栈的运算后GetTop(S)的值是（ A ）。 InitStack(s); Push(s,a); Push(s,b); Pop(s); A a B b C 1 D 2

6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i

数据结构期中试卷信息11)2015-1-21 16.12.11

嘉兴学院试卷 2012—2013 学年第1 学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码：班级：姓名：学号：一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分) 1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是（ D ）的有限集。 A．算法B．数据元素C．数据操作D．数据关系 2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的（C）和数据的操作。 A．数据元素B．逻辑结构C．存储结构D．计算方法 3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种（ A ）的存储结构。 A．顺序存取 B．随机存取 C．索引存取 D．散列存取 4．线性表L在（ B ）情况下，最适合采用链式存储结构来实现算法。 A．不需经常对L进行修改 B．需经常对L进行删除和插入操作 C．需经常修改L中结点值 D．L中结点结构复杂 5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。 A.O(1) B. O(log2n) C. O(n) D. O(n2) 6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（ A ）。 A．front==rear B. front= =rear && num==0 C. front= =rear && num>0 D. num= =maxSize 7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是（ D ）。 A．abcde B．decba C．edcba D．dceab 8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-1 9．设线性表有n个元素，严格说来，以下操作中，（ B ）在顺序表上实现比链表上实现比链表上实现效率更高。 Ⅰ输出第i个（0≤i≤n-1）数据元素的值 Ⅱ交换第3个数据元素与第4个数据元素的值 Ⅲ顺序输出这n个数据元素的值 A．Ⅰ B．Ⅰ、Ⅱ C．Ⅰ、Ⅲ D．Ⅱ、Ⅲ 10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列是（ D ）。 A．s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 二、填空题（20分，每空1分） 1．算法的复杂度通常体现为时间复杂度和空间复杂度两个指标。 2．设有函数T (n)=3n2-n+4，T (n)=O ( n2)。 3．要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，会引起n-1-i个数据元素的移动。 4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。 5．在一个单链表中删除p所指结点时，可执行如下操作： q=p.getNext(); p.setData(q.getData());p.setNext( q.getNext() ); 6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是3。 7．若双向链表的结点类描述为：public class DuLNode { pvivate Object data; private DuLNode piror; private DuLNode next; …… } 则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是： 1）p.getPiror().setNext(s); 2）s.setPiror(p.gettPiror()); 3）s.setNext(p); 4）p.setPiror(s); 8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为： class Node { 命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：

数据结构期中考试模试卷

数据结构模拟试卷一. 单选题（每题1分，共14分） 1．数据结构所讨论的基本数据单位是（B）。 A、数据对象 B、数据元素 C、数据项 D、数据类 2. 在数据结构的讨论中把数据结构从逻辑上分为（C）两大类。 A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构。 3．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A．问题规模B．指令条数 C．循环层数D．函数数量 4. 算法分析的目的是（C）。 A. 研究算法的输入与输出之间的关系 B. 找出数据结构的合理性 C. 分析算法的效率以求改进算法 D. 分析算法的可读性与可移植性 5、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A.必须是连续的 B.部分地址必须是连续 C. 一定是不连续的 D. 可连续可不连续 6. 在一个当前长度为n的顺序表中向第j个元素（1next＝＝NULL C、head一>next= = head D、head!＝NULL 8、设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（A） A、p→next=p→next→next B、p=p→next C、p=p→next→next D、p→next=p 9、若有一个最大长度为size，且设有队首指针front和队尾指针rear的顺序循环队列，试问判断队列满的条件应是下列哪一个语句（D） A、front==rear B、front- rear==size C、front+rear==size; D、front==(rear+1)%size

数据结构期末考试试题及答案

贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；jnext; p->next= Q.rear->next; （D）、p=Q->next; Q->next=p->next; 9． Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值 10．线索二叉链表是利用（）域存储后继结点的地址。（A）、lchild （B）、data （C）、rchild （D）、root 二、填空题

2015年数据结构期末考试题及答案

2012年数据结构期末考试题及答案一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。

s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。

大学数据结构期末考试题(有答案)

“数据结构”期末考试试题一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。先序：

(完整版)数据结构期末考试试题及答案

数据结构期末考试试题及答案期末样卷参考答案一．是非题（每题1分共10分） 1. 线性表的链式存储结构优于顺序存储结构。F 2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F 3．字符串是数据对象特定的线性表。T 4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F 5．一个无向图的连通分量是其极大的连通子图。T 6．邻接表可以表示有向图，也可以表示无向图。T 7．假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。T 8．通常，二叉树的第i层上有2i-1个结点。F 9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有ém/2ù个关键字。F 10．对于任何待排序序列来说，快速排序均快于起泡排序。F 二．选择题（每题2分共28分） 1．在下列排序方法中，（c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d ）方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中，（a ）可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树 4. 下列查找方法中，（a ）适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查找 5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（ a ）方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中，（c ）具有先进先出特性，（b ）具有先进后出特性。 a．线性表b．栈c．队列d．广义表 7．具有m个结点的二叉排序树，其最大深度为（f ），最小深度为（ b ）。 a. log 2 m b. └log2 m ┘+1 c. m/2 d .┌m/2 ┐-1 e. ┌m/2 ┐ f. m 8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。下列选择中（ c ）是快速排序一趟排序的结果。（ b ）是希尔排序（初始步长为4）一趟排序的结果。（ d ）是基数排序一趟排序的结果。（ a ）是初始堆（大堆顶）。 a. 84，79，64，37，57，52，58，26，28，34，56。 b. 28，34，57，26，56，52，58，37，79，84，64。 c. 28，34，37，26，52，56，64，79，58，84，57。 d. 52，34，64，84，56，26，37，57，58，28，79。 e. 34，56，26，58，52，64，37，28，79，57，84。 f. 34，56，26，58，52，79，37，64，28，84，57。三．填空题（每题2分共20分） 1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。 2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。 3．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是（144）；按列存储时，元素A14的第一个字节的地址是（184）。 4．请在下划线上填入适当的语句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){ //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) { While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;} Pop ( S , p ); If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); } } return ok; 四．简答题（每题5分共25分） 1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。 2．已知Hash函数为H（K）=K mod 13 ，散列地址为0 --14，用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49, 52，36，92，06，55）在散列地址的分布。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

数据结构试卷(手动组卷)

2010年数据结构期中考试试卷及答案

数据结构期中考试试题答案c语言版本

2017年数据结构期末考试题及答案A

最新数据结构期中试卷及答案

《数据结构》期末考试试卷

数据结构期末考试题及答案

数据结构期末考试试题及答案

数据结构复习资料,java数据结构期末考试

数据结构(c语言版)期末考试复习试题

《数据结构》期末考试题及答案

数据结构期末考试试题A卷(完成,不知对不对)

数据结构期中试卷信息11)2015-1-21 16.12.11

数据结构期中考试模试卷

数据结构期末考试试题及答案

2015年数据结构期末考试题及答案

大学数据结构期末考试题(有答案)

(完整版)数据结构期末考试试题及答案

相关文档

最新文档