数据结构Word文件下载.docx
- 文档编号:5860261
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:15
- 大小:22.45KB
数据结构Word文件下载.docx
《数据结构Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构Word文件下载.docx(15页珍藏版)》请在冰点文库上搜索。
5、在有n个子叶节点的哈夫曼树中,其节点总数为()
A.不确定B.2n-1C.2n+1D.2n
【解题关键点】哈夫曼树是一种特殊的满二叉树,因此若有N个叶子节点,则其总节点数也是2N-1。
6、某数列有1000个各不相同的单元,由低到高按序排列,现要对该数列进行二分法检索,在最坏的情况下,需要检视()个单元()
A.1000B.10C.100D.500
【解题关键点】二分法查找元素其基本思想:
将数据元素对半分,将待查找的数与中间位置数相比较,若大于该中间位置的数,则在数据段的后半段检索,否则在前半段检索。
重复上述步骤,最坏的情况下需要查看10个单元。
7、已知数组A中,每个元素A[I,J]在存储时要占3个字节,设I从1变化到8,J从1变化到10,分配内存时是从地址SA开始连续按行存储分配的。
试问:
A[5,8]的起始地址为()A.SA+141B.SA+180C.SA+222D.SA+225
【解题关键点】数组地址计算问题,只要掌握数据是顺序存储并占用连续的存储空间。
注意问题的要求按行存储还是按列存储,就能计算任意单元的起始地址。
如题:
按行分配空间,则A[5,8]前4行共40个单元,第5行开始A[5,1]至A[5,7]共7个单元,即A[5,8]前有47个单元,其地址是SA+(47*3)=SA+141
【答案】A
8、线性表若采用链表存储结构,要求内存中可用存储单元地址()
A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可
【解题关键点】线性表中的链接存储的特点:
是将零散的存储空间通过指针域连接起来,因此链接存储单元一般至少有两个域:
数据域和指针域,通过指针将结点链接后生成链接表。
所以存储单元地址可以连续也可以不连续。
9、下列叙述中,正确的是()
A.线性表的线性存储结构优于链表存储结构B.队列的操作方式是先进后出
C.栈的操作方式是先进先出D.二维数组是指它的每个数据元素为一个线性表的线性表
【解题关键点】二维数组本身是一个M行N列的矩阵,每行、每列都可以看做一个线性表。
而其中其个元素可以看成一个列向量的线性表,也可以看成一个行向量的线性表。
所以二维数组每个数据元素可以看作一个线性表的线性表。
10、电线上停着两种鸟(A,B),可以看出两只相邻的鸟就将电线分为了一个线段。
这些线段可公为两类:
一类是两端的小鸟相同;
另一类是两端的小鸟不相同。
已知:
电线上两个顶点上正好停着相同的小鸟,试问两端为不同小鸟的线段数目一定是()
A.奇数B.偶数C.可奇可偶D.数目固定
【解题关键点】由于线段两端相同,故此,增加一只不同鸟,产生两条两端不同小鸟的线段,增加两只不同鸟,可以产生两条或四条两端不同小鸟的线段。
增加N只不同小鸟,由于线段两端是相同鸟,通过对称排列,必定是偶数个两端为不同小鸟的线段。
11、在列车转辙网络中,有四个车皮编号为1,2,3,4,并按此顺序送入栈中进行调度,这些车皮取出的顺序是()
A.4123B.3241C.3412D.4312
【解题关键点】列车转辙网络是一个栈,数据进入栈中可以随时出栈,但其必须遵循后进先出的规则。
故此,A中既然4最先出栈则,1不可能第二个出栈;
C中既然3、4在前面出栈,1就不可能在2前出栈;
D中原因同上。
12、从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端,这种排序方法称为()
A.插入排序B.归并排序C.选择排序D.快速排序
【解题关键点】选择排序的基本思想:
每次从待排序的记录中选择出关键码值最小(或最大)的记录,顺序放在已排序的记录序列的一端,直到全部排完。
【答案】C
13、在计算递归函数时,如不使用递归过程,则一般情况下必须借助于()数据结构()
A.栈B.树C.双向队列D.广义表
【解题关键点】栈是使用最广泛的数据结构之一,表达式求值、递归过程实现都是栈应用的典型例子。
14、使用双向链表存放数据的优点是()
A.提高检索速度B.很方便地插入和删除数据
C.节约存储空间D.很快回收存储空间
【解题关键点】链表的一个重要特点是插入、删除运算灵活,不需移动结点,只要改变结点中指针域的值就可以了。
15、对一个满二叉树,m个树叶,l分枝结点,n个结点,则()
A.n=l+mB.l+m=2nC.m=l-1D.n=2l-1
【解题关键点】树叶:
度为0的结点;
分枝结点:
度不为0的结点;
结点:
树中的每一个元素都叫结点。
所以无论是什么二叉树,树叶+分枝结点=结点。
16、一维数组与线性表的区别是()
A.前者长度固定,后者长度可变B.后者长度固定,前者长度可变
C.两者长度均固定D.两者长度均可变
【解题关键点】一维数组长度固定,在定义时都必须指出其下标的范围。
线性表是一个相当灵活的数据结构,它的长度可以根据需要增加或缩短。
17、用某种排序方法对线性表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.快速排序
18、具有12个记录的序列,采用冒泡排序最少的比较次数是()
A.1B.144C.11D.66
【解题关键点】冒泡排序的基本思想:
对待排序的记录的关键字进行两两比较,发现两个记录是反序的,则进行交换,直到无反序排序的记录为止。
最理想的情况就是原来已经没有反序排序的记录,那么只需要比较n-1次就可以完成了。
19、下面关于二叉树的叙述正确的是()
A.一棵二叉树中叶子结点的个数等于度为2的结点个数加1
B.一棵二又树中的结点个数大于0
C.二叉树中任何一个结点要么是叶,要么恰有两个子女
D.二叉树中,任何一个结点的左子树和右子树上的结点个数一定相等
【解题关键点】二叉树的性质:
对于任意一棵二叉树,如果其端结点数为N,而其度为2的结点总数为M时,有N=M+1。
20、先序序列和中序序列相同的二叉树为空树或()
A.任一结点均无右孩子的非空二叉树B.仅有两个结点的二叉树
C.任一结点均无左孩子的非空二叉树D.不存在这样的二叉树
【解题关键点】二叉树的先序序列顺序为:
根左右;
中序序列顺序为:
左根右;
要其两个序列的结果相同,必须是缺少了左子树,即大家都变成了根右的顺序了。
21、设有三个元素A、B、C顺序进栈,在进栈过程中可以出栈,出栈次序错误的排列是()
A.ABCB.BCAC.CABD.CBA
【解题关键点】栈是一个后进先出的线性表,C:
如果C先出栈,则必定是A、B均在栈中,而且B比A后进栈,所以出栈必须是B比A先出。
22、下面四种内排序方法中,要求内存容量最大的是()
A.插入排序B.选择排序C.快速排序D.归并排序
【解题关键点】几种排序需要内存容量的比较:
插入排序:
1;
选择排序:
快速排序:
以2为底n的对数;
归并排序:
n。
所以最大的是归并排序。
23、设有序列F:
(49,38,65,97,76,13,27,50),使用快速排序法,其趟数为()
A.3B.2C.1D.4
【解题关键点】快速排序:
第一趟:
{27,38,13},49,{76,96,65,50};
第二趟:
13,27,38,49,{76,96,65,50}(对左子表排序);
第三趟:
13,27,,38,49,50,65,76,96(对右子表排序)。
24、给出一组整型数28、10、37、63、35、30、23,请用二叉树对它进行排序。
为此,首先要生成一棵二叉树,规则是把第一数放在根处,接着凡比它小的数放在左子树,比它大的数放在右子树,直到把所有的数均安排好。
然后对此二叉树进行(),得到的就是按照升序排列好的序列。
A.前序遍历B.中序遍历C.后序遍历D.横向遍历
【解题关键点】利用二叉树对一组数进行排序,先生成一棵二叉排序树,然后进行中序遍历,所得的结果就是按升序排列的数据。
25、用某种排序方法对线性表(84,47,25,15,21)进行排序时,结点序列的变化如下:
(1)84,47,25,15,21;
(2)15,47,25,84,21;
(3)15,21,25,84,47;
(4)15,21,25,47,84.那么,所采用的排序方法是()
A.选择排序B.冒泡排序C.插入排序D.快速排序
这是一个典型的选择排序。
26、设二叉树根结点的层次为0,一棵高度为b的满二叉树中结点的个数是()
A.2^bB.2^(b-1)C.2^b-1D.2^(b+1)-1
【解题关键点】在二叉树中,第I层的结点总数不超过2^(I-1);
而深度为K的二叉树的结点总数不超过2^k-1。
故满二叉树的结点总数为:
2^k-1(k为二叉树的深度)
27、深度为5的二叉树至多有()个结点
A.16B.32C.31D.10
【解题关键点】满二叉树的结点总数为:
2^k-1(k为二叉树的深度)。
由此得:
2^5-1=31。
28、下面关于线性表的描述,错误的是()
A.栈是线性表的一种
B.任给一个索引I(1<
=I<
=表中元素个数),就能在线性表中唯一确定一个元素
C.线性表的任一元素都有前驱和后继
D.线性表是一个线性序列
【解题关键点】线性表的第一个元素没有前趋元素,线性表的最后一个元素没有后继元素。
29、带权路径长度最小的二叉树是()
A.顺序二叉树B.二叉排序树C.判定树D.哈夫曼树
【解题关键点】哈夫曼树,又称最优树,是一类带权路径最短的树。
30、有12个结点的平衡二叉树的最大深度是()
A.4B.5C.6D.3
【解题关键点】平衡二叉树,又称AVL树。
它或者是一棵空树,或具有下列性质的二叉树:
(1)左子树和右子树都是平衡二叉书树;
(2)左子树和右子树的深度之差的绝对值不超过1。
由此,12个结点的平衡二叉树的深度最多可以为5层。
31、若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24从小到大进行排序,共要进行()次比较。
A.33B.45C.70D.91
【解题关键点】冒泡排序:
对待排序的记录进行逐个比较,如发现两个记录是反序的,则进行交换,直到无反序排列的记录为止,即当一次比较后没有进行交换则排序完成。
由此可得,当第七趟排序时就没有出现交换了,所以只比较了70次就可以完成排序。
32、设n,m为某二叉树上的两个结点,在中序遍历时,n在m前的条件是()
A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙
【解题关键点】中序遍历的顺序是左根右;
故此要n在m前,必须n在m的左方。
33、下列四种排序方法,如果被排序的序列中诸元素恰好已经按要求(由小到大或由大到小排序,就元素的比较次数和移动次数而言,哪种方法最少?
()
A.冒泡排序B.直接选择排序C.直接插入排序D.归并排序
【解题关键点】直接插入排序的比较的次数为n-1次,交换次数为0。
34、如果某二叉树的前序为STUWV,中序为UWTVS,那么该二叉树的后序是()
A.WUVTSB.UWVTSC.VWUTSD.WUTSV
【解题关键点】由于已知二叉树的前序与中序后,可画出二叉树,并得出后序。
由于前序为STUWV,所以根必然是S,由于中序是UWTVS,故此此二叉树没有右子树。
左子树前序为TUWV可得左子树根为T,中序为UWTV可得左子树根T有一右子根V,左子树T的左子树根为U,U有一右子树W。
故此后序为A。
35、按照二叉树的定义,具有3个结点的二叉树有()
A.3种B.4种C.5种D.6种
【解题关键点】具有3个结点的的二叉树有5种。
分别是:
左孙、左子、根;
右孙、左子根;
左子、根、右子;
根、右子、左孙;
根、右子、右孙。
36、对以下关键字序列用快速排序法进行排序,速度最慢的情况是()
A.{19,23,3,15,7,21,8}B.{23,21,28,15,19,3,7}
C.{19,7,15,28,23,21,3}D.{3,7,15,19,21,23,28}
【解题关键点】快速排序适用了原数列没有序的情况,如果原数大部分成序的话,速度越慢。
最慢的情况就是所有数据已经成序。
37、数组A中,每个元素A[I,j]的长度为3个字节,行下标I为1到8,列下标j从1到10。
从首地址SA开始连续存放在存储器中,存放该数组至少需要的单元数是()
A.80B.100C.240D.270
【解题关键点】该数组一共有80个元素,一个元素需要3个字节,故存放该数组至少需要240个字节。
38、树的基本遍历策略可分为先根遍历和后根遍历;
二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。
这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。
正确的结论是()
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C.树的后根遍历序列与其对应的二叉树的先序遍历序列相同
D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同
【解题关键点】因为把树转化为二叉树时,把所有原来同层的子树都变成了原来的左子树的右子树了。
故此,树的先根遍历序列与其对应的二叉树的先序遍历序列相同。
39、在数据结构中,从逻辑上可以把数据结构分成()
A.动态结构和静态结构B.线性结构和非线性结构
C.内部结构和外部结构D.紧凑结构和非紧凑结构
【解题关键点】在数据结构中,从逻辑上把数据结构分成线性结构和非线性结构。
40、如果T2是由有序树T转换而来的二叉树,那么T中结点的后序就是T2中结点的()
A.前序B.中序C.后序D.层次序
故此,有序树的后序就是其转化成得的二叉树的中序。
41、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是()
A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca
【解题关键点】通过二叉树的先序与中序可以写出二叉树,并由此可以得出后序为gdbehfca。
42、从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端,这种排序方法称为()A.插入排序B.选择排序C.归并排序D.快速排序
【解题关键点】选择排序的基本思想是:
每次从待排序的记录中选择出最小(或最大)的记录,顺序放在已排好的记录序列的最后。
43、快速排序方法在()情况下最不利于发挥其长处
A.被排序的数据量太大B.被排序数据中含有多个相同值
C.被排序数据已基本有序D.被排序数据数目为奇
【解题关键点】快速排序在被排序数据中已基本有序的情况下最不利于发挥其长处。
44、下面关于数据结构的叙述中,正确的叙述是()
A.顺序存储方式的优点是存储密度大,且插入、删除运算效率高
B.链表中的每一个结点都包含一个指针
C.包含n个结点的二叉排序树的最大检索长度为log\-2n
D.将一棵树转换为二又树后,根结点没有右子树
【解题关键点】A:
顺序存储插入、删除运算效率低;
B:
链表中的最后一个结点的指针域为空。
C:
包含n个结点的二叉排序树的平均检索长度为(log2n)2为底n的对数。
THANKS!
!
致力为企业和个人提供合同协议,策划案计划书,学习课件等等
打造全网一站式需求
欢迎您的下载,资料仅供参考
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构