2011年山东省数据结构试题大全考试答题技巧(精)

1、1、有向图采用邻接矩阵存储，某一行中非零元素的个数等于 A 对应顶点 v 的度 B.对应顶点 v 的出度 C.对应顶点 v 的入度 D.依附于对应顶点 v 的边数 2、在一个长度为 n (n1)的单链表上，设有头和尾两个指针，执行 B 操作与链表 的长度有关。A 删除单链表中的第一个元素 B 删除单链表中的最后一个元素 C.在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个 新元素 3、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构 是 B。A .单链表 B.静态链表 C.线性链表 D .顺序存储结构 4、在二维数组 a910中：每个数组元素占用 3 个存储

2、空间，从首地址 SA 开始按行优先 连续存 放，则元素 a85的起始地址是 A. SA+141 B. SA+144 C. SA+222 D. SA+255 5、链表不具备的特点是 A o A .可随机访问任一结点 B .插入删除不需要移动元 素 C.不必事先估计存储空间 D .所需空间与其长度成正比 6、栈采用不同的存储 方式时，下列关于出栈过程的叙述中，正确的是 A .顺序栈需要判定栈空，链栈也 需要判定 B.顺序栈需要判定栈空，而链栈不需要判定 C.顺序栈不需要判定栈 空，而链栈需要判定 D.顺序栈不需要判定栈空，链栈也不需要判定 7、向一个长 度为 n 的顺序表中插人一个新元素的平均时间

3、复杂度为 (。A . O(n B. 0(1 C. 0(n2 D. O(10g2n 8、深度为 k 的完全二叉树所含叶结点的个数最多为(B)。 A) 2k B) 2k-1 C) k D) 2k 9、若进栈序列为 1, 2, 3, 4,则不可能得到的出栈 序列是(C )o A) 3, 2，1, 4 B) 3，2, 4，1 C) 4, 2, 3，1 D) 2，3, 4，1 10、已知关键字序列为66 , 82, 25, 51, 98, 108，利用快速排序方法，以第一 个元素为基准得到的一趟排序结果为 A . 25 , 51, 66, 82, 98, 108 B . 25 , 51, 66, 98,

4、 82, 108 C. 51 , 25, 66, 108, 98, 82 D . 51 , 25, 66, 82, 98, 108 11、已知关键字序列为66, 82, 25, 51, 98, 108，利用快速排序方 法，以第一个元素为基准得到的一趟排序结果为 A. 25 , 51, 66, 82, 98, 108 B. 25 , 51, 66, 98, 82, 108 C. 51 , 25, 66, 108, 98, 82 D . 51 , 25, 66, 82, 98, 108 12、栈采用不同的存储方式时，下列关于出栈过程的叙述中， 正确的是 A .顺序栈需要判定栈空，链栈也需要判定 B

5、 .顺序栈需要判定栈空，而 链栈不需要判定 C.顺序栈不需要判定栈空，而链栈需要判定 D .顺序栈不需要判定栈空，链栈也不需要判定 13、如果最常用的操作是取第 i 个结点及其前驱，则采 用 D存储方式 最节省时间。 A 单链表B.双链表C.单循环链表D.顺序表14、 在一个 长度为n (n1)的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有 关。A .删除单链表中的第一个元素 B.删除单链表中的最后一个元素 C.在单链 表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 15、下述排序方法中，时间性能和待排序记录的初始状态无关的是( )A 插入排 序和快速排序

6、 B 归并排序和快速排序 C 选择排序和归并排序 D 插入排序和归并排 序 16、对于图 1 所示的二叉树， 其后序序列为(C )。 A) ABDECFG B ) DBEAFCG C ) DEBFGCA D ) GFCEBDA 17、在存储数据时，通常不仅要存储各 数据元素的值，而且还要存储 C。A .数据的处理方法 B .数据元素的类型 C.数 据元素之间的关系 D.数据的存储方法 18、长度为 n 的顺序表，删除位置 i 上的元 素(0 i 一 1,需要移动的元素个数为 A . n i B. ni I C . i D . i+1 19、在数 据结构中，与所使用的计算机无关的是数据的 A 结

7、构。A .逻辑 B.存储 C.逻 辑和存储 D.物理 20、长度为 n 的顺序表，删除位置 i 上的元素(0 1)的 单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。 A .删除单链 表中的第一个元素 B.删除单链表中的最后一个元素 C .在单链表第一个元素前插 入一个新元素 D.在单链表最后一个元素后插入一个新元素 22、在一个具有 n 个 结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B。A . O (1) B . O (n) C . O (n2) D . O ( nlog2n) 23、深度为 k 的完全二叉树所含叶 结点的个数最多为(B)o A) 2k B)

8、 2k-1 C) k D) 2k 24、栈采用不同的存储方 式时，下列关于出栈过程的叙述中，正确的是 A .顺序栈需要判定栈空，链栈也需 要判定 B .顺序栈需要判定栈空，而链栈不需要判定 C .顺序栈不需要判定栈空， 而链栈需要判定 D.顺序栈不需要判定栈空，链栈也不需要判定 25、由权值分别 为 3, 8, 6, 2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 (。A . 24 B . 48 C . 72 D . 53 26、下列选项中，符合堆定义的是 A . 102, 24, 55, 60, 89, 93 B . 24, 89, 55, 60, 93, 102 C . 102,

9、93, 55, 60, 89, 24 D. 102 , 60。89, 93, 55, 24 27、需要分配较大空间，插入和删除不需要移动 元素的线性表，其存储结构是 B。 A 单链表 B 静态链表 C.线性链表 D.顺序存储结构 28、下列选项中，符 合堆定义的是 A. 102，24，55，60，89，93 B . 24，89，55，60，93，102 C. 102，93，55，60，89，24 D . 102，60。89，93，55，24 29、当一个作为 实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为 （参 数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引

10、用型 C.指针型 D.常 值引用型？ 30、下述排序方法中，时间性能和待排序记录的初始状态无关的是（ ） A 插入排序和快速排序 B 归并排序和快速排序 C 选择排序和归并排序 D 插入排序 和归并排序 31、从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 （。 A. O（1 B.O（n C.O（1Ogz n D.O（ n2 32、不带头结点的单链表 head 为空的判定条件是 A。 A. head = NULL B head-next =NULL C . head-next =head D head!=NULL 33、非空的循环单链表 head 的尾结点（由 p 所指向）满足 C。A.

11、 p- next = NULL B . p = NULL C . p-next =head D. p = head 34 由权值分别为 3, 8, 6, 2, 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 （。A . 24 B. 48 C. 72 D. 53 35、当一个作为实际传递的对象占用的存储空间较大并可能 需要修改时，应最好把它说明为（参数，以节省参数值的传输时间和存储参数的空 间。A.整形 B.引用型 C.指针型 D.常值引用型？ 36 由权值分别为 3, 8, 6, 2, 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 （。A . 24 B. 48 C. 72 D. 53

12、 37、一棵左子树为空的二叉树在前序线索化后，其空指针域个数为 A. 0 B . 1 C . 2 D .不确定 38、一个栈的入栈序列是 1,2,3,4,5,则不可能的出栈序列是 （A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5 39 在平衡二叉树中插入一个结点后 造成不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子平衡因子为 0,右孩子 平衡因子为 1,则应该做（）型调整以使其平衡 A LL B LR C RL D RR 40、若某 表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A

13、 .单链表 B.给出表头指针的单循环链表 C.双链 表 D.带头结点的双循环链表 41、若进栈序列为 1, 2, 3, 4,则不可能得到的出栈序列是（C ）。A） 3, 2, 1, 4 B） 3, 2, 4, 1 C） 4, 2, 3, 1 D） 2, 3, 4, 1 42、与单链表相比，双链表的优点之一是 D o A 插入、删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结 点更灵活 43、在二维数组 a910中：每个数组元素占用 3 个存储空间，从首地址 SA 开始按行优先 连续存放，则元素 a85的起始地址是 A. SA+141 B. SA+144

14、C. SA+222 D. SA+255 44、衡量查找算法效率的主要标准是（ C ）。A）元素个 数 B）所需的存储量 C）平均查找长度 D）算法难易程度 45、下列选项中，符合 堆定义的是 A. 102 , 24, 55, 60, 89, 93 B . 24, 89, 55, 60, 93, 102 C. 102, 93, 55, 60, 89, 24 D . 102 , 60。89, 93, 55, 24 46、在数据结构 中，从逻辑上可以把数据结构分为 C o A 动态结构和静态结构 B 紧凑结构和 非紧凑结构 C线性结构和非线性结构D 内部结构和外部结构 47、 若进栈序列 为 1,

15、2, 3, 4,则不可能得到的出栈序列是 （C ）o A） 3, 2, 1, 4 B） 3, 2, 4, 1 C） 4, 2, 3, 1 D） 2, 3, 4, 1 48、下列选项中，符合堆定义的是 A. 102, 24, 55, 60, 89, 93 B . 24 , 89, 55, 60, 93, 102 C . 102 , 93, 55, 60, 89, 24 D . 102, 60。89, 93, 55, 24 49、在存储数据时，通常不仅 要存储各数据元素的值，而且还要存储 C o A .数据的处理方法 B .数据元素的 类型 C.数据元素之间的关系 D 数据的存储方法 50、如果最

16、常用的操作是取第 i 个结点及其前驱，则采用 D 存储方式最节省时间。A .单链表 B.双链表 C.单 循环链表 D.顺序表 51、需要分配较大空间，插入和删除不需要移动元素的线性 表，其存储结构是 B o A 单链表 B静态链表 C线性链表 D 顺序存储结构 52、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把 它说明为（参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C. 指针型 D.常值引用型？ 53、不带头结点的单链表 head 为空的判定条件是 A o A. head = NULL B head-next =NULL C . head-ne

17、xt =head D head!=NULL 54、对于图 1 所示的二叉树，其后序序列为（C ）o A） ABDECFG B ） DBEAFCG C ） DEBFGCA D ） GFCEBDA 55、在数据结构中，从逻辑上可以把数 据结构分为 C o A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C.线性结构 和非线性结构 D.内部结构和外部结构 56、如果最常用的操作是取第 i 个结点及其 前驱，则采用 D 存储方式最节省时间。A 单链表 B 双链表 C单循环链表 D. 顺序表 57、深度为 k 的完全二叉树至多有()个结点 A B C D 58、在一个具有 n 个结点的有序单链表中插入

18、一个新结点并仍然保持有序的 时间复杂度是 B o A. O (1) B. O (n) C. O (n 2) D. O (n Iog2 n) 59、若某 表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A .单链表 B.给出表头指针的单循环链表 C.双链 表 D.带头结点的双循环链表 60、在二维数组 a910中：每个数组元素占用 3 个 存储空间，从首地址 SA 开始按行优先连续存放，则元素 a85的起始地址是 A. SA+141 B. SA+144 C. SA+222 D. SA+255 61、一个栈的入栈序列是 1,2,3,4,5,贝

19、U 不可能的出栈序列是(A 5,4,3,2,1 B 4,5,3,2,1 C 4,3,5,1,2 D 1,2,3,4,5 62 在一个单链表HL 中，若要向表头插入一个由指针 p 指向的结点，则执行(。 A. HL = ps pnext= HL B . p 一next= HL ; HL = p3 C. p 一next= Hl; p= HL; D . p 一next= HL 一next;HL 一next= p 63、如果对线性表的操作只有两 种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 B。 A .只有表头指针没有表尾指针的循环单链表 B.只有表尾指针没有表头指针的循 环单链表

20、 C.非循环双链表 D .循环双链表 64、以下说法正确的是 D。A .数据 项是数据的基本单位 B.数据元素是数据的最小单位 C .数据结构是带结构的数据 项的集合 D. 些表面上很不相同的数据可以有相同的逻辑结构 65、在以下的叙 述中，正确的是 Bo A .线性表的顺序存储结构优于链表存储结构 B .二维数组 是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D .队列的操作方式 是先进后出 66、对于图 1 所示的二叉树，其后序序列为(C )o A) ABDECFG B) DBEAFCG C ) DEBFGCA D ) GFCEBDA 67、已知关键字序列为66，82， 25,

21、 51，98，108，利用快速排序方法，以第一个元素为基准得到的一趟排序结果 为 A. 25，51，66，82，98，108 B . 25，51，66，98，82，108 C. 51， 25，66，108，98，82 D . 51，25，66，82，98，108 68、如果对线性表的操作 只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用 B。 A .只有表头指针没有表尾指针的循环单链表 B.只有表尾指针没有表头指针 的循环单链表 C.非循环双链表 D .循环双链表 69、算法分析的目的是 C ,算法 分析的两个主要方面是 A。 （1） A 找出数据结构的合理性 B 研究算

22、法中的输 入和输出的关系 C分析算法的效率以求改进 C 分析算法的易读性和文档性 （2） A.空间复杂度和时间复 杂度 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性 70、由权值分别为 3, 8, 6, 2, 5 的叶子结点生成一棵哈夫曼树，它的带权路径长 度为（。A. 24 B. 48 C. 72 D. 53 71、在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是 D。A. p-prior = s; s-next = p； p-prior-next = s； s-prior =p-prior B . p-prior = s; p-prior-next = s; s

23、-next = p； s-prior = p-prior C. s-next = p； s-prior = p-prior ； p-prior = s; p-prior-next = s D . s-next = p； s-prior = p-prior； p-prior-next = s； p-prior = s 72、在数据结构中，从逻辑 上可以把数据结构分为 C o A .动态结构和静态结构 B .紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D.内部结构和外部结构 73、由权值分别为 3, 8, 6, 2, 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 （。A . 24 B

24、. 48 C. 72 D. 53 74、在数据结构中，与所使用的计算机无关的是数据的 A 结构。A .逻辑 B. 存储 C.逻辑和存储 D.物理 75、衡量查找算法效率的主要标准是（C ）o A）元素个数 B）所需的存储量 C）平均查找长度 D）算法难易程度 76、数据结构 在计算机内存中的表示是指 A。A.数据的存储结构 B .数据结构 C.数据的逻 辑结构 D.数据元素之间的关系 77、下述排序方法中，时间性能和待排序记录的 初始状态无关的是（）A 插入排序和快速排序 B 归并排序和快速排序 C 选择排序 和归并排序 D 插入排序和归并排序78、非空的循环单链表 head 的尾结点（由 p

25、 所 指向）满足 C。A. p-next = NULL B . p = NULL C . p-next =head D. p = head 79 不带头结点的单链表 head 为空的判定条件是 A。A. head = NULL B head-next =NULL C . head-next =head D head!=NULL 80 若某线性表中最常 用的操作是取第 i 个元素和找第 i 个元素的前驱，则采用（存储方法最节省时间 A 顺序表 B 单链表 C 双链表 D 单循环链表 81、通常要求同一逻辑结构中的所有数据 元素具有相同的特性，这意味着 Bo A .数据元素具有同一特点 B .不仅数据元 素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C.每个数据元 素都一样 D.数据元素所包含的数据项的个数要相等 82、在数据结构中，从逻辑 上可以把数据结构分为 C。A .动态结构和静态结构 B .紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D.内部结构和外部结构 83、