whut数据结构复习题.doc

复****题集
一判断题
(×)1. 线性表在物理存储空间中也一定是连续的。
(×)2. 顺序存储方式只能用于存储线性结构。
(√)3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。
(√)4. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。
(×)5. 二叉树的度为2。
(√)6. 若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。
(×)7. 二叉树中每个结点的两棵子树的高度差等于1。
(√)8. 用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。
( )9. 在冒泡法排序中,关键值较小的元素总是向前移动,关键值较大的元素总是向后移动。
( )。
( )。
(×)。
(×)。
( )。
( )。
(×)。
( )。
( ),处于同一层上的各结点之间都存在兄弟关系。
( ),则该图一定是无向图。
( ),则该图一定是有向图。
( )。
( )。
( )。
( )。
( ),在进行第一次分组时,排序码的比较次数总是n-1次。
( ),各顶点的入度之和等于各顶点的出度之和。
一、选择题
( )1. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:
A) 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) C) 删除第i个结点(1≤i≤n)
B) 在第i个结点后插入一个新结点(1≤i≤n) D) 将n个结点从小到大排序
(C)2. 算法分析的目的是:
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
(A)3. 算法分析的两个主要方面是:
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
(B)4. 计算机算法必须具备输入、输出和等5个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性
(B),每个元素的长度为2,则第5个元素的地址是
(A)110 (B)108 (C)100 (D)120
(A)5. 链接存储的存储结构所占存储空间:
(A)分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
(B)只有一部分,存放结点值