试卷代号：1252 座位号■■ 中央广播电视大学2013一2014学年度第一学期“开放本科”期末考试 数据结构（本）·试题 2014年1月 题 号 二 三 四 总分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.在数据结构和算法中，与所使用的计算机有关的是( )。 A.数据元数间的抽象关系 B.数据的存储结构 C.算法的时间复杂度 D.数据的逻辑结构 2.对顺序表，以下叙述中正确的是( )。 A.用一组地址连续的存储单元依次存放线性表的数据元素 B.各个数据元素的首地址是连续的 C.数据元素不能随机访问 D.插人操作不需要移动元素 3.设有一个长度为25的顺序表，要删除第10个元素（下标从1开始），需移动元素的个 数为()。 A.9 B.10 C.15 D.16 4.设单向链表中，指针p指向结点A,若要删除A的直接后继，则所需修改指针的操作为 )。 A.p->next=p->next->next; B.p=p->next; C.p=p->next->next; D.p->next=p 1091
试卷代号 座位号CD 中央广播电视大学 4学年度第一学期"开放本科"期末考试 数据结构{本)试题 2014 年1 题号|一|二|三|四|总分| |分数 'I I I II |得分|评卷人 11 项选择题 1.在数据结构和算法中，与所使用的计算机有关的是( )。 A.数据元数间的抽象关系且数据的存储结构 C. 算法 杂度 D. 逻辑 2. A. 址连续 储单元依次存放 B. 各个数 地址是连续 据元 D. 插入 需要 3. 有一个长 为25 删 除第10 下标从1 ，需移动元素的个 、数为( )。 A. 9 C. 15 B.10 D.16 4. 设单 指针 点A 除A 后继 指针 ( )。 A.p一>next=p->next 一>next; c. p=p 一>next->next; B.p=p 一>next; D.p 一>next=p; 1091
5.元素1,3,5,7按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的可能输 出序列是( )。(进栈出栈可以交替进行) A.7,5,3,1 B.7,3,1,5 C.7,5,1,3 D.5,1,3,7 6,对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行()。 A.p=top->next;top=top-next; B.p->next=top; C.p->next=top;top=p; D.top=p; 7.设有一个18阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是()。 (矩阵中的第1个元素是a11) A.a1,6 B.a10,8 C.a9.2 D.a8,5 8.设有一个17阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中（数组下标从1开始），则矩阵中元素1o,6在一维数组B中的下标是()。 (矩阵中的第1个元素是a.) A.45. B.18 C.51 D.53 9.串函数StrCmp(“ABCd”,“ABCD”)的值为(t)。 A.0 B.-1 C.1 D.3 10.一棵采用链式存储的二叉树中有个指针域为空，该二叉树共有( )个结点。 A.n+1 B.n C.n-1 D.n-2 11.设一棵哈夫曼树共有n个非叶结点，则该树有( )个结点。 A.2n B.2n+2 C.2n-1 D.2n+1 12.一棵结点数31<n<40的完全二叉树，最后一层有4个结点，则该树有()个叶结 点。 A.18 B.17 C.36 D.35 1092
5. 素1 ，3 ，5 ，7 按顺 依次进钱 按该 队列 能输 出序列是( ). (进找出钱可以交替进行〉 A.7 ,5,3. 1 C.7 ,5,1.3 B.7 ,3 ,1 ,5 D.5 ,1. 3,7 6. 战顶 为top 钱进行进校 设P 待进 执行 )。 A. p=top一>next; top=top•next; B. p->next=top; C.p一>next=top;top=p; D. top=p; 7. 有一 阶的 阵A 压缩存 方式 下三 序为主 到一维数组B中(数组下标从 开始 .则数组中第 3号元素对应于矩阵中的元素是()。 (矩阵中的第 1个元素是 A. a1.6 C. a9.2 B. alO. S D. as.s 8. 称矩 压缩存储 将其 部分 存储 到一维数组 B中〈数组下标从 .则矩阵中元素 6在一维数组 B中的下标是( )。 〈矩阵中的第 1个元素是 A.45. B.18 C.51 D.53 9. 数StrCmp("ABCd" ABCD勺 的 )。 A.O B. 一1 C. 1 D.3 10. 指针 二叉 )个结点。 A.n C. n-l B.n D.n 1. 夫曼树 该树 )个结点。 A.2n C.2n-1 B.2n+2 D.2n+l 12. 一棵结 数31<n<40 有4 该树 )个叶结 点。 1092 A.18 C.36 B.17 D.35
13.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为()。 b 图1 A.abedfc B.acfebd C.aebefd D.aedfbc 14.一组记录的关键字序列为(46,20,30,79,56,38,40,84,90,110)，利用快速排序，以第 一个关键字为分割元素，经过一次划分后结果为(·)。 A.20,30,40,38,46,79,56,84,90,100 B.40,20,30,38,46,56,79,84,90,110 C.30,20,40,38,46,84,56,79,90,100 D.20,3038,40,46,56,79,84,90,100 15.一组记录的关键字序列为(75,63,95,80,53,45,38,20)，利用堆排序（堆顶元素是最 大元素)的方法建立的初始堆为()。 A.95,80,75,63,53,45,38,20 B.95,63,75,80,53,45,38,20 C.95,80,45,63,53,75,38,20 D.95,80,75,20,53,45,38,63 得 分 评卷人 二、填空题（每小题2分，共24分）】 16.数据元素之间的抽象关系称为 结构。 17.要求在n个数据元素中找值最大的元素，其基本操作为 算法的时间复杂度为 1093
13. 知如 图1 进行遍历 则 可 能得 到的一种顶点序列为〈 A. abedfc c. aebefd B. acfebd D. aedfbc 14. 一组记录 字序 为(46 ，20 ，30 ，79 ，56 ，38 ，40 ，84 ，90 ，110) 用快速 一个关键字为分割元素，经过一次划分后结果为( )。 A.20 ,30 ,40 ,38 ,46 ,79 ,56 ,84 ,90 ,100 B.40 ,20 ,30 ,38 ,46 ,56 ,79 ,84 ,90 ,110 C.30 ,20 ,40 ,38 ,46 ,84 ,56 ,79 ,90 ,100 D.20 ,3038 ,40 ,46 ,56 ,79 ,84 ,90 ,100 15. 一组 为(75 ，63 ，95 ，80 ，53 ，45 ，38 ，20) 堆排 堆顶 是最 大元素〉的方法建立的初始堆为( )。 A.95 ,80 ,75 ,63 ,53 ,45 ,38 ,20 B.95 ,63 ,75 ,80 ,53 ,45 ,38 ,20 C. 95 , 80 , 45 , 63 , 5!, 75 , 38 , 20 D.95 , 80 ,75,20 ,53 ,45 ,38,63 |得分|评卷人| I I I 二、填空题{每小题 2 4 16. 据元 间 的 象关 17. 求在 数据 本操 算法的时间复杂度为 1093
18.设有一个长度为25的顺序表，第8号元素到第25号元素依次存放的值为8,9,10， 11,…,25,某人想要副除第8个元素，他的做法是从第25号元素开始，直到第9号元素依次 向前移动1个位置，其结果新表中第9号元素的值为 19.在双向链表中，要在p所指的结后插人q所指的结点（设q所指的结点已赋值），可以 先用语句q一>next=p一>next;(p一>next)一>prior=q:然后再用语句q一>prior=p; 和语句一。 20.在一个单向链表中，要副除P所指结点的直接后继结点。则可以用操作 。(用一条语句) 21.向一个栈顶指针为top的链栈中插人一个P所指结点时，可执行 操作。（填两条语句，结点的指针域为next) 22.在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则别除一个结点 的操作为p=front一>next: =p一>next;(结点的指针域为 next,p为辅助用指针) 23.设有n阶对称矩阵A,用一维数组s压缩存储A的下三角元素，s的下标从零开始，最 后一个元素的下标为27，则n= 。(矩阵中的第1个元素是a1:) 24.一棵3度的树，其中3度结1个，2度结，2个，1度结2个，则该树共有 个叶 结点。 25.一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有 个 结点 26.如图2所示的二叉树，其中序遍历序列为 5 6 9 图2 1094
18. 一个长度为25 序表 第8 素到第25 号元 存放 为8 ，9 ，10 11 想要删 除第8 2 5 第9 向前移动 1个位置，其结果新表中第 9号元素的值为 19. 在双 链表 要在 结后插 ，可以 先用语句 q一 p一 (p 一>next) 一>prior=q; 然后 句q一>prior=p; 和语句 20. 删除 指结点 后继 • (用一条语句〉 1. 一个钱顶 所指结点 时 操作。(填两条语句，结点的指针域为 t ) 22. 在一 为 队 和 队 指针 的操作为 t一 =p 一>next; (结点的指针域为 next, 助用指针 23. 称矩阵A 压缩 储A 下三 标从 开始 后一个元素的下标为 7，则 • (矩阵中的第 1个元素是 24. 棵3 中3 结1 ，2 结2 ，1 结2 结点. 25. 有7 其1 个数为2 结点 26. 图2 1094
27.二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非 空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点 的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是·的。 (回答正确或不正确) 得 分 评卷人 三、综合题（每小题10分，共30分】 28.(1)以3,4,5,8,9,10作为叶结点的权，构造一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。 (3)一棵哈夫曼树有2-1个结点，它是共有多少个权重值构造而成的？简述理由？ 29.(1)简述拓扑排序的步骤。 (2)说明有向图的拓扑序列不一定是唯一的原因。 (3)如何利用拓扑排序算法判定图是否存在回路。 (4)设有向图G如下，写出首先删除顶点1的3种拓扑序列。 图3 30.设有序表为(21,22,23,24,25,26,27,28,29,30,31,32)，元素的下标从0开始。 (1)说出有哪几个元素需要经过4次元素间的比较才能成功查到。 (2)画出对上述有序表进行折半查找所对应的判定树（树结点用数值表示） (3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 (4)求在等概率条件下，成功查找的平均比较次数？ 1095
27. 树或者是一 有 下 列 排z 空，则左子树的所有结点的值都小于它的根结点的值$若它的右子树非空， Jt~右子的所有结点 的值都大于(若允许结点有相同的值，则大于等于〉它的根结点的值。这种说法是--'"的。 〈回答正确或不正确〉 |得分|评卷人| I I I 三、综合题{每小题 28. (1)以 造一 (2) 应权 夫曼 (3) 一棵 夫曼树有 是共 构造而 29. (1)简述拓扑排序的步骤。 (2) 不一定 (3) 用拓扑 (4) 图G 点1 的3 扑序 30. 为(21 ，22 ，23 ，24 ，25 ，26 ，27 ，28 ，29 ，30 ，31 ，32) 从O 开 (1)说出有哪几个元素需要经过 4次元素间的比较才能成功查到。 (2) 表进行折半查 所对 定树 点用 (3) 为5 间 的 确定 (4) 求在 条件 功查 平均 1095
得分 评卷人 四、程序填空题（每空2分，共16分） 31.以下程序是快速排序的算法 设待序的记录序列存放在a[start],…a[end]中，按记录的关健字进行快速排序，先进行 一次划分，再分别进行递归调用 void quicksort NODE a[]int start ,int end int i,j; NODE mid if (start>=end return; i=start; j=end; mid=ai]; while (imid.key) j-; if(i<j) {a[i]=a[j]; while(i<j&&.a[i].key<=mid.key) if(<j) 1096
|得分|评卷人! I I I 四、程序填空题{每空 1. 下程序是快 算法 设待序的记录序列存放在 ，… [ e J中，按记录的关键宇进行快速排序，先进行 一次划分，再分别进行递归调用 void quicksort ( NODE a[ ], int start ,int end) 5·J n , ··A NODE mid; if (start> = end ) return; i=start; j=end; mid=a[i]; while Omid. key) ifO<j) a[i]=a[j] , whi1eO<j &.&. a[i]. key<=mid. key) ifO<j) 1096
aCi]=mid; quicksort (a,stat,i-1); quicksort 32.以下函数为链队列的人队操作，x为要人队的结点的数据域的值，front、rear分别是 链队列的队头、队尾指针 struct node ElemType data; struct node next; }； struct node front,rear; void InQueue(ElemType x) { struct node *p; p=(struct node * p->data=x; p->next=NULL; rear= 1097
a[i]=mid; quicksort (a ,stat, i-I) ; quicksort 32. ，x 数据 front、rear 别是 链队列的队头、队尾指针 struct node ElemType data; struct node 铸next; struct node 铸front 椅rear; void InQueue(ElemType x) struct node 必p; p= (struct node 一>data=x; p->next= NULL; rear= 1097
试卷代号：1252 中央广播电视大学2013一2014学年度第一学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2014年1月 一、单项选择题（每小题2分，共30分）】 1.B 2.A 3.C 4.A 5.A 6.C 7.D 8.C 9.C 10.C 11.D 12.A 13.A 14.B 15.A 二、填空题（每题2分，共24分】 16.逻辑 17.元素间的比较0(n) 18.25 19.p->next=q; 20.p->next=p->next->next; 21.p->next=top;top=p; 22.front->next 23.7 24.5 25.15 26.512389746 27.不正确 三、综合应用题（每小题10分，共30分） 28.(1) 22 12 10 图4 1098
试卷代号 中央广播电视大学 01 4学年度第一学期"开放本科"期末考试 数据结构〈本〉试题答案及评分标准 (供参考) 2014 年1 一、单项选择题{每小题 1. B 2.A 3.C 6. C 7. D 8. C l 1.D 12.A 13.A 二、填空题{每题 16. 17. 较O(n) 18.25 19.p一>next=q; 20.p一>next=p一>next一>next; 21. 一>next=top; top=p; 22. front 一>next 23.7 24.5 25.15 26.512389746 27. 不正 三、综合应用题{每小题 28. (1) 4.A 9.C 14. B 5.A 10. C 15. A 1098
(2)3 0000 4 0001 购 001 10 01 810 911 (3)个，因为非叶结点数比叶结点数少一个，而权值个数=叶结点数 29.(1)循环执行以下两步 选择一个度为0的顶点并输出 从网中删除此结点及所有出边 (2)因为选择一个度为0的顶点时不一定是唯一的 (3)由顶点活动网构造拓扑序列的过程中，输出结点后，余下的结点均有前驱 (4)152364152634 156234 30.(1)5 (2) 26 23 21 24 27 22 25 28 32 图5 (3)3 (4)ASL=(1+2*2+3*4+5*4)/12=37/12 四、程序填空题（每空2分，共16分） 31.(1)i++; (2)i++; 。 (3)aj]=a[]; (4)j--; (5)(a,i+1,end); 32.(1)malloc(sizeof (struct node)) (2)rear->next=p (3)p 1099
(2)3 0000 4 0001 5 001 10 01 8 10 9 11 (3)n 结点 少一 个数 29. (1)循环执行以下两步 选择一个度为 O的顶点并输出 从网中删除此结点及所有出边 (2) 为O 点 时 一定是 (3) 点活动 拓扑 点后 (4) 152364 152634 156234 30. (1) 5 (2) (3) 3 (4) ASL= (l 7 / 四、程序填空题{每空 31. (1) (2) 十 十 (3) aCi]=a[i]; (4) (5) (a , i+1 ,end) ; 32. (l)malloc( sizeof (struct node» (2 )rear 一>next=p (3)p 1099