计算机二级C语言数据结构历年试题

-.z保持平常心，营造好环境，扬起常笑脸，轻松迎高考。时间

选择

填空

分值比例

2009.3

4

1

1/3

2008.9

4

1

1/3

2008.4

3

2

1/3

2007.9

4

2

3/5

2007.4

5

0

1/3

考点1、算法历年试题：1、算法的有穷性是指〔〕【2008.4〔1.5〕】A〕算法程序的运行时间是有限的B〕算法程序所处理的数据量是有限的C〕算法程序的长度是有限的D〕算法只能被有限的用户使用答案：A〕2、以下表达中正确的选项是〔〕【2007.4〔1.1〕】A〕算法的效率只与问题的规模有关而与数据的存储构造无关B〕算法的时间复杂度是指执行算法所需要的计算工作量C〕数据的逻辑构造与存储构造是一一对应的D〕算法的时间复杂度与空间复杂度一定相关答案：B3、以下表达中正确的选项是〔〕【2006.9〔1.7〕】A〕一个算法的空间复杂度大则其时间复杂度也必定大B〕一个算法的空间复杂度大则其时间复杂度必定小C〕一个算法的时间复杂度大则其空间复杂度必定小D〕上述三种说法都不对答案：D〕4、算法的复杂度主要包括时间复杂度和〔〕复杂度【2005.9〔2.2〕】答案：空间考点2、数据构造的根本概念历年试题：1、以下表达中正确的选项是〔〕【2007.9〔1.5〕】A〕程序执行的效率与数据的存储构造密切相关B〕程序执行的效率只取决于程序的控制构造C〕程序执行的效率只取决于所处理的数据D〕以上三种说法都不对答案：A〕2、以下表达中正确的选项是〔〕【2007.9〔1.6〕】A〕数据的逻辑构造与存储构造必定是一一对应的B〕由于计算机存储空间是向量式的存储构造因此数据的存储构造一定是线性构造C〕程序语言中的数组一般是顺序存储构造的因此利用数组只能处理线性构造D〕以上三种说法都不对答案：D〕3、以下描述中正确的选项是〔〕【2006.4〔1.5〕】A〕线性链表是线性表的链式存储构造B〕栈与队列是非线性构造C〕双向链表是非线性构造D〕只有根结点的二叉树是线性构造答案：A〕4、数据独立性分为逻辑独立性与物理独立性当数据的存储构造发生改变时其逻辑构造可以不变因此基于逻辑构造的应用程序不必修改称为〔〕【2006.4〔2.2〕】答案：物理独立性E〕以下表达中正确的选项是〔〕【2005.9〔1.4〕】A〕一个逻辑数据构造只能有一种存储构造B〕数据的逻辑构造属于线性构造存储构造属于非线性构造C〕一个逻辑数据构造可以有多种存储构造且各种存储构造不影响数据处理的效率D〕一个逻辑数据构造可以有多种村粗构造且各种存储构造影响数据处理的效率答案：D〕5、数据构造分为逻辑构造和存储构造循环队列属于〔〕构造【2005.9〔2.5〕】答案：逻辑6、数据的存储构造是指〔〕【2005.4】A〕存储在外存中的数据B〕数据所占的存储空间量C〕数据在计算机中的顺序存储方式D〕数据的逻辑构造在计算机中的表示答案：D〕考点3、线性表及其顺序存储构造历年试题：1、以下表达中正确的选项是【2009.3〔1.1〕】A〕栈是"先进先出"的线性表B〕队列是"先进后出"的线性表C〕循环队列是非线性构造D〕有序线性表既可以采用顺序存储构造也可以采用链式存储构造答案：D〕2、以下表达中正确的选项是〔〕【2008.9〔1.4〕】A〕顺序存储构造的存储一定是连续的链式存储构造的存储空间不一定是连续的B〕顺序存储构造只针对线性构造链式存储构造只针对非线性构造C〕顺序存储构造能存储有序表链式存储构造不能存储有序表D〕链式存储构造比顺序存储构造节省存储空间答案：A〕考点4、栈和队列历年试题：(1)假设用一个长度为50的数组〔数组元素的下标从0到49〕作为栈的存储空间栈底指针bottom指向栈底元素栈顶指针top指向栈顶元素如果bottom=49top=30(数组下标)则栈中具有〔〕个元素【2009.3〔2.1〕】答案：201、一个栈的初始状态为空现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出栈的顺序是〔〕【2008.9〔1.1〕】A〕12345ABCDEB)EDCBA54321C)ABCDE12345D)54321EDCBA答案：B〕2、以下表达正确的选项是〔〕【2008.9〔1.2〕】A〕循环队列中有队头和队尾两个指针因此循环队列是非线性构造B〕在循环队列中只需要队头指针就能反映队列中元素的动态变化情况C〕在循环队列中只需要队尾指针就能反映队列中元素的动态变化情况D〕循环队列中元素的个数是由队头指针和对尾指针共同决定答案：D3、以下关于栈的表达正确的选项是〔〕【2008.4〔1.7〕】A〕栈按"先进先出"组织数据B〕栈按"先进后出"组织数据C〕只能在栈底插入数据D〕不能删除数据答案：B〕4、设*循环队列的容量是50头指针front=5〔指向队头元素的前一位置〕尾指针rear=29〔指向对尾元素〕则该循环队列中共有〔〕个元素【2008.4〔2.3〕】答案：245、线性表的存储构造主要分为顺序存储构造和链式存储构造队列是一种特殊的线性表循环队列是队列的〔〕存储构造【2007.9〔2.3〕】答案：顺序6、以下队列的表达正确的选项是〔〕【2007.4〔1.5〕】A〕队列属于非线性表B〕队列按"先进后出"原则组织数据C〕队列在队尾删除数据D〕队列按"先进先出"原则组织数据答案：D〕7、按"先进后出"原则组织数据的数据构造是〔〕【2006.9〔2.4〕】答案：栈8、数据构造分为线性构造和非线性构造带链的队列属于〔〕【2006.9〔2.5〕】答案：线性构造9、按照"后进先出"原则组织数据的数据构造是〔〕【2006.4〔1.4〕】A〕队列B〕栈C〕双向链表D〕二叉树答案：B〕10、以下描述中正确的选项是〔〕【2006.4〔1.5〕】A〕线性链表是线性表的链式存储构造B〕栈与队列是非线性构造C〕双向链表是非线性构造D〕只有根结点的二叉树是线性构造答案：A〕11、以下关于栈的描述正确的选项是〔〕【2005.9〔1.3〕】A〕在栈中只能插入元素而不能删除元素B〕在栈中只能删除元素而不能插入元素C〕栈是特殊的线性表只能在一端插入或删除元素D〕栈是特殊的线性表只能在一端插入元素而在另一端删除元素答案：C〕考点5、线性链表历年试题：1、以下描述中正确的选项是〔〕【2006.4〔1.5〕】A〕线性链表是线性表的链式存储构造B〕栈与队列是非线性构造C〕双向链表是非线性构造D〕只有根结点的二叉树是线性构造答案：A〕考点6、树与二叉树历年试题：1、支持子程序调用的数据构造是【2009.3〔1.2〕】A〕栈B〕树C〕队列D〕二叉树答案：B〕2、*二叉树有5个度为2的结点则该二叉树中的叶子结点数是【2009.3〔1.3〕】A〕10B〕8C〕6D〕4答案：C〕3、对以下二叉树进展中序遍历的结果是〔〕【2008.9〔2.7〕】答案：DB*EAYFZC4、深度为5的满二叉树有〔〕个叶子结点【2008.4〔2.2〕】答案：165、一棵二叉树中共有70个叶子结点与80个度为1的结点则该二叉树中总结点数为〔〕【2007.9〔1.8〕】A〕219B)221C)229D)231答案：A〕69+70+806、对以下二叉树进展中序遍历的结果为〔〕【2007.9〔1.4〕】答案：ACBDFEHGP7、对以下二叉树进展前序遍历的结果为〔〕【2007.4〔1.6〕】Ａ〕DYBEAFCZ*B)YDEBFZ*CAC)ABDYECF*ZD)ABCDEF*YZ答案：C〕8、*二叉树中有n个度为2的结点则该二叉树中的叶子结点数为〔〕【2007.4〔1.7〕】A〕n+1B)n-1C)2nD)n/2答案：A〕9、在深度为7的满二叉树中度为2的结点个数为〔〕【2007.4〔2.1〕答案：6310、以下二叉树进展中序遍历的结果是〔〕【2006.9〔1.10〕】A〕ACBDFEGB)ACBDFGEC)ABDCGEFD)FCADBEG答案：A〕11、对如下二叉树进展后序遍历的结果为〔〕【2006.4〔1.6〕】A〕ABCDEFB)DBEAFCC)ABDECFD)DEBFCA答案：D〕12、在深度为7的满二叉树中叶子结点的个数为〔〕【2006.4〔1.7〕】A〕32B〕31C〕64D〕63答案D〕13、一棵二叉树第六层〔根结点为第一层〕的结点数最多为〔〕个【2005.9〔2.4〕】答案：32考点7、查找技术历年试题：1、在长度为n的有序线性表中进展二分查找最坏的情况下需要比拟的次数是〔〕【2008.9〔1.3〕】A〕O〔n〕B)O(n2)C)o(log2n)D)o(nlog2n)答案：C〕2、在长度为64的有序线性表中进展顺序查找最坏情况下需要比拟的次数为〔〕【2006.9〔1.8〕】A〕63B)64C〕6D〕7答案：B〕3、以下数据构造中能用二分法进展查找的是〔〕【2005.9〔2.6〕】A〕顺序存储的有序线形表B〕线形链表C〕二叉链表D〕有序线形链表答案：A4、对于长度为n的线形表进展顺序查找在最坏情况下所需要的比拟次数为〔〕A〕log2nB〕n/2C)nD)n+1答案：C〕考点8、排序技术历年试题：1、以下排序方法中最坏情况下比拟次数最少的是【2009.3〔1.4〕】A〕冒泡排序B〕简单项选择择排序C〕直接插入排序D〕堆排序答案：D〕1、对长度为n的线性表排