试卷代号 : 座位号 CD 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总分分数 I I I I I I 2009 年 7 月得分评卷人 I I I 一

Size: px

Start display at page:

Download "试卷代号 : 座位号 CD 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总分分数 I I I I I I 2009 年 7 月得分评卷人 I I I 一"

鲤沈
5 years ago
Views:

1 试卷代号 : 座位号 CD 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总分分数 I I I I I I 2009 年 7 月得分评卷人 I I I 一单项选择题 ( 每小题 2 分如崎盯扫, 共 3t 3ω O 1. 针对线性表, 在存储后如果最常用的操作是取第 i 个结点及其前驱, 则采用 ( ) 存储方式最节省时间 A. 单链表 B. 双链表 C 单循环链表 D. 顺序表 2. 数据结构中, 与所使用的计算机无关的是数据的 ( ) 结构 A. 物理 B. 存储巳逻辑与物理 D. 逻辑 3. 以下特征中, ( ) 不是算法的特性 A. 有穷性 B. 确定性 C. 可行性 D. 有 O 个或多个输出 4. 设有一个长度为 n 的顺序表, 要在第 i 个元素之前 ( 也就是插入元素作为新表的第 i 个元素 ), 则移动元素个数为 ( ) A. n-j+1 B. n-j 1340 C. n-j-1 D. j

2 5. 械的插入删除操作在 ( ) 进行 A. 找底 B. 任意位置 c. 指定位置 D. 战顶 6. 以下说法正确的是 ( ) A. 拢的特点是先进先出, 队列的特点是先进后出 B. 械和队列的特点都是先进后出 c. 枝的特点是先进后出, 队列的特点是先进先出 D. 械和队列的特点都是先进先出 7. 元素 2,4,6,8 按顺序依次进枝, 则该拔的不可能输出序列是 ( ) ( 进拔出棋可以交替进行 ) A. 8,6,4,2 B. 2,4,6,8 C. 4,2,8,6 D. 8,6,2,4 8. 设有一个 15 阶的对称矩阵 A, 采用压缩存储的方式, 将其下三角部分以行序为主序存储到一维数组 B 中数组下标从 1 开始 ), 则矩阵中元素 a 7, 6 在一维数组 B 中的下标是 ( ) A. 42 B. 13 C. 27 D 串函数 StrCmp("d", "D 勺的值为 ( ) A. a B. 1 C. -1 D 在一棵二叉树中, 若编号为 i 的结点存在右孩子, 则右孩子的顺序编号为 ( ) A. 2i B. 2i-1 C. 2i 十 2 D. 2i 十设一棵有 n 个叶结点采用链式存储的二叉树, 除叶结点外每个结点度数都为 2, 则该树共有 ( ) 个指针域为空 A. 2n B. 2n 十 l C. 2n 十 2 D. n 十

3 12. 已知如图 l 所示的一个图, 若从顶点 a 出发, 按广度优先搜索法进行遍历, 则可能得到的一种顶点序列为 ( ) 图 1 A. abcedf B. abcefd C. aebcfd D. acfdeb 13. 在有序表 {1,3,8,13,33,42,46,63,76,78, 邸,97,100} 中, 用折半查找值 86 时, 经 ( ) 次比较后查找成功 A. 6 B. 3 C. 8 D 有一个长度为 10 的有序表, 按折半查找对该表进行查找, 在等概率情况下查找成功的平均比较次数为 ( ) A. 29/10 B. 31/10 C. 26/10 D. 29/9 15. 一组记录的关键字序列为 (37,70,47,29,31,8 日, 利用快速排序, 以第一个关键字为分割元素, 经过一次划分后结果为 ( ) A. 31,29,37,47,70,85 B. 29,31,37,47,70,85 C. 31,29,37,70,47, D. 31,29,37,85,47,70

4 得分 I l 评卷人 I I 二填空题 ( 每小题 2 分, 共 2 4 分 ) 1. 把数据存储到计算机中, 并具体体现数据之间的逻辑结构称为结构 2. 结构中的数据元素存在一对 - 的关系称为结构 3. 在双向链表中, 每个结点有两个指针域, 一个指向, 另一个指向 4. 设有一个头指针为 head 的单向链表, p 指向表中某一个结点, 且有 p->next= =NULL, 通过操作, 就可使该单向链表构造成单向循环链表 5. 从 - 个战顶指针为 h 的链战中删除一个结点时, 用 x 保存被删结点的值, 可执行 x= h->data; 和 ( 结点的指针域为 n e xt ) 6. 两个串相等的充分必要条件是 7. 对二叉树的遍历可分为一一一一一一一一一一 - 一一一一 - 四种不同的遍历次序 8. 一棵有 n 个叶结点的二叉树, 其每一个非叶结点的度数都为 2, 则该树共有个结点 9. 一棵有 14 个结点的完全二叉树, 则它的最高层上有个结点 10. 如图 2 所示的二叉树, 其先序遍历序列为图

5 1 1. 哈希函数是记录关键宇值与该记录之间所构造的对应关系 12. 二叉树排序中任一棵子树都是二叉排序树, 这种说法是的 ( 回答正确或不正确 ) 得分 l 评卷人 I 1 -, 三综合题 ( 每小题 1 0 分, 共 3 0 分 ) 1. 设一组记录的关键宇序列为 ( 4 9, 8 3, 5 9, 4 1, 4 3, 4 7 ), 采用堆排序算法完成以下操作 : ( 要求小根堆, 井画出中间过程 ) (1) 以二叉树描述 6 个元素的初始堆 ; (2) 以二叉树描述逐次取走堆顶元素后, 经调整得到的 5 个元素 4 个元素的堆 2. 设有序表为 (13,19,25,36,48,51,63,84,91,116,135,200), 元素的下标依次为 1, 2,.., 12 0 (1) 说出有哪几个元素需要经过 4 次元素间的比较才能成功查到 p (2) 画出对上述有序表进行折半查找所对应的判定树 ( 树结点用下标表示 h (3) 设查找元素为 5, 需要进行多少次元素间的比较才能确定不能查到 3. (1) 对给定数列 { 7, 1 6, 4, 8, 2 0, 9, 6, 1 8, 日, 依次取数列中的数据, 构造一棵二叉排序树 (2 ) 对 - 个给定的查找值, 简述针对二叉排序树进行查找的算法步骤, 在上述二叉树中查找元素 20 共要进行多少次元素的比较? 1344

6 得分评卷人 l I 四程序填空题 ( 每空 2 分. 共 1 6 分 ) L 以下冒泡法程序对存放在 a[ 口,a[2],,a[n] 中的序列进行排序, 完成程序中的空格部分, 其中 n 是元素个数, 要求按升序排列 void bsort (NODE a[ ], int n) { NODE temp; int i,j,flag; for(j=l; (1) ;j 十 + ) ; {flag=o; for(i= 1; (2) if(a[i]. key>a[i+ 1]. key) {flag= 1; temp=a[i] ; ;i++) (3) (4) ifcflag= =O)break; 程序中 flag 的功能是 ( 5 ) 2. 以下程序是先序遍历二叉树的递归算法的程序, 完成程序中空格部分 ( 树结构中左右指针域分别为 l e f t 和 r i g ht, 数据域 d a ta 为字符型,BT 指向根结点 ) void Preorder (struct BTreeNode 长 BT) if(bt! =NULL) { (1) (2) (3) 1345

7 试卷代号 : 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构 ( 本试题答案及评分标准 ( 供参考 ) - 单项选择题 ( 每小题 2 分, 共 3 0 分 ) 2009 年 7 月 I. D 2, D 3. D 4. A 5. D 6. C 7.D 8. C 9. B 10. D 11. D 12. B 13. D 14. A 15. A 二填空题 { 每小题 2 分, 共 2 4 分 ) 1. 物理 ( 存储 ) 2. 线性 3. 结点的直接后继结点的直接前驱 4. p->next=head; 5. h=h->next; 6. 串长度相等且对应位置的字符相等 7. 先序中序后序层次 8.2n abdgcefhi 1 1. 存储地址正确

8 三综合题 ( 每小题 1 0 分, 共 3 0 分 ) 1. (1) 图 3 (2) ' 1 59 )1 ~Q 图

9 2. (1)19,48,84,116,200 (2) 12 图 5 (3)3 次 3. (1) '-I;.l' ; 图 6 (2) 先将给定值与根结点比较, 若相等则查找成功, 否则若小于根结点则在左子树中继续查找, 大于根结点在右子树中查找, 查找 20 共进行 3 次比较四程序填空题 ( 每空 2 分. 共 1 6 分 ) 1. (1 月 < = n 一 l (2)i<=n 一 j (3 )a[i]=a[i+1] (4)a[i+1]=temp (5) 当某趟冒泡中没有出现交换则已排好序, 结束循环 2. (1 ) printf( " % c",bt -> data) (2) Preorder(BT->left) (3) Preorder(BT->right) 1348

试卷代号 : 座位号中央广播电视大学学年度第一学期 " 开放本科 " 期末考试数据结构试题 2011 年 1 月题号一四五总分一一分数得分评卷人一单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下

试卷代号 : 座位号中央广播电视大学学年度第一学期开放本科期末考试数据结构试题 2011 年 1 月题号一四五总分一一分数得分评卷人一单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下试卷代号 : 1 0 1 0 座位号中央广播电视大学 2 0 1 0 2011 学年度第一学期 " 开放本科 " 期末考试数据结构试题 2011 年 1 月题号一四五总分一一分数一单项选择题, 在括号内填写所选择的标号 ( 每小题 2 分, 共 1 8 分 ) 1. 执行下面程序段时, s 语句的执行次数为 ( ) forcint i= 1; i

试卷代号 : 座位号 CD 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总 分 分数 I I I I I I 2009 年 7 月 得分 评卷人 I I I 一

试卷代号 : 座位号 CD 中央广播电视大学学年度第二学期 " 开放本科 " 期末考试数据结构 ( 本 ) 试题 I 题号 - - I 二 l 三 l 四 l 总分分数 I I I I I I 2009 年 7 月得分评卷人 I I I 一