试卷代号：1010 座位■■ 中央广播电视大学2010一2011学年度第一学期“开放本科”期末考试 数据结构 试题 2011年1月 题 多 三 四 五 总 分 分 数 得分 评卷人 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1.执行下面程序段时，S语句的执行次数为( )。 for(int i=1;ilink==NULL; C.first->link==first; D.first!=NULL; 74
试卷代号 座位号 中央广播电视大学 2 0 2011 度第 一学期 期末考试 数据结构试题 2011 年1 总分 分数 得分|评卷人 一、单项选择题，在括号内填写所选择的标号(每小题 2分，共 8分) 1.执行下面程序段时， s语句的执行次数为( )。 forCint i= 1; i link= = NULL; C. first- >link= =first; D. first! = NULL; 74
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 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.向一棵二叉搜索树插入一个元素后，该树中的叶子结点数比插人前一定()。 A.增加 B.减少 C.相等 D.不减少 8.为了实现图的广度优先搜索遍历，其算法使用的一个辅助数据结构是()。 A.栈 B.队列 C.二叉树 D.树 9.在一棵5阶B树中，每个结点最多允许有()个关键码。 A.2 B.3 C.4 D.5 75
4. 若让元 1，2 ，3 依次 钱次序不 )种情况。 A. 3 ,2 ,1 B.2 ,1 ,3 C. 3 , 1,2 D. 1 ,3 ,2 5. )个分支结点。 A. n-1 B. n/2 C. n/2 十1 D. n/2-1 6. 搜索 概率相 等 在 长 序 表 平均搜 度为( )。 A. n B. C. (n- 1)/ 2 D. (n+1)/2 7. 二叉 个元 一定 )。 A. B. 减少 c.相等 。.不减少 8. 广度优先搜索遍 法使用 数据结构是 )。 A. B. c.二叉树 D. 9. 棵5 阶B 树 每 个 )个关键码。 A. 2 C. 4 B. 3 D. 5 75
得 分 评卷人 二、判断题，在每小题后面的括号内打对号（√）表示叙述正确或打叉 号(×)表示叙述错误（每小题2分，共14分）】 10.若每次从队列中取出的是具有最高优先权的元素，则称此队列为优先级队列。 ( ) 11.递归定义的数据结构通常不需要采用递归的算法对其运算。() 12.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件 把它逐层向下调整，直到调整到合适位置为止。() 13.对于一棵具有个结点、高度为h的二叉树，进行任一种次序遍历的时间复杂度均为 O(n)。() 14.对于同一组数据元素，生成二叉搜索树的形态与插入元素的次序无关。() 15.装载因子是散列存储中的一个重要指标，它不能反映散列表的装满程度。() 16.在一棵B树中，所有叶结点都处在同一层上。() 得 分 评卷人 三、填空题，在横线处填写合适的内容（每小题2分，共14分） 17.在类的继承结构中，位于上层的类叫做基类或父类，而位于下层的类叫做派生类或 类。 18.设链栈中结点的结构为(dat,link),栈顶指针为top,当从该链栈删除-一个结点时，应 把 的值赋给top。 19.广义表的 定义为广义表中括号被嵌套的最大重数。 20.在一棵高度为3的完全二叉树中，最少含有 个结点。假定树根结点的高度 为0。 21.从有序表(12,18,30,43,56,78,82,95)中折半搜索56元素时.其搜索长度为 22.具有n个顶点的连通图中至少包含有条边。 23.假定一个数据集合为{46,79,56,38,40,84}，则在构成的最大堆（即大根堆）中，其堆 顶元素为 76
得分|评卷人 二、判断题，在每小题后面的括号内打对号 -J 确 或打 l表示叙述错误(每小题 2分，共 4分) 10. 次从 队 列 优先 队 列 ( ) 1. 通 常 需要采 用 法对其运算 ) 12. 一 个最 删 除一 个 素 时 尾 元 堆 顶 位置 把它逐层向下调整，直到调整到合适位置为止。( ) 13. 棵具 度 为h 二叉 进 行任→ 种 杂 度 O(n)o ( ) 14. 一组数据元 形态 插入元 次序元 ) ] 5. 个重要 列 表 满 程 。 ( ) 16. 一层 上 ) 得分|评卷人 三、填空题，在横线处填写合适的内容(每小题 2分，共 4分) 17. 于 上 类 或 父 类 类。 18. 设链 l i ，找顶指针为 p，当从该链战删除)个结点时，应 的值赋给 o p 19. 义 为 号被 大重 20. 在一 完 全 叉 树 高 度 1. 有序表(12 ，18 ，30 ，43 ，56 ，78 ，82 ，95) 折半 索56 22. 具 有 1Y 包 含 23. 假定一个数 为{46 ，79 ，38 ，40 ，84} 根 堆 顶元素为 76
得 分 评卷人 四、运算题（每小题8分，共40分） 24.假定一棵二叉树的广义表表示为A(B(,D(G),C(E,F)),分别写出对它进行先序、 中序和按层遍历的结果。 先序： 中序： 按层： 25.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数 组[12]中，根据折半搜索过程填写成功搜索下表中所给元素34、56、74、83时的比较次数。 元素 34 56 74 83 比较次数 26.假定一个线性表为(56,27,34,95,73,16,50,62)，根据此线性表中元素次序生成一 棵二叉搜索树，分别求出该二叉搜索树中的单分支结点数和双分支结点数。 单分支结点数： 双分支结点数： 27.已知一个带权图的顶点集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}; 试根据普里姆算法，从顶点1出发，求出其最小生成树，在下面横线上填写依次得到的最 小生成树中的每条边。 28.设散列表的长度m=7;散列函数为H(K)=K mod m,给定的关键码序列为{19,14， 23,40,69},并假定采用的闭散列表为HT[],采用的解决冲突的方法为线性探查法，求出在 最后得到的散列表中，关键码19、14和69的存储位置和对应的查找长度。 元素： 19 14 69 存储位置： 查找长度： 77
得分|评卷人 四、运算题(每小题 8分，共 0分) 24. 定→棵二叉树 表表示 进行先 中序和按层遍历的结果。 先序: 中序: 按层: 25. 有 序 表 (15 ，26 ，34 ，39 ，56 ，58 ，63 ，74 ，76 ，83 ，94) 存 储 2 ] 根据折半搜索 程填写 功搜 下表 3 4 较次 元素 I 56 74 83 比较次数 26. 假定一个线性 为(56 ，27 ，34 ，95 ，73 ，16 ，50 ，62) 根据 次序 棵二叉搜索树，分别求出该二叉搜索树中的单分支结点数和双分支结点数。 单分支结点数: 双分支结点数: 27. 知 一 带权 图 的 边集 别 为 V={O ,I ,2 ,3 ,4 ,5}; E= { (0 , 1) 19 , (0 ,2) 21 , (0 ,3) 14 , (l , 2) 16 , (l , .5) 5 , (2 ,4) 11 , (3 , 4) 18 , (4 ,5) 6 }; 试根据普里姆算法，从顶点 1出发，求出其最小生成树，在下面横线上填写依次得到的最 小生成树中的每条边。 , ' , , 77
得分 评卷人 五、算法分析题（每小题7分，共14分） 29.设rear是以循环链表表示的队列的队尾指针，EnLQueue函数实现把x插人到队尾 的操作。阅读下面算法，在划有横线的上面填写合适的内容。 void EnLQueue(ListNode *rear,ElemType x) ListNode p; p=new ListNode; /p指向动态分配的结点空间 p->data=x; p->link= rear->>link=p; }; 30.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (ElemType data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面算法定 义写出算法的功能。在此算法中，参数BT为初始指向一棵二叉树的树根指针。 int BTreeLeafCount(BinTreeNode BT) if(BT==NULL)return 0; else if(BT->left==NULL&&.BT->right==NULL)return 1; else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right); } 算法功能： 78
得分|评卷人 五、算法分析题(每小题 7分，共 4分} 29. 设rear 链表表示 列 的 ，EnLQueue 把x 的操作。阅读下面算法，在划有横线的上面填写合适的内容。 void EnLQueue(ListNode &. rear, EIemType x) ListNode 兴p; p= new List N ode ; p->data=x; p->Iink= rear- >link=p; • , lip 态 分 点空 • , 30. 知 二 型BinTreeNode 定义 struct BinTreeNode {EIemType data; BinTreeNode 祷left 长right; }; 其中 a为结点值域， left 和right 根据下 面 义写出算法的功能。在此算法中，参数 T为初始指向一棵二叉树的树根指针。 78 int BTreeL巳afCount(BinTreeNode 长BT) if(BT= = NULL) return 0; else ifCBT->left==NULL &.&. BT 一>right= =NULL) return 1; s巳 rn BTreeLeafCount(BT一>left)十BTreeLeafCount (BT一>right) ; 算法功能:
试卷代号：1010 中央广播电视大学2010一2011学年度第一学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2011年1月 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1.D 2.A 3.A 4.C 5.B 6.D 7.D 8.B 9.C 二、判断题，在每小题后面的括号内打对号（√）表示叙述正确或打叉号(×)表示叙述错误（每 小题2分，共14分) 10./(对) 11.×(错) 12./(对) 13.√（对） 14.×(错) 15.×(错) 16.√（对） 三、填空题，在横线处填写合适的内容（每小题2分，共14分） 17.子（继承） 18.top->link 19.深度 20.8 21.3 22.n-1 23.84 四、运算题（每小题8分，共40分） 24.先序：A,B,D,G,C,E,F /3分 中序：B,G,D,A,E,C,F /13分 按层：A,B,C,D,E,F,G /2分 25.元素 34 56 74 83 比较次数 2 2 3 /1得分 2分2分 2分 2分 79
试卷代号 中央广播电视大学 2011 年 度 第 一 学 期 末考 数据结构试题答案及评分标准 (供参考) 2011 年1 一、单项选择题，在括号内填写所选择的标号(每小题 2分，共 8分) 1. D 2. A 3. A 4. C 5. B 6. D 7. D 8. B 9. C 二、判断题，在每小题后面的括号内打对号 .J )表示叙述正确或打叉号( X )表示叙述错误(每 小题 2分，共 4分) 10. .J (对) 11. X( 12. .J (对) 13. .J (对) 14. X( 15. X (错) 16. .J (对) 三、填空题，在横线处填写合适的内容(每小题 2分，共 4分) 17. 继承 18. top->link 19. 20. 8 21. 3 22. n-1 23. 84 四、运算题(每小题 8分，共 0分) 24. 序:A ，B ，D ，G ，C ，E ，F 中序 按层 A， B， C， D， E， F， 25. 素34 比较次数 1/ 得分 1/3 /13 //2 56 74 1 2 分2 83 3 79
26.单分支结点数：3 /4分 双分支结点数：2 /14分 27.(1,5)5,(5,4)6,(4,2)11,(4,3)18,(3,0)14 /1得分：2分 2分 2分 1分 1分 28. 元素： 19 14 69 存储位置： 5 0 1 查找长度： 1 3 得分： 3分 3分 2分 五、算法分析题（每小题7分，共14分） 29.rear->link,rear=p /第1个空4分，第2个空3分 30.求出并返回树根指针为BT的一棵二叉树中叶子结点的总数。 /7分 80
26. 114 双分支结点数 114 27. (1, 5)5, (5 ,4)6 , (4 ,2)1 1, (4 ,3)18 , (3 ,0)14 II 28. 19 14 69 5 l 1 3 元素: 存储位置: 查找长度: 得分: 五、算法分析题(每小题 7分，共 4分) 29. rear 一>link 、rear=p I 30. 棵二 子结 1 1 80