中央广播电视大学2008-2009学年度第一学期"开放专科"期末考试
数据结构 试题
2009年1月
一、单选题(每小题2分，共20分)
1．若一个数据具有集合结构，则元素之间为( )。
A. 线性关系 B．层次关系
C. 网状关系 D．无任何关系
2．在一个利用数组存储顺序表的表尾插入一个元素的时间复杂度为( )。
3．在一个长度为n的顺序表中向i位置(o≤i≤n)插入一个新元素时，需要从后向前依次后移( )个元素。
A．n-i B．n-i+1
C．n-i一1 D．i
4．在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为( )。
A．n B．n／2
C．(n十1)／2 D．(n一1)／2
5．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结 点，则执行( )操作。
A． q一>next＝p一>next；p一>next＝q；
B． p一->nexI＝q一>next;q＝p；
C． q一>next＝p一>next；p＝q；
D． P一>next＝q一>next；q一>next＝p；
6．当利用大小为N的数组顺序存储一个栈时，假定用top'＝0表示栈空，则向这个栈插入一个元素时，首先应执行( )操作修改top指针。
A．top++ B．top--
C．top＝0 D．top
7．在一个顺序循环队列中，队首指针指向队首元素的( )位置。
A. 后一个 B．前一个
C. 当前 D．任何
8．向二叉搜索树中插入一个元素时，其时间复杂度大致为( )。
A．O(10g2n) B．O(n)
C．O(1) D．O(nlog2n)
9．一个结构类型的对象所占有的存储空间的大小等于所有域类型的( )。
A. 长度之和 B．长度的最大值
C. 长度的最小值 D．长度的平均值
10．对于长度为10的顺序存储的有序表，对应的二分查找判定树的高度为( )。
A．2 B．3
C．4 D．5
二、填空题(每小题2分，共20分)
1。数据的存储结构被分为顺序、链接、索引和 四种结构。
2。对于一个长度为n的单链接存储的线性表，在表头插入结点的时间复杂度 为 。
3．在一棵深度为3的满四叉树中，其结点总数为 个。
4．从一棵二叉搜索树中查找一个元素时，若给定值小于树根结点的值，则继续向树根结点的 子树查找。
5．当从一个堆中删除一个元素时，需要首先把堆尾元素填补到 位置，然后再对它进行筛运算。
6．对于一个具有n个顶点和e条边的连通图，其任一生成树中的边数为 条。
7．二分查找过程所对应的判定树既是一棵 树，又是·一棵二叉搜索树。
8．若对长度n＝1000的线性表进行索引存储，索引表中的每个索引项是主表中40个对应记录的索引，则索引表的长度为 。
9．在一棵m阶的B-树中，每个结点的子树数目最多为 个。
10．在归并排序中，进行每趟归并的时间复杂度为 。
三、运算题(每小题6分，共24分)
1．假定一棵普通树的广义表表示为a(b(e)，c(f，g)，d)，试分别写出先根和按层遍历的结果。
先根：
按层：
2．已知一个带权图的顶点集V和边集G分别为：
V={0，1，2，3，4}；
E={(0，1)8，(0，2)5，(0，3)2，(2，3)10，(2，4)13，(3，4)12}；
按照权值从小到大的次序写出该图的最小生成树中的每条边。
最小生成树中的每条边：
3．假定对线性表(18，25，63，50，41，22)进行散列存储，若选用H(K)：K％9作为散列函数，并采用链接法处理冲突，则在查找成功情况下的平均查找长度为 。
4．假定--组记录的排序码为(40，80，50，62，46，79，56，38，73，38)，写出对其进行归并排序的过程中，第二趟归并后的结果。
第二趟归并后的结果：
四、阅读算法，回答问题(每小题8分，共16分)
1．intAE(inta[]，intn)
{
if(n＝=1)returna[0]；
elsereturn·a[n一1]+AE(a，n一1)；
}
写出此递归算法的功能：
2．在下面算法中假定BT指向一棵具有n个元素的二叉树的根结点。
voidpreserve(BTreeNode * BT，ElemTypea[]，intn)
{
static int i＝0；
if(BT!＝NULL) {
preserve(BT-->left，a，n)；
a[i++]＝BT一>data；
preserve(BT一>right，a，n)；
}
}
写出该递归算法的功能：
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共
12分)
1．下面是从一维数组A[n]中二分查找关键字为K的元素的算法，若查找成功则返回对应元素的下标，否则返回一1。
ihtBinseh(ElemType A[]，intn，KeyType K)
{
int low＝0，high＝n一1；
while(10we＝high)
{
int mid；
mid＝(10w+high)／2；
if(k＝＝A[mid]．key)returnmid；
else if(K else ；
}
return一1；
}
2．下面算法的功能是统计出二叉树BT中大于等于x的结点个数并返回。
iht BTCl(BTreeNode* BT，ElemType x)
{
if(BT＝＝NULL)return 0；
else if(BT一>data>＝x)
return BTCl(BT一>1e{t，x)+BTCl(BT一>right，x)+1;
else
return BTCl(BT一>left，x)+ ;
}
六、编写算法(8分)
编写从类型为List的线性表L中删除其值等于给定值x的、具有最大下标的元素的算法，要求若删除成功返回true，否则返回false。
b00l Delete(List& L，ElemType x)；
试卷代号：2075
中央广播电视大学2008-2009学年度第一学期"开放专科''期末考试
数据结构 试题答案及评分标准
(供参考)
2009年1月
一、单选题(每小题2分，共20分)'
评分标准：选对者得2分，否则不得分。
1．D 2．B 3．A 4．C 5．D
6．A 7．B 8．A 9．A 10．C
二、填空题(每小题2分，共20分)
1．散列
2．O(1)
3． 21
4．左
5．堆顶
6． n-l
7．理想平衡
8． 25
9．m
10．O(n)
三、运算题(每小题6分，共24分)
1．先根：a，b，e，c，f，g，d； ／／3分
按层：a，b，c，d，e，f，g ／／3分
2．最小生成树中的每条边：(0，3)2，(0，2)5，(0，1)8，(3，4)12
3．4／3
4．[40 50 62 80][38 46 56 79][38 73] ／／酌情给分
四、阅读算法，回答问题(每小题8分，共16分)
评分标准：根据叙述完整程度酌情给分。
1．算法功能：求出数组aLn)中n个元素之和。
2．算法功能：对具有n个结点的由BT指针所指向的二叉树进行中序遍历，把得到的结点值序列保存到数组a中。
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1．high＝mid一1 low＝mid+1 ／／每个空3分
2．BTCl(BT-->right，x)
六、编写算法(8分)
评分标准：根据编程的完整情况酌情给分。
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
2045电大《金融企业会计》试题和答案20070104-27
2045电大《金融企业会计》试题和答案20060704-27
2045电大《金融企业会计》试题和答案20050104-27
2045电大《金融企业会计》试题和答案20060104-27
2045电大《金融企业会计》试题和答案20040104-27
2045电大《金融企业会计》试题和答案20040704-27
电大金融学专业《公司财务》试题04-27
电大网上中考《西方经济学》试题（专科）04-27
电大计算机专业《英语》中考试题04-27