数据结构考卷.doc

南京航空航天大学 《数据结构（C语言版）》期末考试 姓名： 班级： 学号： 选择题（1.5X18=27） 数据结构中，从逻辑上可以把数据结构分为( ) A.紧凑结构和非紧凑结构 B.线性结构和非线性结构 C.动态结构和静态结构 D.内部结构和外部结构 以下说法正确的是( ) A.数据元素是数据的基本单位 B.数据结构是带结构的数据项的集合C.存储数据时只要考虑数据元素的值 D.数据项是数据的可分割的最小单位 在数据结构中，与所使用的计算机无关的是数据的( )结构。 A.存储 B.逻辑 C.逻辑和存储 D.物理 4、下列结构中，哪个是不属于数据逻辑结构。( ) A.树形结构 B.图状结构 C. 线性结构 D.物理结构 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( ) A.冒泡排序 B.直接插入排序 C.希尔排序 D.直接选择排序 查找效率最高的二叉排序树是( ) A.平衡二叉树 B.所有节点的右子树都为空的二叉排序树 C.没有左子树的二叉排序树 D.所有节点的左子树都为空的二叉排序树 一个二叉数节点的中序序列为ABCDEFG，后序序列为ABDCAFGE，则其左子树中节点数目为( ) A.2 B.3 C.4 D.5 某森林F对应的二叉树为B，他有m个节点，B的根为p，p的右子树的节点个个数为n，森林F中第一棵树的节点的个数为( ) A.m-n B.m-n-1 C.n-1 D.m-1 子串“ture”在主串“datadistructurer”中的位置是( ) A.5 B.8 C.11 D.12 一个有n个节点的二叉链表中，空链域的个数为( ) A.n B.n+1 C.n-1 D不确定 10、下面关于A树和A+树的表述，不正确的是( ) A. A树和A+树都是平衡的多茶树 B .A树和A+树都可用于文件索引结构 C .A树和A+树都能有效的支持顺序查找 D. A树和A+树都能有效支持随即查找 11、采用这版查找法查找长度为n的线性表时，每隔元素的平均查找长度为( ) A .O(log2n) B. O(n2) C .O(nlog2n) D .O(n+1) 12、无向图中，所有顶点度数之和等于所有边数的( )倍。 A.1/2 B.1 C.2 D.4 13、某一数组中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1只10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素[8][5]的起始地址为( ) A.SA+141 B. SA+222 C. SA+225 D. SA+228 14、一个队列的入队列序列是2,4,6,8，则队列的输出队列是( ) A .8,6,4,2 B.2,6,4,8 C.2,8,6,4 D.2,4,6,8 15、数据结构中，队列与栈具有相同点是( ) A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有相同点 16在长度为m的线性表采取顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( ) A.O(m) B .O(0) C . O(1) D .O(2m) 17、深度为4的二叉树至多有( )个节点。 A.8 B.7 C.32 D.31 18下列论述中，正确的是( ) I.只有一个节点的二叉树的度为0；II.深度为k的满二叉树的节点数为2k-1； III.二叉树的左右子树可任意交换；IV.二叉树的第i层至多有2i-1个节点。 A.I 、III、 IV B. I、 II、 III C.II、 III、 IV D. I 、II 、IV 判断题（2X10=20） 取线性表的第i个元素的时间同i的大小有关。( ) 具有10个顶点的无向图，边的总数最多为45。( ) 算法的五个重要特性是有穷性、不确定性、可行性、输入和输出。( )