试卷代号：1252 座位口 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试 数据结构（本） 试题 2009年7月 题号 二 三 四 总 分 分数 得分 评卷人 一、单项选择题（每小题2分，共30分） 1.针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用( )存储 方式最节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 2.数据结构中，与所使用的计算机无关的是数据的( )结构。 A.物理 B.存储 C.逻辑与物理 D.逻辑 3.以下特征中，( )不是算法的特性。 A.有穷性 B.确定性 C.可行性 D.有0个或多个输出 4.设有一个长度为的顺序表，要在第i个元素之前（也就是插入元素作为新表的第ⅰ个 元素)，则移动元素个数为()。 A.n-i+l B.n-i C.n-i-1 D.i 1340
试卷代号 :1252 座位号巨口 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试 数据结构(本) 试题 2009年 7月 题 号 四 总 分 分 数 得 分 评卷人 一、单项选择题(每小题 2分，共 30分) 1.针对线性表 ，在存储后如果最常用的操作是取第 i个结点及其前驱 ，则采用( 方式最节省 时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 2.数据结构中，与所使用的计算机无关的是数据的( )结构 。 A.物理 B.存储 )存储 C.逻辑与物理 D.逻辑 3.以下特征中，( )不是算法的特性 。 A.有穷性 C.可行性 4.设有一个长度为 n的顺序表，要在第 i 元素)，则移动元素个数为( )。 A. n一 1+ 1 C. n- i一 1 又340 B.确定性 D.有 。个或多个输出 个元素之前(也就是插人元素作为新表的第 个 B. n一 i
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开始），则矩阵中元素7,6在一维数组B中的下标是()。 A.42 B.13 C.27 D.32 9.串函数StrCmp(“d”,“D”)的值为( A.0 B.1 C.-1 D.3 10.在一棵二叉树中，若编号为1的结点存在右孩子，则右孩子的顺序编号为()。 A.2i B.2i-1 C.2i+2 D.2i+1 11.设一棵有个叶结点采用链式存储的二叉树，除叶结点外每个结点度数都为2，则该 树共有( )个指针域为空。 A.2n B.2n+1 C.2n+2 D.n+1 1341
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,,。在一维数组 B中的下标是( )。 A.42 B. 13 C. 27 D. 32 9.串函数 StrCmp ("d" , "D")的值为( )。 A. 0 C. 一 1 B. 1 D. 3 10.在一棵二叉树中，若编号为 i的结点存在右孩子 ，则右孩子的顺序编号为( A. 2 i B. 2 i一 1 C. 2i+2 D. 2i+ 1 11.设一棵有 n个叶结点采用链式存储的二叉树，除叶结点外每个结点度数都为 2，则该 树共有 ( )个指针域为空 。 A. 2n B. 2n+ l C. 2 n十2 D. n+ l 1341
12.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到 的一种顶点序列为()。 b 图1 A.abcedf B.abcefd C.aebefd D.acfdeb 13.在有序表(1,3,8,13,33,42,46,63,76,78,86,97,100}中，用折半查找值86时，经 )次比较后查找成功。 A.6 B.3 C.8 D.4 14.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为( ). A.29/10 B.31/10 C.26/10 D.29/9 15.一组记录的关键字序列为(37,70,47,29,31,85)，利用快速排序，以第一个关键字为分 割元素，经过一次划分后结果为( )。 A.31,29,37,47,70,85 B.29,31,37,47,70,85 C.31,29,37,70,47,85 D.31,29,37,85,47,70 1342
12.已知如图 1所示的一个 图，若从顶点 a出发，按广度优先搜索法进行遍历 ，则可能得到 的一种顶点序列为( )。 图 1 A. abeedf B. abeefd C. aebefd D. acfdeb 13.在有序表 {1,3,8,13,33,42,46,63,76,78,86,97,100}中，用折半查找值 86时 ，经 ( )次比较后查找成功 。 A. 6 B. 3 C. 8 D. 4 14.有一个长度为 10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的 平均比较次数为( )。 A. 29/10 B. 31/10 C. 26/10 D. 29/9 15，一组记录的关键字序列为(37,70,47,29,31,85)，利用快速排序，以第一个关键字为分 割元素，经过一次划分后结果为( )。 A. 31,29，37，47，70，85 B.29，31，37,47，70,85 C. 31，29，37，70，47，85 D. 31，29，37,85,47，70 1342
得分 评卷人 二、填空题（每小题2分，共24分）】 1.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为 结构。 2.结构中的数据元素存在一对一的关系称为 结构。 3.在双向链表中，每个结点有两个指针域，一个指向 ,另 一个指向 4.设有一个头指针为head的单向链表，p指向表中某一个结点，且有p>next==NULL, 通过操作 ,就可使该单向链表构造成单向循环链表。 5.从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行 x=h->data;和 (结点的指针域为.next) 6.两个串相等的充分必要条件是 7.对二叉树的遍历可分为 四种不同的遍历次序。 8.一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 个结 点。 9.一棵有14个结点的完全二叉树，则它的最高层上有 个结点。 10.如图2所示的二叉树，其先序遍历序列为 b 图2 1343
得 分 评卷人 二、填空题(每小题 2分，共24分) 1.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为 2.结构中的数据元素存在一对一的关系称为_ 结构。 3.在双向链表中，每个结点有两个指针域，一个指向___ 结构 。 一个指向 4.设有一个头指针为 head的单向链表，P指向表中某一个结点，且有 p-> next= =NULL 通过操作 ，就可使该单向链表构造成单向循环链表。 5.从 一个 栈顶 指针为 h的链栈 中删 除一个 结点 时 ，用 x保存 被删 结点 的值 ，可执 行 x= h-> data;和 。(结点的指针域为一next) 6.两个串相等的充分必要条件是 7.对二叉树的遍历可分为 四种不同的遍历次序。 8一 棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_ 个结 9一 棵有 14个结点的完全二叉树，则它的最高层上有 10.如图2所示的二叉树，其先序遍历序列为_ 个结 点 。 1343
11.哈希函数是记录关键字值与该记录 之间所构造的对应关系。 12.二叉树排序中任一棵子树都是二叉排序树，这种说法是 的。（回答 正确或不正确) 得 分 评卷人 三、综合题（每小题10分，共30分） 1.设一组记录的关键字序列为(49,83,59,41,43,47)，采用堆排序算法完成以下操作：（要 求小根堆，并画出中间过程) (1)以二叉树描述6个元素的初始堆； (2)以二叉树描述逐次取走堆顶元素后，经调整得到的5个元素、4个元素的堆。 2.设有序表为(13,19,25,36,48,51,63,84,91,116,135,200)，元紫的下标依次为1,2， …,12。 (1)说出有哪几个元素需要经过4次元素间的比较才能成功查到： (2)画出对上述有序表进行折半查找所对应的判定树（树结点用下标表示）： (3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 3.(1)对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 (2)对一个给定的查找值，简述针对二叉排序树进行查找的算法步骤，在上述二叉树中查 找元素20共要进行多少次元素的比较？ 1344
11.哈希函数是记录关键字值与该记录 之间所构造的对应关系。 12.二叉树排序中任一棵子树都是二叉排序树，这种说法是 的 。 (回答 正确或不正确) 得 分 评卷人 三、综合题 (每小题 10分 ，共 30分) 1.设一组记录的关键字序列为(49,83,59,41,43,47)，采用堆排序算法完成 以下操 作 :(要 求小根堆 ，并画出中间过程) (1)以二叉树描述 6个元素的初始堆 ; (2)以二叉树描述逐次取走堆顶元素后 ，经调整得到的 5个元素、4个元素的堆 。 2.设有序表为(13,19,25,36,48,51,63,84,91,116,135,200)，元素的下标依次为 1,2, … … ，12。 (1)说出有哪几个元素需要经过 4次元素间的比较才能成功查到; (2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示); (3)设查找元素为5，需要进行多少次元素间的比较才能确定不能查到。 3. (1)对给定数列{7,16,4,8,20,9,6,18,5}，依次取数列中的数据，构造一棵二叉排序树。 (2)对一个给定 的查找值 ，简述针对二叉排序树进行查找的算法步骤，在上述二叉树 中查 找元素 20共要进行多少次元素的 比较? 1344
得 分 评卷人 四、程序填空题（每空2分，共16分） 1.以下冒泡法程序对存放在a[1],a[2],…,a[n]中的序列进行排序，完成程序中的空 格部分，其中n是元素个数，要求按升序排列。 void bsort (NODE a[]int n) NODE temp; int i,j,flag; for(G=1;(1) j++); (flag=0; for(i=1;(2) :i++) if(a[i].key>a[i+1].key) (flag=1; temp=a[i]; (3) (4) } if(flag==0)break; 程序中f1ag的功能是(5) 2.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右 指针域分别为left和right,数据域data为字符型，BT指向根结点)。 void Preorder (struct BTreeNode BT) {f(BT！=NULL){ (1) (2) (3) } 1345
得 分 评卷人 四、程序填空题(每空 2分.共 16分) 1.以下冒泡法程序对存放在 a[1],a[2]....... ,a[n]中的序列进行排序，完成程序中的空 格部分，其中 n是元素个数，要求按升序排列。 void bsort (NODE a[]，int n) {NODE temp; int i,j,flag; for(j=1;(1) ;j++); {flag=0; for(i=1;(2) ;i++)- if (a[i]. key>a[i+1]. key) {flag=l; temp=a[i]; (3) ; (4) ; } if(flag= =0)break; } } 程序中flag的功能是(5) _ 2.以下程序是先序遍历二叉树 的递归算法 的程序 ，完成程序 中空格部分 (树结构 中左 、右 指针域分别为 left和 right，数据域 data为字符型，BT指向根结点)。 void Preorder (struct BTreeNode * BT) if(BT! =NULL){ 1345
试卷代号：1252 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试 数据结构（本）试题答案及评分标准 (供参考) 2009年7月 一、单项选择题（每小题2分，共30分】 1.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分，共24分） 1.物理（存储） 2.线性 3.结点的直接后继 结点的直接前驱 4.p->next=head; 5.h=h->>next; 6.串长度相等且对应位置的字符相等 7.先序 中序 。后序 层次 8.2n-1 9.7 10.abdgcefhi 11.存储地址 12.正确 1346
试卷代号:1252 中央广播电视大学2008--2009学年度第二学期“开放本科”期末考试 数据结构(本) 试题答案及评分标准 (供参考) 2009年 7月 一、单项选择题(每小题 2分，共30分) l. D 2. D 3. D 6. C 7. D 8. C 11. D 12. B 13. D 二、填空题 (每小题 2分 ，共 24分) 1.物理 (存储) 2.线性 3.结点 的直接后继 结点 的直接前驱 4. p-> next 5. h=h-> next; 6.串长度相等且对应位置的字符相等 7.先序 中序 后序 层次 8. 2n- 1 9. 7 10.abdgcefhi 11.存储地址 12.正确 1346 4. A 5. D 9. B 10. D 14. A 15. A
三、综合题（每小题10分，共30分） 1.(1) 49 9 83 47 41 47 83 59 41 43 47 41 43 59 83 43 59 41 41 49 43 83 彩 83 49 59 图3 (2) 43 43 47 59 47 49 7 41 49 41 83 83 47 59 49 47 83 43 41 图4 1347
三、综合题 (每小题 10分 。共 30分) 1.(1) 图 3 (2) 图 4 1347
2.(1)19,48,84,116,200 (2) 12 图5 (3)3次 3.(1) 16 图6 (2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续 查找，大于根结点在右子树中查找，查找20共进行3次比较。 四、程序填空题（每空2分，共16分） 1.(1)jdata) (2)Preorder(BT->left) (3)Preorder(BT->right) 1348
2. (1)19，48，84，116，200 (2) 图 5 (3)3次 3. (1) (2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续 查找 ，大于根结点在右子树中查找 ，查找 20共进行 3次 比较 。 四、程序填空题(每空 2分，共 16分) 1.(1)jdata) (2) Preorder(BT->left) (3) Preorder(BT->right) 1348