数据结构习题集一、选择题1．数据结构中所定义的数据元素，是用于表示数据的。
（ C ）A.最小单位B.最大单位C.基本单位D.不可分割的单位2．从逻辑上可以把数据结构分为（ C ）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构3．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A)A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法4．关于串的的叙述，不正确的是( B)A.串是字符的有限序列B.空串是由空格构成的串C.替换是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5．带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（A ）A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B ）A.n/2B.nC.(n+1)/2D.n+17．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A）A.nB.2n-1C.2nD.n28．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(B )A.236B.239C.242D.2459．一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是(A )A.dceabB.decbaC.edcbaD.abcde10．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top 作为栈顶指针，则出栈处理后，top的值应修改为(D )A.top=topB.top=n-1C.top=top-1D.top=top+111．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（ B ）A.13B.35C.17D.3612．栈和队列(C)A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处13．含有n个结点的二叉树用二叉链表表示时，空指针域个数为(C )A.n-1B.nC.n+1D.n+214．对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ B ）A.99B.98C.97D.5015．在一个图中，所有顶点的度数之和与图的边数的比是( C)A.1∶2B.1∶1C.2∶1D.4∶116．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为(A )A.n-1B.nC.n+1D.n/217．在一个具有n个顶点的无向图中，每个顶点度的最大值为（B）A.nB.n-1C.n+1D.2(n-1)18．若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（D ）A.先序遍历B.中序遍历C.后序遍历D.层次遍历19．对线性表进行二分查找时，要求线性表必须( C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列20．二分查找算法的时间复杂度是（ D ）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)21．采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ C ）A.插入和快速B.冒泡和快速C.选择和插入D.选择和冒泡22. 闭散列表中由于散列到同一个地址而引起的“堆积”现象，是( B)A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的23．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。
这种方式主要适合于( B)A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表24．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是(B )A.选择排序B.插入排序C.冒泡排序D.快速排序25．下列程序段的时间复杂度为。
（C）for（i=0；i<m；i++）for（j=0；j<t；j++）c［i］［j］=0；for（i=0；i<m；i++）for（j=0；j<t；j++）for（k=0；k<n；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；A.O(m+n×t)B.O(m+n+t)C.O(m×n×t)D.O(m×t+n)26．数据的四种基本逻辑结构是指（D ）A.数组、链表、树、图形结构B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构D.集合、线性结构、树、图形结构27．在表长为n的顺序表上做插入运算，平均要移动的结点数为（C ）。
A.n/4B.n/3C.n/2D.n28．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（A ）。
A.3 B.4 C.5 D.629．定义二维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ D ）。
A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L30．下列程序段的时间复杂度为____________。
（ D ）for(i=1；i<=n；i++)for(j=1；j<=n；j++)for(k=1；k<=n；k++)s=i+j+k；A.O(m2)B.O(m3)C.O(n2)D.O(n3)31．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( B )。
A.选择排序B.插入排序C.冒泡排序D.快速排序32．设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( A )。
A.DCBAB. CDABC. DBACD. DCAB33．对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（A ）。
A. 24B. 25C.98D.9934．对一棵二叉排序树采用中序遍历进行输出的数据一定是（D ）。
A.递增或递减序列B.递减序列C.无序序列D.递增序列35．散列表中由于散列到同一个地址而引起的“堆积”现象，是( B )。
A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的36．要解决散列引起的冲突问题，常采用的方法有（D ）。
A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法37．下列程序段的时间复杂度为____________。
（A ）k=1;for（i=0；i<n；i++）for（j=0；j<n；j++）A［i］［j］=k++；A.O（n2）B.O（n）C.O（2n）D.O（1）38．数据的四种基本存储结构是指（ B ）A..顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B.顺序存储结构、索引存储结构、链式存储结构、散列存储结构C.顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构39．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C）A.线性结构 B.树形结构C.线性结构和树型结构D.线性结构和图状结构40．在表长为n的顺序表上做删除运算，其平均时间复杂度为( B )A.O(1)B.O(n)C.O(nlog2n)D.O(n2)41．顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（B ）A.212B.213C.214D.21542．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A)A.直接插入排序法B.快速排序法C.堆排序法D.归并排序法43．在完全二叉树中，若一个结点是叶结点，则它没有(C )A.左孩子结点B.右孩子结点C.左孩子结点和右孩子结点D.左孩子结点，右孩子结点和兄弟结点44．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为(C )A.5B.6C.7D.945．二维数组A［11］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A ［0］［0］的存储地址为300，则A［10］［10］的地址为（ A ）A.700B.1120C.1180D.114046．用n个值构造一棵二叉排序树，它的最大高度为（ B ）A.n/2B. nC. n+1D.log2n47．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ A ）A.3 B.4 C.5 D.648．一个具有n个顶点的无向连通图，它所包含的连通分量数为（ B ）A.0B.1C.nD.不确定49．对线性表进行二分查找时，要求线性表必须(C )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列50．散列表中由于散列到同一个地址而引起的“堆积”现象，是(B )A.由同义词之间发生冲突引起的B.由非同义词之间发生冲突引起的C.由同义词之间或非同义词之间发生冲突引起的D.由散列表“溢出”引起的51．在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。
这种方式主要适合于(B )A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表52．要解决散列引起的冲突问题，常采用的方法有(D)A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法53．设用链表作为栈的存储结构，则进行出栈操作时（）。
A 必须判别栈是否为满B 必须判别栈是否为空C 判别栈元素的类型D 对栈不作任何判别54. 栈和队列的共同特点是( A )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点55.若有10个元素的有序表存放在一维数组A[11]中，第一个元素放A[1]中，最后一个数据存入A[10],对这组数据进行二分查找，则查找A［3］的比较序列的下标依次为( A ) A. 5，2，3 B. 6，4，3C. 6，2，3D. 4，2，356.用链表方式存储的队列，在进行插入运算时( C ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改57.下列各项键值序列中不是堆的为（ C ）A.{5，23，16，68，94，72，71，73}B.{5，16，23，68，94，72，71，73}C.{5，23，16，73，94，72，71，68}D.{5，23，16，68，73，71，72，94}58.以下数据结构中哪一个是非线性结构？( D )A. 队列B. 栈C. 线性表D. 二叉树59二叉树的第k层的结点数最多为( A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-160.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，361.设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。