2习题(带答案).doc

1链表不具有的特点是 。 A可随机访问任一个元素 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比2在一个具有n个结点的单链表中查找值为x的某结点，若查找成功，则平均比较 个结点。 An B. n/2 C. (n-1)/2 D. (n+1)/23.在单链表中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.线性表采用链式存储结构时，其地址( )A) 必须是连续的 B）一定是连续的C)部分地址必须是连续的 D) 连续与否均可以17.带头结点的单链表head为空的判断条件是( )。A)head=NULL B)head-next=NULLC)head-next=head D)head!=NULL 18.线性表的长度是线性表所占用的存储空间的大小。()19.在一个长度为n的顺序表中删除一个数据元素，最少要移动 0 个数据元素，最多要移动 n-1 个数据元素，平均要移动 (n-1)/2 个数据元素。20. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为( )。(1in+1)An-i Bn-i+1 C. i Dn-i-121.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为( )。(1in)AO(0) BO(1) C.O(n) DO(n2)21.带头结点的单循环链表h为空表的条件是 h-next=h; 。22.线性表采用顺序存储结构时，要求内存中可用存储单元的地址 。 A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 连续不连续都可以23. 线性表是具有N个（ ）的有限序列。A、表元素 B、字符 C、数据元素 D、数据项 E、信息24循环链表主要优点是（ ）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表25. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表26.在带头结点的单循环链表中，任一结点的后继指针均不空。()27.在双循环链表中，任意一结点的后继指针均指向其逻辑后继。(错)28.在单链表中，已知r和s是指向链表中两个结点的指针，且满足r-next=s，则删除指针s所指结点的语句序列是 _r-next=s-next_、 free(s) 。29. 在线性表的下列存储结构中，读取元素花费时间最少的是（ ）A、单链表 B、双链表 C、循环链表 D、顺序表30.在单链表中指针p所指向结点的后面插入指针q所指结点的语句序列为 q-next=p-next 、 p-next=q 。31.假设双链表结点的类型如下：typedef struct linknodeint data;数据域struct linknode *prior;指向前趋结点的指针域struct linknode *next;指向后继结点的指针域bnode 现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（）。、q-next=p;q-prior=p-prior;p-prior=q;p-prior-next=q;、p-prior=q;q-next=p;p-prior-next=q;q-prior=p-prior、q-prior=p-next;q-next=p;p-prior-next=q;p-prior=q;、以上都不对32. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。A、O(1) B、O(n) C、O(n2) D、O(nlog2n)33.图2所示的双链表中, _组语句将s所指结点插入到p所指结点的后面。257p6s图2 双链表A)p-next-prior = s;B)s-next = p-next;s-prior = p; p-next = s;p-next = s; s-prior = p;s-next = p-next;p-next-prior = s;C)s-next = p-next;D)p-next = s;p-next = s; s-prior = p;s-next-prior = s;s-next = p-next;s-prior = p; p-next-prior = s;34. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表35.不带头结点的单链表head为空的判断条件是( )。A)head=NULL B)head-next=NULLC)head-next=head D)head!=NULL 36、在单链表中，指针p所指结点为最后一个结点的条件是_p-next=NULL