中央广播电视大学2002—2003学年度第一学期“开放专科”期末考试计算机专业数据结构试题.doc

《中央广播电视大学2002—2003学年度第一学期“开放专科”期末考试计算机专业数据结构试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、___________________________________________________________________________________________中央广播电视大学2002—2003学年度第一学期“开放专科”期末考试计算机专业数据结构试题中央广播电视大学2002—2003学年度第一学期“开放专科”期末考试计算机专业数据结构试题2003年1月一、单选题(每小题2分，共8分)1．若需要利用形参直接访问实参，则应把形参变量说明为()参数。A．指针B．引用C．值2．在一

2、个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行()。A．q—＞next＝p—＞next；p—＞next＝q5B．p—＞next＝q—＞next；q＝p；C．q—＞next＝p—＞next；p—＞next＝q；D．p—＞next＝q—＞next；q—＞next＝p；10____________________________________________________________________________________________________

3、_________________________________________________________________________________3．在一个顺序队列中，队首指针指向队首元素的()位置。A．后一个B．前一个C．当前4．向二叉搜索树中插入一个元素时，其时间复杂度大致为()。A．O(㏒2n)B．O(n)C．O(1)D．O(㏒2n)二、填空题(每空1分，共32分)1．数据的存储结构被分为、、和四种。2．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素

4、的时间复杂度为。3．在稀疏矩阵所对应的三元组线性表中，每个三元组元素按为主序、为辅序的次序排列。4．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为域和域。5．中缀表达式3+x*(2．4／5—6)所对应的后缀表达式为。6．在一棵高度为h的3叉树中，最多含有结点。7．假定一棵二叉树的结点数为18，则它的最小深度为，最大深度为。10_________________________________________________________________________

5、____________________________________________________________________________________________________________8．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定该结点的值，右子树上所有结点的值一定该结点的值。9．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调整到位置为止。10．表示图的三种存储结构为、和。11．对用邻接矩阵表示的具有n个顶点和e条边的图进行

6、任一种遍历时，其时间复杂度为，对用邻接表表示的图进行任一种遍历时，其时间复杂度为。12．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为和。13．假定对长度n＝144的线性表进行索引查找，并假定每个子表的长度均为，则进行索引查找的平均查找长度为，时间复杂度为。14．一棵B_树中的所有叶子结点均处在上。15．每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大元素，把它交换到

7、有序表的一端，此种排序方法叫做排序。16．快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为10_____________________________________________________________________________________________________________________________________________________________________________________。三、运算题(每小题6分，共2

8、4分)1．假定一棵普通树的广义表表示为a(b(e)，c(f(h，i)，g)，d)，分别写出先根、后根、按层遍历的结果。先根：后根：按层：2．已知一个带权图的顶点集V和边集G分别为：V＝{O，1，2，3，4，5，6，7}；E＝{(o，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9}；则求出该图的最小生成树的权。最小生成树的权：10_____________________________________________________________