中央广播电视大学2007-2008学年度第二学期"开放本科"期末考试
计科网络、计科应用、计科硬件专业 数据结构 试题
2008年7月
一、单项选择题(在括号内填写所选择的标号。每小题2分，共18 分)
1．执行下面程序段时，S语句的执行次数为( )。
for(int i＝1;i<＝n；i++)
for(int j＝1;j<＝i;j++)S；
A．n2 B．n2／2
C．n(n+1) D．n(n+1)／2
2．多维数组实际上是由嵌套的( )实现的。
A．一维数组 B．多项式
C. 三元组表 D．简单变量
3．表头指针为first的单链表为空的判定条件是( )。
A．first==NULL： B．first一>link＝＝NULL；
C. first一>link＝＝first； D．first! ＝NULL；
4．若让元素1，2，3依次进栈，则出栈次序不可能出现( )种情况。
A．3，2，1 B．2，1，3
C．3，1，2 D．1，3，2
5．在一棵具有n个结点的完全二叉树中，共包含有( )个分支结点。
A．(n-1)／2 B．n／2
C. n／2+1 D．n／2-1
6．若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度为( )。
A．n B．n+l
C．(n一1)／2 D．(n+1)／2
7．向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为( )
种旋转类型。
A．2 B．3
C．4 D，5
8．为了实现图的广度优先搜索遍历，其算法使用的一个辅助数据结构是( )。
A．栈 B．队列
C. 二叉树 D．树
9．在一棵5阶B树中，每个结点最多允许有( )个关键码。
A．2 B．3
C．4 D．5
二、填空题(在横线处填写合适的内容。每小题2分，共14分)
1．在类的继承结构中，位于上层的类叫做基类，而位于下层的类叫做 类。
2．设链栈中结点的结构为(data，link)，栈顶指针为top，当向该链栈插人一个新结点*p
时，应依次执行p一>link＝top和 这两步操作。
3．广义表的 定义为广义表中括号被嵌套的最大重数。
4．在一棵高度为5的完全二叉树中，最少含有 个结点。假定树根结点的高度为0。
5．从有序表(12，18，30，43，56，78，82，95)中折半搜索56元素时，其搜索长度为
。
6．具有n个顶点的连通图中至少含有 条边。
7．假定一个数据集合为{46，79，56，38，40，84}，则在构成的最大堆(即大根堆)中，其堆顶元素为 。
三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分，共14分)
1. 若每次从队列中取出的是具有最高优先权的元素，则称此队列为优先级队列。 ( )
2．递归定义的数据结构通常不需要采用递归的算法对其运算。 ( )
3．当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 ( )
4．对于一棵具有n个结点、高度为h的二叉树，进行任一种次序遍历的时间复杂度均为O(n)。 ( )
5．对于同一组记录集合，生成二叉搜索树的形态与插人记录的次序无关。 ( )
6．装载因子是散列存储中的一个重要指标，它反映了散列表的装满程度。 ( )
7．在一棵B树中，所有叶结点都处在同一层上。 ( )
四、运算题(每小题6分，共30分)
1．假定一棵二叉树的广义表表示为A(B(，D(G))，C(E，F))，分别写出对它进行先序、中序、按层遍历的结果。
先序：
中序：
按层：
2．已知-个有序表(15，26，34，39，45，56，58，63，74，76，83，94)顺序存储于-维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34、56、58、63时的比较次数。
3．假定一个线性序列为(56，27，34，95，73，16，60，62)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，分别求出该二叉搜索树中双支结点、单支结点和叶子结点的个数。
双支结点数：
单支结点数：
叶子结点数：
4．已知一个带权图的顶点集V和边集G分别为：
V＝{0，1，2，3，4，5}；
E＝{(0，1)19，(0，2)21，(0，3)14，(1，2)16，(1，5)5，(2，4)11，(3，4)18，(4，5)6}； 试根据普里姆算法从顶点。出发求出最小生成树，在下面填写依次得到的最小生成树中的每条边。
5．设散列表的长度m＝7；散列函数为H(K)＝K mod m，给定的关键码序列为{19，14，23，40，68}，并假定采用的闭散列表为HT[m]，采用的解决冲突的方法为线性探查法，求出在最后得到的散列表中，关键码19、40和68的存储位置和对应的查找长度。
五、算法分析题(每小题6分，共12分)
1．设单链表结点的结构为LNode＝(data，link)，阅读下面函数，指出它所实现的功能。
intAA(LNode。Ha){ ／／Ha为指向带表头附加结点的单链表的表头指针
int n＝0；
LNode*p=Ha一>link；
while(p){
n++；
p＝p一>link；
}
return n；
)
算法功能：
2．阅读下面算法，写出算法功能。
LinkNode*BB(LinkNode*first) ／／first为单链表的表头指针
{
if(first＝＝NULLI，first一>link：＝NULL)return first；
LinkNode*p＝first，*r1＝first一>link；
p一>link＝NULL；
while(rl!＝NULL){
ListNode* r2＝r1->link；
r1->link＝p；
p＝r1；
r1＝r2；
}
return p；
}
算法功能：
六、算法设计题(每小题6分，共12分)
1. 根据下面函数原型编写一个对一维数组A[n)中的n个有序元素进行折半查找其值为 K的非递归算法，若查找成功则返回元素下标，否则返回一1。
int BinarySearch(ElemTypeA[]，int n，ElemType K)；
2．已知二叉树中的结点类型用BinTreeNode表示，定义为：
struct BinTreeNode{char data；BinTreeNode *left，*right；}；
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的递归算法，算法中参数BT初始指向这棵二叉树的根结点。
void BTreeSwop(BinTreeNode*BT)；
试卷代号：1010
中央广播电视大学2007-2008学年度第二学期"开放本科"期末考试
计科网络、计科应用、计科硬件专业 数据结构 试题
2008年7月
一、单项选择题(在括号内填写所选择的标号。每小题2分，共18分)
1．D 2．A 3．A 4．C 5．B
6．D 7．C 8．B 9．C
二、填空题(在横线处填写合适的内容。每小题2分，共14分)
1．派生(或子)
2．top＝p
3．深度
4．32
5． 3
6．n一1
7．84
三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分，共14分)
1．√ 2．X 3．√ 4．√ 5．X
四、运算题(每小题6分，共30分)
1．先序：A，B，D，G，C，E，F ／／2分
中序：B，G，D，A，E，C，F ／／2分
按层：A，B，C，D，E，F，G ／／2分
2．评分标准：对1个数据给1分，全对给6分
元素 34 56 58 63
比较次数 2 1 3 4
3．双支结点数：2 ／／2分
单支结点数：3 ／／2分
叶子结点数：3 ／／2分
4．(0，3)14，(3，4)18，(4，5)6，(5，1)5，(4，2)11
5．评分标准：每个数据的存储位置和查找长度正确各得1分，共6分。
五、算法分析题(每小题6分，共12分)
1．计算并返回单链表的长度。
2．逆序排列以first为表头指针的单链表中的所有结点并返回新的表头指针。
六、算法设计题(每小题6分，共12分)
1．请根据编写的完整程度酌情给分。
int BinarySearch(ElemType A[]，int n，ElemType K)
{ ／／对数组A中的n个有序元素进行折半查找
int low＝0，high＝n-1; ／／1分
while(low<＝high) ／／2分
{
int mid＝(low+high)／2； ／／3分
if(K＝A[mid])return mid；
else if(K else low=mid+1； ／／5分
}
return一1; ／／6分
}
2．请根据编写的完整程度酌情给分。
void BTreeSwop(BinTreeNOde*BT)
{
if(BT! ＝NULl){ ／／1分
／／交换左右子女指针域的值
BinTreeNode * pt＝BT一>left；
BT一>left＝BT一>right；
BT->right＝pt； ／／2分
／／对左子树进行同样处理
BTreeSwop(BT一>left)； ／／4分
／／对右子树进行同样处理
BTreeSwop(BT一>，right)； ／／6分
}
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
你作为卫生防疫部门的工作人员，当前新型冠状肺炎的防治04-27
小王是一名下沉社区支援基层防疫的工作人员。社区领导04-27
你是刘处长，分管单位的办公室，小王是办公室新进员工，上班04-27
材料：近日，某海事局对一违法运输船舶处以21.8万元罚款，刷04-27
单位要组织大型会议，准备时间非常紧，领导便安排你和其他04-27
2019年5月5日凌晨，被告人彭某与朋友吃宵夜、喝啤酒，并在04-27
疫情防控期间，单位要求50%的人员到岗，你作为科室负责人04-27
小张是办公室工作人员，这是一天的工作，假如你是小张，请合04-27