中央广播电视大学2005—2006学年度第二学期“开放本科”期末考试计算机专业数据结构试题

《中央广播电视大学2005—2006学年度第二学期“开放本科”期末考试计算机专业数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、___________________________________________________________________________________________中央广播电视大学2005—2006学年度第二学期“开放本科”期末考试计算机专业数据结构试题 试卷代号：1010 中央广播电视大学2005—2006学年度第二学期“开放本科”期末考试 计算机专业数据结构试题 2006年7月 一、单项选择题，在括号内填写所选择的标号(9小题，每小题2分，共18分) 5．如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后可执行语句，则称这种递归为()，它很容易被

2、改写为非递归过程。 A．单向递归B．回溯递归 C.间接递归D．尾递归 6．假定一棵二叉树的第i层上有3i个结点，则第i+l层上最多有()个结点。 A．8iB．6i C.9i10_____________________________________________________________________________________________________________________________________________________________________________________D．2i 7．从具有n个结点的AVL树中搜索一个元

3、素时，在等概率情况下进行成功搜索的时间复杂度大致为()。 9．图的深度优先搜索遍历类似于树的()次序遍历。 A．先根B．中根 C.后根10_____________________________________________________________________________________________________________________________________________________________________________________D．层次 二、填空题，在横线处填写合适内容(每小题1分，共12分) 1。数据结构的存储

4、结构包括顺序、——、索引和散列四种。 2。在程序运行过程中进行存储空间分配的数组是——分配的数组。这种数组在声明它时需要使用数组指针。 3．在链表中进行插入和————操作的效率比在顺序存储结构中进行相同操作的效率高。 4．栈是一种限定在表的一端进行插入和删除操作的线性表，又称它为——表。 5．如果一个对象部分地包含自己，或自己定义自己，则称这个对象是——的对象。 6．假定一棵树的广义表表示为a(b，c，d(e，f)，g(h))，则结点f的层数为——·假定树根结点的层数为0。 7．若把一棵树按照左子女一右兄弟表示法转换成一棵对应的二叉树，则该二叉树的树根结点肯定没有——子女。 8．向

5、一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的——上。 9．设图G＝(V，E)，V=(1，2，3，4}，E={<l，2>，<l，3>，<2，4>，<3，4>}，从顶点1出发，对图G进行广度优先搜索的序列有——种。 10．每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做——类排序。 11．快速排序在平均情况下的空间复杂度为——。 12．若对长度n＝10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为——。 三、判断

6、题，在每小题前面打对号表示正确或打叉号表示错误(每小题1分，共10分) ()1．算法和程序的概念完全相同，在讨论数据结构时二者是通用的。 ()2．插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。 (10_________________________________________________________________________________________________________________________________________________________________________________

7、____)3．栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。 ()4．将f＝1十1／2十1／3+…十1／n转化为递归函数时，递归部分为f(n)=f(n一1)+l／n，递归结束条件为f(1)＝1。 ()5．在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历时具有相同的结果。 ()6．进行折半搜索的表必须是顺序存储的有序表。 ()7．用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶