2009数据结构练习题.doc

2009数据结构练习题 一、选择题 （ D ）1、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 存储方式节省时间： A、 单链表 B、 双链表 C、 单循环链表 D、 顺序表。 （ A ）2、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为 。 A、 98 B、 99 C、 50 D、 48 （ A ）3、数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5,5]的地址是 。 A、 1140 B、 1145 C、 1120 D、 1125 （ C ）4、对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用 实现编号。 A、先序遍历 B、中序遍历 C、后序遍历 D、从根开始进行层次遍历 （ B ）5、栈和队列都是 。 A、顺序存储的线性结构 B、限制存取点的线性结构 C、链式存储的线性结构 D、限制存取点的非线性结构 （ C ）6、若二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 。 A、二叉排序树 B、哈夫曼树 C、堆 D、AVL树 （ C ）7、在顺序表（3,6,8,10,12,15,16,18,21,25,30） C、40,38,46,56,79,84 D、40,38,46,84,56,79 （ D ）9、对包含n个元素的哈希表进行查找，平均查找长度为 。 A、O(log2n) B、 O(n) C、 O(nlog2n) D、 不直接依赖于n （ C ）10、一个有n个顶点的无向图最多有 边。 A、n B、 n(n-1) C、 n(n-1)/2 D、 2n （ B ）11、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 。 A. 60 B. 66 C. 18000 D. 33 （ B ）12、有关二叉树下列说法正确的是 。 A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 （ C ）13、二叉树的第I层上最多含有结点数为（ ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 （ D ）14、n个结点的完全有向图含有边的数目 。 A．n*n B．n（n＋１） C．n／2 D．n*（n－l） （ B D ）15、一个有n个结点的图，最少有 个连通分量，最多有 个连通分量。 A．0 B．1 C．n-1 D．n （ B ）16、一个有向无环图的拓扑排序序列（ ）是唯一的。 A．一定 B．不一定 （ A ）17、关键路径是事件结点网络中（ ）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 （ D ）18、设一个栈的输入序列是A，B，C，D，则借助一个栈所得到的输出序列不可能是 。 A． A，B，C，D B． D，C，B，A C． A，C，D，B D． D，A，B，C （ C ）19、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为 。 A、48 B、49 C、50 D、51 二、填空题 已知L是带表头结点的非空单链表，且P结点既不是头结点