数据结构试题和答案

数据结构试题和答案A卷一、填空题（共8小题，每空1分，共计20分）1．栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和在_队头_删除元素。2．一个广义表中的元素分为单元素和表元素两类。3．对于一个长度为n的顺序存储的线形表，在表头插入元素的时间复杂度为__O(n)_______，在表尾插入元素的时间复杂度为____O(1)_______。5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于n+1。6．若一个图的顶点集为{a,b,c,d,e,f},边集为{（a,b）,(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。8．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为（15，02，21，24，26，57，43，66，80，48，73）。9.在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。10.在线形表的散列存储中，处理冲突有开放定址法和链地址法两种方法。11.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有______12______个叶子的结点。12.设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二叉树中叶子结点是_E,F,H___。13．若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为4,带权路径长度为87。二、选择题（共15小题，每题1分，共计15分）1．算法指的是（D）A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列2．如下陈述中正确的是（A）A．串是一种特殊的线性表B．串的长度必须大于零C．串中元素只能是字母D．空串就是空白串3．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）A．3，2，6，1，4，5B．3，4，2，1，6，5C．1，2，5，3，4，6D．5，6，4，2，3，14．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)A．s-next=p；p-next=sB．s-next=p-next；p-next=sC．s-next=p-next；p=sD．p-next=s；s-next=p5．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）A．队列B．栈C．线性表D．有序表6．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图7．深度为5的二叉树其结点数最多为C。A、16；B、30；C、31；D、32。8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（D）A．s=rear；rear=rear-next；deletes；B．rear=rear-next；deleterear；C．rear=rear-next-next；deleterear；D．s=rear-next-next；rear-next-next=s-next；deletes；9．线性表采用链式存储时，结点的存储地址（B）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续10．线性链表不具有的特点是（A）。A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比11.含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(D)A．eB．2eC．n2－eD．n2－2e12.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（D）A．选择排序B．希尔排序C．归并排序D．快速排序13.采用邻接表存储的图的广度优先遍历算法类似于二叉树的D。A．先序遍历；B．中序遍历；C．后序遍历；D．按层遍历。14.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为C。A．1，2，5，4，3；B．1，2，3，4，5；C．1，2，5，3，4；D．1，4，3，2，5。15.假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为B。A．1，3，5，7，9，12；B．1，3，5，9，7，12；C．1，5，3，7，9，12；D．1，5，3，9，12，7。三、判断题（对的打√，错的打×共15小题，每题1分，共计15分）1、在线性结构中，每个结点都有一个直接前驱和一个直接后继。（×）.2、在堆中，以任何结点为根的子树仍然为堆。（√）3、完全二叉树就是满二叉树。（×）4、若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（√）。5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（×）6、在AOE网中，关键路径是唯一的。(×)7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。(√)8、连通分量是无向图中的极小连通子图。（×）9、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（×）10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳）11、完全二叉树的某结点若无左孩子，则它必是叶结点。(√)12、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（×）13、栈和队列逻辑上都是线性表。(√)14、快速排序是一种稳定的排序方法。(×)15、基数分类只适用于以数字为关键字的情形，不适用以字符串为关键字的情形（×）。四、算法填空题：将折半查找的非递归算法中的空白处进行正确填写。（每空2分，共计10分）intSearch_Bin(SSTableST,KeyTypekey){intlow=1；high=_ST.length_________；（1）While(__low=high_____________){(2)mid=_(low+high)/2________________；(3)if(EQ(key,ST.elem[mid].key)returnmid；elseif(LT(key,ST.elem[mid].key))_high=mid-1___________；(4)else__low=mid+1________________；(5)}return0；}//Search_Bin五、综合应用题（每题10分，共计40分）１．已知一个连通图的边集为｛（１，２）３，（１，３）６，（１，４）８，（２，３）４，（２，５）１０，（３，５）１２，（４，５）２｝，若从顶点V1出发,求出此图的深度和广度优先遍历序列，按照普里姆算法求最小生成树并画出，写出依次得到的各条边．1.深度优先:123542分广度优先:123452分普里姆算法依次得到的各边(1,2)3,(2,3)4,(1,4)8,(4,5)22分最小生成树如图所示：4分２．一个待散列存储的数据集合为｛３２，７５，２９，６３，４８，９４，２５，４６，１８，７０，５６｝，散列地址空间为ＨＴ［１３］，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到得到的散列表，求平均查找长度．＾＾＾＾6分32mod13=675mod13=1029mod13=363mod13=1148mod13=994mod13=325mod13=1246mod13=718mod13=570mod13=556mod13=42分平均查找长度为：ASL=(9*1+2*2)/10=13/112分012345678910011129429＾7018＾56＾32＾46＾48＾75＾63＾25＾３．在一个空AVL树内，依次插入关键字(46,15,20,35,28,58,18,50,54)，分别画出46，15，20，35插入完和所有关键字都插入完的AVL树。，并求出查找成功状态下的平均查找长度（10分）平均查找长度：(1×1+2×2+4×3+2×4)/9=25/92分4.欲将无序序列（24,79,13,36,70,96,12,10,36*,49,100,27）中的关键码按升序重新排列，请写出快速排序第一趟排序的结果序列。另外请画出堆排序（小根堆）的初始堆和结束堆。①快速排序第一趟排序的结果序列为：10，12，13，[24]，70，96,36,79,36*,49,100,27（注意要按振荡式逼近算法实现）5分②堆排序的初始堆如下，注意要从排无序堆开始，从最后一个非终端结点开始，自下而上调整,而且要排成小根堆！初始堆序列为：10，24，12，79，49，27，13，36，36*,70,100,96无序堆有序初始堆247913367096121036*4910027102412794927133636*70100966分2分4分结束堆1分B卷一、填空题（共8小题，每空1分，共计20分）1．数据的逻辑结构被分为集合、线性结构、树形结构和图状结构4种。2．链表最后一个结点的指针指向链表的头节点，这样的链表称为_循环_链表；链表的每个结点都有两个指针域，一个指针指向前一结点，另一个指针指向后一结点，这样的链表称为_双向_链表。3．某二叉树结点的中序遍历序列为A，B，C，D，E，F，G，后序遍历序列为B，D，C，A，F，G，E，则该二叉树结点的前序遍历序列为__E;A;C;B;D;G;F___，该二叉树对应的树林包括___2_____棵树。5．按照锦标赛排序的思想，决出8个选手的名次排列，共需要进行___11___场比赛（考虑最坏的情况）。6．Hanoi塔、求一个数的阶乘、二叉树遍历等类似问题的解决一般通过使用_递归_来解决。7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。10121324273636*497079961008．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是__R-next=s______；r=s;r-next=null;。9.在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。10.在线形表的散列存储中，处理冲突有开放定址法和链地址法两种方法。11.在一棵二叉树中，第五层的结点数最多为16个。12.用冒泡法对n个关键码排序，在最好情况下，只需做_____n-1________次比较和_______0_____次移动；在最坏的情况下要做______n(n-1)/2___________次比较。二、选择题（共15小题，每题1分，共计15分）1．在数据结构的讨论中把数据结构从逻辑上分为（C）A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构2．算法分析的两个主要方面是（A）。A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3．一个非空广义表的表头（D）A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B)A．s-next=p；p-next=sB．s-next=p-next；p-next=sC．s-next=p-next；p=sD．p-next=