2015宁夏回族自治区数据结构基础最新考试试题库(完整版)

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

cA．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

数据结构试题集（8套卷子+答案）《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i ３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D)Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

《数据结构-C语言版》第一章绪论单项选择题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．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。

A. n2B. nlognC. nD. logn7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。

A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1．链表不具有的特点是____ ____。

A. 可随机访问任一元素B. 插入和删除时不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表的长度正比2．设顺序表的每个元素占8个存储单元。

第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。

A. 139B. 140C. 147D. 1483．在线性链表存储结构下，插入操作算法。

A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满4．在一个单链表中，若删除p所指结点的后继结点，则执行。

A. p->next = p->next->next;B. p->next = p->next;C. p = p->next->next;D. p = p->next; p->next = p->next->next;5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。

一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。

●判断题（一）1.数据元素是数据最小单位。

错2.数据对象就是一组数据元素的集合。

错3.任何数据结构都具备三个基本运算：插入、删除和查找。

错4.数据对象是由有限个类型相同的数据元素构成的。

对5.数据的逻辑结构与各数据元素在计算机中如何存储有关。

错6.如果数据元素值发生改变，则数据的逻辑结构也随之改变。

错7.逻辑结构相同的数据，可以采用多种不同的存储方法。

对8.逻辑结构不相同的数据，必须采用不同的存储方法来储存。

错9.数据的逻辑结构是指数据元素的各数据项之间的逻辑关系。

错●判断题（二）1.顺序存储方式只能用于存储线性结构。

错2.数据元素是数据最小的单位。

错3.数据结构是带有结构的数据元素的集合。

对4.数据的逻辑结构是指各数据元素之间的逻辑关系。

对5.数据结构、数据元素、数据项在计算机中的表示分别称为存储结构、节点和数据域。

对6.数据的物理结构是指数据在计算机内的实际的存储形式。

对●判断题一1.分配给单链表的内存单元地址必须是连续的。

错2.与顺序表相比，在链表中顺序访问所有节点，其算法的效率比较低。

错3.从长度为n的顺序表中删除任何一个元素，时间复杂度都是O（n）。

错4.向顺序表中插入一个元素，平均要移动大约一半的元素。

对5.凡是为空的单链表都是不含任何节点的。

错6.如果单链表带有头结点，则插入操作永远不会改变头节点指针的值。

对7.在循环单链表中，任何一个节点的指针域都不可能为空。

对●判断题二1.顺序存储方式的特点是存储密度大且插入、删除运算效率高。

错2.线性表的顺序存储结构优于链式存储结构。

错3.顺序存储结构属于静态结构而链式存储结构属于动态结构。

对4.由于顺序存储结构要求连续的存储区域，所以再存储管理上不够灵活。

对5.对于单链表来说，只有从头节点开始才能扫描表中全部节点。

对6.对于循环单链表来说，从表中任一节点出发都能扫描整个链表。

对7.双链表的特点是很容易找任一节点的前驱和后继。

对第三章1.栈底元素是不能删除的元素。

第1章绪论1 自测习题二、选择题1．以下数据结构中，属于线性结构的是 ( B )A）有向图B）串C）线索二叉树D）B树2．下列与数据元素有关的叙述中错误的是 (A)A）数据元素是有独立含义的数据最小单位B）数据元素是描述数据的基本单位C）数据元素可以称做结点D）数据元素可以称做记录3．以下术语中与数据的存储结构无关的是 (A)A）栈B）散列表C）顺序表D）双链表4．以下数据结构中，属于线性结构的是 (B)A）有向图B）串C）线索二叉树D）B树三、填空题1．数据结构包括的三方面内容分别是：数据的逻辑结构、数据的存储结构和数据的运算。

2．数据元素是数据的基本单位，在某些情况下也可以称为结点、记录和顶点。

3．数据逻辑结构的4种基本形态包括集合结构、线性结构、树型结构和图（网）结构。

4．一个正确的算法应该具有5个特性：输入、输出、确定性、可行性和有穷性。

5．数据的存储结构包括顺序、链式、索引和散列四种。

6．一个数据结构在计算机中的映象称为存储结构。

7．一个算法的效率主要是指该算法的时间效率和空间效率。

8．以下程序段的时间复杂度T（n）=_)O_____。

(2nsum=0;for(i=0 ; i<n; i++)for( j=0; j<n; j++)sum+=a[i][j];printf("%d\n",sum);第2章线性表2 自测习题二、选择题1．以下链表结构中，从当前结点出发能够访问到任一结点的是（B） A）单向链表和双向链表B）双向链表和循环链表C）单向链表和循环链表D）单向链表、双向链表和循环链表2．线性表是具有n 个 (B) 的有限序列。

A ）数据项B ）数据元素C ）表元素D ）字符3．若长度为n 的线性表采用链式存储结构，访问其第i 个元素的算法时间复杂度为 (B)A ）O(1)B ）O(n)C ） O(n 2)D ）O(log 2n)4．在长度为n 的顺序表中，若要删除第i （1≤i ≤n ）个元素，则需要向前移动的元素的次数为 (B)A ）iB ）n-iC ）n-i+1D ）n-i-15．在长度为n 的顺序表中第i （1≤i ≤n ）个位置上插入一个元素时，为留出插入位置所需移动元素的次数为 (C)A ）n-iB ）iC ）n-i+1D ）n-i-1三、填空题1．有一单链表结构如下：图2-1 填空题1附图若要删除值为c 的结点，应做的操作是p->link=p->link->link 。

数据结构1、算法的计算量大小称为计算的（）——[单选题]A 效率B 复杂性C 现实性D 难度正确答案：B2、树形结构是数据元素之间存在一种（）——[单选题]A 一对一关系B 多对多关系C 多对一关系D 一对多关系正确答案：D3、算法的空间复杂度是指（——[单选题]A 执行算法程序所占的存储空间B 算法程序中的指令条数C 算法程序的长度D 算法执行过程中所需要的存储空间正确答案：D4、算法的时间复杂度是指()——[单选题]A 执行算法程序所需要的时间B 算法执行过程中所需要的基本运算次数C 算法程序的长度D 算法程序中的指令条数正确答案：B5、算法的时间复杂度取决于()——[单选题]A 问题的规模B 待处理数据的初态C A和B正确答案：C6、数据结构只是研究数据的逻辑结构和物理结构,这种观点()——[单选题]A 正确B 错误C 前半句正确,后半句错误D 前半句错误,后半句正确正确答案：B7、计算机算法指的是(),它具有输入、输出、可行性、确定性和有穷性等五个特性。

——[单选题]A 计算方法B 排序方法C 解决问题的优先运算序列D 调度方法正确答案：C8、计算机内部数据处理的基本单位是()——[单选题]A 数据B 数据元素C 数据项D 数据库正确答案：B9、以下说法正确的是( )——[单选题]A 数据元素是数据的最小单位B 数据项是数据的基本单位C 数据结构是带有结构的各数据项的集合D 数据结构是带有结构的数据元素的集合正确答案：D10、下列数据结构中,()是非线性数据结构——[单选题]A 树B 字符串C 队D 栈正确答案：A11、下面关于算法的说法错误的是()——[单选题]A 算法最终必须由计算机程序实现B 为解决某问题的算法同为该问题编写的程序含义是相同的C 算法的可行性是指指令不能有二义性D 以上几个都是错误的正确答案：D12、下列叙述正确的是()——[单选题]A 线性表是线性结构B 栈和队列是非线性结构C 线性链表是非线性结构D 二叉树是线性结构正确答案：A13、数据在计算机存储器内表示时,物理地址与逻辑地址不相同的,称为()——[单选题]A 存储结构B 逻辑结构C 链式存储结构D 顺序存储结构正确答案：C14、在等概率情况下,顺序表的插入操作要移动()结点。

数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。

答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。

答案：队尾、队头11. 二叉树中的节点包括______和______。

答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。

答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。

数据结构试题库及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用（）来存储。

A. 链表B. 栈C. 队列D. 数组答案：D2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C3. 在二叉树的遍历算法中，先访问根节点，然后遍历左子树，最后遍历右子树的遍历方式是（）。

A. 先序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A4. 哈希表的冲突解决方法不包括以下哪种？A. 链地址法B. 线性探测法C. 二分查找法D. 再散列法答案：C5. 在图的遍历算法中，广度优先搜索（BFS）使用的辅助数据结构是（）。

A. 栈B. 队列C. 堆D. 链表答案：B6. 下列关于堆的描述中，错误的是（）。

A. 堆是一种特殊的完全二叉树B. 堆中的每个节点的值都大于其子节点的值C. 堆可以用于实现优先队列D. 堆的插入操作的时间复杂度为O(log n)答案：B7. 在一个长度为n的数组中，使用二分查找算法查找一个元素的最坏情况下的时间复杂度是（）。

A. O(1)B. O(n)C. O(n^2)D. O(log n)答案：D8. 以下哪个数据结构不是线性结构？A. 链表B. 栈C. 队列D. 二叉树答案：D9. 以下哪个算法是动态查找表？A. 直接索引B. 顺序查找C. 二分查找D. 哈希表答案：D10. 在图的表示方法中，邻接矩阵表示法的缺点是（）。

A. 占用空间大B. 占用空间小C. 插入和删除操作复杂D. 遍历操作复杂答案：A二、填空题（每题2分，共20分）1. 在一个长度为n的数组中，使用顺序查找算法查找一个元素的时间复杂度为________。

答案：O(n)2. 一个具有n个节点的完全二叉树的高度为________。

答案：log2(n) + 1（向上取整）3. 一个长度为n的链表，删除一个节点的时间复杂度为________。

答案：O(1)4. 在图的表示方法中，邻接表表示法的缺点是________。

第1章绪论一、判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。

（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（√）3.数据元素是数据的最小单位。

（×）4.数据的逻辑结构和数据的存储结构是相同的。

（×）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）7.数据的存储结构是数据的逻辑结构的存储映象。

（√）8.数据的物理结构是指数据在计算机内实际的存储形式。

（√）9.数据的逻辑结构是依赖于计算机的。

（×）10.算法是对解题方法和步骤的描述。

（√）二、填空题1.数据有逻辑结构和存储结构两种结构。

2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。

3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

4.树形结构和图形结构合称为非线性结构。

5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。

6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。

7.数据的存储结构又叫物理结构。

8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。

9.线性结构中的元素之间存在一对一的关系。

10.树形结构中的元素之间存在一对多的关系。

11.图形结构的元素之间存在多对多的关系。

12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容。

13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。

14.算法是一个有穷指令的集合。

15.算法效率的度量可以分为事先估算法和事后统计法。

16.一个算法的时间复杂度是算法输入规模的函数。

17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。

18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n）。