试卷代号：1252 座位■ 中央广播电视大学2007一2008学年度第二学期“开放本科”期末考试 计算机科学技术专业 数据结构（本） 试题 2008年7月 题 二 三 四 总分 分 数 得分 评卷人 一、单项选择题（每小题2分，共30分） 1.非空的单向循环链表的尾结点满足( )(设头指针为head,指针p指向尾结点)。 A.p->next ==NULL B.p==NULL C.p->next==head D.p==head 2.一种逻辑结构()。 A.可以有不同的存储结构 B.只能有唯一的存储结构 C.是指某一种数据元素之间的存储关系 D.以上三种说法均不正确 3。把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为()。 A.物理结构 B.逻辑结构 C.算法的具体实现 D.给相关变量分配存储单元 4.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行()。 A.p->next=s;s->next=p->next B.p->next=s->next C.p=s->next D.s->next=p->next;p->next=s 5.在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算为(）。 A.f->next=s;f=s B.r->next=s;r=s C.s->next=r;r=s D.s->next=f;f=s 1350
试卷代号:1252 座位号口二」 中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试 计算机科学技术专业 数据结构(本) 试题 2008年 7月 题 号 四 总 分 分 数 得 分 评卷人 一、单项选择题(每小题 2分，共 30分) 1.非空的单向循环链表的尾结点满足( )(设头指针为 head，指针p指向尾结点)。 A. p->next= =NULL B. p= =NULL C. p->next= =head D. p= =head 2.一种逻辑结构( )。 A.可以有不同的存储结构 B.只能有唯一的存储结构 C.是指某一种数据元素之间的存储关系 D.以上三种说法均不正确 3.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为( )。 A.物理结构 B.逻辑结构 C.算法的具体实现 D.给相关变量分配存储单元 4.在一个单链表中p所指结点之后插人一个 s所指的结点时，可执行( )。 A. p->next= s; s->next= p->next B. p->next=s->next C. p=s->next D. s->next =p->next; p->next=s 5.在一个链队中，假设 f和 r分别为队头和队尾指针，则插入s所指结点的运算为( A. f->next=s; f=s B. r->next=s;r=s C. s--,next =r;r=s D. s->next=f;f=s 1350
6.元素1,3,5,7按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交 替进行)。 A.7,5,3,1 B.1,3,5,7 C.7,5,1,3 D.3,1,7,5 7.设有一个20阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存 储到一维数组B中（数组下标从1开始），则矩阵中元素a,2在一维数组B中的下标是()。 A.41 B.32 C.18 D.38 8.设有两个串p和q,求q在p中首次出现的位置的运算称作( )。 A.连接 B.求子串 C.求串长 D.模式匹配 9.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为( A.2i B.2i-1 C.2i+1 D.2i+2 10.设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有() 个结点。 A.2n B.2n+1 C.2n+2 D.2n-1 11.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能 到的一种顶点序列为()。 图1 A.abecdf B.acfebd C.aebefd D.aedfcb 1351
6.元素 1,3,5,7按顺序依次进栈，则该栈的不可能输出序列是( )(进栈出栈可以交 替进行)。 A. 7，5,3，1 B. 1，3，5,7 C. 7,5，1,3 D.3，1，7，5 7.设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存 储到一维数组 B中(数组下标从 1开始)，则矩阵中元素 as, 2在一维数组 B中的下标是( )。 A. 41 B. 32 C. 18 D. 38 8.设有两个串P和 9，求 q在 P中首次出现的位置的运算称作( )。 A.连接 B.求子串 C。求串长 D.模式匹配 9。在一棵二叉树中，若编号为 i的结点存在左孩子，则左孩子的顺序编号为( )。 A. 2i B.21一 1 C. 2i十1 D. 2i十2 10.设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有( ) 个结点。 A. 2n B. 2n十1 C. 2n+2 D. 2n一1 11.已知如图 1所示的一个图，若从顶点 a出发，按深度优先搜索法进行遍历，则可能‘ 到的一种顶点序列为( )。 图 1 A. abecdf B. acfebd C. aebcfd D. aedfcb 1351
】2.线性表以( )方式存储，能进行折半查找。 A.关键字有序的顺序 B.顺序 C.链接 D.二插树 13.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功 的平均比较次数为( ）。 A.35/12 B.39/12 C.41/12 D.37/12 14.设已有m个元素有序，在未排好序的序列中挑选第m十1个元素，并且只经过一次元 素的交换就使第m十1个元素排序到位，该方法是()。 A.折半排序 B.冒泡排序 C.归并排序 D.简单选择排序 15.一组记录的关键字序列为(47,80,57,39,41,46)，利用堆排序（堆顶元素是最小元素） 的方法建立的初始堆为( )。 A.39,41,46,80,47,57 B.39,47,46,80,41,57 C.41,39,46,47,57,80 D.39,80,46,47,41,57 得分 评卷人 二、填空题（每小题2分，共24分） 1.结构中的数据元素存在一对多的关系称为 结构。 2.求两个阶矩阵的乘积，算法的基本操作和时间复杂度分别为 和 1352
12.线性表以( )方式存储，能进行折半查找。 A.关键字有序的顺序 B.顺序 C.链接 D.二插树 13.有一个长度为 12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功 的平均比较次数为( )。 A. 35/12 B. 39八2 C. 41八2 D. 37八2 14.设已有 m个元素有序，在未排好序的序列中挑选第 m+1个元素，并且只经过一次元 素的交换就使第 m+1个元素排序到位，该方法是( )。 A.折半排序 B.冒泡排序 C.归并排序 D.简单选择排序 15.一组记录的关键字序列为(47,80,57,39,41,46)，利用堆排序(堆顶元素是最小元素) 的方法建立的初始堆为( )。 A. 39，41,46,80,47，57 B. 39，47，46,80,41，57 C. 41，39,46,47,57,80 D.39,80,46,47,41,57 得 分 评卷人 二、填空题【每小题 2分，共 24分) 1.结构中的数据元素存在一对多的关系称为_ 结构。 2.求两个 n阶矩阵的乘积，算法的基本操作和时间复杂度分别为 和 1352
3.在一个单向链表中，要别除p所指结点，已知q指向P所指结点的前驱结点。则可以 用操作 4.向一个栈顶指针为h的链栈中插人一个s所指结点时，可执行 和 h=s;操作。（结点的指针域为next) 5.串的两种最基本的存储方式分别是 和 6.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 和 三项信息。 7.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 个结点。 (根所在结点为第1层) 8.一棵二叉树中有2一2条边（结点间的连线），其中每一个非叶结点的度数都为2，则该 树共有 个非叶结点。 9.如图2所示的二叉树，其中序遍历序列为 h 图2 10.哈希函数是记录关键字值与该记录 之间所构造的对应关系。 11.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插人排序时，当把第7个记 录65插人到有序表时，为寻找插入位置需比较 次。 l2.n个元素进行冒泡法排序，通常需要进行 趟冒泡，第j趟冒泡要进行 次元素间的比较。 1353
3.在一个单向链表中，要删除P所指结点，已知Q指向P所指结点的前驱结点。则可以 用操作 4.向一个栈顶指针为h的链栈中插人一个s所指结点时，可执行_ 和 h=s;操作。(结点的指针域为next) .串的两种最基本的存储方式分别是 _和 _ 。 .对稀疏矩阵进行 压缩存储，矩阵 中每个 非零元素对应的三元组包括该元素 的 __和 三项信息。 7.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_ 个结点。 (根所在结点为第 1层) 8.一棵二叉树中有 2n-2条边(结点间的连线)，其中每一个非叶结点的度数都为 2，则该 树共有 个非叶结点。 如图 2所示的二叉树，其中序遍历序列为 图 2 哈希函数是记录关键字值与该记录 之间所构造的对应关系。 在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插人排序时，当把第 7个记 : 八U ll 一. 1 1. 1 录65插人到有序表时，为寻找插人位置需比较 次。 12. n个元素进行冒泡法排序，通常需要进行_ 趟冒泡，第J趟冒泡要进行 次元素间的比较 。 1353
得分 评卷人 三、综合题（每小题10分，共30分）】 1.设查找表为(7,15,21,22,40,58,68,80,88,89,120)，元素的下标依次为1,2,3，…，11。 (1)画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） (2)说明成功查找到元素40需要经过多少次比较？ (3)求在等概率条件下，成功查找的平均比较次数？ 2.(1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二 叉排序树，这种说法是否正确？若认为正确，则回答正确，若认为不正确，则举例说明。 (2)设有数据集合{40,29,7,73,101,4,55,2,81,92,39}，依次取集合中各数据，构造一棵 二叉排序树。 3.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈 夫曼编码。 (2)一棵哈夫曼树有个叶结点，它一共有多少个结点？简述理由？ 得 分 评卷人 四、程序填空题（每空2分，共16分） 1.设线性表为(6,10,16,4)，以下程序用说明结构变量的方法建立单向链表，并输出链表 中各结点中的数据。 #define NULL 0 void main() (NODE a,b,c,d,head,p; a.data=6; b.data=10; c.data=16; d,data=4;/d是尾结点*/ head=(1) a.next=&.b; b.next=&c; c.next=&.d; 1354
得 分 评卷人 三、综合题(每小题 10分，共 30分) 1.设查找表为(7,15,21,22,40,58,68,80,88,89,120)，元素的下标依次为 1,2,3,"""""",11, (1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示) (2)说明成功查找到元素 40需要经过多少次比较? (3)求在等概率条件下，成功查找的平均比较次数? 2. (1)如果二叉树中任一结点的值均大于其左孩子的值、小于其右孩子的值，则该树为二 叉排序树，这种说法是否正确?若认为正确，则回答正确，若认为不正确，则举例说明。 (2)设有数据集合{40,29,7,73,101,4,55,2,81,92,39)，依次取集合中各数据，构造一棵 二叉排序树。 3. (1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树，给出相应权重值叶结点的哈 夫曼编码。 (2)一棵哈夫曼树有 n个叶结点，它一共有多少个结点?简述理由? 得 分 评卷人 四、程序填空题(每空 2分，共 16分) 1.设线性表为(6,10,16,4)，以下程序用说明结构变量的方法建立单向链表，并输出链表 中各结点 中的数据 。 #define NULL 0 void main() (NODE a, b，c, d, * head，‘P; a. data= 6; b. data= 10; c. data= 16; d. data= 4;/‘d是尾结点，/ head= (1) ; a. next=乙b; b. next=&c; c. next=乙d; 1354
(2) ；/以上结束建表过程*/ p=head;/p为工作指针，准备输出链表*/ do {printf(“%d\n”,(3) (4) )while((5) 2.以下程序是中序遍历二又树的递归算法的程序，完成程序中空格部分（树结构中左、右 指针域分别为left和right,.数据域data为字符型，BT指向根结点)。 void Inorder (struct BTreeNode BT) if(BT!=NULL) (1) (2) Inorder(BT->right);} } d 利用上述程序对右图进行遍历，结果是(3) 图3 1355
(2) ;/，以上结束建表过程*/ p=head; / * p为工作指针，准备输出链表关/ do {printf(" Yo An"，(3) ); (4) ; }while( (5) ); } 2.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、右 指针域分别为left和 right，数据域 data为字符型，BT指向根结点)。 void Inorder (struct BTreeNode * BT) {if (BT!=NULL){ (1) (2) Inorder(BT-> right);} } 利用上述程序对右图进行遍历 ，结果是 (3) 1355
试卷代号：1252 中央广播电视大学2007一2008学年度第二学期“开放本科”期末考试 计算机科学技术专业数据结构（本） 试题答案及评分标准 (供参考) 2008年7月 一、单项选择题（每小题2分，共30分）》 1.c 2.A 3.A 4.D 5.B 6.C 7.D 8.D 9.A 10.D 11.D 12.A 13.D 14.D 15.A 二、填空题（每小题2分，共24分） 1.树形 2.乘法，0(n3) 3.q->next=p->next; 4.s->next=h; 5.顺序存储 链式存储 6.行下标 列下标 非零元素值 7.12 8.n-1 9.dgbaechif 10.存储地址 11.3 12.n-1n-j 1356
试卷代号:1252 中央广播电视大学2007-2008学年度第二学期“开放本科”期末考试 计算机科学技术专业 数据结构(本) 试题答案及评分标准 (供参考) 2008年 7月 一、单项选择题(每小题 2分，共 30分) 1. C 2. A 3. A 6. C 7. D 8. D 11. D 12. A 13. D 二、填空题(每小题 2分，共 24分) 1.树形 2.乘法，0(n3) 3. q->next=p->next; 4. s->next=h; 5.顺序存储 链式存储 6.行下标 列下标 非零元素值 7.12 8. n一 1 9. dgbaechif 10.存储地址 11.3 12. n一1 n- I 1356 4. D 5. B 9. A 10. D 14. D 15. A
三、综合题（每小题10分，共30分） 1. (1) 10 图4 (2)4次 (3)ASL=(1+2*2+3*4+4*4)/11=3 2. (1)不正确，例 图5 (2) 29 9 55 101 81 图6 1357
三、综合题 (每小题 10分 .共 30分 ) 1 (2)4次 (3)ASL=(1+2，2+3*4+4，4)/11=3 2. (1)不正确 ，例 1357
3. (1) 33 图7 2:0000 30001 001 10 811 901 (2)2n一1个，因为非叶结点数比叶结点数少一个。 四、程序填空题（每空2分，共16分） 1.(1)8a (2)d->next==NULL (3)p->data (4)p=p->next (5)p！=NULL 2.(1)Inorder(BT->left) (2)printf(“%c”,BT->data) (3)dbeafc 1358
(1) 2，0000 ‘. 土 n 甘 1 1 0 0 0 n 介 0 1.1 ‘任 勺 矛 8 11 9 01 (2)2n-1个，因为非叶结点数比叶结点数少一个。 四、程序填空题(每空2分，共 16分) 1.(1)乙a (2 )d->next= =NULL (3) p-> data (4)p=p->next (5) p!=NULL 2.(1)Inorder(BT->Ieft) (2) printf("%c"，BI’一)data) (3)dbeafc 1358