试卷代号：1252 座位号■ 中央广播电视大学2009一2010学年度第一学期“开放本科”期末考试 数据结构（本） 试题 2010年1月 题 号 三 四 总分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.一种逻辑结构( )存储结构。 A.可以有不同的 B.只能有唯一的 C.的数据元素在计算机中的表示称为D.的数据元素之间的关系称为 2.以下说法中不正确的是(）。 A.双向循环链表中每个结点需要包含两个指针域 B.已知单向链表中任一结点的指针就能访问到链表中每个结点 C.顺序存储的线性链表是可以随机访问的 D.单向循环链表中尾结点的指针域中存放的是头指针 3.双向循环链表结点的数据类型为： struct node int data; struct node*next;/*指向直接后继/ struct node prior; }: 设P指向表中某一结点，要显示p所指结点的直接前驱结点的数据元素，可用操作 () A.printf(“%d"”,p->next->data);B.printf(“%d”,p->prior->data); C.printf(“%d”,p->prior-->next);D.printf(“%d”,p->data); 1365
试卷代号:1252 座位号口口 中央广播电视大学2009-2010学年度第一学期“开放本科”期末考试 数据结构(本) 试题 2010年 1月 题 号 四 总 分 分 数 得 分 评卷人 一、单项选择题(每小题 2分 ，共 30分) 1.一种逻辑结构( )存储结构 。 A.可以有不同的 B.只能有唯一的 C.的数据元素在计算机中的表示称为 D.的数据元素之间的关系称为 2.以下说法中不正确的是( )。 A.双向循环链表中每个结点需要包含两个指针域 B.已知单向链表中任一结点的指针就能访问到链表中每个结点 C.顺序存储的线性链表是可以随机访问的 D.单向循环链表中尾结点的指针域中存放的是头指针 3.双向循环链表结点的数据类型为: struct node { int data; struct node * next;/，指向直接后继，/ struct node * prior; }; 设 p指向表中某一结点，要显示 p所指结点的直接前驱结点的数据元素，可用操作 ( A. printf (" 0 o d"，p一>next一>data); B. print{("%d"，p一>prior一>data); C. print{(" 0 o d"，p一>prior->next); D. printf (" o d"，p一>data); 1365
4.一个栈的进栈序列是efgh,则栈的不可能的出栈序列是()（进出栈操作可以交替 进行)。 A.hgfe B.gfeh C.fgeh D.ehfg 5.设top是一个链栈的栈顶指针，栈中每个结点由-一个数据域data和指针域next组成， 设用x接收栈顶元素，则取栈顶元素的操作为()。 A.top->data=x; B.top=top->next; C.x=top->data; D.x=top->data;top=top->next; 6.以下说法不正确的是()。 A,栈的特点是后进先出 B.队列的特点是先进先出 C.栈的删除操作在栈底进行，插入操作在栈顶进行 D.队列的插入操作在队尾进行，别除操作在队头进行 7.char p; p=StrCat(“ABD”,“ABC"); Printf(“%s”,p); 的显示结果为()。 A.-1 B.ABDABC C.AB D.1 8.深度为5的满二叉树至多有( )个结点（根结点为第一层）。 A.40 B.31 C.34 D.35 9.已知一个图的所有顶点的度数之和为m,则该图的边数为( )。 A.2m B.m C.2m+1 D.m/2 1366
4.一个栈的进栈序列是efgh，则栈的不可能的出栈序列是( )(进出栈操作可以交替 进行)。 A. hgfe C. fgeh B. gfeh D. ehfg 5.设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成， 设用 x接收栈顶元素，则取栈顶元素的操作为( ) top一>data= x; top= top一>next; A. B. C. x=top一>data; D. x=top一>data; top= top一>next; 6.以下说法不正确的是( )。 A.栈的特点是后进先出 B.队列的特点是先进先出 C.栈的删除操作在栈底进行，插人操作在栈顶进行 D.队列的插入操作在队尾进行，删除操作在队头进行 7. char * p; p= StrCat ("ABD" , "ABC"); Printf("%s", p); 的显示结果为( )。 A. 一 1 B. ABDABC C. AB D. 1 8.深度为 5的满二叉树至多有( A. 40 )个结点(根结点为第一层)。 B. 31 C. 3 4 D。 35 9.已知一个图的所有顶点的度数之和为 m，则该 图的边数为( )。 A. 2 m C. 2m+ 1 B.m D. m/2 1366
10.以下说法不正确的是()。 A.连通图G的生成树一定是唯一的 B.连通图G一定存在生成树 C.连通图G的生成树中一定要包含G的所有顶点 D.连通图G的生成树一定是连通而且不包含回路 11.有序表为{1,2,4,6,10,18,20,32}，用课本中折半查找算法查找值18，经(. )次比 较后成功查到。 A.3 B.2 C.4 D.5 12.在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排 好序，从而可以提前结束排序过程的排序算法是( )。 A.冒泡 B.选择 C.直接插入 D.折半插人 13.用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行()次 元素间的比较。 A.4 B.3 C.5 D.6 14.如图若从顶点a出发按深度优先搜索法进行遍历， 则可能得到的顶点序列为()。 A.acfgedb B.aedbgfc C.acfebdg D.aecbdgf 15.一棵哈夫曼树总共有25个结点，该树共有( )个非叶结点（非终端结点）。 A.12 B.13 C.14 D.15 1367
10.以下说法不正确的是( )。 A.连通图G的生成树一定是唯一的 B.连通图 G一定存在生成树 C.连通图 G的生成树中一定要包含 G的所有顶点 D.连通图 G的生成树一定是连通而且不包含回路 11.有序表为{1,2,4,6,10,18召0,32}，用课本中折半查找算法查找值18，经( )次比 较后成功查到。 A. 3 B. 2 C. 4 D. 5 12.在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排 好序，从而可以提前结束排序过程的排序算法是( )。 A.冒泡 B.选择 C.直接插人 D.折半插人 13.用折半查找法，对长度为 12的有序的线性表进行查找，最坏情况下要进行( )次 元素间的比较。 A. 4 B. 3 C. 5 D. 6 14.如图若从顶点 a出发按深度优先搜索法进行遍历， 则可能得到的顶点序列为( A. acfgedb B. aedbgfc C. acfebdg D. aecbdgf 15.一棵哈夫曼树总共有 25个结点，该树共有( )个非叶结点(非终端结点)。 A.12 B. 13 C. 14 D. 15 1367
得分 评卷人 二、填空题（每小题2分，共24分】 1.结构中的元素之间存在多对多的关系称为 结构。 2.设有一个单向循环链表，结点的指针域为next,头指针为head,指针p指向表中某结 点，若逻辑表达式 的结果为真，则p所指结点为尾结点。 3.设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要人栈，则可执行操作s一> next=hs; 4.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next,s指向一个要入 队的结点，则入队操作为 5.循环队列的最大存储空间为MaxSize=6,采用少用一个元素空间以有效地判断栈空 或栈满，若队头指针front=4,当队尾指针rear= 时队满，队列中共有 个元素。 6.程序段char*s=”aBcD”;n=0: while(*s！=八0) {if(*s>=’a'&&*s<=’z')n十+： s++; }执行后n= 7.一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中对应位 置上结点的编号相同)，若它存在左孩子，则左孩子的编号为 8.根据搜索方法的不同，图的遍历有 两种方法。 9.结构中的数据元素存在多对多的关系称为 结构。 10.一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 个结点。 11.串的两种最基本的存储方式分别是 和 12.按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保 它们的前后关系，则排序算法是稳定的，否则是不稳定的。 1368
得 分 评卷人 二、填空题(每小题 2分，共 24分》 1.结构中的元素之间存在多对多的关系称为 结构。 2.设有一个单向循环链表，结点的指针域为next，头指针为head，指针P指向表中某结 点，若逻辑表达式 的结果为真，则A所指结点为尾结点。 3.设有一个链栈，栈顶指针为 hs，现有一个 s所指向的结点要人栈，则可执行操作 s-> next=hs; 4.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next, s指向一个要人 队的结点，则人队操作为 ;_ _____ 。 5.循环队列的最大存储空间为 MaxSize= 6，采用少用一个元素空间以有效地判断栈空 或栈满，若队头指针front= 4，当队尾指针rear=_ 时队满，队列中共有_ 个元素。 6.程序段 char，s="aBcD" ; n=0; while(，s!“'\0') if，S>= ' a'&今* s<=Y )n++; 5+十 ; }执行后 n= 7.一棵二叉树中顺序编号为5的结点(树中各结点的编号与等深度的完全二叉中对应位 置上结点的编号相同)，若它存在左孩子，则左孩子的编号为_ 。 .根据搜索方法的不同，图的遍历有_ .结构中的数据元素存在多对多的关系称为 两种方法。 结构。 10一 棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有 个结点。 11.串的两种最基本的存储方式分别是 _ __和 __ 。 12.按某关键字对记录序列排序，若关键字_ 的记录在排序前和排序后仍保I 它们的前后关系，则排序算法是稳定的，否则是不稳定的。 1368
得分 评卷人 三、综合题（每小题10分，共30分） 1.(l)已知某二叉树的先序遍历序列是aecdb,中序遍历序列是eadcb,试画出该二叉树。 (2)给出上述二叉树的后序遍历序列。 (3)若上述二叉树的各个结点的字符分别是1,2,3,4,5，并恰好使该树成为一棵二叉排序 树，试问a、b、c、d、e的值各为多少？ 2.(1)给定数列{8,17,5,9,21,10,7,19,6}，依次取序列中的数构造一棵二叉排序树。 (2)对上述二叉树给出中序遍历得到的序列。 3.(1)以给定权重值1,2,12,13,20,25为叶结点，建立一棵哈夫曼树。 (②)若哈夫曼树有个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵 哈夫曼树是否一定唯一。 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回 值是指向树结点的结构指针p(查找成功p指向查到的树结点，不成功P指向为NULL)完成 程序中的空格。 typedef struct Bnode int key; struct Bnode left; struct Bnode right; Bnode; Bnode BSearch(Bnode bt,int k) /bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/ Bnode p; if(bt==(1) return (bt); p=bt; 1369
得 分 评卷人 三、综合题(每小题 10分，共 30分) 1. (1)已知某二叉树的先序遍历序列是 aecdb，中序遍历序列是 eadcb，试画出该二叉树。 (2)给出上述二叉树的后序遍历序列。 (3)若上述二叉树的各个结点的字符分别是 1,2,3,4,5，并恰好使该树成为一棵二叉排序 树，试问 a,b,c,d,e的值各为多少? 2.(l)给定数列{8,17,5,补21,10,7,19,6)，依次取序列中的数构造丫棵二叉排序树· (2)对上述二叉树给出中序遍历得到的序列。 3. (1)以给定权重值1,2,12,13,20,25为叶结点，建立一棵哈夫曼树。 (幻若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵 哈夫曼树是否一定唯一。 得 分 评卷人 四、程序填空题(每空 2分，共 16分) 1.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回 值是指向树结点的结构指针 P(查找成功 P指向查到的树结点，不成功 P指向为 NULL)完成 程序中的空格。 typedef struct Bnode 左 int key; struct Bnode * left; struct Bnode * right; }Bnode; Bnode二BSearch (Bnode二bt, int k) /二bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字 二/ 丈 Bnode，P; if(bt== (1) _) return (bt); v=bt; 1369
while(p->key！=(2) if(kkey) (3) else (4) if(p==NULL)break; Return((5) 2.以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由x返 回，front、rear分别是链队列的队头、队尾指针。 struct node ElemType data; struct node next; }: struct node front,rear; ElemType OutQueue() { ElemType x; if(1) )( printf(“队列下溢错误！\n”); exit(1); else struct node p=front->next; x=p->data; front->next=(2) if(p->next==NULL)rear=front; free(p); (3) 1370
while(p一>key!=(2) ) if(kkey) (3) (4)二 ; ==NULL) break; Return((5) ) 2.以下函数为链队列的出队操作(链队列带有头结点)，出队结点厂的数据域的值由 x返 回，front,rear分别是链队列的队头、队尾指针。 struct node ElernType data; struct node * next }; struct node * front, * rear; ElernType OutQueue() { 川 ElernType x; if((1) printf“队列下溢错误!}n;); exit(1); } else{ struct node * p=front一>next; X=P一>data; front一> next= (2) ; if (p一>next==NULL) rear-front; free(p); (3) ; } 1370
试卷代号：1252 中央广播电视大学2009一2010学年度第一学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2010年1月 一、单项选择题（每小题2分，共30分） 1.A 2.B 3.B 4.D 5.C 6.C 7.B 8.B 9.D 10.A 11.B 12.A 13.A 14.B 15.A 二、填空题（每题2分，共24分） 1.图状 2.p->next==head; 3.hs=s; 4.r->next=s r=s 5.35 6.2 7.10 8.深度优先 广度优先 9.图状（网状） 10.2n-1 11.顺序存储 链式存储 12.相等 1371
试卷代号:1252 中央广播电视大学2009-2010学年度第一学期“开放本科”期末考试 数据结构(本) 试题答案及评分标准 (供参考) 2010年 1月 一、单项选择题(每小题 2分.共 30分) 1. A 2. B 3. B 4. D 5. C 6. C 7. B 8. B 9.D 10. A 11. B 12. A 13. A 14. B 15. A 二、填空题(每题 2分，共 24分 ) 1.图状 2. p一>next= =head 3. hs=s; 4. r一 > next= s r=s; 5. 3 5 6. 2 7.10 8.深度优先 广度优先 9.图状(网状) 10. 2n一 1 n.顺序存储 链式存储 12.相等 1371
三、综合应用题（每小题10分，共30分） 1.(1) (2)edbca (3)e=1,a=2,d=3,c=4,b=5 2.(1) 8 17 9 21 6 10 (2)5,6,7,8,9,10,17,18,19,21 3.(1) 73 28 15 13 45 12 20 25 2 1372
三、综合应用题(每小题 10分，共 30分) 1. (1) \ ③ (2) edbca (3)e=l,a=2,d二3,c=4,b=5 2.0 ) (2)5，6,7,8，9，10，17，18，19,21 3. (1) 1372
(2)2n-1不一定唯一 四、程序填空题（每空2分，共16分） 1.(1)NULL (2)k (3)p=p->left (4)p=p->right (5)p 2.(1)front==rear (2)p->next (3)return(x) 1373
(2)2n-1 不一定唯一 四、程序填空题(每空 2分，共 16分) 1. (1 )NULL (2)k (3)p=p一>left (4)p=p一>right (5)p 2. (1) front= =rear (2)p一_>next (3)return(x) 1373