数据结构试题库

、选择题A)head—>next="null”B)head=nullC)head!=nullD)head—>next=null2、一个栈的入栈序列是a，b，1，5,6,则栈的不可能的输出序列是。A)6，5，1，b，aB)6，a，b，5，1C)1，b，a，5，6D)5，1，b，a，63、在线索化二叉树中，T指针所指结点没有右子树的充要条件是。A)T—>RLchild=nullB)T一>Ltag=1C)T一>Rtag=0D)T一>Rtag=14、二叉树的先序遍历结点访问顺序是gbcaef，中序遍历结点访问顺序是cbagfe，则后序遍历结点访问顺序是0A)cabfegB)cbagfeC)bacfegD)cabgef5、请指出在顺序表｛2,5，7，10，14，15，18，23，35，41，52｝中用折半查找关键字12需做多少次关键字比较0A)2B)3C)4D)56、设有字符序列｛Q，H，C，Y，P，A，M，S，R，D，F，X｝，新序列｛F，H，C，D，P，A，M，Q，R，S，Y，乂｝是下列哪个排序算法一趟扫描的结果。A)冒泡排序B)初始步长为4的希尔排序C)二路归并排序D)从第一个兀素为支点的快速排序带头结点的单链表head为空的判定条件是一1、7、用顺序查找法对具有n个结点的线性表查找一个结点所需的平均比较次数为O(n2)B)O(n)C)O(log2n)D)O(nlog2n)8、下面关于图的存储的叙述中，哪一个是正确的?2用邻接矩阵法存储图，占用的存储空间只与图中结点个数有关，而与边无关。用邻接矩阵法存储图，占用的存储空间只与图中边数有关，而与结点个数无关。用邻接表法存储图，占用的存储空间只与图中结点个数有关，而与边无关。用邻接表法存储图，占用的存储空间只与图中边数有关，而与结点个数无关。9、下面的四棵二叉树中，是不平衡二叉树。B)12｝，下列二叉树哪个是该整数集合对应10、给定一个整数集合｛3，5，6，9,的赫夫曼树。B)12｝，下列二叉树哪个是该整数集合对应10、给定一个整数集合｛3，5，6，9,的赫夫曼树。TOC\o"1-5"\h\z11、输入序列为(A,B,C,D),不可能得到的输出序列有；A、(A,B,C,D)B、(D,C,B,A)C、(A,C,D,B)D、(C,A,B,D)12、直接插入排序在最好情况下的时间复杂度为。A、O(logn)B、O(n)C、O(n*logn)D、O(n2)13、判断下列叙述中哪个不正确A、将一棵树转换成二叉树后，根结点没有左子树；B、用树的前序遍历和中序遍历可以导出树的后序遍历；C、一棵深度为K且有2k-1个结点的二叉树称为满二叉树D、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近14、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动()个元素。A、8B、63.5C、63D、715、设有一个二维数组A[m][n],假设A[0][0]存放位置在644直，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在()位置，(10)'表明用10进数表示。A.692⑴)B.626⑩C.709⑩D.724⑩TOC\o"1-5"\h\z16、一个有序顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为()。A.128B.127C.126D.25517、含5个结点(元素值均不相同)的二叉排序树有()种。A.54B.42C.36D.6518、在分析折半搜索的性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为L，那么搜索失败到达失败结点时所做的数据比较次数是()。A、li+1B、L+2'C、li-1D、li19、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5,则散列存储空间应能够至少容纳()个表项。(设搜索成功的平均搜索长度为Snl=(1+1/(1-a)/2,其中a为装填因子)A、400B、526C、624D、67620、n个顶点的连通图至少有()条边。A、n-1B、nC、n+1D、0

21、一个二叉树按顺序方式存储在一个一维数组中，如图ABCDEFGHIJTOC\o"1-5"\h\z01234567891011121314则结点E在二叉树的第（）层。A、1B、2C、3D、422、高度为h的满二叉树（仅含根结点的二叉树高度为零）的结点最少是多少。A、h+1B、2h+1C、2h+"1D、2h23、二维数组A的成员是6个字符组成的串。行下标I从0到8,列下标J的范围从1到则存放A至少需要个字节；A的第8列和第5行共占个字节，若A按行优先方式存储，元素A[8,5]的起始地址与当A按列优先方式存储时的元素的起始地址一致。A、90B、180C、240D、540E、108F、114G、54H、60I、A[8,5]J、A[3,10]K、A[5,8]24、如图所示二叉树的中序遍历序列为A、abcdgefB、dfebagcC、dbaefcgD、defbagc25、在一个单链表中，若删除P所指结点的后续结点，则执行A、p->next=p->next->next;B、p->next=p->next;C、p=p->next->next;D、p=p->next;p->next=p->next->next;26、按二叉树的定义，具有3个结点的二叉树有种A、3B、4C、5D、627、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是A、acbedB、decabC、deabcD、cedba28、二叉树的先序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则后序遍历的结点访问的顺序是。A、bdgcefhaB、gdbecfC、bdgaechfD、gdbehfca29、顺序查找法适用于存贮结构为的线性表。A、散列存贮B、压缩存贮C、顺序存贮或链式存贮D、索引存贮30、折半查找法适用于存贮结构为的，且按关键字排好序的线性表。A、顺序存贮B、链式存贮C、顺序存贮或链式存贮D、索引存贮31、二叉排序树的查找和折半查找时间性能相同，这种说法A、正确B、不正确32、与其它查找方法相比，哈希表查找法的特点是。通过关键字比较进行查找通过关键字计算记录存贮地址进行查找通过关键字计算存贮地址，并进行一定的比较进行查找通过计算地址进行查找33、长度为12的有序表，Apr,Auy,Dec,Feb,Jan,Jul,Jun,Mar,May,NOv,Oct,Sep,按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为。A、35/12B、37/12C、39/12D、43/12TOC\o"1-5"\h\z34、若用冒泡排序法对序列18,14,6,27,8,12,16,52,10,26,47,29,41,24,从小到大进行排序，共需进行次比较。A、33B、45C、70D、9135、用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时，结点序列的变化情况如下：(1)258421471527683520(2)201521254727683584(3)152021252735476884(4)152021252735476884那么所采用的排序方法是。A、选择排序B、冒泡排序C、归并排序D、快速排序36、快速排序在最坏情况下的时间复杂度为。A、O(nlog2n)B、O(n2)C、O(n3)D、O(n)37、具有12个记录的序列，采用冒泡排序最少的比较次数。A、1B、144C、11D、638、在一个具有n个结点的有序单链表中插入一个新结点，并仍然有序的时间复杂度是A、O(1)B、O(n)C、O(n2)D、O(nlog2n)39、双向链表的结构如下：|…|2LlinkdataRlink其中：Llink是指向前驱的指针域；dada是放数据元素的数据域；Rlink是指向继的指针域。下面给出的算法段是要把一个新的结点Q作为非空双向链表P的前驱，插入到此双向链表中。能正确完成插入要求的算法段是：―A、Q->Llink=P->Llink;Q->Rlink=P;B、P->Llink=Q;Q->Rlink=P;C、P->Llink=Q;P->Llink->Rlink=Q;Q->Llink=P->Llink;P->Llink->Rlink=Q;Q->Llink=P->Llink;D、Q->Llink=P->Llink;Q->Rlink=P;P->Llink->Rlink=Q;P->Llink=Q;P->Llink->Rlink=Q;Q->Rlink=P;P->Llink=Q;

40、对希尔排序来说，给定的一组排序数值为：49、38、65、97、76、13、27、50、55、04；则第二趟排序后的结果为A、04，13，27，49，50，38，55，65，76，97；d1=3,d2=3B、04，13，27，38，50，49，55，65，76，97；d1=2,d2=1C、13，04，49，38，27，50，55，65，97，76；d1=5,d2=3D、13，27，50，55，04，49，38，65，97，76；d1=5,d2=3二、填空题1、算法具有五个重要特性，即、、、、。2、深度为K的完全二叉树至少有个结点，若按自下而上，从左到右次序给结点编号（从1开始），则编号为j的结点的双亲结点为，左孩子结点（非空）为3、已知一有向图如下:3、已知一有向图如下:试写出按有向图的深度优先遍历算法从顶点V1出发所得到的顶点序列广度优先序列。4、已知图G4、已知图G如下，求出该图的拓扑排序序列8、9、5、在树结构里，有且仅有一个结点没有前驱，称为，非根结点有且仅有一个8、9、，且存在一条从根到该结点的。6、一组关键字K={22，16，15，24，32，64，35}构造一棵二叉排序树，这棵二叉排序树的最终形态为。（注：以第一个关键字22为根）7、已知无向图G的顶点数为n，边数为e，其邻接表中的表结点数与表头结点数之和为n个顶点的连通图至少有条边。已知图G如下：其从顶点V1出发产生的深度优先生成树为，其从顶点V1出发的广度优先生成树为。10、一组记录的排序码是(46,79,56,48,30,84)，则利用堆排序的方法建立初始堆(大顶堆)为11、已知AOV网如下，按关键路径算法找出其关键路径为11、已知AOV网如下，按关键路径算法找出其关键路径为12、评价数据结构的两条基本标准是和13、已知图如下：(1)该有向图的顺序存储结构邻接矩阵为(2)该有向图的链式存储结构邻接表为(2)该有向图的链式存储结构邻接表为14、给出4个点的权值，10,7,5,3,构造哈夫曼树。15、假定用于通讯的电文仅由8个字母C1、C2、C3、C4、C5、C6、C7、C8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计哈夫曼编码，画出编码树，写出编码结果。16、顺序输入序列25,30,8,5,1,27,24,26,10,21,9,28,7,13,15。假定每个结点的查找概率相同，若用顺序存贮方式组织该数列，则查找一个数成功的平均比较次数为,若按二叉树排序树结构组织该数列，则查找一个数成功的平均比较次数为。17、折半查找法仅适用于这样的表，表中的记录必须，其存贮结构必须是18、已知关键字序列{51,28,86,70,90,7,30}用冒泡法对该序列进行排序，前三趟的结果依次是。用二路归并法对该序列进行排序，前三趟的结果依次。19、已知一个有序表为12,18,24,35,47,50,62,83,90,115,134,用二分查找法查找值47元素，需比次。20、将关键字序列25,73,191,325,138中各关键字依次插入到下面的二叉排序树中，以构成一棵新的二叉排序树，请画出二叉排序树的最后结果。

参考答案：一、选择题:1、D2、B3、D4、A5、C6、D7、B8、A9、A10、D11、D12、B13、A14、B15、C16、A17、B18、D19、A20、A21、C22、C23、(1)D(2)E(3)J24、B25、A26、C27、D28、D29、C30、A31、B32、C33、B34、C35、D36、B37、C38、C39、D40、C二、填空题1、算法具有五个重要特性，即_有穷性_、确定性、可行性、输入、输出。2、深度为K的完全二叉树至少有2K-1一个结点，若按自下而上，从左到右次序给结点编号（从1开始），则编号为j的结点的双亲结点为J/2，左孩子结点（非空）为2J。试写出按有向图的深度优先遍历算法从顶点V1出发所得到的顶点序列VI、V2、V3、V5、V4，广度优先序列VI、V3、V4、V5。4、已知图G如下，求出该图的拓扑排序序列VI、V5、V2、V4、V3、V6。5、在树结构里，有且仅有一个结点没有前驱，称为根，非根结点有且仅有一个双亲结点—，且存在一条从根到该结点的路径。6、一组关键字K={22，16，15，24，32，64，35}构造一棵二叉排序树，这棵二叉排序树的最终形态为。（注：以第一个关键字22为根）7、8、9、已知无向图G的顶点数为n,边数为e,其邻接表中的表结点数与表头结点数之和为n+2e条边。深度优先生成树:n个顶点的连通图至少有__虹1已知图G如下：其从顶点V1出发产生的深度优先生成树为，其从顶点V1出发的广度优先生成树为。79，56，48，30，84），则利用堆排序的方法建立初始堆广度优先生成树:10、一组记录的排序码是（46,13、已知图如下:(2)该有向图的链式存储结构邻接表为13、已知图如下:(2)该有向图的链式存储结构邻接表为10、已知AOV网如下，按关键路径算法找出其关咐径为QXSXS>Q,Ve(v1)=_0VL(v8)=_37Ve(v6)=37设＜V6,V8＞弧称为活动a,~、e(a)=___35/'、、、一.V8＞L(a)=J5—12、评价数据结构的两条基本标准是一时间复杂度和空间复杂度(1)该有向图的顺序存储结构邻接矩阵为TOC\o"1-5"\h\z广0110'00010001,0000.14、给出4个点的权值，10,7,5,3,构造哈夫曼树15、假定用于通讯的电文仅由8个字母C1、电文中出现的频率分别为5,25,3,6编码，画出编码树，写出编码