[IT认证]全国计算机等级考试《数据结构》典型试题

典型题目分类§1概述［全真模拟试卷３选择题３］数据结构中，与计算机无关的是数据的Ａ存储结构Ｂ物理结构Ｃ逻辑结构Ｄ物理和存储结构答案：Ｃ［全真模拟试卷５选择题１］数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及Ａ数据的存储结构Ｂ计算方法Ｃ数据映象Ｄ逻辑存储答案：Ａ［全真模拟试卷５选择题３］在计算机中，算法是指Ａ加工方法Ｂ解决方案的准确而完整的描述Ｃ排序方法Ｄ查询方法答案：Ｂ［全真模拟试卷１填空题１］算法的基本特征是可行性、确定性、和拥有足够的情报。答案：有穷性［全真模拟试卷６选择题２］算法分析的目的是Ａ找出数据结构的合理性Ｂ找出算法中输入和输出之间的关系Ｃ分析算法的易懂性和可靠性Ｄ分析算法的效率以求改进答案：Ｄ［全真模拟试卷６填空题１］在算法正确的前提下，评价一个算法的两个标准是。答案：时间复杂度和空间复杂度［专家预测试卷３填空题１］算法的工作量大小和实现算法所需的存储单元多少分别称为算法的。答案：时间复杂度和空间复杂度［全真模拟试卷３选择题１］算法的空间复杂度是指Ａ算法程序的长度Ｂ算法程序中的指令条数Ｃ算法程序所占的存储空间Ｄ执行过程中所需要的存储空间答案：Ｄ§2线性表［全真模拟试卷６选择题３］线性表Ｌ＝（a1,a2,……,ai,……,an），下列说法正确的是Ａ每个元素都有一个直接前件和直接后件Ｂ线性表中至少要有一个元素Ｃ表中诸元素的排列顺序必须是由小到大或由大到小Ｄ除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前件和一个直接后件答案：Ｄ［全真模拟试卷７选择题１］下列叙述正确的是Ａ线性表是线性结构Ｂ栈和队列是非线性结构Ｃ线性链表是非线性结构Ｄ二叉树是线性结构答案：Ａ［专家预测试卷３选择题１］根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成Ａ动态结构和静态结构Ｂ紧凑结构和非紧凑结构Ｃ线性结构和非线性结构Ｄ内部结构和外部结构答案：Ｃ［全真模拟试卷３填空题１］数据的逻辑结构有线性结构和两大类。答案：非线性结构［专家预测试卷１选择题３］线性表的顺序存储结构和线性表的链式存储结构分别是Ａ顺序存取的存储结构，顺序存取的存储结构Ｂ随机存取的存储结构，顺序存取的存储结构Ｃ随机存取的存储结构，随机存取的存储结构Ｄ任意存取的存储结构，任意存取的存储结构答案：Ｂ［全真模拟试卷５填空题１］长度为ｎ的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为。答案：ｎ/2§3栈和队列［全真模拟试卷１选择题１］栈和队列的共同特点是Ａ都是先进先出Ｂ都是后进先出Ｃ只允许在端点处插入和删除元素Ｄ没有共同点答案：Ｃ［全真模拟试卷２选择题３］如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是Ａe3,e1,e4,e2Ｂe2,e4,e3,e1Ce3,e4,e1,e2D任意顺序答案：Ｂ［全真模拟试卷８选择题２］栈底至栈顶依次存放元素Ａ、Ｂ、Ｃ、Ｄ，在第五个元素Ｅ入栈前，栈中元素可以出栈，则出栈序列可能是ＡＡＢＣＥＤＢＤＣＢＥＡＣＤＢＣＥＡＤＣＤＡＢＥ答案：Ｂ［专家预测试卷２选择题１］下列数据结构中，按先进后出原则组织数据的是Ａ线性链表Ｂ栈Ｃ循环链表Ｄ顺序表答案：Ｂ［专家预测试卷１填空题１］栈和队列通常采用的存储结构是。答案：链式结构和顺序结构注：实事上各种数据结构都可以有以上两种存储结构。［全真模拟试卷４选择题３］一些重要的程序设计语言（如Ｃ和Pascal语言）允许过程的递归调用。而实现递归调用中的存储分配通常用Ａ栈Ｂ堆Ｃ数组Ｄ链表答案：Ａ§4线性链表［全真模拟试卷３选择题２］用链表表示线性表的优点是Ａ便于随机存取Ｂ花费的存储空间比顺序存储少Ｃ便于插入和删除操作Ｄ数据元素的物理顺序与逻辑顺序相同答案：Ｃ［全真模拟试卷１选择题３］链表不具有的特点是Ａ不必事先估计存储空间Ｂ可随机访问任一元素Ｃ插入和删除不需要移动元素Ｄ所需空间与线性表长度成正比［全真模拟试卷２填空题１］数据结构分为逻辑结构和存储结构，线性链表属于。答案：存储结构［全真模拟试卷６选择题４］在单链表中，增加头结点的目的是Ａ方便运算的实现Ｂ使单链表至少有一个结点Ｃ标识表结点中首结点的位置Ｄ说明单链表是线性表的链式存储实现答案：Ａ［全真模拟试卷７选择题２］非空的循环单链表head的尾结点（由p所指向），满足Ａp-next==NULLBp==NULLCp-next==headDp==head答案：Ｃ［全真模拟试卷８选择题１］循环链表的主要优点是Ａ不再需要头指针了Ｂ从表中任一结点出发都能访问到整个链表Ｃ在进行插入、删除运算时，能更好地保证链表不断开Ｄ已知某个结点的位置后，能够容易的找到它的直接前件答案：Ｂ［全真模拟试卷５选择题２］串的长度是Ａ串中不同字符的个数Ｂ串中不同字母的个数Ｃ串中所含字符的个数且字符个数大于零Ｄ串中所含字符的个数答案：Ｄ§5树与二叉树［全真模拟试卷２选择题２］树是结点的集合，它的根结点的数目是Ａ有且只有１Ｂ１或多于１Ｃ０或１Ｄ至少２答案：Ａ［全真模拟试卷４填空题１］在深度为５的满二叉树中，叶子结点的个数为Ａ３２Ｂ３１Ｃ１６Ｄ１５答案：Ｃ（注：满二叉树的叶结点都在最底层，本题即第５层）［专家预测试卷２选择题２］具有３个结点的二叉树有Ａ２种形态Ｂ４种形态Ｃ７种形态Ｄ５种形态答案：Ｄ［专家预测试卷３选择题２］设一棵二叉树中有３个叶子结点，有８个度为１的结点，则该二叉树中总的结点数为Ａ１２Ｂ１３Ｃ１４Ｄ１５答案：Ｂ［专家预测试卷２选择题３］设有下列二叉树，CＡTXBZYP对此二叉树前序遍历的结果为Ａ）ZBTYCPXAＢ）ATBZXCYPＣ）ZBTACYXPＤ）ATBZXCPY答案：Ｂ［全真模拟试卷１选择题２］已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是ＡacbedＢdecbaＣdeabcＤcedba答案：Ｄ注：由前序和中序或由后序和中序序列都可以唯一确定一棵二叉树的形状，而仅由前序和后序序列是不能确定的。［全真模拟试卷２选择题１］已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为Ａ）GEDHFBCAＢ）DGEBHFCAＣ）ABCDEFGHＤ）ACBFEDHG答案：Ｂ［全真模拟试卷４选择题２］已知一棵二叉树前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则该二叉树的后序遍历的结点访问顺序是ＡbdgcefhaＢgdbecfhaＣbdgaechfＤgdbehfca答案：Ｄ§6查找［全真模拟试卷1填空题2］在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为。答案：log2n§7排序［专家预测试卷２填空题1］排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、和选择排序等。答案：交换排序［全真模拟试卷7选择题3］已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是A堆排序B直接插入排序C快速排序D直接选择排序答案：Bcedba［专家预测试卷1选择题1］最简单的交换排序方法是A快速排序B选择排序C堆排序D冒泡排序答案：D［全真模拟试卷7填空题1］冒泡排序算法在最好情况下的元素交换次数为。答案：0注：排序前已经完全有序，比较次数为n-1，交换次数为0。［全真模拟试卷6选择题1］假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为Alog2nBn2CO(n1.5)Dn(n-1)/2答案：D［全真模拟试卷7填空题2］在最坏情况下，堆排序需要的比较次数为。答案：nlog2n［专家预测试卷3选择题3］在下列几种排序方法中，要求内存量最大的是A插入排序B选择排序C快速排序D归并排序答案：D