1、密 封 线 内 不 要 答 题O-O-O-学 号姓 名分校(工作站)O-O-O-试卷代号：11252座位号 国家开放大学2022年秋季学期期末统 一考试数据结构(本) 试题2023年1月题 号二三总 分分 数得 分评卷人一 、单项选择题(把合适的选项编号填写在括号内。每小题3分，共45分)1. 线性结构中数据元素之间的关系是( )。A. 一对一 B. 一 对多C. 多对一 D. 多对多2. 线性表中( )称为线性表的长度。A. 数据最大值B. 数据最小值C. 数据元素个数D. 表的行数3. 与顺序表相比，链表的优势是()。A. 查找数据元素较快B. 修改数据元素较快C. 遍历数据元素较快D.
2、插入数据元素较快4. ( )的一个重要应用是在程序设计中实现递归调用。A. 双向链表 B. 循环链表C. 栈 D. 队列5. 假设存放循环队列的数组长度为 MaxSize, 循环队列能装入的元素最大个数为( )。A. MaxSize B. MaxSize 1C. MaxSize+1 D. MaxSize-2(11252号)数据结构(本)试题第1页(共6页)6. 在 一个栈顶指针为 top 的链栈中删除一个结点时，用 x 保存被删结点的值，则执行()。A.B.C.D.x=top;top=top-next;x=top-data;top=top-next;x=top-data;x=top-data;
3、 top=top-next;7. 判断一个顺序队列 sq(最多元素为m) 为空的条件是( )。A. sq-rear-sq-front=m B. sq-rear-sq-front- 1=mC. sq-front=sq-rear D. sq-front=sq-rear+18. 串函数 strcat(a,b)的功能是进行串( )。A. 比较 B. 复制C. 赋值 D. 连接9. 稀疏矩阵采用压缩存储的目的主要是( )。A. 表达变得简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素D. 减少不必要的存储空间的开销10. 深度为5的二叉树至多有( )个结点。A. 16 B. 32C. 31
4、D. 1011. 如图所示二叉树的中序遍历序列是( )。B. dgbaechfD. abcdefgh)条边。B. n(n+1)D. n(n+1)/2A. abdgcefhC. gdbehfca12. 一个具有n 个顶点的无向完全图包含(A. n(n- 1)C. n(n- 1)/2(11252号)数据结构(本)试题第2页(共6页)密 封 线 内 不 要 答 题二、判断题(根据叙述正确与否在其后面的括号内打对号“ ”或打叉号“”。每小题2分，共30分)13. 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有( )邻接点A. 入边 B. 出边C. 入边和出边 D. 不是入边也不是出边14. 已知一
5、个有序表为11,22,33,44,55,66,77,88,99,则顺序查找元素55需要比较 ( )次。A. 3 B. 4C. 5 D. 615. 依次将每两个相邻的有序表合并成一个有序表的排序方法称为( )A. 插入排序B. 交换排序C. 选择排序D. 归并排序得 分评卷人16. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效 性。( )17. 线性表用顺序方式存储可以随机访问。( )18. 在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针后移，当删除一个元素队列时，头指针后移。( )19. 串函数 strcmp(“ABCd”,“ABCD”)的值为-1。( )20
6、. 设广义表 L=(),(), 则其长度是0。( )21. 队列允许删除的一端称为队尾，允许插入的一端称为队头。( )22. 将新元素插入到队列任意位置是队列的基本运算之一。( )23. 空串的长度是1。( )24. 一个广义表(a),(b),c),(d) 的长度为3,深度为4。( )25. 如果结点A 有3个兄弟，而且B 是 A 的双亲，则 B 的度是4。( )26. 哈夫曼树只存在着双支结点，不存在单支结点。( )27. 无向图的邻接矩阵一定是对称的。( )28.AOV 网拓扑排序的结果是惟一的。( )29. 折半查找的前提条件是，查找表中记录相应的关键字值必须有序或者部分有序。( )30
7、. 对16个元素的序列用冒泡排序法进行排序，最多需要进行15趟冒泡。( )(11252号)数据结构(本)试题第3页(共6页)得 分评卷人三、综合应用及程序设计题(每小题5分，共25分)31. 在下面空格处填写一条语句，以使下面的出栈算法完整ElemType Pop(struct SeqStack*s)ElemType x;if (StackEmpty(s) printf(“栈下溢错误!n”);exit(1);x=s-datas-top;x;returnA.B.C.D.s-top-;s-top+;s-data-;s-data+;32. 在下面空格处填写一条语句，以使下面的循环队列入队算法完整，v
8、oid InQueue(struct SeqQueue * sq,int x) if(sq-rear+1)%MaxSize=sq-front) printf(“循环队列已满!n”);exit(1)sq-rear=(sq-rear+1)%MaxSize;A. x=sq-datasq-rear;B. x=sq-rearsq-data;C. sq-rearsq-data=x;D. sq-datasq-rear=x;(11252号)数据结构(本)试题第4页(共6页)密 封 线 内 不 要 答 题33. 以下程序段执行后，c 的值为( )。char *a5=“12378”,”1237”,”1236789
9、”,”1237”,”123708”int i,c=0for(i=0;i5;i+)if (strcmp(ai,”1237”)=0)c+;A. 2 B. 5C. 0 D. 123734. 已知一个无向图的邻接矩如下所示，写出从顶点0出发按深度优先搜索遍历得到的顶点序列。( )0 1 2 3 4 5 6A.0,2,3,4,5,1,6 B.0,2,3,5,1,6,4C. 0,2,3,5,6,1,4 D.0,2,3,4,5,1,635. 以下直接插入排序算法对存放在ao,a1, ,an-1 中，长度为 n 的记录序列按关键字key 由小到大排序，完成程序中空格部分。void disort(NODE a, int n) int i,j;NODE tempifor(i=1;i=0&temp.keytop- - ;32.D. sq- datasq- rear= x;33.A. 234.C. 0,2,3,5,6,1,435.C. j- -页 (共 1 页 )(11252 号 ) 数据结构 (本 ) 答案第 1
