中央广播电视大学2007-2008学年度第一学期"开放专科"期末考试
计算机专业 数据结构 试题
2008年1月
一、单选题(每小题2分，共20分)
1．在一个长度为n的顺序存储的线性表中，插入一个元素的时间复杂度为( )。
A．O(n) B．O(n／2)
C．O(1) D．O(n2)
2．在一个长度为n的顺序存储的线性表中，删除第i个元素(0≤i≤n-1)时，需要从前向后依次前移( )个元素。
A．n-i B．n-i+1
C．n-i-1 D．i
3．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为( )。
A．O(1) B，O(n)
C． O(n2) D． O(log2n)
4．假定一个顺序循环队列的队首和队尾指针分别为f和r，则判断队空的条件为( )。
A．f+1＝＝r B．r+1＝＝f
C．f＝＝0 D．f＝＝r
5．在由表头指针f所指向的循环单链表中，只含有一个结点的判断条件为( )。
A. f一>next==NULL； B．F==NULL；
C. f一>next==f D f一>next!=f;
6．在一棵二叉树的二叉链表中，空指针域数等于结点数加( )。
A．2 B． 1
C．0 D．-1
7．从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A．O(n) B．()(1)
C. O(log2n) D．O(n2)
8．在一棵5阶B树中，每个结点最多允许有( )个关键字。
A， 1 B．2
C． 3 D． 4
9．二分查找过程所对应的判定构，既是一棵理想平衡树，又是一棵( )。
A. 一般二叉树 B. 二叉搜索对
C. 满二叉树 D．完全二叉树
10．在对n个元素进行直接选择排序的过程中，需要进行( )趟选择和交换。
A．n-l B. n
C. n+l D．n／2
二、填空题(每小题2分，共20分)
1．数据的 结构被分为顺序、链接、索引和散列四种结构。
2．对于一个长度为n的单链接存储的线性表，在表头插入结点的时间复杂度为
。
3．在一棵深度为3的满四叉树中，其结点总数为 个。
4．从一棵二叉搜索树中查找一个元素时，若给定值小于树根结点的值，则继续向树根结点的 子树查找。
5．当从一个堆中删除一个元素时，需要把堆尾元素填补到 位置，然后再对它进行筛运算。
6．对于一个具有n个顶点和e条边的连通图，其任-生成树中的边数为 条。
7．二分查找过程所对应的判定树既是一棵 树，又是一棵二叉搜索树。
8．若对长度n＝1000的线性表进行二级索引存储，每级索引表十的索引项是下一级10个记录的索引，则二级索引表的长度为 。
9．在一棵m阶的B_树中，每个结点的子树数目最多为 个。
lo．在归并排序中，进行每趟归并的时间复杂度为 。
三、运算题(每小题6分，共24分)
1．假定一棵二叉树广义表表示为a(b(c，d)，e(f(，g)))，分别写出对它进行先序、中序和后序遍历的结果。
先序：
中序：
后序：
2．已知一个带权图的顶点集V和边集G分别为：
V={0，1，2，3，4，5}；
E＝{(0，1)12，(0，2)5，(0，3)2，(1，5)10，(2，3)6，(2，4)15，(3，5)9}；
写出按照克鲁斯卡尔算法依次得到该图的最小生成树中的各条边，以及最小生成树的权。
各条边：--，--，--，--，--，--。
最小生成树的权：
3．假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为--。
4. 假定-组记录的排序码为(46，79，56，38，40，80，25)，在对其进行快速排序的过程中，进行第一次划分后得到的排序码序列。
排序码序列：
四、阅读算法，回答问题(每小题8分，共1．6分)
1．void AD(LNode * & HL)
{
Insert(HL，30)； ／／在有序单链表上进行有序插入
Insert(HL，50)； ／／在有序单链表上进行有序插入
Delete(HL，28)；
Delete(HL,53)；
}
假定调用该算法时以HL为表头指针的有序单链表巾的内容为(28，36，42，53，66)，则给出调用返回后该有序单链表中的内容。
有序单链表中的内容：
2．void Al(adjmatrix GA，int i，int n)
{
cout<
for(int j＝0;j
if(b) Al((GA，j，n)；
}
}
该算法的功能为；
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共
12分)
]．向以BST为树根指针的二叉搜索树上插入值为item的结点的非递归算法。
void Insert(BTreeNode*& BST,const ElemType &item)
BTreeNode * t＝BST，*parent＝NULL；
while(t!＝NULL){
parent＝t；
if(item
else----；
BTreeNode* p＝new BTreeNode；
p->data＝item；P->left＝p->right＝NULL;
if(parent=＝NULL)BST＝P；
else if(item
else------；
}
2．从类型List的线性表L中删除与x值相等的所有元素。
void Delete2(List&L,ElemType x)
{
int i=0；
while(i
for(int j＝i+1;j
L.size一一；
}
else ：
}
}
六、编写算法(共8分)
编写从类型为List的线性表L中删除其值等于给定值x的第一个元素的算法，要求若删除成功返回true，否则返回false。
bool Delete(List&L，ElemType x)：
试卷代号：2075
中央广播电视大学2007-2008学年度第一学期"开放专科"期末考试
计算机专业 数据结构 试题答案及评分标准
(供参考)
2008年1月
一、单选题(每小题2分，共20分)
1．A 2．C 3．B 4．D 5．C
6．B 7．C 8. D 9．B 10．A
二、填空题(每小题2分，共20分)
1．存储(物理)
2． O(1)
3． 2l
4．左
5．堆顶
6． n-l
7．理想平衡
8． 10
9． m
10． O(n)
三、运算题(每小题6分，共24分)
1．先序：a，b，c，d，e，f，g 2分
中序：c，b，d，a，f，g，e 2分
后序：c，d，b，g，f，e，a 2分
2．各条边：(0，3)2，(0，2)5，(3，5)9，(1，5)10．(2，4)15 4分
最小生成树的权：4l 2分
3．(84，79，56，42，40，46，50，38) 6分，酌情给分
4．(38，25，40，46，56，80，79) 6分，酌情给分
四。阅读算法，回答问题(每小题8分，共16分)
1．(30，36，42，50，66) 全对给6分，否则酌情给分
2。从初始点Vi出发深度优先搜索遍历由邻接矩阵GA所表示的图。
评分标准：请根据叙述的完整情况酌情给分。
五、算法填空，在画有横线的地方填写合适的内容(每小题6分，共12分)
1。t＝t一>right parent一>right=p 每空对给3分
2．L.list[j] i++ 每空对给3分
六、编写算法(共8分)
评分标准：根据编程的完整情况酌情给分。
bool Delete(List&L,ElemType x){
for(int i=0；i
for(int j＝i+l；j
relurn true; 8分
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
2045电大《金融企业会计》试题和答案20050104-27
2045电大《金融企业会计》试题和答案20060104-27
2045电大《金融企业会计》试题和答案20040104-27
2045电大《金融企业会计》试题和答案20040704-27
电大金融学专业《公司财务》试题04-27
电大网上中考《西方经济学》试题（专科）04-27
电大计算机专业《英语》中考试题04-27
2058电大《C++语言程序设计》试题和答案20040104-27