数据结构(计算机科学与技术).doc

《数据结构(计算机科学与技术).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.《数据结构》（计算机科学与技术本科）第一部分客观题一、单项选择（每题2分，共20分）1、设n为正整数。则下面程序段的时间复杂度为________。k=0;for(i=1;i<=n;i++)for(j=i;j<=n;j++)k++;A.O(1)B.O(n)C.O(nlogn)D.O(n2)2、若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n的顺序表中插入一个元素时需平均移动________个元素。A.nB.(n-1)/2C.n/2D.(n+1)/23、栈的入栈序列是1，2，…，n，输出

2、序列为p1,p2,…pn,若p1=n,则pi为_____。A.iB.n-iC.n-i+1D.不确定4、已知串s="ABCDEFGH’,则s的所有不同子串的个数为________。A.8B.9C.36D.375、下列关于二叉树的说法中，正确的是_______。A.二叉树的度为2B.二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任一个结点的度都为26、图的深度优先遍历算法类似于二叉树的_____。A.先序遍历B.中序遍历C.后序遍历D.层序遍历7..、用链地址法处理冲突构造的散列表

3、中，每个地址单元所链接的同义词表中结点的_____相同。A.关键字B.元素值C.散列地址D.含义8、有序表（1，32，41，45，62，75，77，82，95，100），使用折半查找关键字为95的元素时，需要经过____次比较后才能查找成功。A.2B.3C.4D.59、下列方法中，________是稳定的排序方法。A．堆排序B.希尔排序C.快速排序D.直接插入排序10、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为______。A.O(logn)B.O(nlogn)C.O(n)D.O(n2)

4、二、是非题：（每题1分，共10分）（说明：正确的选“A”,错误选“B”）11、在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。（B）12、在不带头结点的非空单链表中，首元结点的存储位置由头指针指示。（B）13、队列是限定在队尾插入元素，在队头删除元素的线性表。（A）14、空串和空格串是相同的。（A）15、在哈夫曼树中，通常权值较大的结点离根较远。（B）16、若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点，则该图一定是连通图。（A）17、有n个顶点和n-1条边的无向图

5、一定是生成树。（B）18、折半查找时，要求线性表必须是有序的且以顺序结构存储。（A）19、快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。（B）..20、对一个堆按层次遍历，不一定能得到一个有序序列。（A）第二部分主观题一、简答题（每题10分，共50分）1、在快速排序过程中，通常取序列中的第1个记录作为枢轴，以它为“分界线”重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，为改进之，应如何选取枢轴记录？答有序或者基本有序时，每次划分只能完成1个（左

6、右），时间复杂度为O(n^2)如果要改进，选择枢轴可以使用方法：方法1、三者取中：序列第一个、中间位置、最后位置三个值的中间值方法2、随机选取：不再是第一个记录，而是在序列中随机选取2、证明：任何一棵满二叉树中的分支数B满足B=2(n0－1)，其中n0为叶子结点个数。证明：设n0为叶子结点个数，证明：设，n2为叶子结点个数，则由二叉树的性质2可知：n2=n0-1又：满二叉树中只有度为2的结点和叶子结点，所以满二叉树中的结点总数n=n2+n0=2n0-1又：二叉树中的分支数B=n-1所以：B=2n0

7、-1-1=2(n0-1)3、一个图的邻接矩阵G.arcs=..，则该图有多少个顶点？如果是有向图，该图共有多少条弧？如果是无向图，该图共有多少条边?图有3个顶点,如果是有向图,则有4条弧,如果是无向图,则有2条边4、设散列函数H(key)=keyMOD7，用线性探测再散列法解决冲突。对关键字序列{13，28，72，5，16，8，7，11}在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。ASL=(1+1+1+2+5+1+1+4)/8=25、设关键字集合为{

8、10，2，14，8，12，13}，(1)写出用希尔排序方法对序列排序时每一趟结束时的关键字状态。(2)用堆排序方法对其从小到大排序，画出堆排序的初态、建堆和排序过程中重建堆的过程。（1）希尔排序：d1=3:{8213101214}d2=2:{8212101314}d3=1:{2810121314}(2)..堆排序初态:{10，2，14，8，12，13}建堆:{1412138210}输出14之后再建堆：{1312108214}输出13之后再建堆：{1281021314}输出12之后再