数据结构第2章-答案(共7页).doc

《数据结构第2章-答案(共7页).doc》由会员分享，可在线阅读，更多相关《数据结构第2章-答案(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上一、填空题01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。02、线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。03、在有n个元素的顺序表中插入一个新元素，需要平均移动n/2元素，具体移动的元素个数与表长和该元素在表中的位置有关。04、线性表中结点的集合是有限的，结点间的关系是一对一的。05、向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后移动n-i+1个元素。06、向一个长度为n的顺序表中删

2、除第i个元素(1in)时，需向前移动n-i个元素。07、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。08、顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置未必相邻。09、在单链表中，除了首结点外，任一结点的存储位置由其直接前驱结点的链域值指示。10、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O(n)。11、设单链表的结点结构为(data,next)，next 为指针域，已知指针px指向单链表中data域为x的结点，指针py 指向data域为y的新结点，若将结点y插入结点x之后，则需要

3、执行以下语句：py-next=px-next; px-next=py;12、在单链表中设置头结点的作用是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。13、对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x 的结点后插入一个新结点的时间复杂度为O(n)。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是：f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;15、在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列

4、语句：s-next=p; s-prior= p-prior; p-prior=s; s-prior-next =s;16、链接存储的特点是利用指针来表示数据元素之间的逻辑关系。17、对于双向链表，在两个结点之间插入一个新结点需修改的指针共4个，单链表为2个。18、循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素。19、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是 u=p-next; p-next=u-next; free(u);20、带头结点的双循环链表L中只有一个元素结点的条件是 L-next-next=L21、在单链表L 中，指针p 所指结点有后继结点的条件是

5、p-next!=null22、带头结点的双循环链表L为空表的条件是 L-next=L & L-prior=L23、在单链表p结点之后插入s结点的操作是 s-next=p-next; p-next=s;二、判断题01、链表的每个结点中都恰好包含一个指针。02、链表的物理存储结构具有同链表一样的顺序。03、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。04、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。05、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 06、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。07

6、、线性表在物理存储空间中也一定是连续的。08、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。09、顺序存储方式只能用于存储线性结构。10、线性表的逻辑顺序与存储顺序总是一致的。11、链表中的头结点仅起到标识的作用。12、顺序存储结构的主要缺点是不利于插入或删除操作。13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。14、对任何数据结构链式存储结构一定优于顺序存储结构。15、集合与线性表的区别在于是否按关键字排序。16、所谓静态链表就是一直不发生变化的链表。17、线性表的特点是每个元素都有一个前驱和一个后继。18、取线性表的第i个元素的时间同i的大小有关。

7、19、循环链表不是线性表。20、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。三、单项选择题C01、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_。 A) 存储结构 B) 逻辑结构 C) 顺序存储结构 D) 链式存储结构B02、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 A) 110 B) 108 C) 100 D) 120A03、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是_。 A) 访问第i个结点(1in)和求第i个结点的直接前驱(2in) B) 在第i个结点后插入一个新

8、结点(1in) C) 删除第i个结点(1in) D) 将n个结点从小到大排序B04、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 _ 个元素。 A) 8 B) 63.5 C) 63 D) 7A05、链式存储的存储结构所占存储空间_。 A) 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B) 只有一部分，存放结点值 C) 只有一部分，存储表示结点间关系的指针 D) 分两部分，一部分存放结点值，另一部分存放结点所占单元数A06、下述_是顺序存储结构的优点。 A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D)可方便地用于各种逻辑结构的存储表示

9、D07、线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。 A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续或不连续都可以B08、线性表L在 情况下适用于使用链式结构实现。 A) 需经常修改L中的结点值 B) 需不断对L进行删除插入 C) L中含有大量的结点 D) L中结点结构复杂C09、单链表的存储密度_。 A) 大于1 B) 等于1 C) 小于1 D) 不能确定D10、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用_存储方式最节省运算时间。 A) 单向链表 B) 双向链表 C) 单向循环链表 D) 带头结点的双向循

10、环链表D11、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_存储方式最节省时间。 A) 单向链表 B) 双向链表 C) 单向循环链表 D) 顺序表A12、链表不具有的特点是_。 A) 可随机访问任一元素 B) 插入删除操作不需要移动元素 C) 不必事先估算存储空间 D) 所需空间与线性表长度成正比B13、在单向链表的指针p所指结点后插入结点*s(*p不是尾结点)，则应执行_操作。 A) s-next=p; p-next=s; B) s-next=p-next; p-next=s; C) s-next=p-next; p=s; D) p-next=s; s-next=p;C14、非空

11、的循环单向链表first的尾结点(由p指向)满足_。 A) p-next=NULL B) p=NULL C) p-next=first D) p=firstC15、下列关于线性表的叙述中，不正确的是_。 A) 线性表是n个结点的有穷序列 B) 线性表可以为空表 C) 线性表的每一个结点有且仅有一个前趋和一个后继 D) 线性表结点间的逻辑关系是1:1的联系 A16、在双向链表存储结构中删除p所指的结点时，需要按_修改指针的链接。 A) p-prior-next=p-next; p-next-prior=p-prior; B) p-prior=p-prior-next; p-prior-prior

12、-next=p; C) p-prior-prior-next=p; p-prior=p-prior-prior; D) p-next-next-prior=p; p-next=p-next-next;A17、在单循环链表中指针p指向结点A，若要删除A之后的结点(存在)，则其中指针的链接操作为_。 A) p-next=p-next-next B) p=p-next C) p=p-next-next D) next=pB18、带头结点的单链表head为空的判定条件是_。 A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULLD1

13、9、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_个结点。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2B20、在一个具有n个结点的有序单链表中插入一个新结点，并仍然有序的时间复杂度为_。 A) O(1) B) O(n) C) O() D) O()C21、给定有n个元素的向量，建立一个有序的单链表的时间复杂度为_。 A) O(1) B) O(n) C) O() D) O()A22、下面程序的功能是_。void delete(Linklist *L) p=L; while (p-next!=NULL) m=p-next-data; q=

14、p; while (q-next!=NULL) if (q-next-data=m) r=q-next; q-next=r-next; free(r); q=q-next; p=p-next; A) 在单链表中删除重复结点 B) 在单链表中删除第m个结点 C) 在单链表中的第m个位置插入结点 D) 在单链表中统计结点的数目并保存到m中C23、线性表是具有n 个_的有限序列(n0)。 A) 表元素 B) 字符 C) 数据元素 D) 数据项A24、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用_存储方式最节省时间。 A) 顺序表 B) 双链表 C) 带头结点的双循

15、环链表 D) 单循环链表B25、静态链表中指针表示的是_。 A) 内存地址 B) 下一元素数组下标 C) 下一元素地址 D) 下一元素的偏移地址C26、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。 A) O(n) O(n) B) O(n) O(1) C) O(1) O(n) D) O(1) O(1)C27、线性表(a1,a2,an)以链接方式存储时，访问第i位置元素的时间复杂性为_。 A) O(i) B) O(1) C) O(n) D) O(i-1)C28、在双向链表指针p的结点前插入一个指针q的结点操作是_。 A) p-piror=q;q-next=p;p-prior-n

16、ext=q;q-piror=q; B) p-piror=q;p-piror-next=q;q-next=p;q-piror=p-piror; C) q-next=p;q-piror=p-piror;p-piror-next=q;p-piror=q; D) q-piror=p-piror;q-next=q;p-piror=q;p-piror=q;B29、占用连续的存储空间，但插入和删除不需要移动元素，这种线性表的存储结构是_。 A) 单向链表 B) 静态链表 C) 双向链表 D) 顺序表B30、在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行_操作与链表的长度有关。 A) 删除单链表中

17、的第1个元素 B) 删除单链表中的最后1个元素 C) 在单链表第1个元素之前插入1个新元素 D) 在单链表最后1个元素之后插入1个新元素A31、对于具有n个元素的线性表，算法_在单链表上实现要比在顺序表上实现效率更高。 A) 删除所有值为x的元素 B) 在最后一个元素的后面插入一个新元素 C) 顺序输出前k个元素 D) 第i个元素与第n-i-1个元素交换D32、与单向链表相比，双向链表的优点之一是_。 A) 插入、删除操作更简单 B) 可以进行随机访问 C) 可以省略表头指针或表尾指针 D) 顺序访问相邻结点更灵活A33、在长度为n的_上，删除第1个结点，其算法的时间复杂度为O(n)。 A)

18、只有表头指针的不带头结点的循环单链表 B) 只有表尾指针的不带头结点的循环单链表 C) 只有表尾指针的带头结点的循环单链表 D) 只有表头指针的带头结点的循环单链表四、代码填空题01、下面函数是链表的插入算法，根据要求填空。ListInsert(LinkList L, int i, ElemType e)/在带头结点的单链表L中第i个位置之前插入元素e。 p=L; j=0; while(p&jnext; +j; if(!p|ji-1) return ERROR; s=(LinkList)malloc(sizeof(LNode);/请填空，要求将新结点插入到L中。 s-data=e; s-nex

19、t=p-next; p-next=s;02、下面函数是链表的删除算法，根据要求填空。ListDelete(LinkList L, int i, ElemType *e)/在带头结点的单链表L中删除第i个元素，由e返回值。 p=L; j=0; while(p-next&jnext; +j; if(!(p-next)|ji-1) return ERROR;/请填空，要求删除并释放结点。 q=p-next; p-next=q-next; *e=q-data; free(q); 03、下面函数的功能是采用前插法建立带头结点的链表，请填空。void CreateList_1(LinkList *L, i

20、nt n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for(i=1; idata); p-next=L-next; L-next=p; 04、下面函数的功能是采用后接法建立带头结点的链表，请填空。void CreateList_2(LinkList *L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; q=L; for(i=1; idata); q-next=p; q=p; p-next=NULL;05、下面函数的功能是求无头结点的单向循环链表的长度，请填空。int ListLe

21、ngth(LinkList L) LinkList p; int n; if (L=NULL或!L) n=0; else p=L-next; n=1; while (p!=L) p=p-next; n+; return(n);06、下面函数的功能是实现带头结点单链表的就地逆置，请填空。void Reverse(LinkList *L) LinkList p,q,r; /p为遍历指针,q是其前驱,r为其后继 q=NULL;p=(*L)-next; while(p!=NULL) r=p-next; p-next=q; q=p; p=r; (*L)-next=q;07、在有头结点的链表中删除具有特定

22、值的所有元素。void DelListElem(LinkList &L, ElemType e) p=L-next; q=L; while (pNULL) if (p-data=e) q=p-next; free(p); p=q-next; else q=p; p=p-next; 五、算法设计题01、在顺序表中求值为X的元素个数。int count(SqList L, ElemType x) if (!L.Elem) return ERROR; n=0; for(i=0;inext; while (r!=NULL) q=r; p=r-next; while (p!=NULL) if (p-da

23、ta=r-data) q-next=p-next; free(p); p=q-next; else q=p; p=p-next; r=r-next; 03、插入法建立有序链表。void CreateList_3(LinkList &L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for(i=1;idata); q=L; p=L-next; while (p!=NULL & p-datadata) q=p; p=p-next; new-next=p; q-next=new; 04、判断链表是否为递增顺序。int Increase(

24、LinkList L) pre=L-next; if (preNULL) while (pre-nextNULL) p=pre-next; if (p-datapre-data) pre=p else return FALSE; return TRUE;05、已知两个线性表A、B，且其数据元素递增，设计算法求出A、B的交集C，并同样以递增顺序存储。void UnionList(List La, List Lb, List &Lc) InitList(Lc); i=1; j=1; k=1; La_len=ListLength(La); Lb_len=ListLength(Lb); while (i=La_len) & (j=Lb_len) GetElem(La,i,ai); GetElem(Lb,j,bj); if (aibj) j+; else ListInsert(Lc,k,ai); i+; j+; k+; 专心-专注-专业