试卷代号：1252 座位号 中央广播电视大学2011一2012学年度第一学期“开放本科”期末考试 数据结构（本） 试题 2012年1月 题 号 二 三 四 总分 分 数 得分 评卷人 一、单项选择题（每小题2分，共30分） 1.数据的物理结构()。 A.与数据的逻辑结构无关 B.仅仅包括数据元素的表示 C.只包括数据元素间关系的表示 D.包括数据元素的表示和关系的表示 2.从n个数中选取最大元素()。 A.基本操作是数据元素间的交换 B.算法的时间复杂度是O(n) C.算法的时间复杂度是O(n) D.需要进行(n十1)次数据元素间的比较 3.线性表的顺序结构中，()。 A.逻辑上相邻的元素在物理位置上不一定相邻 B.数据元素是不能随机访问的 C.逻辑上相邻的元素在物理位置上也相邻 D.进行数据元素的插人、删除效率较高 4.带头结点的单向链表为空的判断条件是( )(设头指针为head)。 A.head==NULL B.head->next==NULL C.head->next==head D.head！=NULL 5.线性结构中数据元素的位置之间存在( )的关系。 A.一对一 B.一对多 C.多对多 D.每一个元素都有一个直接前驱和一个直接后继 1346
试卷代号 座位号CD B. 仅仅 表示 D. 包括 据元 系 的 B. 是O(n D. 要进行也 1) 次数 中央广播电视大学 11 2学年度第一学期"开放本科"期末考试 数据结构(本)试题 2012 年1 |题号|一|二|三|四|总分| !分数 I I J I I |得分|评卷人|，题{每小题 2分，共 0分) I I 1.数据的物理结构( )。 A.与数据的逻辑结构无关 C. 据元 系 的 2. 取最大元 )。 A. 本操作是数据元 间 的 交换 C. 算法 是O(n) 3. 结构 )。 A. 逻辑上相邻 在物 置上不一定 B. 是不能随机 问 的 C. 逻辑上相邻 在物 位置 D. 行数据元 插入 4. 链表为 空 ) (设头指针为 )。 A. head= = NULL C. head->next= = head B. head->next= =NULL D. head! = NULL 5. 结构 )的关系。 儿一对一 旦一对多 C. D. 个元 个直接前 后继 1346
6.设顺序存储的线性表长度为，要删除第i个元素，按课本的算法，当i=()时，移 动元素的次数为3。 A.3 B.n/2 C.n-3 D.4 7.以下说法不正确的是()。 A,栈的特点是后进先出 B.队列的特点是先进先出 C.栈的删除操作在栈底进行，插入操作在栈顶进行 D.队列的插人操作在队尾进行，删除操作在队头进行 8.一个栈的进栈序列是a,b,c,d,则栈的不可能的出栈序列是( )。 A.adbc B.bcad C.cbad D.dcba 9.设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成， 设用x接收栈顶元素，则出栈操作为()。 A.x=top->data;top=top->next; B.top=top->next;x=top->data; C.x=top->next;top=top->data; D.top->next=top;x=top->data; l0.设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组 成，front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值， p为指向结点类型的指针，可执行如下操作：p=front->next;x=p->data;然后执行()。 A.front=p->next; B.front->next=p->next; C.front=pi D.front->next=p; 11.以下说法正确的是( )。 A.队列是后进先出 B.栈的特点是后进后出 C.栈的删除和插入操作都只能在栈顶进行 D.队列的删除和插人操作都只能在队头进行 12.在C语言中，存储字符串“ABCD”需要占用( )字节。 A.4 B.2 C.5 D.3 l3.串函数StrCmp(“abA”,“aba”)的值为( )。 A.1 B.0 C.“abAaba” D.-1 1347
)时，移 B. n/2 C. n-3 D. 4 6. 设顺 除第 动元素的次数为 A. 3 7. 不正 )。 A.榜的特点是后进先出 B. 队列 是先 c.枝的删除操作在战底进行，插入操作在战顶进行 入操作在 进行 删除操作 8. ，h ，d 钱序列 )。 A. adhc C. chad B. head D. dcha 9. 设top 是一 链榜 战顶 个数 域data 域next 组成 设用 x接收钱顶元素，则出钱操作为( )。 A. x=top->data;top=top->next; C. x=top->next;top=top->data; B. top=top->next;x=top->data; D. top->next= top; x= top->data; 10. 有一 带头 个数 域data 域next 成， fr t和 rea r分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值， 执行 作:p=front->next;x= p->data;然后执行 )。 A. front=p->next; C. front=p; B. frant->next= p->next; D. front->next=p; 1. 法正 )。 A. B. C. 插入操作都 在校顶进 D. 插入 12. 在C 语 存储字符 串"ABCD" )字节。 A. 4 C. 5 13. 串 函 数StrCmp("ahA" "aha A. 1 C. "ahAaba" B. 2 D. 3 )。 B. 0 D. -1 1347
14.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储 到一维数组b中。（矩阵A的第一个元素为a1,1,数组b的下标从1开始），则矩阵元素a5,3对 应一维数组b的数组元素是()。 A.b18] B.b[8] c.b[13] D.b[10] 15.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得 到的一种顶点序列为()。 A.abecdf B.acfebd C.aebcfd D.aedfcb 图 得 分 评卷人 二、填空题（每小题2分，共24分） 16.通常数据的逻辑结构包括集合、线性、 四种类型。 17.通常可以把某城市中各公交站点间的线路图抽象成 结构。 18.设有一个单向链表，结点的指针域为next,头指针为head,p指向尾结点，为了使该单 向链表改为单向循环链表，可用语句」 19.循环队列的队头指针为f,队尾指针为r,当 时表明队列已空。 20.设有一个链栈，栈顶指针为s,现有一个s所指向的结点要人栈，则可执行操作 和hs=s。 21.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next,则插人一个s 所指结点的操作为 ；r=S。 22.串的两种最基本的存储方式分别是 和 23.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为 24.两个串相等的充分必要条件是 25.一棵二叉树叶结点（终端结点）数为5，单分支结点数为2，该树共有个结点。 26.根据搜索方法的不同，图的遍历有 两种方法。 27.一个有序表{3,4,10,14,34,43,46,64,75,78,90,96,130}用折半查找法查找值为90 的结点，经 次比较后查找成功。 1348
14. 个10 阵A 压缩存 式将其下 存储 到一维数组 b中。(矩阵 A的第一个元素为 l，数组 b的下标从 ，则矩阵元素 3对 应一维数组 b的数组元素是( )。 A.b[18] B.b[8] c. b[13] D. b[lO] 15. 知如 图1 所示 点a 度优先搜索法 遍历 则 可 到的一种顶点序列为( )。 A. abecdf B. aefebd c. aebefd D. aedfcb |得分|评卷人| I I I 二、填空题{每小题 2分，共 4分) 16. 逻辑结构包 -一一 17. 城市 公交站点 一一一- 结构 18. 一个 为next 指针为head 尾结 使该单 向链表改为单向循环链表，可用语句 19. 循环队列 队头 指针 队列 20. 个链 指 针 现 有 则 可 执 行 1. 个链 ，f 为 队头 尾指 针域为next 所指结点的操作为 s。 22. 种最基本 存储方式分 23. 序 编 在左 右 孩 别 为 24. 相等 25. 棵二 为5 为2 该树 -- 个结 26. 据搜索方法 遍历 两种方法。 27. 表{3 ，4 ，10 ，14 ，34 ，43 ，46 ，64 ，75 ，78 ，90 ，96 ，130} 折半查 找法 为90 的结点，经次比较后查找成功。 1348
得分 评卷人 三、综合题（每小题10分，共30分）】 28.(l)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeac,试画出该二叉树。 (2)若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的），并恰好使该 树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系。 (3)给出该树的前序遍历序列。 29.(1)一组记录的关键字序列为{45,40,65,43,35,95}，写出利用快速排序的方法，以第 一个记录为基准得到的一趙划分的结果（要求给出一趟划分中每次扫描和交换的结果）。 (2)对序列{45,40,65,43,35,95}利用直接插人排序，写出逐次插人过程（从第一个元素一 直到第六个元素)。 30.(1)设有查找表{5,14,2,6,18,7,4,16,3}，依次取表中数据，构造一棵二叉排序树。 (2)说明如何通过序列的二叉排序树得到相应序列的排序结果。 得分 评卷人 四、程序填空题（每空2分，共16分） 31.以下函数在a[0]到a[n一1]中，用折半查找算法查找关键字等于k的记录，查找成功 返回该记录的下标，失败时返回一1，完成程序中的空格。 typedef struct int key; 4: }NODE; int Binary_Search(NODE a[],int n,int k) int low,mid,high; low=0; high=n-1; while ((1) 1349
|得分|评卷人| I I I 三、综合题{每小题 0分，共 0分} 28. (1)已知某二叉树的后序遍历序列是 a，中序遍历序列是 c，试画出该二叉树。 (2) 述二 各个 别代 有相 ，并恰好使该 树成为一棵二叉排序树，试给出 a、 b、 c、 d、 e的大小关系。 (3) 该树 遍历序列 29. (1)一组记录的关键字序列为 5， 0， 5， 3， 3 5， }，写出利用快速排序的方法，以第 一个记录为基准得到的一趟划分的结果(要求给出一趟划分中每次扫描和交换的结果〉。 (2) 列{45 ，40 ，65 ，43 ，35 ，95} 直接插 次插入过程 一个 直到第六个元素〉。 30. (1)设有查找表 5， 4， 2， 6， 8， 7， 4， 6， }，依次取表中数据，构造一棵二叉排序树。 (2) 二叉排 树得到相 排序结果 |得分|评卷人| I I I 四、程序填空题{每空 2分，共 6分) 1. 在a[O] 到a[n-1] 法查 关键字等于k 返回该记录的下标，失败时返回一 1，完成程序中的空格。 typedef struct int key; }NODE; int Binary_Search(NODE ，int n ,int k) int low ,mid,high; low=O; high=n-1; while «1) 1349
mid=(low+high)/2; if(a [mid].key==k) return(2) else if((3) low=mid+1; else(4) (5) } 32.以下函数为链栈的进栈操作，×是要进栈的结点的数据域，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; (2) (3) } 1350
mid= (1ow + high) /2; if(a [mid]. key= = k) return(2) else if«3) low=mid十1 ; else(4) (5) 32. 进校 ，x 数据 ，top struct node ElemType data; struct node 铃next; struct node 铸top; void Push(ElemType x) struct node 铸p; 1350 p= (struct node ma l1oc( (1) p-> data = x ; (2) (3)
试卷代号：1252 中央广播电视大学2011一2012学年度第一学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2012年1月 一、单项选择题（每小题2分，共30分） 1.D 2.C 3.C 4.B 5.A 6.C 7.C 8.A 9.A 10.B 11.C 12.C 13.D 14.C 15.D 二、填空题（每题2分，共24分） 16.树形 图状 17.图状 18.p->next=head; 19.r=f 20.s->next=hs; 21.r->next=s; 22.顺序存储 链式存储 23.2i2i+1 24.串长度相等且对应位置的字符相等 25.11 26.深度优先搜索遍历 广度优先搜索遍历 27.4 三、综合应用题（每小题10分，共30分）】 28.(1) 6 1351
试卷代号 中央广播电视大学 2学年度第一学期"开放本科"期末考试 数据结构(本)试题答案及评分标准 (供参考) 2012 年1 一、单项选择题{每小题 1. D 2. C 3. C 6. C 7. C 8. A l 1.C 12.C 13.D 二、填空题(每题 16. 17. 18. p->next=head; 19. r=f 20. 21. r->next= 22. 储 链 23. 2i 2i+1 24. 长度 且对 26. 深度 先搜索遍历 广度优先搜索遍历 27. 4 三、综合应用题(每小题 3 0 28. (1) 4. B 9.A 14. C 5. A 10.B 15. D Q vQ 1351
(2)dnext=top (3)top=p 1352
(2)d~b~e~a~c (3)abdec 29. (1)囡 65 43 35 95 35 40 65 43 囹95 35 40 囡43 65 95 35 40 43 囚65 95 35 40 43 囹65 95 (2)40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 95 30. (1) (2) 四、程序填空题{每空 31. (1) low~= high (2)mid (3)a[mid]. key~k; (4)high=mid一1 (5)return 一1 ; 32. (1 ) sizeof( struct node) (2)p->next=top C3hop=p 1352