试卷代号：1252 座位号■ 国家开放大学（中央广播电视大学）2016年春季学期“开放本科”期末考试 数据结构（本） 试题 2016年7月 题 号 二 三 四 总 分 分 数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.对稀疏矩阵进行压缩存储，可采用三元组表，一个10行8列的稀疏矩阵A共有73个 零元素，其相应的三元组表共有( )个元素。 A.8 B.80 C.7 D.10 2.字符串( )是“abcd321ABCD”的子串。 A.“21AB” B.“abcD" C.“aBCD” D.“321a” 3.栈和队列的共同特点是()。 A.都是操作受限的线性结构 B.元素都可以随机进出 C.都是先进后出 D.都是先进先出 4.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点，要为结点p所指 结点赋值x,并入队的运算为p一>data=x;p一>next=NULL;()。 A.f->next-p;f=p; B.r->next=p;r=p; C.r=p;p->next=r; D.p->next=f;f=p; 5.数据结构中，与所使用的计算机无关的是数据的( )结构。 A.逻辑 B.存储 C.逻辑与存储 D.物理 842
试卷代号 :1252 座位号 国家开放大学(中央广播电视大学)2016 年春季学期"开放本科"期未考试 数据结构(本} 试题 题号|一|二|三|四|总分| |分数 得分|评卷入 i i i 一、单项选择题(每小题 分，共 30 分} 2016 1.对稀疏矩阵进行压缩存储，可采用三元组表，一个 10 列的稀疏矩阵 共有 73 零元素，其相应的三元组表共有( )个元素。 A.8 B.80 C.7 D.IO 2. 字符串( )是 "abcd321 ABCD" 的子串。 A. "21AB" B. "abcD" C. "aBCD" D. "321a" 3. 战和队列的共同特点是( )。 A. 都是操作受限的线性结构 C. 都是先进后出 B. 元素都可以随机进出 D. 都是先进先出 4. 在一个链队中，假设 分别为队头和队尾指针， 指向一个新结点，要为结点 所指 结点贼值 ，并入队的运算为 p->data=x 叩一 >next=NULL;C )。 A. >next=p;f=p; B.r >next=p;r=p; C. r=p;p >next=r; D. p->next=f;f=p; 5. 数据结构中，与所使用的计算机无关的是数据的( )结构。 A. 逻辑 C. 逻辑与存储 842 B. 存储 D. 物理
6.顺序表所具备的特点之一是()。 A.可以随机访问任一结点 B.不需要占用连续的存储空间 C.插人元素的操作不需要移动元素 D.删除元素的操作不需要移动元素 7.数据元素是数据的基本单位，它()。 A,只能有一个数据项组成 B.至少有二个数据项组成 C.可以是一个数据项也可以由若干个数据项组成 D.至少有一个数据项为指针类型 8.设有头指针为head的非空的单向链表，指针p指向其尾结点，要使该单向链表成为单 向循环链表，则可利用下述语句()。 A.p=head; B.p=NULL; C.p->next=head; D.head=p; 9.在线性表的顺序结构中，以下说法正确的是( ）。 A.逻辑上相邻的元素在物理位置上不一定相邻 B.数据元素是不能随机访问的 C.逻辑上相邻的元素在物理位置上也相邻 D.进行数据元素的插入、删除效率较高 10.对链表，以下叙述中正确的是()。 A,不能随机访问任一结点 B.结点占用的存储空间是连续的 C.插人删除元素的操作一定要要移动结点 D.可以通过下标对链表进行直接访问 11.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插人元素作 为新表的第5个元素)，则移动元素个数为()。 A.30 B.31 C.5 D.6 12.设有一个长度为40的顺序表，要删除第10个元素（下标从1开始）需移动元素的个数 为( )。 A.11 B.10 C.30 D.31 843
6. 顺序表所具备的特点之一是( )。 A. 可以随机访问任一结点 B. 不需要占用连续的存储空间 C. 插人元素的操作不需要移动元素 D. 删除元素的操作不需要移动元素 7. 数据元素是数据的基本单位，它( )。 A. 只能有一个数据项组成 B. 至少有二个数据项组成 C. 可以是一个数据项也可以由若干个数据项组成 D. 至少有一个数据项为指针类型 8. 设有头指针为 head 的非空的单向链表，指针 指向其尾结点，要使该单向链表成为单 向循环链表，则可利用下述语句( )。 A. p=head; C. >next=head; B. p=NULL; D. head=p; 9. 在线性表的顺序结构中，以下说法正确的是( )。 A. 逻辑上相邻的元素在物理位置上不一定相邻 B. 数据元素是不能随机访问的 C. 逻辑上相邻的元素在物理位置上也相邻 D. 进行数据元素的插入、删除效率较高 10. 对链表，以下叙述中正确的是( )。 A. 不能随机访问任一结点 B. 结点占用的存储空间是连续的 C. 插入删除元素的操作一定要要移动结点 D. 可以通过下标对链表进行直接访问 11. 设有一个长度为 35 的顺序表，要在第 个元素之前插入 个元素(也就是插入元素作 为新表的第 个元素) ，则移动元素个数为( )。 A.30 C.5 B.31 D.6 12. 设有一个长度为 40 的顺序表，要删除第 10 个元素(下标从 开始)需移动元素的个数 为( )。 A.11 C.30 B. 10 D. 31 843
13.设有一个25阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中（数组下标从1开始），则矩阵中元素7,5在一维数组B中的下标是()。 A.25 B.24 C.26 D.27 14.线性表在存储后，如果相关操作中有要求：利用已知的指向某结点的指针或序号，访问 该结点的前驱结点，则采用()的存储方式是不可行的。 A.单向链表 B.双向链表 C.单向循环链表 D.顺序表 15.在一棵二叉树中，若编号为i的结点存在左孩子，i结点的左孩子的顺序编号为()。 A.i/2.0 B.2*i C.2*i+1 D.i+2 得 分 评卷人 二、填空题（每小题2分，共24分） l6.广义表((b,a,c),c,d,f,e,((i,j),k)的长度是 17.数据结构中，数据元素之间的抽象关系称为 结构。 18.栈的操作特点是后进 19.广义表(b,a,c),c,d,f,e,((i,j),k))的表头是 20.设有一个长度为18的顺序表，第8号元素到第18号元素依次存放的值为8,9，…，18.某人 想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i一一)a[i一1]=a[];即从第18 号元素开始，直到第9号元素，每个元素依次向前（左）移动1个位置，事实上这样做是错误的，其 结果新表中第9号元素的值为 21.一棵二叉树，有1个2度结点，2个1度结点，则该树共有 个结点。 22.设有一棵深度为5的完全二叉树，该树共有21个结点，第5层上有 个结点。 (根所在结点为第1层) 23.中序遍历 树可得到一个有序序列。 24.序列12,10,13,11,16,14，采用冒泡排序算法，经一趟冒泡后，序列的结果是 (按升序排序) 25.对16个元素的序列用冒泡排序法进行排序，共需要进行」 趟冒泡。 26.一棵有16个叶结点的哈夫曼树，则该树共有 个非叶结点。 27.在对一组记录(40,24,82,9,1,78,46,31,69)进行直接插人排序（由小到大排序），当把 第7个记录46插人到有序表时，为寻找插人位置需比较 次。 844
13. 设有一个 25 阶的对称矩阵 ，采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组 中(数组下标从 开始) ，则矩阵中元素衔， 在一维数组 中的下标是( )。 A.25 C.26 B.24 D. 27 14. 线性表在存储后，如果相关操作中有要求:利用已知的指向某结点的指针或序号，访问 该结点的前驱结点，则采用( )的存储方式是不可行的。 A. 单向链表 B. 双向链表 c.单向循环链表 D. 顺序表 15. 在一棵二叉树中，若编号为 的结点存在左孩子， 结点的左孩子的顺序编号为( )。 A. i/2. 0 C. i+1 B.2 D.i+2 二、填空题{每小题 分，共 24 分} 16. 广义表 ((b c) , c , d ,f, e , ((i,j) k)) 的长度是一一-一一 17. 数据结构中，数据元素之间的抽象关系称为一一一一一结构。 18. 榜的操作特点是后进 19. 广义表 ((b ，心， d , f, e , ( (i, j) , k) )的表头是一一一一一- 20. 设有一个长度为 18 的顺序表，第 号元素到第 18 号元素依次存放的值为 ，"'， 18. 某人 想要删除第 号元素，程序中他的做法是用语句 forO=18;i<=9;i 一一 )a[i -1J=a[iJ; 即从第 18 号元素开始，直到第 号元素，每个元素依次向前(左)移动 个位置，事实上这样做是错误的，其 结果新表中第 号元素的值为一一一一。 1.一棵二叉树，有 度结点， 度结点，则该树共有一一一一-个结点。 22. 设有一棵深度为 的完全二叉树，该树共有 21 个结点，第 层上有一一一一一个结点。 (根所在结点为第 层) 23. 中序遍历 树可得到一个有序序列。 24. 序列 12 10 13 11 16 14 ，采用冒泡排序算法，经一趟冒泡后，序列的结果是 〈按升序排序〉 25. 16 个元素的序列用冒泡排序法进行排序，共需要进行一一一一一趟冒泡。 26. 一棵有 16 个叶结点的哈夫曼树，则该树共有 个非叶结点。 27. 在对一组记录 (40 24 82 78 46 31 69) 进行直接插入排序(由小到大排序) ，当把 个记录 46 插入到有序表时，为寻找插入位置需比较-一一一一次。 844
得分 评卷人 三、问答和综合题（每小题10分，共30分）】 28.设有序表为(5,8,14,15,33,51,61,73,81,82,93)，元素的序号依次为1,2,3，…，11. (1)画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示） (2)说明成功查找到元素33需要经过多少次比较？ (3)在等概率条件下，给出成功查找的平均查找长度？ 29.(I)如图1所示，若从顶点a出发，首先经过c按图的深度优先搜索法进行遍历，给出 可能得到的一种顶点序列。 图1 (2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列。 图2 30.(1)设数据集合a一{7,4,9,8,6,5,3}，依次取a中各数据，构造一棵二叉排序树。 (2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？ (3)给出对上述二叉排序树进行中序遍历的序列 845
|得分|评卷人| | 三、问答和综合题{每小题 10 分，共 30 分} 28. 设有序表为(5 14 15 33 51 61 73 81 82 93) ，元素的序号依次为 ，……， 11. (1)画出对上述查找表进行折半查找所对应的判定树〈树中结点可用序号表示) (2) 说明成功查找到元素 33 需要经过多少次比较? (3) 在等概率条件下，给出成功查找的平均查找长度? 29. (1)如图 所示，若从顶点 出发，首先经过 按图的深度优先搜索法进行遍历，给出 可能得到的一种顶点序列。 (2) 设有向图如图 所示下，写出首先删除顶点 种拓扑序列。 30. (1)设数据集合 a= {7 ,4, 9, 8, 6 , 5 3} ，依次取 中各数据，构造一棵二叉排序树。 (2) 对该二叉树进行查找，成功查找到 要进行多少次元素间的比较? (3) 给出对上述二叉排序树进行中序遍历的序列 845
得 分 评卷人 四、程序填空题（每空2分，共16分） 31.以下函数在a[0]到a[n一1]中，用折半查找算法查找关键字等于k的记录，查找成功 返回该记录的下标，失败时返回一1，完成程序中的空格 typedef struct int key; 中44*4 }NODE; int Binary_Search(NODE a[],int n,int k) { int low,mid,high; low=0; high=n-1; while① mid=(low+high)/2; if(a[mid].key==k) return② elseif(③ low=mid++1; else④ ⑤ 32.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针。 struct node ElemType data; struct node next; }； struct node top; void Push(ElemType x) structnode p; p=(struct node￥)malloc① p->data=x; ② ③ 846
|得分|评卷人| | 四、程序填空题{每空 分，共 16 分) 1.以下函数在 a[O] a[n-1] 中，用折半查找算法查找关键字等于 的记录，查找成功 返回该记录的下标，失败时返回一 ，完成程序中的空格 typedef struct { int key; }NODE; int Binary_Search(NODE 口， int n , int k) int low , mid , high ; low=O; high=n-1; while① ⑤ mid= (low+high)/2; if(a[mid]. key= =k) return② elseif③ low=mid+1; else④ 32. 以下函数为链榜的进找操作， 是要进楼的结点的数据域， top 为钱顶指针。 struct node 846 { ElemType data; struct node next; struct node top; void Push(ElemType x) { structnode p; p= (struct node )mal1 oc >data=x; ② ③
试卷代号：1252 国家开放大学（中央广播电视大学）2016年春季学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2016年7月 一、单项选择题（每小题2分，共30分） 1.c 2.A 3.A 4.B 5.A 6.A 7.C 8.C 9.C 10.A 11.B 12.C 13.C 14.A 15.B 二、填空题（每题2分，共24分） 16.6 17.逻辑 18.先出 19.(b,a,c) 20.18 21.5 22.6 23.二叉排序树 24.10,12,11,13,14,16 25.15 26.15 27.3 847
试卷代号 :1252 国家开放大学(中央广播电视大学 )2016 年春季学期"开放本科"期未考试 数据结构(本) 试题答案及评分标准 (供参考) -、单项选择题{每小题 分，共 30 分} 1. C 6.A 11. B 2.A 7. C 12. C 二、填空题{每题 分，共 24 分} 16.6 17. 逻辑 18. 先出 19. Cb ,a , c) 20.18 21. 5 22.6 23. 二叉排序树 24.10 , 12 , 11 , 13 , 14 , 16 25. 15 26.15 27.3 3.A 8. C 13. C 4. B 9. C 14. A 5.A 10. A 15. B 2016 847
三、综合应用题（每小题10分，共30分） 28.(1)图3 51 6 14 3 81 9 15 61 82 4 2 33 5 73 8 93 11 图3 (2)4次 (3)(1+2*2+3*4+4*4)/11=33/11=3 29.(1)acdbfeh (2)152364或152634或156234 30.(1)图4 7 9 3 6 5 图4 (2)4 (3)3,4,,5,6,7,8,9 848
三、综合应用题{每小题 10 分，共 30 分} 28. (1)图 (2 )4次 (3) (1 +2 2+3 铸的 /11=33/11=3 29. (1 )acdbfeh (2 )1 52364 152634 156234 30. (1)图 (2)4 (3)3 ,4 ,, 5 ,6 ,7 ,8 ,9 848
四、程序填空题（每空2分，共16分） 31.(1)low<=high (2)mid (3)a[mid].key<k (4)high=mid-1 (5)return-1 32.(1)sizeof(struct node) (2)p→next=top (3)top=P 849
四、程序填空题{每空 分，共 16 分} 31. (1) low< = high (2)mid (3)a[midJ. key<k (4)high=mid-1 (5)return-1 32. (1 )sizeof(struct node) (2)p• next=top (3hop=p 849