数据结构习题.docx
- 文档编号:14492260
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:40
- 大小:209.62KB
数据结构习题.docx
《数据结构习题.docx》由会员分享,可在线阅读,更多相关《数据结构习题.docx(40页珍藏版)》请在冰点文库上搜索。
数据结构习题
选择题
1.数据结构是一门研究非数值计算的程学设计问题中计算机的
(1)以及它们之间的
(2)和运算等的学科。
(1)A.数据元素B。
计算方法C。
逻辑存储D。
数据映像
(2)A.结构B。
关系C。
运算D。
算法
答案:
(1)A
(2)B
2.数据结构在计算机内存中的表示是指
A.数据的存储结构B。
数据结构C。
数据的逻辑结构D。
数据元素之间的关系
答案:
A
3.算法分析的目的是
(1),算法分析的两个主要方面是
(2)。
(1)A.找出数据结构的合理性B。
研究算法中的输入和输出的关系
C.分析算法的效率以求改进D。
分析算法的易懂性和文档性
(2)A.空间复杂度和时间复杂度B。
正确性和简明性
C.可读性和文档性D。
数据复杂性和程序复杂性
答案:
(1)A
(2)B
4.以下的叙述中,正确的是
A.线性表的线性存储结构优于链表存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
答案:
B
5.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储
A.数据的处理方法B。
数据元素的类型
C.数据元素之间的关系D。
数据的存储方法
答案:
C
6.下面的说法错误的是
A.算法原地工作的含义是指不需要任何额外的辅助存储空间。
B.在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法。
C.所谓时间复杂度是指最坏情况下,估计算法的执行时间的上界。
D.同一个算法,实现语句的级别越高,执行效率越低。
答案:
A
7.以下说法正确的是
A.数据元素是数据的最小单位。
B.数据项是数据的基本单位
C.数据结构是带结构的数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
答案:
D
8.链表不具备的特点是
A.可随机访问任一结点B。
插入删除不需要移动元素
C.不必事先估计存储空间D。
所需空间与其长度成正比
答案:
A
9。
不带头结点的单链表head为空的判定条件是
A.head==NULLB.head->next==NULLC.head->next==headD.head!
=NULL
答案:
A
10.带头结点的双循环链表L为空表的条件是
A.L==NULLB。
L->next==NULLC.L->prior==NULLD.L->next==L
答案:
D
11.非空的循环单链表head的尾结点(由P所指向)满足
A.p->next==NULLB.p==NULLC.p->next==headD.p==head
答案:
.在非空的循环单链表head中,尾节电*p的next域指向*head结点,即有p->next==head.,即答案为C。
12。
在循环双链表的P所指结点之前插入S所指结点的操作是
A.p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;
B.p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;
C.s->next=p;s->prior=p->prior;p->prior=s;p->prior->next=s;
D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;
答案:
D
13.设线性表有n个元素,以下算法中,在顺序表上实现比在链表上实现效率更高。
A.输出第i(0≤i≤年n-1)个元素值
B.交换第0个元素与第1个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
答案:
A
14。
与单链表相比,双链表的优点之一是
A.插入、删除操作更简单B。
可以进行随机访问
C.可以省略表头指针或表尾指针D。
顺序访问相邻结点更灵活
答案:
D
15。
栈和队列的共同点是
A.都是先进后出B。
都是后进先出C。
只允许在端点处插入和删除元素D。
没有共同点
答案:
C
16。
一个栈的进序列是a,b,c,d,e,则栈的不可能的输出顺序是
A.edcbaB.decbaC.dceabD.abcde
答案:
C
17.若已知一个栈的进栈序列是1,2,3,。
。
。
,n,其输出序列为P1,P2,P3,。
。
。
,Pn,若P1=n,则pi(1
A.iB.n=iC.n-i+1D.不确定
答案:
C
18.若已知一个栈的进栈序列是1,2,3,4,。
。
。
,n,其输出顺序为P1,p2,p3,…,pn,若pn=n,则pi为
A.iB.n=iC.n-i+1D.不确定
答案:
A
19.判定一个顺序栈st(最多元素为Maxsize)为空的条件是
A.st->top!
=-1B.st->top==-1C.st->top!
=Maxsize-1D.st->top==Maxsize-1
答案:
B
20.向一个栈顶指针为hs的链栈中插入一个s所指结点时,则执行
A.hs->next=s;B.s->next=hs->next;hs->next=s;
C.s->next=hs;hs=s;D.s->next=hs;hs=hs->next;
答案:
C
21.一个队列的入队序列是1,2,3,4,则队列的输出顺序是
A.4,3,2,1B。
1,2,3,4C。
1,4,3,2D。
3,2,4,1
答案:
B
22。
判定一个环形队列qu(最多元素为Maxsize)为空的条件是
A.qu->rear-qu->front==MaxsizeB.qu->rear-qu->front-1==Maxsize
C.qu->front==qu->rearD.qu->front==qu->rear+1
答案:
C
23。
判定一个环形队列qu(最多元素为Maxsize)为满的条件是
A.(qu->rean+1)%Maxsize==qu->frontB.qu->rear-qu->front-1==Maxsize
C.qu->front==qu->rearD.qu->front==qu->rear+1
答案:
A
24。
若用一个大小为6的一位数组来实现环形队列,且当前rear和front的值分别为0和3。
当从队列中删除一个元素,再加入两个元素后,rear和front的值分别是
A.1和5B。
2和4C。
4和2D。
5和1
答案:
B
25。
在一个链队中,假设f和r分别为队头和队尾指针,则插入s所指结点的运算是
A.f->next=s;f=s;B.r->next=s;r=s;C.s->next=r;r=s;D.s->next=f;f=s;
答案:
B
26.中缀表达式A*(B+C)/(D-E+F)的后缀表达式是
A.A*B+C/D-E+FB。
AB*C+D/E-F+C。
ABC+*DE-+/D。
ABCDEF*+/-+
答案:
C
27。
串是一种特殊的线性表,其特殊性体现在
A.可以顺序存储B。
数据元素是一个字符C。
可以链式存储D。
数据元素可以是多个字符
答案:
B
28.是C语言中“abcd321ABCD”的子串。
A.abcdB.321ABC.“abcABC”D.“21AB”
答案:
D
29。
设有两个串P和q,求q在P中首次出现的位置的运算称作
A.连接B。
模式匹配C。
求子串D。
求串长
答案:
B
30.若串s=’software’,其子串(不含自身)的个数是()
A.8B.37C.36D.9
答案是C
31.一维数组和线性表的区别是()
A.前者长度固定,后者长度可变B.后者长度固定,前者长度可变
C.两者长度均固定D.两者长度均可变
答案是A
32.数组A中,每个元素A的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是()
A.80B.100C.240D.270
答案是C
33.数组A中,每个元素A的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为()
A.SA+141B.SA+144C.SA+222D.SA+255
答案是C
34.设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a1,1为第一个元素,其存储地址为1,每个元素占1个地址空间,则a8,5的地址为()
A.13B.33C.18D.40
答案是B
35.一个n*n的对称矩阵,如果以行或列为主序放入内存,则容量为()
A.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2
答案是C
36.稀疏矩阵一般的压缩存储方法有两种,即()
A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表
答案是C
37.递归函数f(n)=f(n-1)+n(n>1)的递归出口是()
A.f
(1)=0B.f
(1)=1C.f(0)=1D.f(n)=n
答案是B
38.将递归算法转换成对应的非递归算法时,通常需要使用()
A.栈B.队列C.链表D.树
答案是A
39.广义表((a,b),c,d)的表头是(①),表尾是(②)
A.aB.bC.(a,b)D.(c,d)
答案是①A②B
40.广义表((a,b,c,d))的表头是(①),表尾是(②)
A.aB.()C.(a,b,c,d)D.((a,b,c,d))
答案是①C②B
41.若广义表A=(a,b,(c,d),(e,(f,g))),刚下面式子的值为()
Head[tail[head[tail[tail[A]]]]]
A.(g)B.(d)C.(c)D.(d)
答案是D
42.树最适合用来表示()
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
答案是C
43.在线索化二叉树中,t所指结点没有左子树的充要条件是()
A.t->lchild==NULLB.t->ltag==1C.t->ltag==1且t->lchild==NULLD.以上都不对
答案是B
44.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点树至少为()
A.2hB.2h-1C.2h+1D.h+1
答案是B
45.一棵二叉树如图8.10所示,其中序遍历的序列为()
A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh
答案是B
图8.10
46,如果T2是由有序树T1转换而来的二叉树,那么T1中结点的先序就是T2中结点的()
A.先序B.中序C.后序D.层次序
答案是A
47.如果T2是由有序树T1转换而来的二叉树,那么T1中结点的后序就是T2中结点的()
A.先序B.中序C.后序D.层次序
答案是B
48.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
结论()是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D.以上都不对
答案是A
49.深度为5的二叉树至多有()个结点
A.3B.4C.31D.10
答案是C
50.在一非空二叉树的中序遍历序列中,根结点的右边()
A.只有右子树上的所有结点B.只有右子树上的部分结点
C.只有左子树上的部分结点C.只有左子树上的所有结点
答案是A
51.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序()
A.不发生改变B.发生改变C.不能确定D.以上都不对
答案是A
52.设n,m为一棵二叉树上的两个结点,在中序遍历时,n在m前的条件是()
A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙
答案是C
53.根据使用频率为5个字符设计的哈夫曼编码不可能是()
A.000,001,010,011,1B.0000,0001,001,01,1
C.000,001,01,10,11D.00,100,101,110,111
答案是D
54.在一个无向图中,所有顶点的度数之和等于所有边数的()倍
A.1/2B.1C.2D.4
答案是C
55.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍
A.1/2B.1C.2D.4
答案是B
56.一个有n个顶点的无向图最多有()条边
A.nB.n(n-1)C.n(n-1)/2D.2n
答案是C
57.具有6个顶点的无向图至少应有()条边才能确保是一个连通图
A.5B.6C.7D.8
答案是A
58.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是()
A.nB.(n-1)*(n-1)C.n-1D.n*n
答案是D
59.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为();所有邻接表中的结点总数是()
A.nB.n+1C.n-1D.n+e
A.e/2B.eC.2eD.n+e
答案是AC
60.对某个无向图的邻接矩阵来说,()
A.第i行上的非零元素个数和第i列的非零元素个数一定相等
B.矩阵中的非零元素个数等于图中的边数
C.第i行上,第i列上非零元素总数等于顶点Vi的度数
D.矩阵中非全零行的行数等于图中的顶点数
答案是A
61.已知一个图如图9.5所示,若从顶点a出发按深度搜索法进行遍历,则可能得到一种顶点序列为(①);按广度搜索法进行遍历,则可能得到的一种顶点序列为(②)
①A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b
②A.a,b,c,e,d,fB.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b
答案是①D②B
图9.5
62.已知一有向图的邻接表存储结构如图9.6所示
图9.6
(1)根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点序列是()
A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5C.V1,V3,v4,v5,v2D.V1,v4,v3,v5,v2
答案是C
(2)根据有向图的广度优先遍历算法,从顶点v1出发,所得到的顶点序列是()
A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2
答案是B
63.任何一个无向连通图的最小生成树()
A.有一棵或多棵B.只有一棵C.一定有多棵D.可能不存在
答案是A
64.以下说法中不正确的是()
A.无向图中的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索方法
答案是D
65.顺序查找法适合于存储结构为()的线性表
A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储
答案是B
66.对线性表进行折半查找时,要求线性表必须()
A.以顺序方式存储B.以顺序方式存储,且结点按关键字有序排序
C.以链接方式存储D.以链接方式存储,且结点按关键字有序排序
答案是B
67.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值82的结点时,()次比较后查找成功
A.1B.2C.4D.8
答案是C
68.对有18个元素的有序表作折半查找,则查找A[3]的比较序列的下标为()
A.1、2、3B.9、5、2、3C.9、5、3D.9、4、2、3
答案是D
69.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用()查找方法
A.分块B.顺序C.折半D.散列
答案是A
70.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,作壁上观设采用顺序查找来确定结点所在的块时,每块应分()个结点最佳
A.10B.25C.6D.625
答案是B
71.关于散列表查找说法不正确的有()个
A.m阶B-树中的每个结点的子树个数都小于或等于m
B.m阶B-树中的每个结点的子树个数都大于或等于[m/2]
C.m阶B-树中的任何一个结点的子树高度都相等
D.m阶B-树具有k个子树的非叶子结点含有k-1个关键字
答案是B
72.关于散列表查找说法不正确的有()个
(1)采用链地址法解决冲突时,查找一个元素的时间是相同的
(2)采用链地址法解决冲突时,若规定插入总是在链首,则插入任一个元素的时间是相同的
(3)采用链地址法解决冲突易引起集现象
(4)再散列法不易产生聚集
A.1B.2C.3D.4
答案是B
73.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行()次探测
A.k-1B.kC.k+1D.k(k+1)/2
答案是D
74.以下说法错误的是()
A.散列法存储的基本思想是由关键码值决定数据的存储地址
B.散列表的结点中只包含数据元素自身的信息,不包含任何指针
C.装填因子是散列法的一个重要参数,它反映了散列表的装填程度
D.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法
答案是B
75.散列表的平均查找长度()
A.与处理冲突方法有关而与表的长度无关
B.与处理冲突方法无关而与表的长度有关
C.与处理冲突方法有关且与表的长度有关
D.与处理冲突方法无关且与表的长度无关
答案是A
76.设散列表长m=14,散列函数H(key)=key%11。
表中已有4个结点:
addr(15)=4
Addr(38)=5
Addr(61)=6
Addr(84)=7
其余地址为空。
如用二次探测再散列处理冲突,关键字为49的结点的地址是()
A.8B.3C.5D.9
答案是D
77.排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为()
A.希尔排序B.冒泡排序C.插入排序D.选择排序
答案是C
78.在待排序的元素序列基本有序的前提下,效率最高的排序方法是()
A.插入排序B.选择排序C.快速排序D.归并排序
答案是A
79.对记录的关键字为{50,26,38,80,70,90,8,30,40,20}进行排序,各趟排序结束时的结果为:
5026388070908304020
5083040902026388070
2682040383050908070
8202630384050708090
其使用的排序方法是()
A.快速排序B.基数排序C.希尔排序D.归并排序
答案是C
80.对给出的一组关键字{14,5,19,20,11,19}。
若按关键字非递减排序,第1趟排序结果为{14,5,19,20,11,19},问采用的排序算法是()
A.简单选择排序B.快速排序C.希尔排序D.二路归并排序
答案是C
81.在对n个元素进行冒泡排序的过程中,最好情况下的时间复杂度为()
A.O
(1)B.(log2n)C.O(n2)D.O(n)
答案是D
82.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为()
A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79
答案是C
83.用某种排序方法对线性表{25,84,21,47,15,27,68,35,20}进行排序时,元素序列的变化情况如下:
(1)25,84,21,47,15,27,68,35,20
(2)20,15,21,25,47,27,68,35,84
(3)15,20,21,25,35,27,47,68,84
(4)15,20,21,25,27,35,47,68,84
则用采的排序方法是()
A.直接选择排序B.希尔排序C.归并排序D.快速排序
答案是D
84.快速排序方法在()情况下最不利用发挥其长处
A.要排序的数据量太大B.要排序的数据中含有多个相同值
C.要排序的数据已基本有序D.要排序的数据个数为奇数
答案是C
85.快速排序在最坏情况下时间复杂度是O(n2),比()的性能差
A.堆排序B.冒泡排序C.直接选择排序D.直接插入排序
答案是A
86.在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是()
A.希尔排序B.冒泡排序C.直接插入排序D.直接选择排序
答案是D
87.在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是()
A.O(log2n)B.O
(1)C.O(n)D.O(nlog2n)
答案是B
88.一组记录的排序码为{46,79,56,38,40,84},则利用堆排序(建立大根堆)的方法建初始堆为()
A.79,46,56,38,40,80B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,38
答案是B
89.下述几种排序方法中,要求内存量最大的是()
A.直接插入排序B.选择排序C.快速排序D.归并排序
答案是D
90.外排序是指()
A.在外存上进行的排序方法B.不需要使用内存的排序方法
C.数据很大,需要人工干预的排序方法
D.排序前后数据在外存,排序时数据调入内存的排序方法
答案是D
填空题
1.数据结构包括(线性结构)、(树形结构)和(图形结构)三种类型,树形结构和图形结构合称为(非线性结构)
2.算法的5个重要特性是(有穷性)、(确定性)、(可行性)、输入和输出
3.向一个长度为n的顺序表中的第i个元素(0≤i≤n-1)之前插入一个元素时,需向后移动(n-i+1)个元素
4.在一个长度为n的顺序表中删除第i个元素(0≤i≤n-1)时,需向前移动(n-i-1)个元素
5.在一个单链表中的p所指结点之前插入一个s所指结点时,可执行如下操作:
(1)s->next=(p->next);
(2)p->next=s
(3)t=p->data;
(4)p->data=(s->data)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题