02331数据结构真题精选.docx
- 文档编号:14259663
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:15
- 大小:88.99KB
02331数据结构真题精选.docx
《02331数据结构真题精选.docx》由会员分享,可在线阅读,更多相关《02331数据结构真题精选.docx(15页珍藏版)》请在冰点文库上搜索。
02331数据结构真题精选
2020年02331数据结构真题精选
[判断题]
1、线性表的逻辑顺序与物理顺序总是一致的。
参考答案:
错
[判断题]
2、线性表的顺序存储表示优于链式存储表示。
参考答案:
错
[判断题]
3、二维数组是其数组元素为线性表的线性表。
参考答案:
对
[判断题]
4、每种数据结构都应具备三种基本运算:
插入、删除和搜索。
参考答案:
错
[判断题]
5、线性表中的每个结点最多只有一个前驱和一个后继。
参考答案:
错
[判断题]
6、线性的数据结构可以顺序存储,也可以链接存储。
非线性的数据结构只能链接存储。
参考答案:
错
[单项选择题]
7、若一个栈的输入序列是1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是()。
A.不确定
B.n-i
C.n-i-1
D.n-i+1
参考答案:
D
[判断题]
8、删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。
参考答案:
错
[单项选择题]
9、一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是()。
A.54321
B.45321
C.43512
D.12345
参考答案:
C
[判断题]
10、直接选择排序是一种不稳定的排序方法。
参考答案:
错
[单项选择题]
11、设计一个判别表达式中左右括号是否配对的算法,采用()数据结构最佳
A.顺序表
B.栈
C.队列
D.链表
参考答案:
B
[判断题]
12、对一个堆按层次遍历,不一定能得到一个有序序列。
参考答案:
对
[单项选择题]
13、一个队列的入队顺序是1,2,3,4,则队列的输出顺序是()。
A.4321
B.1234
C.1432
D.3241
参考答案:
B
[判断题]
14、折半搜索只适用与有序表,包括有序的顺序表和有序的链表。
参考答案:
错
[单项选择题]
15、栈和队列的主要区别在于()。
A.它们的逻辑结构不一样
B.它们的存储结构不一样
C.所包含的运算不一样
D.插入、删除运算的限定不一样
参考答案:
D
[判断题]
16、堆栈在数据中的存储原则是先进先出。
参考答案:
错
[单项选择题]
17、设数组S[n]作为两个栈S1和S2的存储空间,对任何一个栈只有当S[n]全满时才不能进行进栈操作。
为这两个栈分配空间的最佳方案是()。
A.S1的栈底位置为0,S2的栈底位置为n-1
B.S1的栈底位置为0,S2的栈底位置为n/2
C.S1的栈底位置为0,S2的栈底位置为n
D.S1的栈底位置为0,S2的栈底位置为1
参考答案:
A
参考解析:
两栈共享空间首先两个栈是相向增长的,栈底应该分别指向两个栈中的第一个元素的位置,并注意C++中的数组下标是从0开始的。
[单项选择题]
18、当采用分快查找时,数据的组织方式为()。
A.数据分成若干块,每块内数据有序
B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
C.数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块
D.数据分成若干块,每块(除最后一块外)中数据个数需相同
参考答案:
B
[判断题]
19、栈可以作为实现过程调用的一种数据结构。
参考答案:
对
[判断题]
20、在栈满的情况下不能做进栈操作,否则将产生“上溢”。
参考答案:
对
[单项选择题]
21、若用数组S[0..n-1]作为两个栈S1和S2的共同存储结构,对任何一个栈,只有当S全满时才不能作入栈操作。
为这两个栈分配空间的最佳方案是()。
A.S1的栈底位置为0,S2的栈底位置为n-1
B.S1的栈底位置为0,S2的栈底位置为n/2-1
C.S1的栈底位置为1,S2的栈底位置为n
D.S1的栈底位置为1,S2的栈底位置为n/2
参考答案:
A
更多内容请访问《睦霖题库》微信公众号
[判断题]
22、空串与空格串是相同的。
参考答案:
错
[单项选择题]
23、关于杂凑查找说法不正确的有几个()。
(1)采用链地址法解决冲突时,查找一个元素的时间是相同的
(2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是相同的(3)用链地址法解决冲突易引起聚集现象(4)再哈希法不易产生聚集
A.1
B.2
C.3
D.4
参考答案:
B
[填空题]
24设有一个栈,元素进栈的次序为A,B,C,D,E,能否得到如下出栈序列,若能,请写出操作序列,若不能,请说明原因。
⑴C,E,A,B,D⑵C,B,A,D,E
参考答案:
⑴不能,因为在C、E出栈的情况下,A一定在栈中,而且在B的下面,不可能先于B出栈。
⑵可以,设I为进栈操作,O为入栈操作,则其操作序列为IIIOOOIOIO。
[单项选择题]
25、与单向链表相比,使用双向链表存储数据,其优点是可以()。
A.提高检索速度
B.很方便地插入和删除数据
C.节约存储空间
D.很快回收存储空间
参考答案:
B
[填空题]
26举例说明顺序队列的“假溢出”现象。
参考答案:
假设有一个顺序队列,如图3-6所示,队尾指针rear=4,队头指针front=1,如果再有元素入队,就会产生“上溢”,此时的“上溢”又称为“假溢出”,因为队列并不是真的溢出了,存储队列的数组中还有2个
存储单元空闲,其下标分别为0和1。
[单项选择题]
27、与线性表相比,串的插入和删除操作的特点是()。
A.通常以串整体作为操作对象
B.需要更多的辅助空间
C.算法的时间复杂度较高
D.涉及移动的元素更多
参考答案:
A
[填空题]
28在操作序列EnQueue
(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后,队头元素和队尾元素分别是什么?
(EnQueue(k)表示整数k入队,DeQueue表示队头元素出队)。
参考答案:
队头元素为5,队尾元素为9。
其执行过程如图3-8所示。
[单项选择题]
29、对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有()个。
A.1
B.2
C.3
D.4
参考答案:
D
[填空题]
30空串和空格串有何区别?
串中的空格符有何意义?
空串在串处理中有何作用?
参考答案:
不含任何字符的串称为空串,其长度为零。
仅含空格的串称为空格串,它的长度为串中空格符的个数。
串中的空格符可用来分隔一般的字符,便于人们识别和阅读,但计算串长时应包括这些空格符。
空串在串处理中可作为任意串的子串。
[单项选择题]
31、带头结点的单链表first为空的判定条件是()。
A.first==NULL
B.first->1ink==NULL
C.first->link==first
D.first!
=NULL
参考答案:
B
[判断题]
32、队列在数据中的存储原则是后进先出。
参考答案:
错
[填空题]
33设顺序栈S中有2n个元素,从栈顶到栈底的元素依次为a2n,a2n-1,…,a1,要求通过一个循环队列重新排列栈中元素,使得从栈顶到栈底的元素依次为a2n,a2n-2,…,a2,a2n-1,a2n-3,…,a1,请设计算法实现该操作,要求空间复杂度和时间复杂度均为O(n)。
参考答案:
操作步骤为:
①将所有元素出栈并入队;
②依次将队列元素出队,如果是偶数结点,则再入队,如果是奇数结点,则入栈;
③将奇数结点出栈并入队;
④将偶数结点出队并入栈;
⑤将所有元素出栈并入队;
⑥将所有元素出队并入栈即为所求。
[单项选择题]
34、在数据结构的讨论中把数据结构从逻辑上分为()
A.内部结构与外部结构
B.静态结构与动态结构
C.线性结构与非线性结构
D.紧凑结构与非紧凑结构
参考答案:
C
[判断题]
35、哈夫曼树一定是满二叉树。
参考答案:
错
[填空题]
36用顺序存储结构存储串S,编写算法删除S中第i个字符开始的连续j个字符。
参考答案:
先判断串S中要删除的内容是否存在,若存在,则将第i+j-1之后的字符前移j个位置。
算法如下:
[单项选择题]
37、假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?
()
A.k-1次
B.k次
C.k+1次
D.k(k+1)/2次
参考答案:
D
[单项选择题]
38、设有两个串t和p,求p在t中首次出现的位置的运算叫做()。
A.求子串
B.模式匹配
C.串替换
D.串连接
参考答案:
B
[填空题]
39对于采用顺序存储结构的串S,编写一个函数删除其值等于ch的所有字符。
参考答案:
从后向前删除值为ch的所有元素,这样所有移动的元素中没有值为ch的元素,能减少移动元素的次数,提高算法的效率。
算法如下:
[判断题]
40、程序是用计算机语言表述的算法。
参考答案:
对
[单项选择题]
41、在循环队列中用数组A[0..m-1]存放队列元素,其队头和队尾指针分别为front和rear,则当前队列中的元素个数是()
A.(front-rear+1)%m
B.(rear-front+1)%m
C.(front-rear+m)%m
D.(rear-front+m)%m
参考答案:
D
[单项选择题]
42、二叉查找树的查找效率与二叉树的树型有关,在()时其查找效率最低。
A.结点太多
B.完全二叉树
C.呈单枝树
D.结点太复杂
参考答案:
B
[单项选择题]
43、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的出栈序列是()。
A.edcba
B.cdeba
C.debca
D.abcde
参考答案:
C
[判断题]
44、用一组地址连续的存储单元存放的元素一定构成线性表。
参考答案:
对
[单项选择题]
45、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继,则应执行下列哪一个操作()
A.p->link=p->link->link
B.p=p->link;p->link=p->link->link
C.p->link=p->link
D.p=p->link->link
参考答案:
A
[单项选择题]
46、对包含n个元素的哈希表进行查找,平均查找长度为()
A.O(log2n)
B.O(n)
C.O(nlog2n)
D.不直接依赖于n
参考答案:
D
[单项选择题]
47、设循环队列的元素存放在一维数组Q[0‥30]中,队列非空时,front指示队头元素的前一个位置,rear指示队尾元素。
如果队列中元素的个数为11,front的值为25,则rear应指向()元素。
A.Q[4]
B.Q[5]
C.Q[14]
D.Q[15]
参考答案:
B
[单项选择题]
48、若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为()
A.1,2,3
B.9,5,2,3
C.9,5,3
D.9,4,2,3
参考答案:
D
[填空题]
49
(1)设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合中各数据构造一棵二叉排序树。
(2)一组记录的关键字序列为(5,8,6,3,4,7),利用堆排序(堆顶元素是最小元素)的方法建立初始堆。
(要求用完全二叉树表示)
参考答案:
[填空题]
50在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是(),需要内存容量最多的是()
参考答案:
快速;归并
[填空题]
51在函数中对引用形参的修改就是对相应()的修改,对()形参的修改只局限在该函数的内部,不会反映到对应的实参上。
参考答案:
实参;值
[填空题]
52堆排序是不稳定,空间复杂度为()。
在最坏情况下,其时间复杂度也为()
参考答案:
O
(1);O(nlog2n)
[填空题]
53链接存储的特点是通过附加()来表示数据元素之间的逻辑关系
参考答案:
指针域
[填空题]
54设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。
参考答案:
至少有14种。
①全进之后再出情况,只有1种:
4,3,2,1
②进3个之后再出的情况,有3种,3,4,2,13,2,4,13,2,1,4
③进2个之后再出的情况,有5种,2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4
④进1个之后再出的情况,有5种,1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3
[填空题]
55向一个顺序队列插入元素时,需要首先移动(),然后再向所指位置()新插入的元素。
参考答案:
队尾指针;存储
[填空题]
56设如下图所示的二叉树B的存储结构为二叉链表,root为根指针,结点结构为:
(lchild,data,rchild)。
其中lchild,rchild分别为指向左右孩子的指针,data为字符型,root为根指针,试回答下列问题:
对二叉树B,执行下列算法traversal(root),试指出其输出结果;
参考答案:
这是“先根再左再根再右”,比前序遍历多打印各结点一次,输出结果为:
A B C C E E B A D F F D G G
[判断题]
57、结构体是基本类型的。
参考答案:
错
[单项选择题]
58、设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为M1、M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是()
A.M1
B.M1+M2
C.M3
D.M2+M3
参考答案:
D
[判断题]
59、数据结构里,树形结构不是数据的逻辑结构
参考答案:
错
[填空题]
60深度为6(根层次为1)的二叉树至多有()个结点。
参考答案:
26-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 02331 数据结构 精选