试卷代号：1252 座位口 中央广播电视大学2009一2010学年度第二学期“开放本科”期末考试 数据结构（本）试题 2010年7月 题 号 二 三 四 总 分 分 数 得分 评卷人 一、单项选择题（每小题2分，共30分）】 1.从n个数中选取最大元素()。 A.基本操作是数据元素间的交换 B.算法的时间复杂度是O(n) C.算法的时间复杂度是O(n) D.需要进行(n十1)次数据元素间的比较 2.设head为非空的单向循环链表头指针，p指向链表的尾结点，则满足逻辑表达式 )的值为真。 A.p->next=NULL B.p==NULL C.p->next=head D.p->next==head 3.设顺序存储的线性表长度为n,要删除第i个元素，按课本的算法，当i=( )时，移 动元素的次数为3。 A.3 B.n/2 C.n-3 D.3 4.一个栈的进栈序列是a,b,c,d,则栈的不可能的出栈序列是()。 A.adbc B.bcad C.cbad D.dcba 1353
试卷代号 2 5 2 座位号 中央广播电视大学 0 0 2010 二学 放本科 数据结构(本)试题 2010 年7 题号 总分 分数 得分|评卷人 一、单项选择题(每小题 2分，共 0分) 1.从 个数 选取最 )。 A. 基本操作是数据 间 的 B.算法的时间复杂度是 C. 算法 杂度是O(n) D. 需要进行 1) 数据 2. 设head 非 空 头 指 针 ，p ( )的值为真。 A. 一>next=NULL c. 一>next=head B. p= =NULL D. next = = head 3. 线性表长 除第 课本 ( )时，移 动元素的次数为 A. 3 C. n-3 B. n/2 D. 3 4. 进战序 ，b ，d 可能 )。 A. adbc C. cbad B. bead D. dcba 1353
5.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成， front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值，p为 指向结点类型的指针，可执行如下操作：p=front一>next;x=p一>data;然后执行()。 A.front=p->next; B.front->next=p->next; C.front=p; D.front->next =p; 6.在C语言中，存储字符串“ABCD”需要占用()字节。 A.4 B.2 C.5 D.3 7.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储 到一维数组b中。（矩阵A的第一个元素为a1,1,数组b的下标从1开始），则矩阵元素a5,3对 应一维数组b的数组元素是()。 A.b[18] B.b[8] C.b[13] D.b[10] 8.深度为5的完全二叉树共有20个结点，则第5层上有( )个结点。（根所在层为第 一层) A.3 B.8 C.5 D.6 9.已知一个图的所有顶点的度数之和为m,且m是以下4种情况之一，则m只可能是 () A.9 B.7 C.15 D.8 10.线性表只要以( )方式存储就能进行折半查找。 A.链接 B.顺序 C.关键字有序的顺序 D.二叉树 11.对n个元素进行冒泡排序若某趟冒泡中只进行了( )次元素间的交换，则表明序 列已经排好序。 A.1 B.2 C.0 D.n-1 1354
5. 一个带 队列 队列 个结 个数 域data 域next front 和rear 队列 指针 尾指针 用x 保存 ，p 指向结点类型的指针，可执行如下操作 t一 p一 ;然后执行( )。 A. front=p一>next; C. front= B. front 一>next=p 一>next; D. front•>next =p; 6. 在C 串"ABCD"需要 )字节。 A. 4 B. 2 C. 5 D. 3 7. 有一个10 阵A 采 用 存储方 将其 存储 到一维数组 b中。(矩阵 A的第一个元素为 ，数组 b的下标从 ，则矩阵元素衔 3对 应一维数组 b的数组元素是( )。 A. b[18] B. b[8] C. b[13] D. b[10] 8. 为5 全二叉树共有20 个结 第5 )个结点。(根所在层为第 一层) A. 3 C. 5 B. 8 D. 6 9. 和 为 下4 况之 可能 ( ) A. 9 C. 15 B. 7 D. 8 10. )方式存储就能进行折半查找。 A. B. )1 C. 字有 序D. 二叉 1 1. 个元 某 趟 )次元素间的交换，则表明序 列已经排好序。 1354 A. 1 c. 0 B. 2 D. n-1
12.在对一组元素(64,48,106,33,25,82,70,55,93)进行直接插人排序时，当进行到要把 第7个元素70插入到已经排好序的子表时，为找到插入位置，需进行( )次元素间的比较 (指由小到大排序)。 A.6 B.2 C.3 D.4 13.如图，若从顶点a出发按广度优先搜索法进行遍历， 则可能得到的顶点序列为()。 A.acebdgf B.abecdgf C.acfedgb D.abecfdg 14.一棵哈夫曼树有10个非叶子结点（非终端结点），该树总共有()个结点。 A.21 B.20 C.22 D.19 15.队列的插入操作在( )进行。 A.队头 B.队尾 C.队头或队尾 D.在任意指定位置 得 分 评卷人 二、填空题（每小题2分，共24分） 1.通常可以把某城市中各公交站点间的线路图抽象成结构。 2.要在一个单向链表中删除p所指向的结点，已知q指向p所指结点的直接前驱结点， 若链表中结点的指针域为next,则可执行 3.设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要人栈，则可执行操作 和hs=s; 1355
12. 在对一组 素(64 ，48 ，106 ，33 ，25 ，82 ，70 ，55 ，93) 进行直接插入 个元 插入 经排 子表 位 置 需进 )次元素间的比较 (指由小到大排序)。 A. 6 C. 3 B. 2 D. 4 13. 若从 搜 索法进行遍历 则可能得到的顶点序列为( )。 A. acebdgf B. abecdgf C. acfedgb D. abecfdg 14. 有10 子结 端结 ，该树总共有( )个结点。 A. 21 B. 20 C. 22 D. 19 15. 插入 )进行。 A. 队头 B. c.队头或队尾 D. 在任 位置 得分|评卷人 二、填空题(每小题 1.通常可以把某城市中各公交站点间的线路图抽象成结构。 2. 在一个单 链表 所 指 所 指 若链表中结点的指针域为时 t，则可执行 3. 链 拢 顶 指 为hs 有 一 个s 可 执 行 操 1355
4.在一个不带头结点的非空链队中，f和r分别为队头和队尾指针，队结点的数据域为 data,指针域为next,若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为 5.顺序存储字符串“ABCD”需要占用 个字节。 6.一棵二叉树叶结点（终端结点）数为5，单分支结点数为2，该树共有 个结点。 7.设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点 的编号为10，该完全二叉树一共有个结点。 8.结构中的数据元素存在一对多的关系称为 结构。 9.结构中的数据元素存在一对一的关系称为 结构。 10.如图2所示的二叉树，其后序遍历序列为 a h 图2 11.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是 的。 （回答正确或不正确) 12.按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保持它 们的前后关系，则排序算法是稳定的，否则是不稳定的。 1356
4. 不带 为 队 头 数据 data 为next 进行 量x 数据 则 相 • , 5. 存储 串"ABeD"需要 个字节。 6. 叉树 端结 为5 为2 该树共 个结点。 7. 二叉 右边 节 点 的编号为 0，该完全二叉树一共有 个结点。 8. 9. 存在 对一 10. 图2 后序 g 结构。 结构。 1 1. 图 的 优 先 广 度 不 一 定 是 (回答正确或不正确) 12. 键字对记 们的前后关系，则排序算法是稳定的，否则是不稳定的。 的记录在排序前和排序后仍保持它
得 分 评卷人 三、综合题（每小题10分，共30分） 1.（1)一组记录的关键字序列为{45,40,65,43,35,95}写出利用快速排序的方法，以第一 个记录为基准得到的一趟划分的结果（要求给出一趟划分中每次扫描和交换的结果）。 (2)同样对序列{45,40,65,43,35,95}利用直接插入排序，写出逐次插入过程（从第一个元 素一直到第六个元素)。 2.(1)利用筛选过程把序列{42,82,67,102,16,32,57,52}建成堆（小根堆），画出相应的完 全二叉树（不要求中间过程）。 (2)写出对上述堆对应的完全二叉树进行中序遍历得到的序列。 3.(1)设有一个整数序列{50,38,16,82,110,13,64}，依次取出序列中的数，构造一棵二叉 排序树。 (2)利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找 15,经多少次元素间的比较可知道查找失败。 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针。 struct node { ElemType data; struct node next; }； struct node top void Push(ElemType x) { struct node p; p=(struct node *)malloc((1) p->data=x; 1357
得分|评卷人 三、综合题(每小题 0分，共 0分) 1. (1)一组记录的关键字序列为 5， 40， 5， 4 3， 5， 9 5 }写出利用快速排序的方法，以第一 个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果)。 (2) ，40 ，65 ，43 ，35 ，95} 利用直 插入 第 一 素一直到第六个元素)。 2. (1)利用筛选过程把序列 2， 8 2， 7， 2， 6， 2， 7， }建成堆(小根堆儿画出相应的完 全二叉树(不要求中间过程)。 (2) 上述 全二叉树进行 序列 3. (1)设有一个整数序列 0， 8， 6， 2， 0， 3， }，依次取出序列中的数，构造一棵二叉 排序树。 (2) 上述二叉排 找110 次元 间 的 15 经多 可知道查找失 !得分|评卷人 四、程序填空题(每空 2分，共 6分) 1.以下函数为链校的进技操作， x是要进战的结点的数据域， top 找顶 struct node { ElemType data; struct node 铃next; struct node 祷top; void Push(ElemType x) struct node 铸p; p= (struct node 头)malloc«l) 一>data=Xj 1357
(2) (3) 2.以下函数在head为头指针的具有头结点的单向链表中删除第i个结点。 struct node int data; struct node next; }; typedef struct node NODE int delete(NODE head,int i NODE*p,￥q; int j; q=head; j=0; while((g!=NULL)&.&.((1) { (2) j十+； if(q==NULL) return(0); p=(3) (4) free((5) return(1); 3 1358
(2) (3) • , • , 2. 在head 指针 第i 结点 struct node { int data; struct node 铃next; typedef struct node NODE int delete(NODE 祷head，int i ) NODE 祷p 头q; n -] q=head; j=05 while( (q! =NULL) &.&.( (1) » (2) 十 十 ; if(q= =NULL) return(O) ; p=(3) (4) • , =p 一>next; free( (5) return (1 ) ; 1358
试卷代号：1252 中央广播电视大学2009一2010学年度第二学期“开放本科”期末考试 数据结构（本）试题答案及评分标准 (供参考) 2010年7月 一、单项选择题（每小题2分，共30分）》 1.C 2.D 3.C 4.A 5.B 6.C 7.C 8.C 9.D 10.C 11.C 12.C 13.B 14.A 15.B 二、填空题（每题2分，共24分） 1.图状 2.q->next=p->next; 3.s->next=hs; 4.x=f->data f=f->next; 5.5 6.11 7.21 8.树形 9.线性 10.gdbeihfca 11.正确 12.相等 三、综合应用题（每小题10分，共30分） 1.(1)454065433595 354065433595 354065436595 354043436595 354043456595 (2)404565433595 404345653595 354043456595 1359
试卷代号 中央广播电视大学 0 0 2010 二学 开放 数据结构(本)试题答案及评分标准 (供参考) 2010 年7 f=f 一>next; -、单项选择题(每小题 1. C 2. D 3. C 6.C 7.C 8.C l 1. C 12.C 13.B 二、填空题(每题 2 4 1.图状 2. 一>next; 3. s->next=hs; 4. x=f 一>data 5. 5 6. 11 7. 21 8. 9. 10. gdbeihfca 1. 12. 相等 三、综合应用题(每小题 1. (1 ) 45 40 65 43 困95 35 40 65 43 35 95 35 40 囹43 65 95 35 40 43 囹65 95 35 40 43 45 65 95 (2) 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 95 4. A 9.0 14. A 5. B 10. C 15. B 1359
2.(1) 42 16 82 67 AZ 32 102 16 32 57 52 82 67 57 52 102 初始树 堆 (2)102,52,42,82,16,67,32,57 3.(1) 50 38 82 16 64 110 13 (2)三次；四次 四、程序填空题（每空2分，共16分） 1.(1)sizeof (struct node) (2)p->next=top (3)top=p 2.(1)jnext (3)q->next (4)q->next (5)p 1360
2. (1) 初始树 (2)102 ,52 ,42 ,82 ,16 ,67 ,32 ,57 3. (1) (2) 三次 四、程序填空题(每空 1. (1)sizeof (struct node) (2)p 一>next=top (3hop=p 2. (1 )jnext (3)q- >next (4)q- >next (5)p 1360