试卷代号：1010 座位■☐ 中央广播电视大学2007一2008学年度第二学期“开放本科”期末考试 计科网络、计科应用专业 数据结构 试题 计科硬件 2008年7月 题 号 二 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 1.执行下面程序段时，S语句的执行次数为( for (int i=1;ilink==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 70
试卷代号:1010 座位号口口 中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试 计“翠.霍应”专业数据结“试题 2008年 7月 题 号 四 五 六 总 分 分 数 得 分 }评卷人 一、单项选择题(在括号内填写所选择的标号。每小题 2分.共 18 一--二--------二 分) 1.执行下面程序段时 ，S语句的执行次数为( )。 for Grit i二1;ilink==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.若搜索每个元素的概率相等，则在长度为的顺序表上搜索任一元素的平均搜索长度 为()。 A.n B.n+1 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元素时，其搜索长度为 0 6.具有n个顶点的连通图中至少含有 条边。 7.假定一个数据集合为{46,79,56,38,40,84}，则在构成的最大堆（即大根堆）中，其堆顶 元素为 71
为( 6.若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度 )。 A. n B. n十 1 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的完全二叉树中，最少含有 个结点。假定树根结点的高度 为 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时的比较次数。 元素 34 56 58 63 比较次数 72
得 分 评卷人 三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示 叙述错误。每小题 2分.共 14分) 1.若每次从队列中取出的是具有最高优先权的元素，则称此队列为优先级队列。 ( ) ，,2.递归定义的数据结构通常不需要采用递归的算法对其运算。 ( ) 3.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件 把它逐层向下调整，直到调整到合适位置为止。 ( ) 4.对于一棵具有 n个结点、高度为 h的二叉树，进行任一种次序遍历的时间复杂度均为 O(n)。 ( ) 5.对于同一组记录集合，生成二叉搜索树的形态与插人记录的次序无关。 ( ) 6.装载因子是散列存储中的一个重要指标，它反映了散列表的装满程度。 ( ) 7.在一棵 B树中，所有叶结点都处在同一层上。 ( 〕 得 分 评卷人 四、运算题(每小题 6分，共 30分】 l.假定一棵二叉树的广义表表示为 A(以 ,D(G)),C(E,F))，分别写出对它 进行先序、中 序、按层遍历的结果 。 先序 : 中序: 按层 : 2.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储 于一维数组 a [12〕中，根据折半搜索过程填写成功搜索下表中所给元素34,56,58,63时的比较次数。 元素 比较次数 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}: 试根据普里姆算法从顶点0出发求出最小生成树，在下面填写依次得到的最小生成树中 的每条边。 5.设散列表的长度m=7;散列函数为H(K)=K mod m,给定的关键码序列为{19,14， 23,40,68},并假定采用的闭散列表为HT[m],采用的解决冲突的方法为线性探查法，求出在 最后得到的散列表中，关键码19、40和68的存储位置和对应的查找长度。 元素： 19 40 68 存储位置： 查找长度： 得 分 评卷人 五、算法分析题（每小题6分，共12分）】 l.设单链表结点的结构为LNode=(data,link),阅读下面函数，指出它所实现的功能。 int AA(LNode￥Ha){ /Ha为指向带表头附加结点的单链表的表头指针 int n=0; LNode p=Ha->>link; while(p){ n十+： p=p->link; return n; 算法功能： 73
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的存储位置和对应的查找长度。 元素 : 存储位置: 查找长度 : 19 40 68 得 分 评卷人 五、算法分析题【每小题 6分，共 12分) 1.设单链表结点的结构为 LNode=(data, link)，阅读下面函数，指出它所实现的功能。 int AA(LNode二Ha) ( //Ha为指向带表头附加结点的单链表的表头指针 int n=0; LNode * p= Ha一>link; while(p){ n++ ; P=P一>link; ) return n; } 算法功能: 73
2.阅读下面算法，写出算法功能。 LinkNode BB(LinkNode first) /irst为单链表的表头指针 if(first==NULL]first->link==NULL)return first; LinkNode p=first,*rl=first->link; p->link=NULL; while(rl！=NULL){ ListNode r2=r1->link; rl->link=p; p=rl; rl=r2; } return pi 算法功能： 得·分 评卷人 六、算法设计题（每小题6分，共12分） l.根据下面函数原型编写一个对一维数组A[]中的n个有序元素进行折半查找其值为 K的非递归算法，若查找成功则返回元素下标，否则返回一1。 int BinarySearch(ElemType A[],int n,ElemType K); 2.已知二叉树中的结点类型用BinTreeNode表示，定义为： struct BinTreeNode (char data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声 明编写出交换一棵二叉树中所有结点的左、右指针域值的递归算法，算法中参数BT初始指向 这棵二叉树的根结点。 void BTreeSwop(BinTreeNode BT); 74
2.阅读下面算法，写出算法功能。 LinkNode * BB(LinkNode * first) //first为单链表的表头指针 if(first= =NULL}}first一>link= =NULL) return first; LinkNode * p=first, * rl=first一>link; P一>link=NULL; while(rl!二NULL){ ListNode * r2二rl一>link; r1一>link= p; p=r1; rl二r2; return p } 算法功能 : 得 分 评卷人 六、算法设计题(每小题 6分，共 12分) 1.根据下面函数原型编写一个对一维数组A[司中的n个有序元素进行折半查找其值为 K的非递归算法，若查找成功则返回元素下标，否则返回一1, int BinarySearch(ElemType A[]，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.V 4.V 5.X 6.√ 7.V 四、运算题（每小题6分，共30分） 1.先序：A,B,D,G,C,E,F /2分 中序：B,G,D,A,E,C,F /12分 按层：A,B,C,D,E,F,G 112分 75
试卷代号:1010 中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试 计科网络、计科应用 计科硬件 专业 数据结构 试题答案及评分标准 (供参考) 2008年 7月 一、单项选择题(在括号内填写所选择的标号。每小题 2分.共 18分} 1.D 6. D 2.A 3. A 4. C 5. B 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.火 6.了 7.了 四、运算题(每小题 6分，共 30分) 1.先序 :A, B, D, G, C,E,F 中序 :B,G,D,A,E,C,F 按层 :A,B,C,D,E,F,G 3.训 4.训 5.X 刀2分 //2分 //2分 75
2.评分标准：对1个数据给1分，全对给6分 元素 34 56 58 63 比较次数 2 1 3 3.双支结点数：2 /2分 单支结点数：3 /2分 叶子结点数：3 /12分 4.(0,3)14,(3,4)18,(4,5)6,(5,1)5,(4,2)11 5.评分标准：每个数据的存储位置和查找长度正确各得1分，共6分。 元素： 19 40 68 存储位置： 5 6 1 查找长度： 2 4 五、算法分析题（每小题6分，共12分） 1.计算并返回单链表的长度。 2.逆序排列以fist为表头指针的单链表中的所有结点并返回新的表头指针。 六、算法设计题（每小题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<A[mid])high=mid-1; else low=mid+1; /5分 return -1; /6分 76
2.评分标准:对 1个数据给 1分，全对给 6分 元素 比较次数 3.双支结点数:2 单支结点数:3 叶子结点数:3 4. (0,3)14，(3,4)18，(4,5)6，(5，1)5，(4,2)11 5.评分标准:每个数据的存储位置和查找长度正确各得 1分，共 6分。 //2分 刀2分 刀2分 元素 : 存储位置 : 查找长度 : 19 40 68 5 6 1 1 2 4 五、算法分析题 (每小题 6分 ，共 12分) 1.计算并返回单链表的长度。 2.逆序排列以 first为表头指针的单链表中的所有结点并返回新的表头指针。 六、算法设计题 (每小题 6分 ，共 12分) 1.请根据编写的完整程度酌情给分。 int BinarySearch(ElemType A仁3，int n, ElemType K) { 刀对数组 A中的 n个有序元素进行折半查找 int low=0，high= n一1; while Gow<= high) { 刀1分 //2分 int mid=(low+high)/2; if(K=A[mid]) return mid; else if (K<A[mid])high=mid一1; else low-mid+l; //3 分 /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); /14分 //对右子树进行同样处理 BTreeSwop(BT->right); /16分 } 77
2.请根据编写的完整程度酌情给分。 void BTreeSwop(BinTreeNode‘BT) { if (BT!二NULL)( 刀交换左右子女指针域的值 BinTreeNode，pt=BT一>left; BT一>left =BT一>right; BT一>right=pt; 刀对左子树进行同样处理 BTreeSwop (BT一>left); 刀对右子树进行同样处理 BTreeSwop(BT一>right); } 刀1分 刀2分 刀4分 刀6分