数据结构答案20150617

《数据结构答案20150617》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》复习资料参考答案（红色字体为答案）一、选择题40题1.下面程序段的时间复杂度为____________for(inti=0;i

2、______A.有序表B.分块有序表C.二叉排序树D.线性链表5．对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______A.O（1）B.O（log2n）C.O（n）D.O（nlog2n）6.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。A.98B.99C.50D.487．某二叉树的前序和后序序列正好相反，则该二叉树一定是_____的二叉树A空或者只有一个结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子8．一个序列中有10000个元素，若只想得到其中前10个最小

3、元素，最好采用_______方法A.快速排序B.堆排序C.插入排序D.二路归并排序9．设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是________。A8B3C5D910．图的深度优先遍历类似于二叉树的_______。A.先序遍历B.中序遍历C.后序遍历D.层次遍历11．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行____。A.q一>next=p一>next；p一>next=q；C.q

4、一>next=p一>next；p一>next=q；B.p一>next=q一>next；q=p；D.p一>next=q一>next；q一>next=p；12．在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为________。A.eB.2eC.n2-eD.n2-2e13.二叉树中第5层上的结点个数最多为________A.8B.15C.16D.3214.一个无向连通图的生成树是含有该连通图的全部顶点的_______。A.极小连通子图B.极小子图C.极大连通子图D.极大子图15.堆的形状是一棵_______。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树16.在

5、一棵具有n个结点的二叉树中，所有结点的空子树个数等于______。A.nB.n-1C.n+1D.2*n17．有向图的一个顶点的度为该顶点的______。A.入度B.出度C.入度与出度之和D.(入度＋出度)/218.对线性表进行折半查找时，要求线性表必须______。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且元素按关键字有序排序D.以链接方式存储，且元素按关键字有序排序19．在一个有向图中，所有顶点的度数之和等于所有弧数的______倍。A.3B.2C.1D.1/220．一棵树的广义表表示为a(b(c),d(e(g(h)),f))，则该二叉树中度为1的结点数为

6、______。A.2B.3C.4D.521．在一棵深度为h的完全二叉树中，所含结点个数不大于______。A.2hB.2h+1C.2h-1D.2h-122．对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，为查找元素26，若采用折半查找，需要比较______次才能查找成功。A.3B.4C.5D.623．在对n个元素进行简单选择排序的过程中，需要进行______趟选择和交换。A.n/2B.n-1C.nD.n+124．顶点个数为n的无向图最多有______条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)25.用某种排序方法对关键

7、字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下________：23，21，47，15，27，59，35，20，7221，23，15，27，47，35，20，59，7221，15，23，27，35，20，47，59，72则所采用的排序方法是________A.选择排序B.起泡排序C.归并排序D.快速排序26.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6;r(84)=7，其他地址为空，如用二次探测再