数据结构与课程设计练习

1、第2章 线性表一 选择题1下述哪一条是顺序存储结构的优点？（ ） A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ ） A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有n个（ ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 E信息项4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A顺序表

2、B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表8. 静态链表中指针表示的是（ ）. A 内

3、存地址 B数组下标 C下一元素地址 D左、右孩子地址9. 链表不具有的特点是（ ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比10. 下面的叙述不正确的是（ ） A线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最

4、大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ ） A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llin

5、k=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 25对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL 26. 在双向链表存储结构中，删除p所

6、指的结点时须修改指针（ ）。A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink;B p.llink:=(p.llink).llink (p.llink).rlink:=p;C (p.rlink).llink:=p p.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llink p.llink:=(p.rlink).rlink; 27. 双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）

7、Ap.llink.rlink:=p.llink; p.llink.rlink:=p.rlink; dispose(p);Bdispose(p); p.llink.rlink:=p.llink; p.llink,rlink:=p.rlink;Cp.llink.rlink:=p.llink; dispose(p); p.llink.rlink:=p.rlink;D以上A，B，C都不对。 二、判断1. 链表中的头结点仅起到标识的作用。( ) 2. 顺序存储结构的主要缺点是不利于插入或删除操作。( ) 3线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4顺序存储方式插入和删除时效

8、率太低，因此它不如链式存储方式好。( ) 5. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 6顺序存储方式只能用于存储线性结构。( ) 7集合与线性表的区别在于是否按关键字排序。( ) 8. 所谓静态链表就是一直不发生变化的链表。( ) 9. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 10. 取线性表的第i个元素的时间同i的大小有关. ( ) 11. 循环链表不是线性表. ( ) 12. 线性表只能用顺序存储结构实现。( ) 13. 线性表就是顺序存储的表。( ) 14为了很方便的插入和删除数据，可以使用双向链表存放数据。( ) 15. 顺序存储方式的优点是存储密度大，

9、且插入、删除运算效率高。( ) 16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 20. 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。void reverse（linklist &L）p=null；q=L；while（q！=null） (1) ; q-next=p；p=q；(2)_ ; (3)_; 四算法设计题1假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。（解答）2. 设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表