试卷代号：1252 座位 国家开放大学（中央广播电视大学）2014年秋季学期“开放本科”期末考试 数据结构（本）试题 2015年1月 题 号 三 四 总 分 分 数 得分 评卷人 一、单项选择题（每小题2分，共30分） 1.一种逻辑结构在存储时()。 A.只要存储数据元素间的关系 B.只能采用一种存储结构 C.可采用不同的存储结构 D.只要存储数据元素的值 2.对链表，以下叙述中正确的是( )。 A.不能随机访问任一结点 B.结点占用的存储空间是连续的 C.插人删除元素的操作一定要移动结点 D.可以通过下标对链表进行直接访问 3.线性表在存储后，如果相关操作是：要求已知第ⅰ个结点的位置访问该结点的前驱结 点，则采用( )存储方式是不可行的。 A.单链表 B.双链表 C.单循环链表 D.顺序表 4.栈和队列的共同特点是()。 A.都是先进后出 B.元素都可以随机进出 C.只容许在端点处插入和删除元素 D.都是先进先出 1028
试卷代号 :1252 座位号 国家开放大学(中央广播电视大学)2014 年秋季学期"开放本科"期末考试 数据结构(本) 试题 2015 E 一、单项选择题(每小题 分，共 30 分) 1.一种逻辑结构在存储时( )。 A. 只要存储数据元素间的关系 c.可采用不同的存储结构 2. 对链表，以下叙述中正确的是( A. 不能随机访问任一结点 B. 结点占用的存储空间是连续的 c.插入删除元素的操作一定要移动结点 B. 只能采用一种存储结构 D.只要存储数据元素的值 D. 可以通过下标对链表进行直接访问 3. 线性表在存储后，如果相关操作是:要求已知第 个结点的位置访问该结点的前驱结 点，则采用( )存储方式是不可行的。 A. 单链表 B. 双链表 c. 单循环链表 D.顺序表 4. 校和队列的共同特点是( )。 A. 都是先进后出 B.元素都可以随机进出 c.只容许在端点处插入和删除元素 D. 都是先进先出 1028
5.元素2,4,6,8按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的可能输 出序列是( )(进栈出栈可以交替进行)。 A.8,6,2,4 B.8,4,2,6 C.6,2,4,8 D.8,6,4,2 6.在一个不带头结点的链队中，假设「和r分别为队头和队尾指针，则从该对列中删除一 个结点并把结点的值保存在变量x中的运算为()。 A.x=r→data;r=r→next B.r=r→next;x=r→data C.x=f-data;f=f-next; D.f=f→next;x=f→data 7.设有一个20阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中（数组下标从1开始），则数组中第38号元素对应于矩阵中的元素是()。 (矩阵中的第1个元素是a1,1) A.ato,8 B.a7.6 C.a9.2 D.as.s 8.在C语言中，分别存储“S”和‘s’,各需要占用( )字节。 A.一个和两个 B.两个 C.一个 D.两个和一个 9.一棵有n个结点，采用链式存储的二叉树中，共有( )个指针域被有效使用（即指针 域为非空)。 A.n+1 B.n C.n-1 D.n-2 10.在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为()。 A.i/2.0 B.i/2向下取整 C.2i+1 D.i+2 11.设一棵哈夫曼树共有2n十1个结点，则该树有()个非叶结点。 A.n B.n+1 C.n-1 D.2n 12.一棵完全二叉树共有4层，且第4层上有2个结点，该树共有( )个非叶子结点 (根为第一层)。 A.5 B.4 C.3 D.9 1029
5. 元素 按顺序依次进枝，按该拢的可能输出序列依次入队列，该队列的可能输 出序列是( )(进找出校可以交替进行)。 A.8 , 6 , 2 , 4 C. 6, 2, 4 , 8 B.8 , 4, 2, 6 D. 8 , 6, 4 , 2 6. 在一个不带头结点的链队中，假设 分别为队头和队尾指针，则从该对列中删除一 个结点并把结点的值保存在变量 中的运算为)。 A.x=r• data;r=r• next; B.r=r• next; x=r• data C. x=f• data ;Í=f• next; D. f=f• next; x=f• data 7. 设有一个 20 阶的对称矩阵 ，采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组 中(数组下标从 开始) ，则数组中第 38 号元素对应于矩阵中的元素是( )。 (矩阵中的第 个元素是旬， ) A. a lO, g B. a7 , 6 C. a9 , 2 D. ag , 5 8. 语言中，分别存储 "S" 和‘ s' ，各需要占用( )字节。 A. 一个和两个 B. 两个 c. 一个 D.两个和一个 9. 一棵有 个结点，采用链式存储的二叉树中，共有)个指针域被有效使用(即指针 域为非空)。 A. n+1 C. n-1 B. n D.口一 10. 在一棵二叉树中，若编号为 的结点存在双亲结点，则双亲结点的顺序编号为)。 A. i/2. 0 C. 2i B. i/2 向下取整 D.i 1.设一棵哈夫曼树共有 2n 个结点，则该树有( )个非叶结点。 A.n c. B. D.2n 12. 一棵完全二叉树共有 层，且第 层上有 个结点，该树共有( (根为第一层)。 A.5 C. 3 B.4 D.9 )个非叶子结点 1029
13.如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的 一种顶点序列为()。 b 图1 A.abedfc B.acfebd C.aebcdf D.aebefd 14.一组记录的关键字序列为(56,30,89,66,48,50,94,87,100)，利用快速排序，以第一 个关键字为分割元素，经过一次划分后结果为()。 A.30,50,48,56,66,89,94,100,87 B.50,30,48,56,66,89,94,87,100 C.48,30,50,56,66,89,94,87,100 D.50,30,48,66,56,89,94,87,100 15.线性表以( )方式存储，能进行折半查找。 A.关键字有序的链接 B.顺序 C.关键字有序的顺序 D.数组 得分 评卷人 二、填空题（每小题2分，共24分） 16.数据的逻辑结构在计算机中的表示称为 结构。 17.求两个n阶矩阵的乘积，算法的基本操作为 ,时间复杂度为 18.设有一个长度为25的顺序表，第8号元素到第25号元素依次存放的值为8,9,10， 11,…25,某人想要在第8个元素前插人1个元素7（也就是插入元素作为新表的第8个元 素)，他的做法是从第8号元素开始，直到第25号元素依次向后移动1个位置，然后把7存放 在8号位置，其结果是新表中第25号元素的值为 1030
13. 如图 所示的一个图，若从顶点 出发，按广度优先搜索法进行遍历，则可能得到的 一种顶点序列为( )。 A. abedfc c. aebcdf B. acfebd D. aebcfd 14. 一组记录的关键字序列为 (56 30 89 66 48 50 94 87 100) ，利用快速排序，以第一 个关键字为分割元素，经过一次划分后结果为( )。 A.30 , 50 , 48 , 56 , 66 , 89 , 94 , 100 , 87 B. 50 , 30 , 48 , 56 , 66 , 89 , 94 , 87 , 100 C.48 , 30 , 50 , 56 , 66 , 89 , 94 , 87 , 100 D.50 , 30 , 48 , 66 , 56 , 89 , 94 , 87 , 100 15. 线性表以( )方式存储，能进行折半查找。 A. 关键字有序的链接 B. 顺序 C. 关键字有序的顺序 D. 数组 二、填空题(每小题 分，共 24 分} 16. 数据的逻辑结构在计算机中的表示称为 结构。 17. 求两个 阶矩阵的乘积，算法的基本操作为 ，时间复杂度为 18. 设有一个长度为 25 的顺序表，第 号元素到第 25 号元素依次存放的值为 10 11 ，… 25 ，某人想要在第 个元素前插入 个元素 7( 也就是插入元素作为新表的第 个元 素) ，他的做法是从第 号元素开始，直到第 25 号元素依次向后移动 个位置，然后把 存放 号位置，其结果是新表中第 25 号元素的值为 1030
19.在双向链表中，要在p所指结点后插入q所指的结点（设q所指的结点已赋值），其中 所用的一条语句(p一>next)一>prior=q;功能是使P所指结点的 指向q。 20.设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有p→ next=为=NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过操作head= head->next; 21.从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行_ 。(结点的指针域为next,数据域为data) 22.循环链队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,采用 少用一个元素的模式)，判断循环链队列为满的条件为 23.对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A相应的三元 组表共有8个元素，则矩阵A共有 个零元素。 24.一棵有8个权垂值构造的哈夫曼树，共有个结点。 25.一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有 个1度结 点。 26.如图2所示的二叉树，其先序遍历序列为 9 图2 27.在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为 1031
19. 在双向链表中，要在 所指结点后插入 所指的结点(设 所指的结点己赋值) ，其中 所用的一条语句句一 >next) >prior=q; 功能是使 所指结点的 指向 0 20. 设有一个带头结点的，头指针为 head 的单向链表， 指向表中某一个结点，且有 next= =NULL ，现要删除头结点，并使该单向链表构造成单向循环链表，通过操作 head= head >next; 1.从一个战顶指针为 top 的链找中删除一个结点时，用 保存被删结点的值，可执行 。(结点的指针域为 next ，数据域为 data) 22. 循环链队列中，设 front rear 分别为队头和队尾指针， (最多元素为 MaxSize ，采用 少用一个元素的模式) ，判断循环链队列为满的条件为 23. 对稀疏矩阵进行压缩存储，可采用三元组表，一个 列的稀疏矩阵 相应的三元 组表共有 个元素，则矩阵 共有 个零元素。 24. 一棵有 个权垂值构造的哈夫曼树，共有一-一一个结点。 25. 一棵有 18 个结点的二叉树，其 度结点数的个数为 ，则该树共有 度结 占。 26. 如图 所示的二叉树，其先序遍历序列为 27. 在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键宇称为 1031
得分 评卷人 三、综合题（每小题10分，共30分） 28.(1)对给定权值3,1,4,4,5,6，构造深度为5的哈夫曼树。（设根为第1层） (2)求树的带权路径长度。 (3)链接存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由。 29.(1)如下的一棵树，给出先序遍历序列 (2)把1,2,3,4,5,6,7,8,9填人，使它成为一棵二叉排序树 提示：设图中的树是二叉排序树，找出中序遍历序列与1,2，…9的对应关系 (3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。 A2 A3 A4 A6 A5 A7 A8 A9 图3 30.设查找表为(5,6,7,8,9,10,11,12,13,14) (1)画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点） (2)给出二叉排序树的定义，针对上述折半查找所对应的判定树的构造过程，说明判定树 是否是二叉排序树（设树中没有相同结点）？ (3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？ 1032
三、综合题{每小题 10 分，共 30 分) 28. (1)对给定权值 ，构造深度为 的哈夫曼树。(设根为第 层) (2) 求树的带权路径长度。 ( 3) 链接存储上述哈夫曼树，结点中共有多少个指针域为空，说明理由。 29. (1)如下的一棵树，给出先序遍历序列 (2) 填人，使它成为一棵二叉排序树 提示:设图中的树是二叉排序树，找出中序遍历序列与 2. 的对应关系 (3) 请在该树中再插入一个结点 3. 作为叶结点，并使它仍然是一棵二叉排序树。 13 30. 设查找表为 (5 10 11 12 13 14) (1)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2) 给出二叉排序树的定义，针对七述折半查找所对应的判定树的构造过程，说明判定树 是否是二叉排序树(设树中没有相同结点)? (3) 为了查找元素 5.5 ，经过多少次元素间的比较才能确定不能查到? 1032
得分 评卷人 四、程序填空题（每空2分，共16分） 31.以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完 成程序中的空格 typedef struct int key; 4 )NODE; void selsort(NODE a[],int n) int i,j,k; NODE temp; for(i=1;i<= i++) { k=i; for(j=i+1;j<= j++) if(a[j].key<a[k].key) if(i!=k) temp=ai]; 32,设有一个头指针为head的不带头结点单向链表，且p、q是指向链表中结点类型的 指针变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同)，写出 相关语句 (1)使该单向链表成为单向循环链表 1033
|得分|评卷人| | 四、程序填空题(每空 分，共 16 分) 1.以下函数为直接选择排序算法，对 a[ 口， a[2] ，… a[n] 中的记录进行直接选择排序，完 成程序中的空格 typedef struct int key; }NODE; void selsort(NODE 口， int n) -J 'K n NODE temp; for<i=l;i<= ;i 十十) k=i; for(j=i+l;j<= ;j+ 十) iECa[jJ. key<a[kJ. key) if(i! = k) temp=a[i]; 32 .设有一个头指针为 head 的不带头结点单向链表，且 是指向链表中结点类型的 指针变量， 指向链表中某结点 a( 设链表中没有结点的数据域与结点 的数据域相同) ，写出 相关语句 (1)使该单向链表成为单向循环链表 1033
(2)删去a结点 q=p;x=p->data; while (q->next!=NULL)q=q->next; q=p;p=p->next; while(p->data！=x) {q=p; 1034
(2) 删去 结点 q=p; x=p >data; while 何一 >next! =NULL)q=q >next; q=p; p=p >next; while(p >data! =x) { q=p; 1034
试卷代号：1252 国家开放大学（中央广播电视大学）2014年秋季学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2015年1月 一、单项选择题（每小题2分，共30分）】 1.C 2.A 3.A 4.C 5.D 6.C 7.C 8.D 9.C 10.B 11.A 12.B 13.C 14.B 15.C 二、填空题（每题2分，共24分】 16.物理（存储） 17.乘法0(n3) 18.8 19.直接前驱的左指针 20.p->>next=head; 21.d=top->data;top=top->next; 22.front==(rear+1)%MaxSize 23.34 24.15 25.1 26.215347896 27.主关键字 三、综合应用题（每小题10分，共30分） 28.(1) 23 14 图4 1035
试卷代号 :1252 国家开放大学(中央广播电视大学 )2014 年秋季学期"开放本科"期末考试 数据结构(本) 试题答案及评分标准 (供参考) 一、单项选择题(每小题 分，共 30 分) 1. C 2. A 6. C 7. C l 1. A 12.B 二、填空题{每题 分，共 24 分) 16. 物理(存储) 17. 乘法 Q(n3 ) 18. 8 19. 直接前驱的左指针 20. >next= head; 3. A 8. D 13. C 21. d=top->data;top=top->next; 22. front= = (rear+ l) % MaxSize 23.34 24.15 25. 1 26.215347896 27. 主关键字 三、综合应用题(每小题 10 分，共 30 分) 28. (1) 4. C 9. C 14. B 5. D 10. B 15. C 2015 1035
(2)WPL=3%4+14+4*3+6%2+4*2+52=58 (3)共11个结点，22个指针域，除根结点外，每个结点对应一个指针域，共10个指针域非 空，故有22一10=12个空指针域， 29.(1)A1A2A4A7A8A5A9A3A6 (2) (3) 7 4 8 2 5 6 3.5 图5 30.(1) 9 6 12 13 1 10 14 图6 (2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉树：若它的左子树非 空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子树的所有结 1036
(2) WPL=3 4+1 4+4 3+6 2+4 2+5 2=58 (3) 11 个结点， 22 个指针域，除根结点外，每个结点对应一个指针域，共 10 个指针域非 空，故有 22-10=12 个空指针域， 29. (1) A1 A2 A4 A7 A8 A5 A9 A3 A6 (2) (3) U 30. (1) G \ C (2) 二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉树:若它的左子树非 空，则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空，则右子树的所有结 1036
点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值；左，右子树也是一棵二 叉排序树，按定义判定树是二叉排序树。 (3)3次 四、程序填空题（每空2分，共16分） 31.(1)n-1 (2)n (3)k=j (4)a[i]=a[k] (5)a[k]=temp 32.(1)q->next=head; (2)p=p->next; (3)q->next=p->next; 1037
点的值都大于(若允许结点有相同的值，则大于等于)它的根结点的值;左，右子树也是一棵二 叉排序树，按定义判定树是二叉排序树。 (3) 四、程序填空题{每空 分，共 16 分} 31. (l) n-1 (2)n (3)k=j (4) a[iJ=a[kJ (5)a[kJ=temp 32. (1 )q 一> next = head; (2)p=p >next; (3)q >next=p >next; 1037