中央广播电视大学2008-2009学年度第二学期"开放专科"期末考试
数据结构 试题
2009年7月
一、单选题(每小题2分，共20分)
1．若一个数据具有树结构，则元素之间为( ).
A．线性关系 B. 层次关系
C. 网状关系 D．无任何关系
2．向一个长度为n的顺序表中插入一个新元素的平均时间复杂度为( )。
A． O(n) B．O(1)
C． O(n2) D． O(log2n)
3．对于一个长度为n的单链表，向表头插入一个新结点的时间复杂度为( )o
A． O(n) B．O(n／2)
C． O(1) D．O(n2)
4．在一个单链表HL中，若要向表头插入一个由指针p所指向的结点，则执行( )。
A． HL＝p；p一>next＝HL；
B．p一>next＝HL；HL＝p；
C． p一>next＝HL；p＝HL；
D． p一>next＝HL一>next；HL一>next＝p；
5．当利用大小为N的数组顺序存储一个栈时，假定用top＝＝N表示栈空，用top＝＝0 表示栈满，则向这个栈插入一个元素时，首先应执行( )操作修改top指针.
A．top++ B. top一一
C． top＝0 D． top＝N
6．在具有n个顶点的连通图中至少包含有( )条边.
A．n一1 B．n
C．n(n一1)／2 D．n(n-1)
7．从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A．O(n) B．O(1)
C．O(log2n) D．O(n2)
8．由4个叶子结点生成的一棵哈夫曼树中，共含有( )个分支结点。
A．1 B．2
C．3 D．4
9．在散列存储中，若采用h(K)＝K％13计算散列地址，则元素关键字为48的散列地址
为( )。
A．3 B．13
C．8 D．9
10．在一棵5阶B-树中，每个结点最多允许有( )个关键字。
A．2 B．3
C．4 D．5
二、填空题(每小题2分，共20分)
1．在 结构中，前驱和后继结点之间存在着l对N的联系。
2．在线性表的单链接存储中，假定每个结点的结构为(data，next)，若一个结点的地址为 p，则其后继结点的地址为--。
3．栈又称为--表，队列又称为先进先出表。
4．假定一棵树的广义表表示为A(B，C(I，J)，D(E，F(H，G)))，则树的深度为--。
5．在一棵具有n个结点的二叉树所对应的．-tX链表中，必定包含有--个空指针。
6．对于一个具有n个顶点和e条边的连通图，存储它所用邻接表的空间复杂度为 ---。
7．在一个索引表中，每个索引项至少包含有索引值域和子表的--域这两项。
8．在线性表的--存储中，无法查找到一个元素的前驱或后继元素。
9．在一棵B-树中，所有--结点都处在同一层上，即最低层上。
10．在对n个记录进行堆排序的过程中，由初始堆到堆排序结束，需要对树根结点进行 次筛运算。
三、运算题(每小题6分，共24分)
1．假定一个大根堆为(56，38，42，30，25，20)，则向它插入63元素后得到的大根堆为 ---.
2．已知一个图的顶点集V和边集G分别为：
V＝{0，1．，2，3，4，5}
E＝{(0，1)，(0，2)，(0，3)，(1，5)，(2，3)，(2，4)，(3，5)，(4，5)}
假定该图采用邻接矩阵表示，则分别写出从顶点2出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。
深度优先搜索序列：
广度优先搜索序列：
3。假定一个顺序表为(15，28，36，45，48，72，83，90)，则利用二分查找方法查找元素36时，其查找长度(即所需比较元素的个数)为 .
4．假定一组记录的排序码为(40，80，36，64，75，66，46，79，56，38，84，25)，对其进行归并排序的过程中，第二趟归并后的结果为：
四、阅读算法，回答问题(每小题8分，共16分)
1．求出该算法被调用执行后，以HL为表头指针的单链表中所保存的线性表o
voidAA(LNode*&HL)
{
InitList(HL)；
InsertFront(HL，50)； ／／向表头插入元素
int a[5]＝{15，8，9，26，12}；
for(int i＝0；i<5；i++)InsertRear(HL，a[i])； ／／向表尾插入元素
InsertFront(HL，30)； ／／向表头插入元素}
线性表：
2．写出下面算法的功能。
int Binsch(ElemTypeA[]，int n，KeyType& K)
{
int low＝0，high＝n-l；
while(low<＝high){
int mid；
mid＝(low+high)／2；
if(k＝＝A[mid)．key)return mid；
else if(K else low＝mid+1;
}
return -l；
}
该算法功能为：
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共
12分)
1．下面函数的功能是从由BST指针所指向的一棵二叉搜索树中进行查找的算法，若查找成功则返回真，否则返回假.
bool Find(BTreeNode * BST，ElemType& item)
{
while(BST!＝NULL){
if(itern＝＝BST一>data)return true；
else if(item
else--；
}
Return false；
}
六＼编写算法(8分)
编写从类型为List的线性表L中删除其值等于给定值x的第一个元素的算法，要求若删除成功返回true，否则返回false.
bool Delete(List& L，ElemType x)；
试卷代号：2075
中央广播电视大学2008-2009学年度第二学期"开放专科"期末考试
数据结构 试题答案及评分标准
(供参考)
2009年7月
一＼单选题(每小题2分，共20分)
1．B 2．A 3．C 4．B 5．B
6．A 7．C 8．C 9．D 10．C
二＼填空题(每小题2分，共20分)
1．树
2．p一>next
3．后进先出
4． 4
5．n+l
6．O(n+e)
7．开始位置
8．散列
9．叶子
10．n-1
三、运算题(每小题6分，共24分)
1． (63，38，56，30，25，20，42)
2．深度优先搜索序列：2，0，l，5，3，4 ／／3分
广度优先搜索序列：2，0，3，4，l，5 ／／3分
3． 3
4． [36 40 64 80][46 66 75 79][25 38 56 84]
四＼阅读算法，回答问题(每小题8分，共16分)
评分标准：根据答案正确与叙述的完整程度酌情给分o
1． (30，50，15，8，9，26，12)
2．从一维数组A[n]中二分查找关键字为K的元素的非递归算法，若查找成功则返回对应元素的下标，否则返回一lo
五＼算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1．BST=BST-->right
2．return c2+l
六＼编写算法(8分)
评分标准：根据编程的完整情况酌情给分.
boolDelete(List&L，ElemType x){
for(inti＝0；i
for(int j＝i+1;j
returntrue； ／／8分
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
2045电大《金融企业会计》试题和答案20070104-27
2045电大《金融企业会计》试题和答案20080104-27
2045电大《金融企业会计》试题和答案20060704-27
2045电大《金融企业会计》试题和答案20050104-27
2045电大《金融企业会计》试题和答案20060104-27
2045电大《金融企业会计》试题和答案20040104-27
2045电大《金融企业会计》试题和答案20040704-27
电大金融学专业《公司财务》试题04-27
电大网上中考《西方经济学》试题（专科）04-27
电大计算机专业《英语》中考试题04-27