计算机科学与技术专业数据结构试题 2002年7月.docx
2001-2002学年度第二学期“开放本科”期末考试计算机科学与技术专业数据结构试题2002年7月一、单选题（每小题2分，共20分）1、向顺序栈中压入新元素时，应当（A ）oA.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针C.先后次序无关紧要D.同时进行2、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的 计算时间为（B ）oA. O （nlog2e）C. O（ne）3、一个对象序列的排序码为46, 79, 56, 对象为基准而得到的第一次划分结果为（A. 38, 46, 79, 56, 40, 84C. 40, 38, 46, 56, 79, 844、线性链表不具有的特点是（A ）oA.随机访问C.插入与删除时不必移动元素5、设有一个10阶的对称矩阵A1010,B. O （n+e）D. O（n2）38, 40, 84）,采用快速排序以位于最左位置的 C ）oB. 38, 79, 56, 46, 40, 84D. 38, 46, 56, 79, 40, 84B.不必事先估计所需存储空间大小D.所需空间与线性表长度成正比采用压缩存储方式按行将矩阵中下三角部分的元位置。A. 32B. 33C. 41D. 65素存入一维数组B口中，A00存入B中，则A网在B口中（A ）则B中右指针域6、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点,为空的结点有（A ）个。A. n-1B. nD. n+27、具有65个结点的完全二叉树的高度为（D ）。（根的层次号为0）A. 8B. 7C. 6D. 58、若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（A）方法比较次数最少。A.直接插入排序B.快速排序C.归并排序D.直接选择排序9、在一个无向图中，所有顶点的度数之和等于所有边数的（B ）倍。A. 3B. 2C. 1D. 1/210、对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值,此时元素比较顺序依次为(C )oA. R0, Rl, R2, R3B. R0, R13, R2, R3C. R6, R2, R4, R3D. R6, R4, R2, R3二、判断题(每小题I分，共10分)(F ) 11、数据的基本单位是数据项。/是数据元素()12、带权的无向连通图的最小生成树是唯一的。(T ) 13、数组元素之间的关系，既不是线性的，也不是树形的。(T ) 14、对于有n个对象的待排序序列进行归并排序，所需平均时间为O (nlog2n)。(T ) 15、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。(T ) 16、在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种 情况应当特殊处理。(T ) 17、线性表采用顺序存储表示时，必须占用一片连续的存储单元。(T ) 18、由树转化成二叉树，其根的右子女指针总是空的。(T ) 19、直接选择排序是一种稳定的排序方法。(F ) 20、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。三、阅读理解题(说明下列递归过程的功能。10分)21 >void unknown(BinTreeNode *T, int I) 指针T是完全二叉树的根指针。if(T! =NULL) cout < <T ->data « “，” « I«endl；unknow(T->leftChild, i+1)；unknow(T->rightChild, i+1)； )主程序调用方式unknown (BT. Root, 0)；二叉树根结点的层次号为0,其他结点的层次号等于其双亲的层次号加一。四、简答题(共35分)22、对下面的有向图从顶点Vi开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。(各4分，共8分)23、已知某二叉树的前序序列为EBADCFHGL中序序列为ABCDEFGHL请给出二叉树的 后序序列。（构造出二叉树7分，后序遍历3分，共10分）24、将关键码53, 78, 65, 17, 87, 09, 81, 45, 23依次插入到一棵初始为空的二叉搜索 树中，画出每插入一个关键码后的二叉搜索树。（9分）25、设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的 平均比较次数不超过2次。试问散列表需要设计多大？（设a是散列表的装载因子，则有 ASLsucc= （1 + 1/ （1-a ） /2）o（8 分）五、综合算法题（每小题5分，共15分）一个一维整数数组Am中有n （nWm）个非空整数，它们相继存放于数组的前端并已按 非递减顺序排列，针对下列三种情况，分别编写相应的函数。26、在数组A中插入一个新的整数x ,并使得插入后仍保持非递减有序。要求x插 在值相等的整数后面。（5分）void InsertSort （int A , int m , int & n , int x）（）27、将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。（5分） void reverse （int A , int n ） （ ）28、删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。（5分）Void delDuplicate (int A , int & n)六、填空题(每空2分，共10分)29、设有一个带表头结点的双向循环链表L,每个结点有4个数据成员：指向前驱结点 的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点 的freq初始时都为0。每当在链表上进行一次L.Locate (x)操作时，令元素值x的结点的访 问频度freq加1,并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所 有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。函数中有些语句缺失，请将它们补上。(每一个空2分，共10分)tempiate< class Type>void DblList<Type> ： Locate (Type & x) DblNode<Type>*p=first->next;While (p ! = frist &&)p = ->next;If (p ! =first)链表中存在x；该结点的访问频度加1DblNode<Type>*cuirent=p; 从链表中摘下这个结点 Current -priornext 二 current fnext;Current -nextfprior = current prior;P=currentprior;寻找重新插入的位置While (p !=first &&)P=p prior;Current 9next= (4)；插入在 p 之后Current 9prior=p ;P -next -prior=current;P ->next= ;)else cout«9,Sorry.Not find! n"；没找到)缺失的内容为：2001.2002学年度第二学期“开放本科”期末考试计算机专业数据结构试题答案及评分标准阅卷人请注意:本课程试卷已确定为本年度开放教育考试抽样分析试卷，请在各小题序号前“（得分） 处填入该小题分数。一、单选题（每个2分，共20分）1、A2、B3、C4、A5、C6、C7、C8、A9、B10、CX12、X13、J14、J15、XX17、V18、V19、X20、V判断题（每个1分，共10分）11、16、二、三、阅读理解题（说明下列递归过程的功能。10分）21、以前序顺序输出用二叉链表表示的二叉树各结点的数据和结点的层次号。（每一个下划线标明的概念给2分）四、简答题（共35分）22、遍历得到的DFS生成森林和BFS生成森林如下：（各4分，共8分）V,rV5Vv8V7DFS生成森林v5V6v7BFS生成森林23、构造出的二叉树如下:53全对给9分。24、插入如下（9分）评分标准：除根之外，每插一个正确得1分,cJ25、已知要存储的记录数为n'0找成功的平均查找长度为ASLsuccW2,-1 +则有 ASLsucc= 2 -l - oW2,解得a W 3又有n_ 1502= m W 3 ,贝Im2225。五、综合算法题(每题5分，共15分)26、插入函数如下：void InsertSort (int A , int m , int & n , int x) if (n<m) int Ij ;for (i=0 ; i<n&&Ai<= ; i+ ;)for(j=n-l ;j>=I ;j- )Aj+l = Aj ;A I =x ;n+;)elseceirvv”数组己满，不能插入！"vvendl; exit (); )27、逆置函数如下：void reverse (int A , int n ) int mid=n/2,1, temp ;for (i=0 ; i<mid ; i+ )temp=Ai ; Ai=An-i-l ;An-i-l=temp ; )28、删除函数如下：Void delDuplicate (int A , int & n) Int i=0 , j , k ;While (i<n-l ) J = I+ 1 ;While (j<n) If(Ai= =AU) For ( k=j+1 ; k<n ; k+ )Ak-l=Ak;n- ； )else j+;i+六、填空题(每空2分，共10分)pTdata!二xp-freq+©current freq>p 今freqpfnext©current
