数据结构(C语言)第二次作业.doc

《数据结构(C语言)第二次作业.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2011年上半年数据结构（C语言）作业二学号:姓名：陈石友学习中心：东莞电子入学：2010秋季一、单选题(每题2分，共20分)1、串是一_____D____A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列2、一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为____A______。A.2B.1C.0D.不确定3、用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是___A_____：A.front=(front+1)modN;B.front=(

2、front-2)modN;C.front=front+1;D.front=front–2;4、已知数据表中的每个元素距其最终位置不远，则采用__B_____排序算法最省时间。A.堆排序B.插入排序C.快速排序D.直接选择排序5、在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为___B______。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)6、在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是___D___。A.O(1)B.O(n2)C.O(nlogn)D.O(n)7、下

3、面程序段的时间复杂度是___D______。i=1;while(i<=n)i=i*2;A.O(n)B.O(n2)C.O(2n)D.O(log2n)8、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是___D___。A.A，B，C，DB.D，C，B，AC.A，C，D，BD.D，A，B，C9、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为C。A.nB.n/2C.(n+1)/2D.(n-1)/210、设图的顶点数=n,边数=e，若用邻接表表示图，那么

4、求最短路径的Dijkstra算法的时间复杂度为____B_____。A.O(n*e)B.O(n2)C.O(n+e)D.O(n3)二、填空作图解答题（第1小题6分，其余每题9分，共60分）1.假设数组A含有n个元素，函数Random(n)需花费常数时间，sort(A,n)需花费nlog2n步，那么，下面程序段的时间复杂度T(n)=O(n2log2n)sum=0;for(inti=0;i

5、{40，20，60，15，50，45，95，10，75}，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。答案：第1趟：40，20，10，15，50，45，95，60，75第2趟：15，20，10，40，50，45，95，60，75第3趟：10，15，20，40，45，50，60，75，952.对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。20104012163050283.假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为ABCDEFGHIJK。请画

6、出该森林的带双亲的孩子链表示。4.如果采用一运算数栈和一运算符栈来计算由键盘输入的中缀表达式1+((2+3)*4+5)*9/(5-(6+7)*8)#的值,这里运算数栈用来存放计算过程中使用或产生的运算数，运算符栈用来存放尚未用于计算的运算符，那么按照算法，请将当运算数栈第一次在栈顶出现13时各栈中存放的数据情况填入下表。1352251运算数栈-（/+#运算符栈1.用堆排序算法(“最大堆”排序算法)对关键字{70，33，79，67，46，24，30，40}进行排序，请先建“最大堆”，然后输出一个堆顶元素,并调整成堆：初始状态{40，33，24，67，

7、46，79，30，70}所建大顶堆{79，70，40，67，46，24，30，33}或{79,70,67,46,40,24,30,33}输出一个堆顶元素后调整的结果{70,67,40,33,46,24,30,79}或{70,46,67,33,40,24,30,79}2.求出下图中顶点A到其余个顶点的最短路径和最短路径长度。103ABCDHEFG20789919863127AE=10;AF=17;AB=19;AG=25;AC=26;AD=27;AH=28一、程序填空题（每空2分，共20分）1.下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语

8、句或表达式，以使该算法在发现数据有序时能及时停止。voidBubbleSort(intdatalist[],intsize