全国自考网成绩查询 全国2013年10月高等教育自学考试数据结构导论试题

全国2013年10月高等教育自学考试数据结构导论试题  

全国 年 月高等教育自学考试数据结构导论试题课程代码

一 单项选择题(本大题共 小题 每小题 分 共 分)在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题后的括号内 错选 多选或未选均无分 数据的基本单位是（　　　）A 数据项                             B 数据类型 C 数据元素                        　 D 数据变量

下列程序的时间复杂度为（　　　）　　i= s= 　　while（s<n）　　{ i++ 　　s=s+i 　　}A O（ ）                     B O（ ）C O（n）                     D O（n ）

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则最节省运算时间的存储方式是（　　　）A 单链表                    B 仅有头指针的单循环链表C 双链表                    D 仅有尾指针的单循环链表

从一个长度为n的顺序表中删除第i个元素（ ≤i≤n）时 需向前移动的元素的个数是（　　　）A n i                           B n i+ C n i                          D i

顺序栈S中top为栈顶指针 指向栈顶元素所在的位置 elem为存放栈的数组 则元素e进栈操作的主要语句为（　　　）A s elem［top］=e                    B s elem［top+ ］=e s top=s top+                            s top=s top+ C s top=s top+                      D s top=s top+ s elem［top+ ］=e                        s elem［top］=e

循环队列sq中 用数组elem［ &# ;&# ; ］存放数据元素 sq front指示队头元素的前一个位置 sq rear指示队尾元素的当前位置 设当前sq front为 sq rear为 则当前队列中的元素个数为（　　　）A                             B C                            D

设有一个 阶的对称矩阵A 采用压缩存储方式以行序为主序存储 a 为第一个元素 其存储地址为 每个元素占有 个存储地址空间 则a 的地址为（　　　）A                            B C                            D

含有 个结点的二叉树中 度为 的结点数为 则度为 的结点数为（　　　） A                             B C                             D

对一棵有 个结点的完全二叉树按层编号 则编号为 的结点 它的父结点的编号为（　　　）A                        B C                        D

可以惟一地转化成一棵一般树的二叉树的特点是（　　　）A 根结点无左孩子                      B 根结点无右孩子C 根结点有两个孩子                    D 根结点没有孩子

有n个结点的有向完全图的弧数是（　　　）A n  　　　　    B nC n(n )         D n(n+ )

设图的邻接链表如题 图所示 则该图的边的数目是（　　　）A                B C               D

已知一个有序表为（ ） 当二分检索值为 的元素时 检索成功需比较的次数是（　　　）A                              B C                               D

排序算法中 第一趟排序后 任一元素都不能确定其最终位置的算法是（　　　）A 选择排序                      B 快速排序C 冒泡排序                      D 插入排序

排序算法中 不稳定的排序是（　　　）A 直接插入排序                          B 冒泡排序C 堆排序                                D 归并排序

二 填空题(本大题共 小题 每小题 分 共 分)请在每小题的空格中填上正确答案 错填 不填均无分 在数据结构中 数据的逻辑结构分为集合 ________ 树形结构和图状结构等四类

通常从正确性 易读性 ________和高效率等 个方面评价算法（包括程序）的质量

顺序表的存储密度为________ 而链表的存储密度为________

对于栈只能在________插入和删除元素

在循环队列中 存储空间为 ～n 设队头指针front指向队头元素前一个空闲元素 队尾指针指向队尾元素 那么队满标志为front=(rear+ )%n 队空标志为________

三个结点可构成________种不同形态的二叉树

对于一棵具有n个结点的二叉树 当进行链接存储时 其二叉链表中的指针域的总数为 n个 其中________个用于链接孩子结点

有向图G用邻接矩阵A［ &# ;&# ;n &# ;&# ;n］存储 其第i列的所有元素之和等于顶点Vi的________

对二叉排序树进行________遍历 可得到排好序的递增结点序列

采用折半查找方法进行查找的数据序列应为________且________

索引文件只能是________ 因为索引文件的组织方式是为随机存取而设计的

在插入和选择排序中 若初始数据基本正序 则选用________ 若初始数据基本反序 则选用________