数据结构练习题--2011级--参考答案讲解VIP免费

1第1章选择题：1.1数据结构在计算机内存中的表示是指：A．数据的存储结构B.数据结构C．数据的逻辑结构D.数据元素之间的关系1.2数据的逻辑结构是指：A.数据所占的存储空间量B．各数据元素之间的逻辑关系C.数据在计算机中顺序或链接的存储方式D.存储在内存或外存中的数据1.3在下列的叙述中，正确的是：A．数据的逻辑结构是指数据的各数据项之间的逻辑关系。B．数据的物理结构是指数据在计算机内的实际存储形式。C．在顺序存储结构中，数据元素之间的关系是显示体现的。D．链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。填空题：1.4数据结构主要研究数据的逻辑结构，数据的存储结构，数据的运算三个方面的内容。1.5链接存储的特点是通过附加指针域来表示数据元素之间的逻辑关系。1.6数据结构中讨论的三种经典结构包括：线性表，树，图。1.7数据结构中常用的存储方法有：顺序，链接，索引，散列。1.8顺序存储结构可以通过位置隐含表示关系，链接存储结构通过附加指针来显示表示关系。1.9算法的特性包括有穷性，确定性，可行性，输入和输出。1.10算法性能分析的两个主要定量评价指标是时间复杂度和空间复杂度。简答题：1.11数据结构研究的三方面内容之间有什么联系和区别？数据结构研究的三方面内容包括:数据的逻辑结构、存储结构和运算。数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。1.12简述数据结构中讨论的三种经典结构的逻辑特征是什么？三种经典结构：线性表、树和图。逻辑特征分别为：（1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。（2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。（3）图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。1.13简述各种常用存储方法的基本思想。各种方法的基本思想：顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。链接存储：通过附加指针域表示数据元素之间的关系。索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字－地址转换法。2第2章选择题：2.1线性表L=（a1，a2，⋯，an），下列说法正确的是：A.每个元素都有一个直接前驱和一个直接后继。B.线性表中至少有一个元素。C.表中元素的排列顺序必须是由小到大或由大到小。D.除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。2.2下面关于线性表的叙述中，错误的是：A．线性表若采用顺序存储，必须占用一片连续的存储单元B．线性表若采用顺序存储，便于进行插入和删除操作C．线性表若采用链接存储，不必占用一片连续的存储单元D．线性表若采用链接存储，便于插入和删除操作2.3在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为：A.n-i+1B.n-iC.iD.i-12.4删除长度为n的顺序表中的第i(1≤i≤n)个位置上的元素，元素的移动次数为：A.n-i+1B.n-iC.iD.i-12.5已知一个带头结点单链表L，在表头元素前插入新结点*s的语句为：A.L=s;s->next=L;B.s->next=L->next;L->next=s;C.s=L;s->next=L;D.s->next=L;s=L;2.6已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为：A.L=s;s->next=L;B.s->next=L;L=s;C.s=L;s->next=L;D.s->next=L;s=L;2.7已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为：A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;2.8已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是：A．s=p->next;p=p->next;free(s);B．p=p->next;free(p);C．s=p->next;p->next=s->next;free(s);D．p=p->next;free(p->next);2.9设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构...