计算机专业基础综合数据结构(排序)历年真题试卷汇编1.doc

计算机专业基础综合数据结构（查找）历年真题试卷汇编1(总分：108.00，做题时间：90分钟)一、单项选择题(总题数：34，分数：76.00)1.顺序查找法适合于存储结构为____的线性表。

【北京航空航天大学2002年】（分数：2.00）A.顺序存储结构或链式存储结构√B.散列存储结构C.索引存储结构D.压缩存储结构解析：解析：考查顺序查找的适合结构。

顺序查找从线性表的一端开始，逐个检查关键字是否满足给定的条件。

存储结构为顺序存储或链式存储。

2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为____。

【北京航空航天大学2004年】（分数：2.00）A.(n—1)／2B.n／2C.(n+1)／2 √D.n解析：解析：考查顺序查找法平均查找长度。

查找第1个记录的查找长度为1，查找第n个记录的查找长度为n，查找每个记录的概率为1／n。

ASL为[n(1+n)／2]／n=(n+1)／2。

3.当采用分块查找时，数据的组织方式为____。

【太原科技大学2007年】（分数：2.00）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块√C.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D.数据分成若干块，每块(除最后一块外)中数据个数需相同解析：解析：考查分块查找的定义。

分块查找要求将查找表按照关键码的区间分成若干个子表，并对子表建立索引表。

索引表有序，子表不一定有序。

子表中最大或最小的数据组成索引块。

4.对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为____。

【华中科技大学2007年】（分数：2.00）A.50 √B.125C.500D.[log 2 2500]解析：解析：考查分块查找的最优块长。

分块查找的平均查找长度不仅和表的总长度n有关，而且和所分的子表个数s有关，对于n给定的情况下，s取时，ASL。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

计算机专业基础综合数据结构（图）历年真题试卷汇编1(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：20，分数：40.00)1.下列关于无向连通图特性的叙述中，正确的是( )。

【2009年全国试题7(2分)】I．所有顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1（分数：2.00）A.只有I √B.只有ⅡC.I和ⅡD.I和Ⅲ解析：解析：无向图中一条边要连接两个顶点，因此顶点的度数之和必为偶数。

n个顶点的无向连通图至少需要n-1条边。

无向连通图并不要求“至少有一个顶点的度为1”。

2.若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是( )。

【2010年全国试题7(2分)】（分数：2.00）A.6B.15C.16 √D.21解析：解析：要保证n个顶点的无向图G在任何情况下都是连通的，则需要先由n-1个顶点组成完全图，从第n个顶点引一条到n-1任一顶点的边，则图肯定是连通的。

本题先由6个顶点组成完全图，需要6(6-1)／2=15条边，故按题目要求“需要的边数最少”是15+1=16。

3.对下图进行拓扑排序，可以得到不同拓扑序列的个数是( )。

【2010年全国试题8(2分)（分数：2.00）A.4B.3 √C.2D.1解析：4.下列关于图的叙述中，正确的是( )。

【2011年全国试题8(2分)】I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（分数：2.00）A.仅ⅡB.仅I、ⅡC.仅Ⅲ√D.仅I、Ⅲ解析：解析：图中第1个顶点和最后一个顶点相同的路径称为回路或环。

序列中所有顶点不重复出现的路径称为简单路径，邻接矩阵的大小只和顶点个数相关，存储稀疏图，用邻接表比邻接矩阵更省空间。

拓扑序列成功的前提是有向图中不存在回路。

5.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是( )。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

数据结构排序历年考研练习题库试卷及答案数据结构排序历年考研练习题库试卷及答案一、冒泡排序冒泡排序是一种基本的排序算法，它通过重复地交换相邻两个元素的位置来实现排序。

算法的基本思想是从待排序的元素中比较相邻的两个元素大小，并根据需要交换它们的位置，直到整个序列有序为止。

冒泡排序的原理如下：首先从序列的第一个元素开始，比较相邻的两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置；否则，继续比较下一对相邻元素，直到比较到序列的最后一个元素。

这样一趟比较下来，序列中最大的元素就会被交换到最后一个位置。

接着，对序列中剩下的 n-1 个元素重复上述过程，执行 n-1 趟比较，直到整个序列有序。

在实践中，冒泡排序的时间复杂度为 O(n^2)，其中 n 为待排序序列的长度。

尽管冒泡排序存在其它更好的排序算法，但它具有编码简单、实现容易以及对小规模数据排序的优势。

二、选择排序选择排序也是一种简单直观的排序算法，它的思想是将待排序序列分为已排好序的部分和未排序的部分，每次选取未排序部分中最小（或最大）的元素，将其放置在已排好序的部分的末尾。

重复此过程，直到整个序列有序。

选择排序的具体步骤如下：首先从待排序序列中找到最小（或最大）的元素，然后将其与序列的第一个元素交换位置，将该元素视为已排序部分；接着，在剩下的未排序部分中找到最小（或最大）的元素，将其与第二个元素交换位置，将该元素视为已排序部分的最后一个元素；以此类推，每次选择序列中最小（或最大）的元素，并将该元素放置在已排序部分的末尾。

最终完成排序。

选择排序的时间复杂度同样为 O(n^2)，其中 n 为待排序序列的长度。

相比于冒泡排序，选择排序的交换操作较少，因此在实际应用中，选择排序的性能要优于冒泡排序。

三、插入排序插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素逐个插入已排好序的部分中，直到整个序列有序。

与冒泡排序和选择排序不同，插入排序是一种原地排序算法。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编1(总分：86.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。

【西安交通大学1996三、2(3分)】（分数：2.00）A.250B.500C.254D.505E.以上答案都不对2.一棵124个叶结点的完全二叉树，最多有( )个结点。

【中国科学技术大学1995十四、3(2分)】（分数：2.00）A.247B.248C.249D.250E.2513.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。

【上海交通大学2005四、6(2分)】（分数：2.00）A.3 11B.3 12C.3 13D.3 14E.其他4.具有300个结点的二叉树，其高度至少应为( )。

【北京理工大学2006五、8(1分)】（分数：2.00）A.6B.7C.8D.95.当结点数目一定时，具有最小深度的二叉树是( )。

【北京航空航天大学2005】（分数：2.00）A.满二叉树B.完全二叉树C.线索二叉树D.二叉排序树6.二叉树的第I层上最多含有的结点数为( )。

【中山大学1998二、7(2分)】【北京理工大学2001六、5(2分)】（分数：2.00）A.2 IB.2 I-1一1C.2 I-1D.2 I一17.从树根(第0层)起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h 层的从左到右第k个结点的编号为( )。

【电子科技大学2005一、6(1分)】（分数：2.00）A.2 h +h-1B.2 h一k+1C.2 h +k+1D.2 h一k-18.下列判断中，( )是正确的。

【华南理工大学2006一、2(2分)】（分数：2.00）A.深度为k的二叉树最多有2 k -1个结点(k≥1)，最少有k个结点B.二叉树中不存在度大于2的结点C.对二叉树遍历是指先序、中序或后序遍历中的一种D.构造线索二叉树是为能方便找到每个结点的双亲9.一个具有1025个结点的二叉树的高h为( )。

数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。

每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。

下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。

2. 在二叉搜索树中，中序遍历的结果是________。

编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。

2. 二叉树每个节点最多有______个子节点。

编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。

每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。

计算机专业基础综合数据结构（查找）历年真题试卷汇编1(总分108,考试时间90分钟)1. 单项选择题1. 顺序查找法适合于存储结构为____的线性表。

【北京航空航天大学2002年】A. 顺序存储结构或链式存储结构B. 散列存储结构C. 索引存储结构D. 压缩存储结构2. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为____。

【北京航空航天大学2004年】A. (n—1)／2B. n／2C. (n+1)／2D. n3. 当采用分块查找时，数据的组织方式为____。

【太原科技大学2007年】A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同4. 对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为____。

【华中科技大学2007年】A. 50B. 125C. 500D. [log22500]5. 下面关于二分查找的叙述正确的是____。

【南京理工大学1996年】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型、实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储6. 当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是____。

【北京航空航天大学2002年】A. (n+1)／2B. n／2C. log2(n+1)一1D. log2(n+1)7. 在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录．需要进行____次关键字值的比较。

【北京航空航天大学2004年】A. 0B. 4C. 5D. 158. 对一个长度为50的有序表进行折半查找，最多比较____次就能查找出结果。

计算机专业基础综合计算机组成原理（数据的表示和运算）历年真题试卷汇编1(总分：84.00，做题时间：90分钟)一、单项选择题(总题数：35，分数：70.00)1.定点补码加减法运算中，当运算结果出现____时，表示运算结果负溢出。

【华中科技大学2002年】A.符号位为00B.符号位为01C.符号位为10 √D.符号位为11考查双符号位时溢出的判别。

两个符号位不同时，表示溢出，此时最高位符号位代表真实符号。

2.采用变形补码判溢出，当发生正溢出时，其两位符号位为____。

【国防科技大学2002年】A.0B.1 √C.10D.11考查双符号位时溢出的判别。

原理同上题。

3.在定点运算器中，无论采用双符号位还是单符号位，必须有____。

【上海大学2001年】A.译码电路，它一般用与非门来实现B.编码电路，它一般用或非门来实现C.溢出判断电路，它一般用异或门来实现√D.移位电路，它一般用与或非门来实现考查溢出判别所需硬件配置。

三种溢出判别方法，均必须有溢出判别电路，可用异或门来实现。

4.在原码不恢复余数除法(又称原码加减交替法)的算法中，____。

【哈尔滨工程大学2004年】A.每步操作后，若不够减，则需恢复余数B.若为负商，则恢复余数C.整个算法过程中，从不恢复余数√D.仅当最后一步不够减时，才恢复一次余数考查原码不恢复余数除法。

5.在补码一位乘中，若判断位Y n Y n+1 +1=10，则应执行的操作是____。

【电予科技大学1996年】【上海大学1998年】A.原部分积加[X] 补，然后右移一位√B.原部分积加[X] 补，然后右移一位C.原部分积加[X] 补，然后左移一位D.原部分积加[X] 补，然后左移一位考查补码一位乘。

6.实现N位(不包括符号位)补码一位乘时，乘积为____位。

【西安电子科技大学2007年】A.NB.N十1C.2N √D.2N+1考查补码一位乘。

补码一位乘法运算过程中一共向右移位N次，加卜原先的N位，一共是2N位数值位。

计算机专业基础综合数据结构（排序）历年真题试卷汇编2(总分：58.00，做题时间：90分钟)一、单项选择题(总题数：10，分数：20.00)1.以下序列不是堆的是( )。

【西安电子科技大学2001计算机应用一、5(2分)】（分数：2.00）A.(100，85，98，77，80，60，82，40，20，lO，66)B.(100，98，85，82，80，77，66，60，40，20，10)C.(10，20，40，60，66，77，80，82，85，98，100)D.(100，85，40，77，80，60，66，98，82，10，20) √解析：2.一组关键字为(46，79，56，38，40，84)，则利用堆排序的方法建立大顶堆的初始堆为( )。

【北京交通大学2006一、8(2分)】（分数：2.00）A.79，46，56，38，40，84B.84，79，56，38，40，46 √C.84，79，56，46，40，38D.84，56，79，40，46，38解析：3.在对，z个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。

【西安电子科技大学2001计算机应用一、10(2分)】（分数：2.00）A.O(log 2 n)B.D(1) √C.O(n)D.()(nlog 2 n)解析：4.对n个记录的文件进行堆排序，最坏情况下的执行时间是多少? ( )。

【北京交通大学2001一、9(2分)】（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n) √D.O(n*n)解析：5.有一组数据(15，9，7，8，20，一1，7，4)，用堆排序的筛选方法建立的初始堆为( )。

【南京理工大学1996二、5(2分)】（分数：2.00）A.一1，4，8，9，20，7，15，7B.一1，7，15，7，4，8，20，9C.一1，4，7，8，20，1 5，7，9 √D.A，B，C均不对解析：6.归并排序中，归并的趟数是( )。

计算机专业基础综合数据结构（概论）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：32.00)1.以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】（分数：2.00）A.栈B.广义表C.有向图D.字符串√解析：2.以下数据结构中，( )是非线性数据结构【中山大学1999一、4】（分数：2.00）A.树√B.字符串C.队D.栈解析：3.下列数据中，( )是非线性数据结构。

【北京理工大学2001六、1(2分)】（分数：2.00）A.栈B.队列C.完全二叉树√D.堆解析：解析：栈、队列是线性结构，堆是元素的序列，存在一维数组中，可以看成是线性结构。

完全二叉树是非线性结构，只是由于双亲和子女编号间存在固定关系，用一维数组存储更好。

4.连续存储设计时，存储单元的地址( )。

【中山大学1999一、1(1分)】（分数：2.00）A.一定连续√B.一定不连续C.不一定连续D.部分连续，部分不连续解析：5.以下属于逻辑结构的是( )。

【西安电子科技大学应用2001一、1】（分数：2.00）A.顺序表B.哈希表C.有序表√D.单链表解析：6.算法的计算量的大小称为计算的( )。

【北京邮电大学2000二、3(20／8分)】（分数：2.00）A.效率B.复杂性√C.现实性D.难度解析：7.算法的时间复杂度取决于( )。

【中科院计算所1998二、1(2分)】（分数：2.00）A.问题的规模B.待处理数据的初态C.A和B √解析：计算机算法指的是(1)，它必须具备(2)这三个特陛。

【南京理工大学1999一、1(2分)】（分数：4.00）(1).(1)（分数：2.00）A.计算方法B.排序方法C.解决问题的步骤序列√D.调度方法解析：(2).(2)（分数：2.00）A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性√C.确定性、有穷性、稳定性D.易读性、稳定性、安全性解析：8.一个算法应该是( )。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】（分数：2.00）__________________________________________________________________________________________ 2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】（分数：2.00）__________________________________________________________________________________________3.设散列表长度为14 2.00）__________________________________________________________________________________________ 4.常用的构造哈希函数的方法有哪些?若在哈希表中删除一个记录，应如何操作?为什么?已知一组关键字为(19，14，23，01，68，20，84，27，55，11，10，79)，按哈希函数H(Key)=KeyMOD 13和线性探测再散列处理冲突的方法在地址空间A[0．．15]中构造哈希表。

计算机专业基础综合数据结构（排序）历年真题试卷汇编4(总分66, 做题时间90分钟)1. 单项选择题1.在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是( )。

[山东大学2001二、2(1分)】SSS_SINGLE_SELA 直接插入排序B 冒泡排序C 简单选择排序D 快速排序分值: 2答案:A2.在排序算法中，每次从未排序的记录中挑出最小(或最大)关键字的记录，加入到已排序记录的末尾，该排序方法是( )。

【中山大学1999一、11(1分)】SSS_SINGLE_SELA 选择B 冒泡C 插入D 堆分值: 2答案:A3.若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行( )次比较。

【南京理工大学1999一、11(4分)】SSS_SINGLE_SELA 3B 10C 15D 25分值: 2答案:C4.采用简单选择排序，比较次数与移动次数分别为( )。

【南京理工大学2000一、18(1．5分)】SSS_SINGLE_SELA O(n)，O(logn)B O(logn)，O(n*n)C O(n*n)，O(n)D O(nlogn)，O(n)分值: 2答案:C5.对序列{15，9，7，8，20，一1，4，)用希尔排序方法排序，经一趟后序列变为{15，一1，4，8，20，9，7}，则该次采用的增量是( )。

【南京理工大学1999一、15(1分)】SSS_SINGLE_SELA 1B 4C 3D 2分值: 2答案:B6.快速排序在最坏情况下的时间复杂度与下列哪个算法最坏情况下的时间复杂度相同? ( )。

【北京交通大学2006一、7(2分)】SSS_SINGLE_SELA Shell排序B 堆排序C 起泡排序D 基排序分值: 2答案:C7.下列排序方法中，( )在待排序的数据为有序时，花费时间反而最多。

【华中科技大学2007一、8(2分)】SSS_SINGLE_SELA 快速排序B 插入排序C 堆排序D 冒泡排序分值: 2答案:A8.快速排序算法在最好情况下的时间复杂度是( )。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编1(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：9，分数：18.00)1.对于双向循环链表，在P指针所指的结点之后插入s指针所指结点的操作应为( )。

【北京工业大学2004一、1(3分)】（分数：2.00）A.P一>right=s；s一>left=p；p->right一>left=s；s一>right=p一>right；B.P一>right=s；p->right一>left=s； s一>left=p； s一>right=p一>fight；C.s一>left=p； s一>right=p一>right；P一>right=-s；P一>right一>left=s；D.s一>left=p； s一>right=p一>fight；P一>right一>left=s；P一>right=s；√解析：解析：双链表在p指向的结点前或结点后插入结点都可以，但是必须避免“断链”。

本例A和B第一个语句就将p的原后继断链，没必要再浪费时间看这两个选择答案后边的其他语句。

2.设双向循环链表中结点的结构有数据域data，指针域pre和next，链表不带头结点。

若在指针P所指结点之后插入结点S，则应执行下列( )操作。

【南京理工大学2005一、3 (1分)】【北京交通大学2006一、1(2分)】（分数：2.00）A.P一>next=s；s一≥pre=p；P一>next一>pre=s；s一>next=p一>next；B.P一>next=s；P一>next->pre=s；s一≥pre=p；s一>next=p一>next；C.s一>pre=p；s一>nex=p一>next；P一>next=s；P一>next->pre=s；D.s一≥pre=p；s->next=p一>next；P一>next一>pre=s；P一>next=s；√解析：3.在下列双向链表中，已知指针pa指向结点A，若在A、C之间插入指针pb所指的结点B，则依次执行的【华中科技大学2006二、4(2分)】(1)pb一>next=pa->next；(2)pb一>prior=pa；语句序列可以是( )。

计算机专业基础综合历年真题试卷汇编1(总分：62.00，做题时间：90分钟)一、单项选择题(总题数：27，分数：54.00)1.单项选择题1-40小题。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

（分数：2.00）__________________________________________________________________________________________解析：2.先序序列为a，b，c，d的不同二叉树的个数是_______。

（分数：2.00）A.13B.14 √C.15D.16解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。

因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个不同元素进栈，出栈序列的个数为 C 2n n =14。

3.假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是_______。

（分数：2.00）A.+(*-B.+(-* √C.／+(*-*D.／+-*解析：解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时： a．若为‘(’，入栈； b．若为‘)’，则依次把栈中的的运算符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’； c．若为除括号外的其他运算符，当其优先级高于除‘(’以外的栈顶运算符时，直接入栈。

否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。

当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。

4.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是_______。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编1(总分64,考试时间90分钟)1. 单项选择题1. 数组A[0．．5，0．．6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

【南京理工大学2001一、13(1．5分)】A. 1 175 B. 1 180C. 1205D. 12102. 设7行6列的数组a以列序为主序顺序存储，基地址为1024，每个元素占2个存储单元，第4行第5列的元素(假定无第0行第0列)的存储地址是( )。

【华中科技大学2006一、3(2分)】A. 1068B. 1086C. 1084D. 10663. 若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素(假定无第0行第0列)的地址是( )。

【华中科技大学2004一、4(1分)】A. 1040B. 1042C. 1026D. 备选答案A，B，C都不对二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节；(2)A的第8 N一和第5行共占( )个字节；(3)若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素( )的起始地址一致。

【山东工业大学2000三、1(4分)】【山东大学1998三、1(4分)】4. (1)A. 90B. 180C. 240D. 270E. 5405. (2)A. 108B. 1 14C. 54D. 60E. 1506. (3)A. A[8，5]B. A[3，10]C. A[5，8]D. A[0，9]7. 设二维数组A[1．．m，1,n](即m行n列)按行存储在数组研1一m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

【南京理工大学1998一、2(2分)】A. (i-1)*n+jB. (i—1)*n+j-1C. t*(f一1)D. f*m+i-18. 将一个A[1—100，1．．100]的三对角矩阵，按行优先存入一维数组B[1—298]中，A中元素A6665(即该元素下标i=66，j=65)，在B数组中的位置K为( )。