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

2011年上半年数据结构（C语言）作业二 学号: 姓名：陈石友 学习中心：东莞电子 入学：2010秋季 单选题(每题2分，共20分) 1、串是一_____D____ A. 不少于一个字母的序列 B. 任意个字母的序列 C. 不少于一个字符的序列 D. 有限个字符的序列 2、一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为____A______。 A. 2 B. 1 C. 0 D. 不确定 3、用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是___A_____： A. front = (front + 1) mod N; B. front = (front - 2)mod N; 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，D B. D，C，B，A C. A，C，D，B D. D，A，B，C 9、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 10、设图的顶点数=n, 边数=e，若用邻接表表示图，那么求最短路径的Dijkstra算法的时间复杂度为____B_____。 A.O(n*e) B.O(n2) C.O(n+e) D.O(n3) 填空作图解答题（第1小题6分，其余每题9分，共60分） 假设数组A含有n个元素，函数Random(n)需花费常数时间，sort(A,n)需花费nlog2n步，那么，下面程序段的时间复杂度T(n)=O(n2log2 n) sum=0;for(int i=0; in*n; i++) sum++;for (i=0; in; i++){ for(j=0; jn; j++) A[i]=Random(n); sort(A, n);} 有一组关键码序列{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，95 对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。 假设某森林的先根遍历序列为EBADCFHGIKJ和中根遍历序列为ABCDEFGHIJK。请画出该森林的带双亲的孩子链表示。 如果采用一运算数栈和一运算符栈来计算由键盘输入的中缀表达式1+((2+3)*4+5)*9/(5-(6+7)*8)#的值,这里运算数栈用来存放计算过程中使用或产生的运算数，运算符栈用来存放尚未用于计算的运算符，那么按照算法，请将当运算数栈第一次在栈顶出现13时各栈中存放的数据情况填入下表。 13 5 225 1 运算数栈 - （ / + # 运算符栈 用堆排序算法(“最大堆”排序算法)对关键字{