数据结构总复习.docx
- 文档编号:18529103
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:28
- 大小:48.10KB
数据结构总复习.docx
《数据结构总复习.docx》由会员分享,可在线阅读,更多相关《数据结构总复习.docx(28页珍藏版)》请在冰点文库上搜索。
数据结构总复习
一、单选题
1.数据结构研究()。
A.数据的逻辑结构、存储结构及操作的实现B.数据的物理结构
C.数据的逻辑结构与存储结构D.数据的逻辑结构。
2.数据的存储结构包括顺序;链式;散列和()4种基本类型。
A.VectorB.IndexC.SetsD.Array
3.若某线性表最常用的操作是取第i个元素,则采用()存储方式最节省运算时间。
A.双链表B.单链表C.顺序表D.单循环链表
4.一个单链表中,已知*q结点是*p结点的前趋结点,若在*q和*p之间插入*s结点,则必须执行()操作。
A.q->next=p->next;p->next=s;B.p->next=s;s->next=q
C.p->next=s->next;s->next=pD.q->next=s;s->next=p;
5.在一个具有n个结点的有序单链表中,若插入一个新结点,单链表仍然有序,则算法的时间复杂度为()。
A.O(n)B.O
(1)C.O(n2)D.O(nlog2n)
6.队列与一般线性表的区别在于()。
A.数据元素的类型不同B.插入或删除操作的位置受限制
C.数据元素的个数不同D.逻辑结构不同
7.设进栈的顺序为abcd,则不可能得到的出栈序列是()。
A.abcdB.dcbaC.dabcD.acdb
8.用链接方式存储的队列,在进行插入运算时().
A.仅修改头指针 B.头、尾指针都要修改
C.仅修改尾指针D.头、尾指针可能都要修改
9.循环队列的队满条件为(在牺牲一个存储空间的情况下)()
A.rear%maxsize==(front+1)%maxsize;B.(rear+1)%maxsize==front+1
C.(rear+1)%maxsize==frontD.rear==front
10.下面关于串的叙述中,哪一个是不正确的()
A.串是字符的有限序列B.模式匹配是串的一种重要运算
C.空串是由空格构成的串D.串既可以采用顺序存储,也可以采用链式存储
11.稀疏矩阵一般的压缩存储方法有()两种。
A.三元组表和十字链表B.三元组表和哈希表
C.二维数组和三维数组D.哈希表和十字链表
12.中序遍历一颗二叉排序树所得到的结点访问序列是结点值的()序列。
A.递增或递减B.递增C.递减D.无序
13.在树中,若结点A有四个兄弟,而且B是A的双亲,则B的度为()。
A.3B.4C.5D.6
14.若一棵二叉树具有10个度为2的结点,则该二叉树的度为0的结点个数是()
A.9B.11C.12D、不确定
15.n个顶点的连通图至少有()条边
A.0B.nC.n+1D.n-1
16.若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个()。
A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵
17.AOV网是一种()。
A.有向图B.无向图C.有向无环图D.无向无环图
18.采用折半查找方法进行查找,数据文件应为()。
A.有序表和链式存储结构B.有序表和顺序存储结构
C.随机表和顺序存储结构D.随机表和链式存储结构
19.在顺序表{2、5、7、10、14、15、18}中,用二分法查找关键码12需做()次关键码比较。
A.2B.3C.1D.5
20.下面的排序算法中,时间复杂度不是O(n2)的是()。
A.直接插入排序B.冒泡排序C.二路归并排序D.直接选择排序
21.算法指的是()
A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列
22.下列数据结构中,()是线性结构。
A.树B.队列C.图D.A和B
23.下面程序的时间复杂为()
for(i=1,s=0;i<=n;i++)
{t=1;
for(j=1;j<=i;j++)t=t*j;
s=s+t;
}
A.O(n)B.O(n2)C.O(n3)D.O(n4)
24.用链表表示线性表的优点是()。
A.便于随机存取B.花费的存储空间比顺序表少
C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同
25.从一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较()个结点。
A.nB.n/2C.(n-1)/2D.(n+1)/2
26.在一个单链表中,已知q所指节点是p所指节点的前驱节点,若在q和p之间插入s节点,则执行()。
A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;
C.q->next=s;s->next=p;D.p->next=s;s->next=q;
27.栈的插入和删除操作在()进行。
A栈顶B栈底C任意位置D指定位置
28.设栈的输入序列是1234,则()是不可能的出栈序列。
A.1243B.2134C.1432D.4312
29.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为()
A.front=front+1B.front=(front+1)%(m-1)
C.front=(front-1)%mD.front=(front+1)%m
30.如下陈述中正确的是()
A.串是一种特殊的线性表B.串的长度必须大于零
C.串中元素只能是字母D.空串就是空白串
31.树型结构中元素间存在()的关系。
A.一对一B.多对多C.一对多D.随机
32.一棵深度为5的满二叉树中,结点的总数为()。
A.31B.32C.33D.16
33.一棵二叉树有67个结点,这些结点的度或者是0,或者是2。
这棵二叉树中度为2的结点有()个。
A.33B.34C.32D.30
34.下面关于图的存储的叙述中正确的是()
A.邻接矩阵占用的存储空间只与图中结点个数有关,而与边数无关;
B.邻接矩阵占用的存储空间只与图中边数有关,而与结点个数无关;
C.邻接表占用的存储空间只与图中结点个数有关,而与边数无关;
D.邻接表占用的存储空间只与图中边数有关,而与结点个数无关。
35.n个顶点的连通图至少有()条边。
A.n-1B.nC.n+1D.0
36.AOV网是一种()。
A.有向图B.无向图C.无向无环图D.有向无环图
37.若采用邻接矩阵法存储一个n个顶点的无向图,则该邻接矩阵是一个()。
A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵
38.对二叉排序树进行()遍历,可以得到该二叉树所有结点构成的有序序列
A.前序B.中序C.后序D.按层序
39.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},如果采用二分查找法,查值为82的结点时,()次比较后查找成功。
A.1B.2C.4D.8
40.假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行()次探测。
A.K-1次B.K(K-1)/2次C.K+1次D.K(K+1)/2次
41.对一个算法的评价,不包括如下()方面的内容。
A.健壮性和可读性B.并行性C.正确性D.时空复杂度
42. 对线性表,在下列哪种情况下应当采用链表表示?
()
A.经常需要随机地存取元素B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变
43.在带有头结点的单链表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;
44.栈和队列的共同特点是()。
A.只允许在端点处插入和删除元素B.都是先进后出
C.都是先进先出D.没有共同点
45.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是()
A.231B.321
C.312D.123
46.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为()
A.front=front+1B.front=(front+1)%(m-1)
C.front=(front-1)%mD.front=(front+1)%m
47.用链接方式存储的队列,在进行插入运算时().
A.仅修改头指针 B.头、尾指针都要修改
C.仅修改尾指针D.头、尾指针可能都要修改
48.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?
脚注(10)表示用10进制表示。
A.688B.678C.692D.696
49.树最适合用来表示()。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
50.二叉树的第k层的结点数最多为().
A.2k-1B.2K+1C.2K-1 D.2k+1
51.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()
A.1,2,3B.9,5,2,3
C.9,5,3D.9,4,2,3
52.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为
A.O
(1) B.O(n) C.O(1og2n)D.O(n2)
53.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有()个,
A.1B.2C.3D.4
54.设有6个结点的无向图,该图至少应有()条边才能确保是一个连通图。
A.5B.6C.7D.8
55.AOV网是一种()。
A.有向图B.无向图C.无向无环图D.有向无环图
56.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是()。
A.堆排序B.冒泡排序C.希尔排序D.快速排序
57.快速排序在最坏情况下的时间复杂度为()。
A.O(log2n)B.O(nlog2n)C.0(n)D.0(n2)
58.从二叉搜索树中查找一个元素时,其时间复杂度大致为()。
A.O(n)B.O
(1)C.O(log2n)D.O(n2)
59.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则所采用的排序方法是()
A.选择排序B.希尔排序C.归并排序D.快速排序
60.设某完全无向图中有n个顶点,则该完全无向图中有()条边。
(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-1
61.下面程序段的时间复杂度为()。
for(i=0;i for(j=0;j A[i][j]=0; A.O(m-1)*O(n-1)B.O((m-1)*(n-1)) C.O((m+1)*(n+1))D.O(m*n) 62.从一个长度为n的顺序表中,在第i个元素之前插入一个元素需要向后移动()个元素。 A.n-iB.n-i+1C.n-i-1D.i 63.在一个单链表head中,若要在指针q所指的结点后面插入一个由指针p所指的结点,则执行()。 A.q->next=p->next;p->next=q;B.p->next=q->next;q=p; C.q->next=p;p->next=q->next;D.p->next=q->next;q->next=p; 64.若入栈序列为A、B、C、D、E,入栈过程中可以出栈,则不可以是出栈序列()。 A.ABCDEB.BCDEAC.EABCDD.EDCBA 65.在一个链队列中,假设f和r分别为队首指针和队尾指针,则出队列操作中,下列()语句是必要的。 A.r=f->nextB.r=r->nextC.f=f->nextD.f=r->next 66.假定一个顺序循环队列的队首队尾指针分别用front和rear表示,则判断队空的条件是()。 A.front=rearB.rear+1=frontC.front=0D.front+1=rear 67.设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为(D). A.top=top+1B.top=top-1C.top->next=topD.top=top->next 68.在一棵完全二叉树中,若编号为j的结点有右孩子,则其编号为()。 A.2jB.2j+1C.2j-1D.└j/2┘ 69.已知一个图的邻接矩阵表示,计算第i个结点的入度的方法是()。 A.求矩阵第i行非零元素之和B.求矩阵第i列非零元素之和 C.求矩阵第i行第i列元素之和 D.求矩阵第i行非零元素之和与第i列非零元素之和的差的绝对值 70.n个顶点的连通图至少有()条边。 A.n-1B.n-2C.nD.n+1 71.有一个有序表(6,9,11,12,14,17,21,33,37),当二分查找值为11的结点时,()次比较后查找成功。 A.2B.3C.4D.5 72.从一个具有n个结点的单链表中查找其值等于x的结点,在查找成功时,需平均比较的结点数是()。 A.nB.n/2C.(n-1)/2D.(n+1)/2 73.设哈希表长m=14,哈希函数H(key)=key%11。 表中已有4个结点: addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。 如用线性探测再散列处理冲突,关键字为49的结点的地址是()。 A.3B.5C.8D.9 74.对于下图所示的AOV网,不能出现的拓扑排序序列为()。 A.12345B.12435C.24135D.21435 75.数据表A中有10000个记录,如果仅要求求出其中最大的10个元素,则采用()排序最节省时间。 A.堆B.希尔C.快速D.直接选择 76.数据的最小单位是()。 A.数据项B.数据类型C.数据元素D.数据变量 77.下面程序段的时间复杂度是()。 for(i=0;i for(j=0;j c[i][j]=0; for(i=0;i for(j=0;j for(k=0;k 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) 78.一维数组有n个数据元素,则读取第i个数据元素的平均时间复杂度为()。 A.O(n)B.O(nlog2n)C.O (1)D.O(n) 79.若某链表(不带头结点)中最常用的操作是在链表的尾部插入或删除元素,则选用下列()的存储方式最节省运算时间。 A.单链表B.循环单链表C.双链表D.循环双链表 80.设一个单链表的头指针为head,且该链表没有头结点,则其判空条件是()。 A.head==NULLB.head->next==NULLC.head->next==head D.head! =NULL 81.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B建插入结点X的操作序列为()。 A.s->next=p->next;p->next=s;B.q->next=s;s->next=p; C.p->next=s->next;s->next=p;D.p->next=s;s->next=q; 82、若如栈序列为A、B、C、D、E,入栈过程中可以出栈,则()不可以是出栈序列。 A.ABCDEB.BCDEAC.EABCDD.EDCBA 83、输入受限的双端队列是指元素只能从队列的一端输入,但可以从队列的两端输出,如图所示。 若有8、1、4、2依次进入输入受限的双端队列,则得不到的输出序列为()。 A.2,8,1,4B.1,4,8,2C.4,2,1,8D.2,1,4,8 84、对稀疏矩阵进行压缩存储时为了()。 A.便于进行矩阵运算B.便于输入和输出 C.节省存储空间D.降低运算的时间复杂度 85、数组A行下标i从1到8,列下标j从1到10,每个元素的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为()。 A.SA+141B.SA+144C.SA+222D.SA+225 86、在一棵完全二叉树中,若编号为j的结点有右孩子,则其编号为()。 A.2jB.2j+1C.2j-1D.└j/2┘ 87、若某无向图有n个顶点,则该无向图的邻接表中有()个表头结点。 A.2nB.nC.n/2D.n(n-1) 88、设用邻接矩阵A表示有向图G的存储结构,则有向图G中顶点i的入度为()。 A.第i行非零元素的个数之和B.第i列非零元素个数之和 C.第i行零元素的个数之和D.第i列零元素个数之和 89、设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分查找关键字90需要比较的关键字个数为()。 A.1B.2C.3D.4 100、下列四种排序中()的空间复杂度最大。 A.快速排序B.冒泡排序C.希尔排序D.堆排序 1011、下面程序段的时间复杂度为()。 for(i=1,s=0;i {t=1; for(j=1;j<=i;j++) t=t*j; s=s+t;} A.O(n)B.O(n2)C.O(n3)D.O(n4) 102、以下数据结构中哪个是非线性结构()。 A.队列B.栈C.线性表D.二叉树 103、设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能的是()。 A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C 104、在一个单链表中,已知q所指结点是p所指结点的前驱,若在q和p之间插入s结点,则执行()。 A.s->next=p->next;p->next=s;B.q->next=s;s->next=p; C.p->next=s->next;s->next=p;D.p->next=s;s->next=p->next; 105、从一个长度为n的顺序表中,删除第i个元素时,需要向前移动()个元素。 A.n-iB.n-i+1C.n-i-1D.i 106、设顺序循环队列Q[0: M-1]的头指针和尾指针F和R,头指针F总是指向队头元素的前一位置,尾指针总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。 A.R-FB.F-RC.(R-F+M)%MD.(F-R+M)%M 107、设指针变量front表示链式队列的队头指针,指针变量rear表示链式队列的队尾指针,指针变量s指向将要入队列的结点X,则入队列的操作序列为()。 A.front->next=s;front=s;B.s->next=rear;rear=s; C.rear->next=s;rear=s;D.s->nxet=front;fronts; 108、在一棵完全二叉树中,若编号为j的结点有右孩子,则其编号为()。 A.2jB.2j+1C.2j-1D.└j/2┘ 109、在数组A中,每个元素的长度为3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[8][5]的起始地址为()。 A.SA+141B.SA+144C.SA+222D.SA+225 110.以下选项中对广义表LS=(1,2,(3,4),(5,6),7)的正确描述是()。 A.该广义表的数据元素都是单元素数据B.该表的长度为6 C.该广义表表头为1,表尾为7D.该广义表表头为1,表尾为(2,(3,4),(5,6),7) 111、树最适合用来表示()。 A.有序数据元素B.无序数据元素 C.元素之间具有分支层次关系的数据D.元素之间无联系的数据 112、n个结点的二叉树,如果采用二叉链表存储,值非空的链域个数为()。 A.n-1B.2n-1C.n+1D.2n+1 113、如有18个元素的有序表存放在一维数组A[19]中,第一个元素存放在A[1]中,先进行二分查找,则查找A[3]的比较序列的下标依次为()。 A.1,2,3B.9,5,2,3C.9,5,3D.9,4,2,3 114、已知10个数据元素(54,28,16,34,73,62,95,60,26,43),按照依次插入结点的方法生成一棵二叉排序树后,则查找值为62的结点所需比较的次数是()。 A.2B.3C.4D.5 115、时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是()。 A.堆排序B.冒泡排序C.希尔排序D.快速排序 二、判断题 1.线性表的长度是线性表所占用的存储空间的大小。 () 2.在顺序表中取出第i个元素所花费的时间与i成正比。 () 3.在栈为空的情况下,不能做出栈操作,否则产生下溢出。 () 4.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习