《2018年10月自考02331数据结构试题及答案含评分.pdf》由会员分享，可在线阅读，更多相关《2018年10月自考02331数据结构试题及答案含评分.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 2018 年 10 月高等教育自学考试全国统一命题考试 数据结构 试卷(课程代码 02331)本试卷共 7 页，满分 l00 分，考试时间 l50 分钟。考生答题注意事项：1本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2第一部分为选择题。必须对应试卷上的题号使用 2B 铅笔将“答题卡”的相应代码涂黑。3第二部分为非选择题。必须注明大、小题号，使用 05 毫米黑色字迹签字笔作答。4合理安排答题空间，超出答题区域无效。第一部分 选择题 一、单项选择题：本大题共 l5 小题，每小题 2 分，共 30 分。在每小题列出的备选项中 只有一项是最符合题目要求的。请将
2、其选出。1下列数据结构中，逻辑结构不同的是 A线性表 B栈 C队列 D二叉树 2将 l6 个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地 址是 l000，第 6 个元素的存储地址是 1040，则最后一个元素的存储地址是 A1112 B1120 C1124 D1128 3设栈的初始状态为空，元素 1，2，3，4，5 依次入栈，不能得到的出栈序列是 A1，2，3，4，5 B4，5，3，2，1 C1，2，5，4，3 D1，2，5，3，4 4设指针变量 P 指向非空单链表中的结点，next 是结点的指针域，则判断 P 所指结点 为尾结点前一个结点的逻辑表达式中，正确的是 A.p-n
3、ext!=NULL&p-next 一next-next=NULL Bp-next!=NULL&p-next-nextNULL Cp-next-next=NULL Dp-nextNULL 5已知广义表 LS=(a，b，c)，d)，(e，(fg，(h i)，LS 的深度是 A2 B3 C4 D5 2 6已知一棵完全二叉树 T 的第 5 层上共有 5 个叶结点，则 T 中叶结点个数最少是 A5 88 C10 D27 7已知二叉树 T 的前序遍历序列为 a，b，c，e，d，中序遍历序列为 C，e，b，d，a，则 T 的后序遍历序列为 Ac，e，d,b，a Bd，e，c，b，a Ce，c，d，b，a D
4、e，c，b，a，d 8有向图 G 有玎个顶点和 e 条边，G 保存在邻接矩阵 M 中，M 中 0 与 1 的个数差是 An(n+1)2-e Bn(n+1)2-2e Cnn-e Dnn-2e 9有向图 G 中所有顶点的度数之和是 24，则 G 中弧的数量是 A10 B12 C14 D16 10设有向图 G 含有 n 个顶点、e 条边，使用邻接表存储。对 G 进行深度优先搜索遍历 算法的时间复杂度是 AO(n)BO(口)CO(n+e)DO(ne)11对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为 A14，26，17，l2，4，7，3 B1
5、2，l4，l7，26，3，4，7 C14，26，12，l7，3，4，7 D14，26，l2，l7，3，7，4 12下列选项中，不稳定的排序方法是 A希尔排序 B归并排序 C直接插入排序 D冒泡排序 13一组记录的关键字为(35，48，47，23，44，88)，利用堆排序算法进行降序排序，建立 的初始堆为 A23，35，48，47，44，88 B23，35，47，48，44，88 C35，23，47，48，44，88 D35，23，47，44，48，88 3 14一棵二叉排序树中，关键字 n 所在结点是关键字 m 所在结点的孩子，则 An 一定大于 m Bn 一定小于 m Cn 一定等于 m D
6、n 与 m 的大小关系不确定 15设敖列表长 m=16，散列函数 H(key)=key15。表中已保存 4 个关键字：addr(18)=3，addr(35)=5，addr(51)=6，addr(22)=7，其余地址均为开放地址。存储关键字 36 时存 在冲突，采用线性探测法来处理。则查找关键字 36 时的探查次数是 A1 B2 C3 D4 第二部分 非选择题 二、填空题：本大题共 l0 小题，每小题 2 分，共 20 分。16数据项是具有独立含义的_标识单位。17指针 P 和 q 分别指向单链表 L 中的两个相邻结点，即 q-next=P。若要在 q 所指结 点后插入指针 r 所指结点，则执行
7、的语句是 r-ne 处=p；_。18递归算法设计中的最小子问题称为递归的_。19广义表(a，b)，(c，d)，e，(f(g,h)的表尾是_。20已知二叉树的前序遍历序列和后序遍历序列，则对应的二叉树_确定。21如果有向无环图 G 中仅有一个顶点的入度为 0，若要求 G 的拓扑序列不唯一，则 G 中必须存在一个出度至少为_的顶点。22将森林 T 转换为一棵二叉树 T1，在 T 中结点 A 是结点 B 的右邻的兄弟(下一个兄 弟)，则在 T1 中，A 是 B 的_结点。23对含玎个元素的数据序列采用快速排序算法进行排序，平均时间复杂度 是_。24散列存储中，常用的解决冲突的方法有开放地址法和_两大
8、类。25假设顺序存储的有序表 R 含有 8 个关键字，进行二分查找时，平均查找长度 4 为_。三、解答题：本大题共 4 小题，每小题 5 分，共 20 分。26设电文字符集是el，e2，e3，e4，e5)，各字符出现的次数分别为36，l3，26，l8，23。现要为该字符集设计哈夫曼编码。请回答下列问题。(1)给出构造的哈夫曼树。(2)给出各字符的哈夫曼编码。(3)计算电文编码总长。27已知图 G 采用邻接矩阵存储，邻接矩阵如题 27 图所示。(1)根据邻接矩阵画出图 G。(2)根据图 G 写出从顶点 A 开始图 G 的 1 个深度优先搜索遍历序列。(3)根据图 G 写出从顶点 A 开始图 G
9、的 1 个广度优先搜索遍历序列。28有数据序列(12，l7，O5，l0，20，24，45，ll，l0，l2)，使用希尔排序方法将其排成升序序列。请回答下列问题。(1)分别写出增量为 3 和 1 的希尔排序结果。(2)计算第一趟希尔排序中数据元素之间的总交换次数(两个 (a)元素之间的交换记 l 次)。5 29设有二叉排序树 T 如题 29 图所示。现需在 T 中删除结点 e，请 回答下列问题。(1)画出删除后的二叉排序树(仅需画出一棵)。(2)在你实现的删除过程中，指针域更新的次数是多少?四、算法阅读题：本大题共 4 小题，每小题 5 分，共 20 分。30顺序表类型定义如下：6 7 8 9 10 11