数据结构习题集
一、选择题
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!=ar!=NULL D.front==NULL
6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B ）
A.n/2 B.n C.(n+1)/2 D.n+1
7．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A）
A.n B.2n-1 C.2n D.n2
8．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(B )
A.236 B.239 C.242 D.245
9．一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是(A )
A.dceab B.decba C.edcba D.abcde
10．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为(D )
A.top=top B.top=n-1 C.top=top-1 D.top=top+1
11．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（ B ）
A.13 B.35 C.17 D.36
12．栈和队列( C )
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
13．含有n个结点的二叉树用二叉链表表示时，空指针域个数为(C )
A.n-1 B.n C.n+1 D.n+2
14．对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（ B ）
A.99 B.98 C.97 D.50
15．在一个图中，所有顶点的度数之和与图的边数的比是( C)
A.1∶2 B.1∶1 C.2∶1 D.4∶1
16．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为(A )
A.n-1 B.n C.n+1 D.n/2
17．在一个具有n个顶点的无向图中，每个顶点度的最大值为（ B ）
A.n B.n-1 C.n+1 D.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/4 B.n/3 C.n/2 D.n
28．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（ A ）。
A.3 B.4 C.5 D.6
29．定义二维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（ D ）。
A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L
30．下列程序段的时间复杂度为____________。 （ 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.DCBA B. CDAB C. DBAC D. DCAB
33．对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（A ）。
A. 24 B. 25 C.98 D.99
34．对一棵二叉排序树采用中序遍历进行输出的数据一定是（ 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.212 B.213 C.214 D.215
42．当待排序序列中记录数较少或基本有序时，最适合的排序方法为( A )
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论