《计算机软件网专业《数据结构》试题》由会员分享，可在线阅读，更多相关《计算机软件网专业《数据结构》试题（13页珍藏版）》请在金锄头文库上搜索。
1、试卷代号：5849座位号irn广东广播电视大学2005年下半年期末考试计算机、软件(网)专业数据结构试题题号一二三四五六总分得分2006年1月一、填空题(每空1分，共30分)1、数据的逻辑结构被分为集合结构、和图结构四种。2、一个顺序存储的线性表中，第一个元素的存储地址是100,每个元素的长度为4,则第五个元素的地址是3、从一个具有n个结点的单链表中査找其值为x结点时，在査找成功的情况下，需平均比较个结点。4、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点则执行命令和5、广义表(a,(b,( ),c),(d),e)的表头为，表尾为6、在一棵二叉树中，假定双分支结点数
2、为6个，单分支结点数为5个,则叶子结点数为个。7、一棵二叉树的广义表表示为a ( b ( c, d ), e ( f (, g ),则它含有双分支结点个，单分支结点个，叶子结点 个。8. 若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a 中，即编号为0的结点存储到a0中，其余类推，则a订元素的左孩子元素为,右孩子元索为，双亲元索（i0）为9在一个顺序队列Q中，判断队空的条件为判断队满时条件为o10、当从一个小根堆中删除一个元索时，需要把元索填补到 位置，然后再按条件把它逐层 调整。11、图的存储包括存储图的 倍息和 的信息。12、在有向图的邻接表和逆邻接表中，每个顶点的邻
3、接表分别链接昔该顶点的所有和结点。13、从有序表（12,18,30,43,56,78,82,95）中依次二分査找43和56元素时，其査找长度分别为和.14、在线性表的散列存储中，处理冲突有和两种方法.15、在堆排序的过程中对任一分支结点进行筛运算的时间复杂度为，整个堆排序过程的时间复杂度为得分评卷人二、选择题（每小题2分，共10分）1、线性表的顺序存储结构是一种）的存储结构.A.随机存取 B.顺序存取C.索引存取D.散列存取）。2、若HI,为一个带表头结点的单链表的表头指针，则该表为空衣的条件是（A. HL= =NU1 丄B. Hl, next= = NU1,C.HI一ncxt=HI,DHL!
4、 =NULL3、设一个具有i个非零元素的m養n大小的稀疏矩阵采用顺序存储，其转置矩阵的普通转置算法的时间复杂度为(A. O(m)B. O(n)C. O(n-f-t)D. O(n * t)4、一个栈的入栈序列是a,b,cd,e,则栈的不可能的输出序列是().A. edcbaB. decbaC.dcebaD. dceab5、在一棵高度为4的理想平術树中，最多含有个结点。B.8C. 16D. 17三、算法填空题(共10分)下面算法描述了向非递减的线性表满足条件的位置俪入一个元索，请将算法填写完整。void Insert (List & L,const ElemType&- item)if (L si
5、ze = Maxsize) ceer*List overflow n = i? j)L. list JhL list_Ji= iiem；I” size+ + ；将答案填在下面:得分评卷人四、运算题（每小题6分，共24分）1 已知一组元素为（30,52,74,15,2342,18,26,63）.画出按元素排列顺序输入生成 的一棵二叉搜索树。：2对于如下所示的连通图（网络），写岀从顶点VI出发按照普里姆算法并入最小生 成树中各边的次序写岀各条边.（填在下表中）A2345边的顶点1边的顶点2边的权值3、设有序顺序表中的元素依次为（12.23,26,37.54,60,68.75,82,96）,试画出对
6、其二 分査找时的判定树，并计算査找成功时的平均査找长度4、已知序列503,87,512,61.908,170,897.275,653 .162，请写出采用堆排序法建立 的初始堆及前四趟排序并调整后的结果。五算法阅读题（每小题8分，共16分）void AS(Stack& S)InitStack(S);Push(S,50)；int a =36,87,12?for(int i = 0$iV3$i+ + )Push(S,ai) iint x=2 * Pop(S)-f-Pop(S)/3jPush(S,x) iwhile (top ! = 1)coutPop(SXleft) + test (BT righ
7、t)$该算法的功能为:得分评卷人六、编写鼻法（共10分）假设在一个链队列中（结点类型为LNode）只设置队尾指针，不设置队首指针，并且让 队尾结点的指针域指向队首结点（称此为循环链队），试写出在循环链队上进行删除操作 的算法（假设链队列非空，并返回被删结点的值）.ElemType Qdelete next = q next;q next = p；5、(a,(b,( ),c),(d),e)()6、77、2238、a2i+la2i + 2 a(i-l)/2%9、Q. front = =Q rear (Q. rear +1) %QueucMaxSize= =Q. front10.堆尾堆顶向下11、顶
8、点边12、岀边人边13 J31仁开放定址法 链接法15 X）Clog2n） 0（nlog2n）二、选择题（每小题2分，共10分）1-5：ABDDA三、算法填空题（每对一空2分全对10分） break L. size 1j+1jI- listi四、运算题（每小题6分共24分）1、解：按元素排列顺序输人生成的二叉搜索树为：2、边的顶点112335边的顶点224456边的权值79576解：二分資找的判定树如下示:查找成功的平均査找长度为：ASL= （1+2*2+4*3+3*4） /10=2.94、初始堆：(908,653,897,503,462,170,512,275,61,87) 第一通：(897
9、.653,512,503,462,170,87,275,61 ),908第二趙：(653,503,512,275,462,170,87,61 ),897,908第三趙：(512,503,170,275,462,61,87),653,897,908第四趙：(503,462,170,275,87,61 ),512,653,897,908五、算法阅读题(每小题8分，共16分)1、该算法被调用后得到的输出结果为：5336 502、此算法的功能是：计算给定的二叉树中结点的个数。六、编写算法(共10分)算法参考：(酬情给分)ElcmTypc Qdelete ( LNodc 关&rear)l,Nodc p = rear next ;if (p= =rear)rear = NULL ;elserear next = p next ；ElemType temp = pdaia ；delete p ；return temp ；（5849号） 数据结构-答案 第3页（共3页）
