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

题目部份，（卷面共有78题,分,各大题标有题量和总分）一、简答题（78小题,共分）（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有n0个叶子结点，那么，树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］<key2<...<keyn）（2） 关键字（自大至小）逆序有序；（key2>key2>...>keyn）（3） 序号为奇数的关键字顺序有序，序号为偶数的关键字顺序有序：（key1<key3<.,key2<key4<.）（4） 前半个序列中的关键字顺序有序，后半个序列中的关键字逆序有序：（key1<key=2<.<keyn/2,key（n/2）+1>.>keyn）（4分）［43］简述栈和线性表的不同。（7分）［44］关于循环向量中的循环队列，写出求队列长度的公式。（5分）［45］简述队列和栈这两种数据类型的相同点和不同处。（7分）［46］—个长度为n的序列，假设去掉其中少数k个记录后，序列是按关键字有序的，那么称为近似有序序列。试对这种序列讨论各类简单排序方式的时刻复杂度。（6分）［47］试问：按锦标赛排序的思想，决出八名运动员之间的名次排列，至少需编排多少场次的竞赛（应考虑最坏的情形）？（7分）［48］不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依托于这n个元素的初始排列。试问：当n为7时，在最好情形下需进行多少次比较？请说明理由。（6分）［49］假设咱们把n个元素的序列知a2,…,an｝中知足条件ak<max｛al｝的元素a.称为“逆1<l<k序元素”假设在一个无序序列有一对元素ai>aj（i<j）,试问当将ai和aj彼此互换以后（即序列由｛..勺…即..｝变成｛..冋..冷111｝）,该序列中逆序元素的个数会有什么转变？什么缘故？（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题,分,各大题标有题量和总分）一、简答题（78小题,共分）（5分）［1］［答案］堆排序不是一种稳固的排序方式。因为在堆调整的进程中，关键字进行比较和互换的所走线路是沿着根结点到叶子结点，因此关于相同的关键字就可能存在后面的先被变换到前面。例如关于初始大J顶堆（2,1，1），第一遍堆调整为J,1）（2），因此堆排序不是稳固的。（10分）［2］［答案］B树是一种平衡的多路查找树，通常用在文件系统中。B_树的概念为:一棵m阶的B_树，或为空树，或为知足以下特性的m叉树：（1） 树中每一个结点至多有m棵子树。（2） 假设根结点不是叶于结点，那么至少有两棵子树。（3除根之外的所有非终端结点至少有［m/2］棵子树。（4）所有的非终端结点中包含以下信息数据：(n，AKA,K,A...K,A)A0,K1,A1,K2,A2...Kn,An(n，0,1,122nnKi1其中：K（i=1,2,.,n）为关健字，且指针K1所指子树中所有结点的关键字均小于K（i=1,i i-1 i2，..,n）,A所指子树中所有结点的关键字均大于K，n（［m/2］<n<m-1）为关键字的个数（或nnn+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<d-1）排序时，只能用稳固的排序方式。另一方面，按LSD进行排序时，能够不通过关键字比较实现排序，而是通过假设干次“分派”和“搜集”来实现排序。（4分）［4］［答案］不是。因为当序列已有序时，快速排序将退化成冒泡排序，时刻复杂度为0（n2）o当待排序序列无序，使每次划分完成后，枢轴双侧子文件长度相当，现在快速排序性能最好。（3分）［5］［答案］快速排序。（5分）［6］［答案］设待排序记录的个数为n,那么快速排序的最小递归深度为Llog2n」+1，最大递归深度no（7分）［7］［答案］这种观点不对。此题的表达与稳固性的概念无关，不能据此来判定排序中的稳固性。例如5,4,123在第一趟冒泡排序后取得4,123,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)，空间复杂度是0(1)，是稳固排序。简单项选择择排序的大体思想是基于选择，开始有序序列长度为零，第i(1<=i<n)趟简单项选择择排序是，从无序序列R[i..n]的n-i+1记录当选出关键字最小的记录，和第i个记录互换，使有序序列慢慢扩大，最后整个文件有序。共进行n-1趟选择。最坏时刻复杂度是0(n2)，平均时刻复杂度是0(n2)，空间复杂度是0(1)，是不稳固排序。二路并归排序的大体思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，取得Tn/2〕个长度为2的有序序列，再进行两两归并，取得「n/4[个长度为4的有序序列。如此重复，通过Iog2n]趟归并，最终取得一个长度为n的有序序列。最坏时刻复杂度和平均时刻复杂度都是0(nlog2n),空间复杂度是0(n)，是稳固排序。(6分)[14][答案]拓扑排序，是有向图的极点依照弧的走向，找出一个全序集的进程，主若是依照与极点连接的弧来确信极点序列；冒泡排序是借助互换思想通过比较相邻结点关键字大小进行排序的算法。(5分)[15][答案]这种说法不对。因为排序的不稳固性是指两个关键字值相同的元素的相对顺序在排序前、后发生了转变，而题中表达和排序中稳固性的概念无关，因此此说法不对。对4，3，2，1起泡排序就可否定此题结论。(7分)[16][答案]从节省存储空间考虑：先选堆排序，再选快速排序，最后选择归并排序；从排序结果的稳固性考虑：选择归并排序。堆排序和快速排序都是不稳固排序；从平均情形下排序最快考虑：先选择快速排序。(4分)[17][答案]八皇后问题是利用回溯法求解，而回溯法的一个很重要的特点确实是：空间需求为0(从开始结点起最长途径的长度)。因此，八皇后问题的最大递归深度是8。(4分)[18][答案]因为Huffman树没有度为1的结点，因此树T有2n0-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/2o具体的取决于表长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）/2n/2⑶n-1+乙ii=1（4）n/2- ii=n/2+1（4分）［43］［答案］栈是操作受限的线性表，栈的插入和删除操作都只能在栈顶端进行，因此相应的称为“入栈”和“出栈”。（7分）［44］［答案］公式如下（设采纳第二种方式，front指向真正的队首元素，rear指向真正队尾后一名置，向量空间大小：QueueSizeQueuelen=（QueueSize+rear-front）%QueueSize（5分）［45］［答案］队列和栈都是操作受限的线性表，都属于线性表的逻辑结构。区别在于，队列的插入是在对尾端进行，删除是在队头端进行；而栈的插入和删除都只能在栈顶端进行。（7分）［46］［答案］对近似有序的序列可用直接插入排序法，其时刻复杂度为O（kn），当k远远小于n且n专门大时，将比快速排序更有效。而起泡排序和简单项选择择排序的时刻复杂度均为O（n2），和k无关。（6分）［47］［答案］至少需编排17场竞赛。(7分)[48][答案]快速排序最好成绩的情形是指，排序所需的“关键字间的比较次数”和“记录的移动次数”最少的情形，在n为7的情形下，至少需进行2趟排序。(6分)[49][答案]只要考虑序列中位于ai和aj之间的元素ak(i<k<j)的几种情形即可，当ak>ai>aj时，有可能使ai由非逆元素变成逆序元素，但整个序列的“逆序对”不变。(10分)[50][答案](1)设归并路数为k,初始归并段个数m=80,依照归并趟数计算公式S=「logkm]=「logk80]=3得：k3280。由此解得k±3,即应取的归并路数至少为3。(2)设多路归并的归并路数为k,需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件，有k+1=15,因此k=14,可做14路归并。由S=「logkm]=「log1480]=2。即至少需2趟归并可完成排序。假设限定那个趟数，由S=「logk80]=2,有80Wk2，可取的最低路数为9。即要在2趟内完成排序，进行9路排序即可。(6分)[51][答案]由于高位优先的MSD方式是递归的方式，就一样情形来讲，不像低位优先的LSD方式那样直观自然，而且实现的效率较低。但如果是待排序的排序码的大小只取决于高位的少数几位而与大多数低位无关时，采纳MSD方式比LSD方式的效率要高。(12分)[52][答案](1)希尔排序{512275275*061}增量为2{275*061512275}增量为1{061275*275512}(2)直接选择排序{275275*512061}i=1{061275*512275}i=2{061275*512275}i=3{061275*275512}(3)快速排序{512275275*}{275*275512}(4)堆排序{275275*061170}已经是最大堆，交换275与170{170275*061275}对前3个调整{275*170061275}前3个最大堆，交换275*与061{061170275*275}对前2个调整{170061275*275}前2个最大堆，交换170与061{061170275*275}(15分)[53][答案](1)设有一个布尔变量exchange,判定在每一次做过一趟奇数项扫描和一趟偶数项扫描后是不是有过互换。假设exchange=1,表示适才有过互换，还需继续做下一趟奇数项扫描和一趟偶数项扫描；假设exchange=0,表示适才没有互换，能够终止排序。(2)奇偶排序的算法template<Type>voiddataList<Type>::odd-evenSort(){inti,exchange;do{exchange=0;for(i=1;i<CurrentSize;i+=2)

0卫24初始状态卫1第1趟排序结果卫第2趟排序结果卫第3趟排序结果门355、仝亠*禅排计时表*14283566<存放结果的表"ount355、仝亠*禅排计时表*14283566<存放结果的表"elseVector[j].count++; ount]=Vector[i];for(i=0;i<CurrentSize;i++)Vector[i]=c->Vector[i];〃结果复制回当前表对象中deletec;}(6分)[68][答案]