搜索
数据结构（C++）作业一一、单选题(每题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=(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、下面程序段的时间复杂度是__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，若用邻接表表示图，那么求最短路径的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)=0(n2log2n)sum=0;for(inti=0;in*n;i++)sum++;for(i=0;in;i++){for(j=0;jn;j++)A[i]=Random(n);sort(A,n);}2.有一组关键码序列{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，953.对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。4.假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为ABCDEFGHIJK。请画出该森林的带双亲的孩子链表示。5.如果采用一运算数栈和一运算符栈来计算由键盘输入的中缀表达式1+((2+3)*4+5)*9/(5-(6+7)*8)#的值,这里运算数栈用来存放计算过程中使用或产生的运算数，运算符栈用来存放尚未用于计算的运算符，那么按照算法，请将当运算数栈第一次在栈顶出现13时各栈中存放的数据情况填入下表。1352251运算数栈6.用堆排序算法(“最大堆”排序算法)对关键字{70，33，79，67，46，24，30，40}进行排序，请先建“最大堆”，然后输出一个堆顶元素,并调整成堆：初始状态{40，33，24，67，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}7.求出下图中顶点A到其余个顶点的最短路径和最短路径长度。-（/+#运算符栈2010401216305028答：AE=10;AF=17;AB=19;AG=25;AC=26;AD=27;AH=28三、程序填空题（每空2分，共20分）1.下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式，以使该算法在发现数据有序时能及时停止。voidBubbleSort(intdatalist[],intsize)//要排序的数据存放在数组datalist[]中，元素个数=size{intexchange,i,j,temp;i=1;exchange=1;while(isize&&_exchange__){_exchange=0;__for(j=size-1;j=i;j--)if(datalist[j-1]datalist[j]){temp=datalist[j-1];datalist[j-1]=datalist[j];datalist[j]=temp;__exchange=1_;}i++;}}2.下面是仅给出了部分操作某线性表类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成相应的操作。typedefnode{intelem;structnode*next;}node,*LinkListPtr;typedefstruct{LinkListPtrhead,tail;LinkListPtrcurr;103ABCDHEFG20789919863127}LinkList;voidInitLinkList(LinkList&L)//初始化线性表{L.head=(node*)malloc(sizeof(node));if(L.head==NULL){coutInsufficientmemoryavailable\n;exit(0);};L.tail=L.head;L.curr=L.head;}voidinsert(LinkList&L,int&item)//在表L的当前位置处插入元素item{if(L.curr==NULL){coutCurrentpositionisnotalegalposition\n;exit(0);};node*newnode=(node*)malloc(sizeof(node));if(newnode==NULL){coutInsufficientmemoryavailable\n;exit(0);};newnode-elem=item;④newnode-next=l.curr-next;⑤l.curr-next=newnode;if(L.tail==L.curr)L.tail=L.curr-next;}voidsetFirst(LinkList&L)//将表的当前位置定位于第1个元素{⑥l.curr=l.hend;}intcurrValue(LinkList&L)//将表的当前位置的元素值返回{if(!isInList(L)){coutCurrentpositionisnotalegalposition\n;exit(0);}return⑦l.curr-next-elem;}boolisEmpty(LinkList&L)//判断线性表是否为空{⑧returnl.hend-next==null;}boolisInList(LinkList&L)//判断curr是否在表中{return(L.curr!=NULL)&&(L.curr-next!=NULL)&&(!isEmpty(L));}boolfind(LinkList&L,constint&eval)//从表的当前位置开始查找元素eval{while(isInList(L))if(⑨l.curr-next-elem)==eval)returnTRUE;else⑩l.curr=l.curr-next;returnFALSE;}