《《数据结构》习题集》由会员分享，可在线阅读，更多相关《《数据结构》习题集（31页珍藏版）》请在金锄头文库上搜索。
1、1 1 绪论绪论一、选择题： 1、下列算法的时间复杂度是（ ）for(i=0;inext=P-next;P-next=SBP-next=S-next;S-next=P；CP-next=P;P-next=S；DP-next=S;S-next=P； 3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ）A（1） B（log2n） CO（n） DO（n2）解析：解析：单就插入运算而言，算法时间复杂度为（1） ，但要将指针定位到链表末尾， 指针移动的时间复杂度为 O（n） ； 4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ）A顺序表 B用头指针表示的
2、单循环链表C用尾指针表示的单循环链表 D单链表解析：解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开 始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为 rear，则开始结点 和终端结点的位置分别是 rear-next-next 和 rear, 查找时间都是 O(1)。 若用头指针来表示该链表，则查找终端结点的时间为 O(n)。 5、线性表是（ ） A一个有限序列，可以为空 B一个有限序列，不能为空C一个无限序列，可以为空 D一个无限序列，不能为空 6、在 n 个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ）AO（n） BO（1） CO（log2
3、n） DO（n2） 7、线性表采用链式存储时，结点的地址（ ）A必须是连续的 B必须是不连续的 C连续与否均可 D必须有相等的间隔 8、在单链表中，增加头结点的目的是（ ）A使单链表至少有一结点 B标志表中首结点位置C方便运算的实现 D说明单链表是线性表的链式存储实现 9、带头结点的单链表 head 为空的判定条件是（ ）Ahead = NULL； Bhead - next = NULL； Chead - next = head； Dhead ! = NULL； 10、在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ）A（1） B（n） C（n2） D（log2n
4、） 11、下列有关线性表的叙述中，正确的是（ ）4A线性表中的元素之间是线性关系B线性表中至少有一个元素C线性表中任何一个元素有且仅有一个直接前趋D线性表中任何一个元素有且仅有一个直接后继 12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向 该结点的（ ）A直接前趋 B直接后继 C开始结点 D终端结点 13、将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ） 。 An B.2n-1 C.2n D.n-1 14、链表不具有的特点是（ ） 。 A随机访问 B不必事先估计存储空间 C插入删除时不需移动元素 D所需的空间与线性表成正比 15、在一个单链
5、表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行的操作是（ ） 。As-next=p-next;p-next=s; Bq-next=s;s-next=p; Cp-next=s-next;s-next=p; Dp-next=s;s-next=q; 16、链表具有的特点是（ ） 。 A可随机访问任一元素B插入、删除需要移动元素 C不必事先估计存储空间D存储空间是静态分配的 17、一个顺序表一旦说明，其中可用空间大小（ ） A已固定B可以改变C不能固定D动态变化 18、若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ）存储
6、方式最节省时间。 A 顺序表B单链表C双向链表D单循环链表 19、两个指针 P 和 Q，分别指向单链表的两个元素，P 所指元素是 Q 所指元素的前驱的 条件是（ ） 。 AP-next=QBQ-next=P CP=QDP-next=Q-next 20、链表不具有的特点是（ ） 。 A可随机访问任一元素 B插入、删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比 21、下面关于线性表的叙述中，错误的是（ ） 。 A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性表采用链接存
7、储，便于进行插入和删除操作 22、在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（ ） 。 A访问第 i 个结点（1in）和求第 i 个结点的直接前趋（2in） B在第 i 个结点后插入一个新结点（1in）5C删除第 i 个结点（1in） D将 n 个结点从小到大排序 23、在一个单链表中，若删除 p 指向结点的后继结点，则执行的操作为（ ） 。 Aq=p-next;p-next=p-next-next;free(q); Bp=p-next;q=p-next;p=q-next;free(q); Cq=p-next-next;p=p-next;free(q); Dp=p-next
8、-next;q=p-next;free(q); 二、二、 填空题：填空题： 1、在双链表中要删除已知结点*p，其时间复杂度为（ ） 。 2、在仅有尾指针 R 指示的单循环链表 R 中，在表尾插入一个结点 S 的语句序列是（ ） 。 3、在带头结点的双链表中，指针所指结点是开始结点的条件是（ ） 。 4、在具有 n 个结点的双链表中做插入、删除运算，平均时间复杂度为（ ） 。 5、在一个长度为 n 的顺序表中第 i 个元素（1 i n）之前插入一个元素时，需向后 移动（ ）个元素。 6、在双循环链表中，若要在指针 p 所指结点之前插入指针 s 所指的结点，则需执行下列 语句：s-prior=p-
9、prior;p-prior-next=s;( )和 p-prior=s;。 7、已知指针 p 指向双向链表中的一个结点（非首结点、非尾结点） ，则将结点 s 插入在 p 结点的直接后继位置的语句是（ ）s-prior=p；s-next-prior=s；p-next=s; 8、已知带表头结点的单链表 L，指针 p 指向 L 链表中的一个结点（非首结点、非尾结点） ，则删除结点 p 的直接后继结点的语句是（ ） ；删除首结点的语句是（ ） 。三、三、 判断题判断题 1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。 （ ） 2、顺序存储的线性表可以随机存取。 （ ） 3、线性表
10、采用顺序存储，必须占用一片连续的存储单元。 （ ）四、四、 程序设计题程序设计题 数据结构的数据类型定义如下：顺序存储：typedef struct int *base; int length; int listsize; sqlist;链式存储：6typedef struct LinkListint data; struct LinkList *next; Node,*LinkList;1、已知带头结点的单链表 head 中的结点是按整数值递增排序的，写一算法将值为 x 的 结点插入到表 head 中，使 head 仍然有序。2、用尾插法建立带头结点的单链表。3、用头插法建立带头结点的单链表
11、。4、对给定的单链表 L，编写一个删除 L 中值为 x 的结点的直接前趋结点算法。5、用顺序存储结顺序存储结构实现线性表的就地逆置算法，即将（a1,a2, ai,an）逆置为 （an,ai,a2,a1）;6、用链式存储结构链式存储结构实现线性表的就地逆置算法，即将（a1,a2, ai,an）逆置为 （an,ai,a2,a1）;7、使用顺序存储结构分别实现 A=AB 和 A=AB 运算；参考答案（线性表）参考答案（线性表）一、选择题一、选择题1 12 23 34 45 56 67 78 89 9101011111212131314141515161617171818191920202121222
12、22323B BA AB BC CA AB BC CC CB BB BA AB BB BA AB BC CB BA AA AA AB BA AA A二、填空题二、填空题 1、在双链表中要删除已知结点*p，其时间复杂度为（O(1)） 。 2、在仅有尾指针 R 指示的单循环链表 R 中，在表尾插入一个结点 S 的语句序列是（P=R; while(P-next!=NULL) P=P-next; P-next=S; S-next=NULL;） 。 3、在带头结点的双链表中，指针所指结点是开始结点的条件是（P= =L） 。 4、在具有 n 个结点的双链表中做插入、删除运算，平均时间复杂度为（O(1)）
13、。 5、在一个长度为 n 的顺序表中第 i 个元素（1 i n）之前插入一个元素时，需向后 移动（n-i+1）个元素。 6、在双循环链表中，若要在指针 p 所指结点之前插入指针 s 所指的结点，则需执行下列 语句：s-prior=p-prior;p-prior-next=s;( s-next=p;s-next=p; )和 p-prior=s;。 7、已知指针 p 指向双向链表中的一个结点（非首结点、非尾结点） ，则将结点 s 插入在 p 结点的直接后继位置的语句是（p-next=s;p-next=s;）s-prior=p；s-next-prior=s；p-next=s;78、已知带表头结点的单链表 L，指针 p 指向 L 链表中的一个结点（非首结点、非尾结点） ，则删除结点 p 的直接后继结点的语句是（q=p-next; p-next=q-next; free(q);） ；删除 首结点的语句是（q=L-next; L=L-next; free(q);） 。三、判断题三、判断题 1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。 （） 2、顺序存储的线性表可以随机存取。 （） 3、线性表采用顺序存储，必须占用一片连续的存储单元。 （） 四、程序设计题四、程序设计题 1、已知带头结点的单链表 head
