中央广播电视大学2002—2003学年度第二学期“开放专科”期末考试计算机应用专业数据结构试题
王新兰2004-03-02 09:19
中央广播电视大学2002—2003学年度第二学期“开放专科”期末考试
计算机应用专业数据结构试题
2003年7月
一、单选题(每小题2分，共8分)
1．在一个长度为n的线性表中顺顷序查找值为x的元素时，在等概率情况下查找成功时的平均查找长度为()。
A．n B．n／2
C．(n+1)／2D．(n—1)／2
2．栈的插入和删除操作在()进行。
A．栈顶B．栈底
C. 任意位置D．指定位置
3．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为()。
A. front＝＝rear B．front! ＝NULL
C. rear ! ＝NULL D．front＝＝NULL
4．从堆中删除一个元素的时间复杂度为()。
A．O(1)B．O(Cn)
C．O(n)D．O(n㏒2n)
二、填空题(每空1分，共32分)
1．一个算法的时间复杂度为(3n3+2n—7)／(5n)，其数量级表示为。
2．在以HL为表头指针的带头附加结点的单链表和循环单链表中，链表为空的条件分别为和。
3．一个广义表中的元素分为元素和元素两类。
4．从一个链栈中删除一个结点时，需要把栈顶结点的域的值赋给 。
5．在进行函数调用时，需要把每个实参的值和调用后的传送给被调用的函数中。
6．对于一棵具有n个结点的二叉树，若一个结点的编号为i(o＜i＜n—1＝，则它的左孩子结点的编号为，右孩子结点的编号为 ，双亲结点的编号为
。
7．在一棵高度为5的理想平衡树中，最少含有个结点，最多含有个结点。
8．在一个堆的顺序存储中，若一个元素的下标为5，则它的左孩子元素的下标为 ，右孩子元素的下标为 。
9．在一个具有6个顶点的无向完全图中，包含有 条边，在一个具有6个顶点的有向完全图中，包含有 条边。
10．对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为 和 条。
11．以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为 。
12，假定一个线性表为(12，23，74，55，63，40，80，36)，若按key％3条件进行划分，使得同一余数的元素成为个一子表，则得到的三个子表的长度依次为、
和 。
13．在线性表的散列存储中，装填因子。又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于 。
14．在一棵5阶B_树上，每个非树根结点的关键字数目最少为 个，最多为个，其子树数目最少为，最多为。
15．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为，整个堆排序过程的时间复杂度为 。
16．快速排序在乎均情况下的时间复杂度为，在最坏情况下的时间复杂度为。
三、运算题(每少题6分，共24分)
1．假定一个大根堆为(56，38，42，30，25，40，35，20)，则从中删除一个元素后得到的堆为。
2．已知一个图的顶点集V和边集G分别为：
V＝(0，1，2，3，4，5，6，7)；
E＝{(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)10，(2，4)13，(3，5)15，(3，6)12，(3，7)18，(4，6)4，(5，7)20}；
试按照克鲁斯卡尔算法写出得到最小生成树的过程中依次求出的各条边：
， ， ， ，，， 。
3．假定一组数据的初始堆为(84，79，56，42，40，46，50，38，20)，请写出在堆排序阶段进行一次对换和筛运算后数据的排列情况。
数据排列情况：
。
4. 假定一组记录的排序码为(40，80，36，64，75，66，46，79，56，38，84，25)，对其进行归并排序的过程中，第二趟归并后的结果为：
。
四、阅读算法，回答问题(每小题8分，共16分)
1．void AB(list& L)
{
InsertRear(L，30)；
InsertFront(L，58)；
Delete(L，12)；
InsertRear(1，DeleteFront(L)；
}
假定调用该算法时线性表L为(35，19，12，15)，则调用返回后线性表L变为：
。
2．void AG(BtreeNode * BT)／／BT为指向一棵二叉树根结点的指针
{
BTreeNode * s[10]；
int top＝—1；
BTreeNode * p＝BT；
while(top!＝—1|| p!＝NULL)
{／／当栈非空或p指针非空时执行循环
while(p！＝NULL){
top++3
s[top]：＝p；
p＝p—＞left
}
if(top ！＝—1){
p＝s[top]；
top——；
cout＜＜p—＞data＜＜”；
p＝p—＞right；
}
}
}
该算法的功能为：
。
五、算法填空，在画有横线的地方填写合适的内容(10分)
从一维数组A[n]中二分查找关键字为K的元素的递归算法，若查找成功则返回对应元
素的下标，否则返回—1。
int Binsch(ElemType A[]，intlow，int high，KeyType K)
{
if(low＜high）
{
int mid＝(low+high)／2；
if(K＝＝A[mid]．key)；
else if(K＜A[mid]．key；
else；
}
else return—1
}
六、编写算法(10分)
按所给函数头编写一个算法，从表头指针为HL的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链表为空则中止运行。
ElemType MaxValue(LNode * HL)