中央电大计算机科学与技术专业数据结构本科试卷7

1中央电大计算机科学与技术专业数据结构（本科）试卷72003年7月已考一、选择题（每小题1分，共10分）1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A.O(n)B.O(n/2)C.O(1)D.O(n2)2.带头结点的单链表first为空的判定条件是：A.first==NULL;B.first-link==NULL;C.first-link==first;D.first!=NULL;3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。A.n-2B.n-1C.nD.n+14.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。A.空间B.副本C.返回地址D.地址5.在一棵树中，（）没有前驱结点。A.分支结点B.叶结点C.树根结点D.空结点6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2B.1C.0D.–17.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。A.20B.18C.25D.228.在有向图中每个顶点的度等于该顶点的（）。A.入度B.出度C.入度与出度之和D.入度与出度之差9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。A.较慢B.较快C.相同二、填空题（每小题1分，共10分）1.二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。22.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_________行的元素。3.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。4.在一个链式栈中，若栈顶指针等于NULL则为________。5.主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的_________地址。6.在一棵树中，______结点没有后继结点。7.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为______。假定根结点的层数为0。8.在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。9.n(n﹥0)个顶点的无向图最多有________条边，最少有________条边。10.在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引为________索引，若对应数据对象表中的若干个表项，则称此索引为________索引。三、判断题（每小题1分，共10分）1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。2.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。4.通常递归的算法简单、易懂、容易编写，而且执行的效率也高。5.一个广义表的表尾总是一个广义表。6.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。38.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。9.直接选择排序是一种稳定的排序方法。10.闭散列法通常比开散列法时间效率更高。四、运算题（每小题8分，共40分）1.设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。intcount(ListNode*Ha,ElemTypex){//Ha为不带头结点的单链表的头指针intn=0;while(Ha-link!=NULL){Ha=Ha-link;if(Ha-data==x)n++;}returnn;}3.已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：4.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63,94时的比较次数。元素值比较次数5.设散列表为HT[17],待插入关键码序列为{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,34565863944Oct,Nov,Dec}，散列函数为H(key)=i2，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。字母ABCDEFGHIJKLM序号12345678910111213字母NOPQRSTUVWXYZ序号14151617181920212223242526(1)试画出相应的散列表；(2)计算等概率下搜索成功的平均搜索长度；五、算法分析题（每小题8分，共24分）1．阅读下列算法，并补充所缺语句voidpurge_linkst(ListNode*&la){//从头指针为la的带表头结点的有序链表中删除所有值相同的多余元素，//并释放被删结点空间。ListNodep,q,t;ElemTypetemp;p=la-link;while(p!=NULL){q=p;temp=p-data;p=p-link;if(p!=NULL&&________)p=p-link;else{while(p!=NULL&&___){t=p;p=p-link;deletet;}q-link=p;}}}2.下面给出一个排序算法，它属于数据表类的成员函数，其中currentSize是数据表实例的当前长度，Vector[]是存放数据表元素的一维数组。templateclassTvoiddataListT::unknown(){Ttemp;inti,j,n=currentSize;5for(i=1;in;i++)if(Vector[i].keyVector[i-1].key){temp=Vector[i];Vector[i]=Vector[i-1];for(j=i-2;j=0;j--)if(temp.keyVector[j].key)Vector[j+1]=Vector[j];elsebreak;Vector[j+1]=temp;}}(1)写出该算法的功能。(2)针对有n个数据对象的待排序的数据表，在最好情况下，算法的排序码比较次数和对象移动次数分别是多少？比较次数：移动次数：3.已知二叉树中的结点类型用BinTreeNode表示，被定义为:structBinTreeNode{ElemTypedata;BinTreeNode*leftChild,*rightChild;};其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的树根结点。BinTreeNode*BinTreeSwopX(BinTreeNode*BT){if(BT==NULL)returnNULL;else{BinTreeNode*pt=newBinTreeNode;pt-data=BT-data;pt-rightChild=BinTreeSwopX(BT-leftChild);pt-lefthild=BinTreeSwopX(BT-rightChild);returnpt;}}六、算法设计题（6分）已知二叉树中的结点类型用BinTreeNode表示，被定义为:structBTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。intBTreeCount(BinTreeNode*BT);67中央电大计算机科学与技术专业数据结构（本科）试题参考答案及评分标准7一、选择题（每小题1分，共10分）1.A2.B3.B4.D5.C6.A7.C8.C9.C10.B二、填空题（每小题1分，共10分）1.22.(K+1)/33.指针4.空栈5.返回6.叶子7.38.19.n(n-1)/2,010.稠密，稀疏第9和10小题中有一空错则1分全扣。三、判断题（每小题1分，共10分）1.对2.错3.对4.错5.对6.对7.错8.错9.错10.错四、运算题（每小题8分，共40分）1.根据题意，矩阵A中当元素下标I与J满足I≥J时，任意元素A[I][J]在一维数组B中的存放位置为I*(I+1)/2+J，因此，A[8][5]在数组B中位置为8*(8+1)/2+5=41。2.while(Ha!=NULL){if(Ha-data==x)n++;Ha=Ha-link;}3.后序序列：C,B,F,E,I,J,H,G,D,A4.判断结果元素值比较次数//对1个给1分，全对给8分5.H(Jan)=102=5，成功.H(Feb)=62=3，成功.H(Mar)=132=6，成功.H(Apr)=12=0，成功.H(May)=132=6，=7，成功，H(June)=102=5，=6，=7，=8，成功.H(July)=102=5，=6，=7，=8，=9，成功.H(Aug)=12=0，=1，成功.H(Sep)=192=9，=10，成功.H(Oct)=152=7，=8，=9，=10，=11，成功.H(Nov)=142=7，=8，=9，=10，=11，=12，成功.34565863940213448H(Dec)=42=2，成功.(1)相应的散列表(6分)，错一个存储位置扣1分，最多扣6分。012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6)(2)搜索成功的平均搜索长度为1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12（2分）五、算法分析题（每小题8分，共24分）1.p-datatemp//4分p-data=temp//4分2.算法功能及执行效率(1)该算法的功能是直接插入排序。(4分)(2)n-10（2分2分）3.算法功能：生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树交换的结果。六、6分，请根据编程情况酌情给分。intBTreeCount(BinTreeNode*BT){if(BT==NULL)return0;//2分elsereturnBTreeCount(BT-leftChild)+BTreeCount(BT-rightChild)+1;//4分}