数据结构课后习题[第二章].docVIP

网络工程2011级1班、计算机科学与技术2011级2班《算法与数据结构》课后习题（第2章） 第  PAGE 6 页 共 5 页 【课后习题】第2章 线性表 ?2011级 计科 (网工) 班 学号： 姓名： 题 号一二三四总分得 分一、判断题（如果正确，在题号前打“?”，否则打“?”。每题2分，共10分) 线性表若采用顺序存储表示时所有结点之间的存储单元地址必须连续。 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 如果某个数据结构的每一个元素都是最多只有一个直接前驱，则必为线性结构。 线性表的逻辑顺序与物理顺序总是一致的。 线性表的长度是指它所占存储空间的大小。 二、填空题（每空1.5分，共21分) 从逻辑结构看，线性表是典型的 。 在一个长度为n的向量中在第i（1≤i≤n+1）个元素之前插入一个元素时，需向后移动 个元素，算法的时间复杂度为 。 在一个长度为n的向量中删除第i（1≤i≤n）个元素时，需向前移动 个元素，算法的时间复杂度为 。 若长度为n的线性表采用链式存储结构，在其第i个结点前插入一个新的元素的算法的时间复杂度为 。删除其第i个元素的算法的时间复杂度为 。 线性表顺序存储结构的优点是可以实现 ，主要缺点是: 。 不带头结点的单链表L为空的条件是 ，带头结点的单链表L为空的条件是 ，带头结点的单循环链表L为空的条件是 。 两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前导的条件是 。 设双向循环链表中结点的结构为（data, prior, next），若指针p指向该链表的某个结点，则有下面的关系：p-next-prior= = 。 三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题2分，共40分) 题号12345678910答案　　　　　　　　题号11　12　　13　1415　16　17181920答案　　　　　　　　P和Q两个指针分别指向双向循环表L的两个元素，P所指元素是Q所指元素的后继的条件是（??? ）。A.P= =Q?????????????? B.Q-﹥Next==P C.P-﹥Next==Q??????? D.Q-﹥PRIOR==P 指针P指向不带头结点的线性链表L的首元素的条件是（??? ）。A.P= =L?????????? B.L-﹥Next==PC.P-﹥next==L???? D.P-﹥next==NULL 指针p指向带头结点的单循环链表L 的首元素的条件是（??? ）。A.P= =L?????????? B.L-﹥Next==PC.P-﹥next==L???? D.P-﹥next==NULL 指针P指向单链表L的尾元素的条件是（??? ）。A.P= =L?????????? B.L-﹥Next==PC.P-﹥next==L???? D.P-﹥next==NULL 指针P 所指的元素是双向循环链表L的尾元素的条件是（??? ）。A.P= =L??????????? B.P= =NULL ??? C. P-﹥next==L D. P-﹥prior==L? 在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（??? ）。A.0(1)??? B.0(n)???? C.0(nlog2n)???? D.0(n2) 顺序存储的线性表(a1,a2,…an)，在任一结点前插入一个新结点时所需移动结点的平均次数为（??? ）。A.n?????? B.n/2 ?????????? ?C.n+1?????? D.(n+1)/2 删除长度为n的顺序表的第i(1≤i≤n)个位置上的元素，元素的移动次数为( )A) i-1 B) i C) n-i D) n-i+1 在C语言中可用（ ）描述线性表。A、数组； B、指针； C、数组或指针； D、结构 链表不具有的特点是（ ）A) 插入、删除不需要移动元素 B) 可随机