第2章习题(带答案).doc

1．链表不具有的特点是 。 A．可随机访问任一个元素 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比 2．在一个具有n个结点的单链表中查找值为x的某结点，若查找成功，则平均比较 个结点。 A．n B. n/2 C. (n-1)/2 D. (n+1)/2 3.在单链表中P所指结点之后插入一个元素x的主要操作语句序列是 s=(node *)malloc(sizeof(node));、 s-data=x;、 s-next=p-next、 p-next=s。 4.在单链表中查找第i个元素所花的时间与i成正比。（√ ） 5．在带头结点的双循环链表中，任一结点的前驱指针均不为空。（ √ ） 6.用链表表示线性表的优点是 ( )。 A. 便于随机存取 B. 花费的存储空间比顺序表少 C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同 7.在双向链表中删除P所指结点的主要操作语句序列是 p-prior-next=p-next; 、 p-next-prior=p-prior; 、 free(p); 。 8.下述哪一条是顺序存储结构的优点？（ ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 9．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 10. 对任何数据结构链式存储结构一定优于顺序存储结构。（×） 11.对于双向链表,在两个结点之间插入一个新结点需修改的指针共 4 个，单链表为____2___个。 12.以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队列 D．栈 13.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 14. “线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。 A、正确的 B、错误的 C、不一定，与具体结构有关。 15.在一个长度为n的顺序表中插入一个数据元素，最少要移动 0 个数据元素，最多要移动 n 个数据元素，平均要移动 n/2 个数据元素。 16.线性表采用链式存储结构时，其地址( ) 必须是连续的 B）一定是连续的 C)部分地址必须是连续的 D) 连续与否均可以 17.带头结点的单链表head为空的判断条件是( )。 A)head==NULL B)head-next==NULL C)head-next==head D)head!=NULL 18.线性表的长度是线性表所占用的存储空间的大小。(×) 19.在一个长度为n的顺序表中删除一个数据元素，最少要移动 0 个数据元素，最多要移动 n-1 个数据元素，平均要移动 (n-1)/2 个数据元素。 20. 若长度为n的线性表采用顺序存储结构，在其第i个位置一个新元素(?? )。(1≤i≤n+1)A．?? B．??? C. i??? D．若长度为n的线性表采用顺序存储结构，在其第i个位置一个元素的算法的时间复杂度为(?? )。(1≤i≤n) A．O(0)??? B．O(1)??? C.O(n)??? D．O(n2)h为空表的条件是 h-next=h; 。 22.线性表采用顺序存储结构时，要求内存中可用存储单元的地址 。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以 23. 线性表是具有N个（ ）的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息 24．循环链表主要优点是（ ） A、不再需要头指针了 B、已知某个结点的位置后，能够容易找到它的直接前趋 C、在进行插入、删除运算时，能更好地保证链表不断开 D、从表中任一结点出发都能扫描到整个链表 25. 若某线性表中最常用的操作是取第个元素和找第个元素的前趋元素，则采用（ ）存储方式最节省时间。 顺序表