试卷代号：1252 座位号■■ 中央广播电视大学2008一2009学年度第一学期“开放本科”期末考试 数据结构（本）试题 2009年1月 题 多 二 三 四 总 分 分 数 得分 评卷人 一、单项选择题（每小题2分，共30分）】 1.链表所具备的特点是()。 A.可以随机访问任一结点 B.占用连续的存储空间 C.插人删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问 之.线性结构中数据元茶的位置之问存在( )的关系 A一对一 B.一对多 C.多对多 D.每一个元素都有一个直接前驱和一个直接后继 3.算法的时间复杂度与()有关。 A.所使用的计算机 B.与计算机的操作系统 C.与算法本身 D.与数据结构 4,在一个单链表中，P,q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直 接后继，现要删除q所指结点，可用的语句是( )。 A.p=q->next B.p->next=q C.p->next=q->next D.g->next=NULL 1372
试卷代号:1252 座位号巨口 中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试 数据结构 (本) 试题 2009年 1月 题 号 四 总 分 分 数 得 分 评卷人 一、单项选择题(每小题 2分，共 30分) 1.链表所具备的特点是( )。 A.可以随机访问任一结点 B.占用连续的存储空间 C.插人删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问 艺.线性结构 中数据元素的位置之间存在( )的关系。 A.一对 一 B.一对多 C.多对多 D.每一个元素都有一个直接前驱和一个直接后继 3.算法的时间复杂度与( )有关 。 A.所使用的计算机 B.与计算机的操作系统 C.与算法本身 D.与数据结构 4.在一个单链表中，p,q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直 接后继，现要删除 q所指结点 ，可用 的语句是( )。 A. p二q->riext B. p->next=q C. p->next=q->next D. q->next=NULL 1372
5.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为()。 A.r=f->next; B.r=r->next C.f=f->next; D.f=r->next; 6.元素3,6,9按顺序依次进栈，则该栈的不可能输出序列是()（进栈出栈可以交替进 行)。 A.9,6,3 B.9,3,6 C.6,3,9 D.3,9,6 7.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存储到 一维数组B中（数组下标从1开始），则矩阵中元素A.5在一维数组B中的下标是()。 A.33 B.32 C.85 D.41 8.在C语言中，顺序存储长度为3的字符串，需要占用( )个字节。 A.4 B.3 C.6 D.12 9.一棵有n个结点采用链式存储的二叉树中，共有( )个指针域为空。 A.n+1 B.n C.n-1 D.n-2 10.设一棵哈夫曼树共有n个叶结点，则该树有( )个非叶结点。 A.n-1 B.n C.n+1 D.2n 11.在一个无向图中，所有顶点的度数之和等于边数的( )倍。 A.3 B.2.5 C.1.5 D.2 1373
5.在一个链队中，假设 f和 r分别为队头和队尾指针 ，则删除一个结点的运算为( A. r二f-> next; B. r=r->next; C. f二f->next; D. f二r-> next; 6.元素 3,6,9按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交替进 行 ) A. 9，6，3 B. 9，3，6 C. 6，3，9 D. 3，9，6 7.设有一个 10阶的对称矩阵 A，采用压缩存储的方式，将其下三角部分以行序为主存储到 一维数组 B中(数组下标从 1开始)，则矩阵中元素 戊.s在一维数组 B中的下标是( A.33 B.32 C. 85 D. 41 8.在 C语言中，顺序存储长度为 3的字符串，需要占用( )个字节。 A. 4 B. 3 C. 6 D. 12 9一 棵有 n个结点采用链式存储的二叉树中，共有( )个指针域为空。 A. n+ 1 B. n C. n一 1 D. n一2 10.设一棵哈夫曼树共有 n个叶结点 ，则该树有( )个非叶结点 。 A. n一 1 B. n C. n牛 1 D. 2 n 11.在一个无向图中，所有顶点的度数之和等于边数的( )倍 A.3 B.2.5 C.1.5 D.艺 1373
12.已知如图1所示的一个图，若从顶点V,出发，按广度优先进行遍历，则可能得到的一 种顶点序列为()。 V 图1 A.Vi V2 V3 Ve VVV,Va B.Vi V2 Va VV Va Ve V7 C.Vi V2 V:VV:V.V,Va D.ViV2 Va V Va V:Vi V 13.在有序表(2,4,7,14,34,43,47,64,75,80,90,97,120}中，用折半查找法查找值80时， 经( )次比较后查找成功。 A.4 B.2 C.3 D.5 14.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比 较（要求比较次数尽量少），然后将其放人已排序序列的正确位置的方法是()。 A.冒泡 B.直接插入 C.折半插入 D.选择排序 15.排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的 一端的方法，称为()排序。 A.归并 B.插入 C.快速 D.选择 1374
12.已知如图 ]所示的一个图，若从顶点 V，出发，按广度优先进行遍历，则可能得到的一 神顶点序列为( )。 图 1 A. V, V, V, V, V, V, V, V, B. V, V, V, V, V, V, V, V, C. V, V,, V, V, V, V, V, V, D. V, V, V, V, V, V, V, V, 13.在有序表{2,4,7,14,34,43,47,64,75,80,90,97,120}中，用折半查找法查找值 80时， 经( )次比较后查找成功。 A. 4 B. 2 C. 3 D. 5 14.排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比 较(要求比较次数尽量少)，然后将其放入已排序序列的正确位置的方法是( )。 A.冒泡 B.直接插入 C.折半插入 D.选择排序 15.排序方法中，从 尚未排序序列中挑选元素，并将其依次放入 已排序序列(初始为空)的 一端的方法 ，称为( )排序。 A.归并 B.插人 C.快速 1).选择 1374
得 分 评卷人 二、填空题（每小题2分，共24分）】 1.结构中的数据元素存在多对多的关系称为 结构。 2.要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的 次数和算法的时间复杂度分别为】 和 3.设有一个头指针为head的单向循环链表，p指向链表中的结点，若p>next== ,则P所指结点为尾结点。 4.向一个栈顶指针为h的链栈中插人一个s所指结点时，可执行s>next=h,和 5.在一个链队中，设f和r分别为队头和队尾指针，则插人s所指结点的操作为 和r=s;(结点的指针域为next) 6.设有n阶对称矩阵A,用数组S进行压缩存储，当i<j时，A的数组元素a:相应于数组 S的数组元素的下标为 。(数组元素的下标从1开始) 7.一棵二叉树中顺序编号为ⅰ的结点，若它存在左、右孩子，则左、右孩子编号分别为 8.一棵有2一1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 个叶结点。 9. 遍历二叉排序树可得到一个有序序列。 10.如图2所示的二叉树，其前序遍历序列为 图2 11.二叉树为二叉排序的充分必要条件是其任-结点的值均大于其左孩子的值、小于其右 孩子的值。这种说法是 的。（回答正确或不正确） 12.按某关键字对记录序列排序，若 在排序前和排序 后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。 1375
得 分 评卷人 二、填空题(每小题 2分，共 24分) 1.结构中的数据元素存在多对多的关系称为_ 结构。 2.要求在 n个数据元素中找其中值最大的元素，设基本操作为元素 间的比较。则比较的 次数和算法的时间复杂度分别为 和 3.设有一个头指针为 head的单向循环链表，P指向链表中的结点，若 p-> next = “ _ ，则P所指结点为尾结点。 4.向一个栈顶指针为 h的链栈 中插人一个 s所指结点时，可执行 s-> next = h;和 5.在一个链队中，设 f和 r分别 为队头和队尾指针，则插人 s所指结点的操作 为 _ 和 r= s;(结点的指针域为 nexo 6.设有 n阶对称矩阵A，用数组 S进行压缩存储，当i<j时，A的数组元素 a。相应于数组 S的数组元素的下标为 。(数组元素的下标从 1开始) 7一 棵二叉树中顺序编号为 i的结点，若它存在左、右孩子，则左、右孩子编号分别为 8一 棵有 2n-1个结点的二叉树 ，其每一个非叶结点 的度数都为 2，则该树共有 个叶结点。 遍历二叉排序树可得到一个有序序列 。 10.如图 2所示的二叉树 ，其前序遍历序列为 11.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右 孩子的值。这种说法是 的。(回答正确或不正确) 12.按某关键字对记录序列排序，若 后仍保持它们的前后关系.则排序算法是稳定的，G-i则是不稳定的。 在排序 前 和排 序 1375
得 分 评卷人 三、综合题（每小题10分，共30分） 1.一组记录的关键字序列为(46,79,56,38,40,84) (1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果。（给出逐次交 换元素的过程，要求以升序排列) (2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 2.设查找表为(16,15,20,53,64,7) (1)用冒泡法对该表进行排序（要求升序排列），要求写出每一趟的排序过程，通常对个 元素进行冒泡排序要进行多少趟冒泡？第趟要进行多少次元素间的比较？ (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据 元素作为树结点) (3)求在等概率条件下，对上述有序表成功查找的平均查找长度。 3.(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的 值，则该树一定是二叉排序树”。该说法是否正确，若认为正确，则回答正确，若认为不正确则 说明理由？ (2)设有查找表{7,16,4,8,20,9,6,18,5}，依次取表中数据构造一棵二叉排序树。对上述 二叉树给出后序遍历的结果。 得 分 评卷人 四、程序填空题（每空2分，共16分） 1,以下是用头插法建立带头结点且有n个结点的单向链表的程序，要求结点中的数据域 从前向后依次为n,n一1，…，1，完成程序中空格部分。 NODE create2(n) {NODE head,￥p,￥q; int i; p=(NODE *malloc(sizeof(NODE)); p-next=NULL; head=(1) 1376
得 分 评卷人 三、综合题 (每小题 10分，共 30分) 1一 组记录的关键字序列为(46,79,56,38,40,84) (l)利用快速排序的方法，给出以第一个记录为墓准得到的一次划分结 果。(给出逐次交 换元素的过程 ，要求 以升序排列) (2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 2.设查找表为(16,15,20 53,64,7) (1)用冒泡法对该表进行排序(要求升一序排列)，要求写出每一趟的排序过程，通常对 n个 兀素进行冒泡排序要进行多少趟冒泡?第]趟要进行多少次元素间的比较? (2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。(要求以数据 元素作为树结点) (3)求在等概率条件下，对 I--述有序表成功查找的平均查找长度。 3. (1)“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的 值，则该树一定是二叉排序树”。该说法是否正确，若认为正确 ，则 回答正确 ，若认为不正确则 说 明理 由? (2)设有查找表{7,16,4,8,20,9,6,18,5)，依次取表中数据构造一棵二叉排序树。对上述 二叉树给出后序遍历的结果 。 得 分 评卷人 四、程序填空题1每空 2分 ，共 16分) 1.以下是用头插法建立带头结点且有 n个结点的单 向链表的程序 ，要求结点中的数据域 从前向后依次为 n,n-1,……， 1，完成程序中空格部分。 NODE * crcate2(n) {NODE *head *p， ac q tnt i; 1> = (NODE、)malloc(sizeof(NODE)) p一)next=N U I_I; head= (1) ; 1376
(2) for(i=1;idata=i; if(i==1) p->next=NULL; else p->next=(4) q->next=(5) return(head); } 2.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右 指针域分别为left和right,数据域data为字符型，BT指向根结点)。 void Postorder (struct BTreeNode BT) if(BT!=NULL)( (1) (2) (3) 3 } 1377
(2) ; for(i=1;1data=i; if(i二 =1) p->next=NULL else p->next= (4) q->next= (5) } return(head); } 2.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中，左、右 指针域分别为 left和right，数据域 data为字符型，BT指向根结点)。 void Postorder (struct BTreeNode * BT) { if (BT!“NULL){ (1) 、 ， 、 尹 9 口 Q J 了 、 2口、 、 、了了 1377
试卷代号：1252 中央广播电视大学2008一2009学年度第一学期“开放本科”期末考试 数据结构（本）试题答案及评分标准 (供参考) 2009年1月 一、单项选择题（每小题2分，共30分） 1.C 2.A 3.C 4.C 5.C 6.B 7.A 8.A 9.A 10.A 11.D 12.C 13.A 14.C 15.D 二、填空题（每小题2分，共24分） 1.图状 (网状) 2.n-1,0(n) 3.head 4.h=s 5.r->next=s; 6.i(i-1)/2+j 7.2i和2i+1 8.n 9.中序 10.abdefcg 11.不正确 12.关键字相等的记录 三、综合题（每小题10分，共30分）】 1.(1)初始序列46,79,56,38,40,84 40,79,56,38,40,84 40,79,56,38,79,84 40,38,56,38,79,84 40,38,56,56,79,84 40,38,46,56,79,84 1378
试卷代号:1252 中央广播电视大学2008-2009 数据结构(本) 学年度第一学期“开放本科”期末考试 试题答案及评分标准 (供参考) 2009年 1月 一、单项选择题(每小题 2分，共30分) 1. C 2. A 3. C 6. 13 7. A 8. A 11.D 12. C 13. A 二、填空题 (每小题 2分 ，共 24分) 1.图状 (网状) 2.n一1，0(n) 3. head 4. h=s; 5. r-> next =s; 6. i(i一1)/2+j 7. 2i和 21+1 8.n 9.中序 10.abdefcg 11.不正确 12.关键字相等的记录 三、综合题 (每小题 10分 ，共 30分) 1. (1)初始序列 46,79,56,38,40,84 40，79，56，38，回，84 40，回，56,38，79，84 40,38，56，国，79,84 40，38，园，56，79，84 40，38，46，56，79，84 1378 4.C 9. A 14. C 5. C 10. A 15. D
(2) 号 46 79 56 多 84 38 0 84 38 40 56 84 84 79 46 79 56 38 0 56 40 46 图3 2.(1)原序列16152053647 15162053764 n一1趟 15162075364 n一j次 15167205364 157162053 64 71516205364 (2) 7 15 20 图4 1379
(2) 2. (1)原序列 16 15 20 53 20 53 64 7 7 64 15 16 20 7 53 64 n一1趟 n-j次 二 d 内b 1 1 1土 15 16 7 20 53 64 月 以玉 J己 玉 几b 只 U 20 53 20 53 八卜 ︺ 八卜钊 1 土 ~. 土 15 7 7 15 (2) 图 4 1379
(3)平均查找长度=(1*1+2*2+3￥3)/6=14/6 3.(1)不正确，二叉排序树要求其子树也是二叉排序树。 (2) 16 20 18 图5 后续遍历5,6,4,9,8,18,20,16,7 四、程序填空题（每空2分，共16分） 1.(1)p (2)q=p (3)(NODE *)malloc(sizeof(NODE)) (4)q->next (5)P 2.(1)Postorder(BT->left) (2)Postorder(BT->right) (3)printf(“%c”,BT->data) 1380
(3)平均查找长度=(1，1+2 * 2-1-3 * 3)/6=14/6 3. (1)不正确，二叉排序树要求其子树也是二叉排序树。 (2) 后续遍历 5,6,4,9,8,18,20,16,7 四、程序填空题(每空 2分。共 16分) 1. (1 )p (2 )q=p (3) (NODE*)malloc(sizeof(NODE)) (4)q->next (Fln 2.(1)Postorder(BT->left) (2) Post order (BT->right) (3) pfintf("%c"，BT->data) 1380