HNSY数据结构习题集

-1-注：答案可能有误，仅供参考绪论一、选择题：1、下列算法的时间复杂度是（B）for(i=0;in;i++)c[i]=i；A．O（1）B．O（n）C．O（log2n）D．O（nlog2n）2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（D）A．索引存储方法B．顺序存储方法C．链式存储方法D．散列存储方法3、以下哪一个术语与数据的存储结构无关？（D）。A.顺序表B.链表C.散列表D.队列4、算法在发生非法操作时可以做出处理的特性称为（C）。A．正确性B．易读性C．健壮性D．高效性5、逻辑结构是指数据元素的（A）。A．关联方式B．存储方式C．结构D．数据项6、研究数据结构就是研究（D）。A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据的运算7、从逻辑上可以把数据结构分为（C）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构8、以下有关数据的叙述中错误的是（B）。A．计算机能够处理的数据包括整数、实数、字符、声音、图像等B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式C．数据存储结构的实现依赖于计算机语言D．数据的运算是定义在数据的逻辑结构上的9、数据的基本单位是（B）。A.数据结构B.数据元素C.数据项D.文件10、下列算法的时间复杂度是（C）for(i=0;im;i++)for(j=0;jn;j++)a[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）11、算法分析的两个主要方面是（D）。A．正确性和简明性B．数据复杂性和程序复杂性C．可读性和可维护性D．时间复杂性和空间复杂性12、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（B）。A．存储结构B．逻辑结构C．算法D．操作213、下列叙述中正确的是(D)。A．一个逻辑数据结构只能有一种存储结构B．数据的逻辑结构属于线性结构，存储结构属于非线性结构C．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D．一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率二、填空题：1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（存储结构）和（运算）。2、(逻辑)结构与数据元素本身的内容和形式无关。3、程序段“for(i=1;i=n;i++){k++;for(j=1;j=n;j++)x=x+k;}”的时间复杂度为(O(n2))。4、数据的存储结构（物理结构）可以用（顺序）、（链式）、（索引）及散列存储等四种存储方法表示。5、数据结构是一门研究非数值计算的程序设计问题中计算机的（操作对象）以及它们之间的（关系）和运算等的学科。6、数据结构被形式地定义为（D,R），其中D是（数据元素）的有限集合，R是D上的（关系）有限集合。7、数据结构包括数据的（逻辑结构）、数据的（存储结构）和数据的（运算）这三个方面的内容。8、数据结构按逻辑结构可分为两大类，它们分别是（线性结构）和（非线性结构）。9、线性结构中元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中元素之间存在（多对多）关系。10、在线性结构中，（第一个结点）没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点（没有）后续结点，其余每个结点有且只有1个后续结点。）11、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（1）个前驱结点；叶子结点没有（后续）结点，其余每个结点的后续结点数可以任意多个。12、在图形结构中，每个结点的前驱结点数和后续结点数可以（任意多个）。13、对于给定的n个元素,可以构造出的逻辑结构有（集合，线性表，树，图）四种。14、顺序映象的特点是借助元素在存储器中的（相对位置）来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的（指针）表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定（逻辑结构），而算法的实现依赖于采用的（存储结构）。15、数据类型是一组（性质相同）的值集合以及定义在这个值集合上的一组操作的总称。16、数据对象是（性质相同的）数据元素的集合，是数据的一个子集。三、判断题：1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。（×）2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。（×）3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（√）4、数据的机内表示称为数据的存储结构。（√）5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）6、数据元素是数据的最小单位。（×）7、基于某种逻辑结构之上的运算，其实现是惟一的。（×）32线性表一、选择题：1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（B）。A．nB．n/2C．n/3D．n/42、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（A）A．S-next=P-next;P-next=SB．P-next=S-next;S-next=P；C．P-next=P;P-next=S；D．P-next=S;S-next=P；3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（B）A．Ｏ（1）B．Ｏ（log2n）C．O（n）D．O（n2）解析：单就插入运算而言，算法时间复杂度为Ｏ（1），但要将指针定位到链表末尾，指针移动的时间复杂度为O（n）；4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（C）A．顺序表B．用头指针表示的单循环链表C．用尾指针表示的单循环链表D．单链表解析：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear-next-next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。5、线性表是（A）A．一个有限序列，可以为空B．一个有限序列，不能为空C．一个无限序列，可以为空D．一个无限序列，不能为空6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（B）A．O（n）B．O（1）C．O（log2n）D．O（n2）7、线性表采用链式存储时，结点的地址（C）A．必须是连续的B．必须是不连续的C．连续与否均可D．必须有相等的间隔8、在单链表中，增加头结点的目的是（C）A．使单链表至少有一结点B．标志表中首结点位置C．方便运算的实现D．说明单链表是线性表的链式存储实现9、带头结点的单链表head为空的判定条件是（B）A．head=NULL；B．head-next=NULL；C．head-next=head；D．head!=NULL；10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（B）A．Ｏ（1）B．Ｏ（n）C．Ｏ（n2）D．Ｏ（log2n）11、下列有关线性表的叙述中，正确的是（A）A．线性表中的元素之间是线性关系B．线性表中至少有一个元素C．线性表中任何一个元素有且仅有一个直接前趋D．线性表中任何一个元素有且仅有一个直接后继12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（B）A．直接前趋B．直接后继C．开始结点D．终端结点13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（B）。A．nB.2n-1C.2nD.n-1414、链表不具有的特点是（A）。A．随机访问B．不必事先估计存储空间C．插入删除时不需移动元素D．所需的空间与线性表成正比15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的操作是（B）。A．s-next=p-next;p-next=s;B．q-next=s;s-next=p;C．p-next=s-next;s-next=p;D．p-next=s;s-next=q;16、链表具有的特点是（C）。A．可随机访问任一元素B．插入、删除需要移动元素C．不必事先估计存储空间D．存储空间是静态分配的17、一个顺序表一旦说明，其中可用空间大小（B）A．已固定B．可以改变C．不能固定D．动态变化18、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（A）存储方式最节省时间。A．顺序表B．单链表C．双向链表D．单循环链表19、两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素的前驱的条件是（A）。A．P-next==QB．Q-next==PC．P==QD．P-next==Q-next20、链表不具有的特点是（A）。A．可随机访问任一元素B．插入、删除不需要移动元素C．不必事先估计存储空间D．所需空间与线性表长度成正比21、下面关于线性表的叙述中，错误的是（B）。A．线性表采用顺序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进行插入和删除操作C．线性表采用链接存储，不必占用一片连续的存储单元D．线性表采用链接存储，便于进行插入和删除操作22、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。A．访问第i个结点（1≤i≤n）和求第i个结点的直接前趋（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序23、在一个单链表中，若删除p指向结点的后继结点，则执行的操作为（A）。A．q=p-next;p-next=p-next-next;free(q);B．p=p-next;q=p-next;p=q-next;free(q);C．q=p-next-next;p=p-next;free(q);D．p=p-next-next;q=p-next;free(q);24、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（D）。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表25、求循环链表中当前结点的后继和前驱的时间复杂度分别是（C）。A．O(n)和O(1)B．O(1)和O(1)C．O(1)和O(n)D．O(n)和O(n)26、求单链表中当前结点的后继和前驱的时间复杂度分别是（C）。A．O（n）和O（1）B．O（1）和O（1）C．O（1）和O（n）D．O(n)和O（n）27、非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（A）。5A．rear-next==headB．rear-next-next==headC．head-next==rearD．head-next-next==rear28、从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（A）。A．n-iB．n-i+1C．n-i-1D．i29、用链表表示线性表的优点是（D）。A．便于随机存取B．花费的存储空间比顺序表少C．数据元素的物理顺序与逻辑顺序相同D．便于插入与删除30、链表不具有的特点是（B）。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比31、采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（D）。A．nB．n/2C．(n-1)/2D．(n+1)/232、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）。A．O(1)B．O(n)C．O(m)D．O(m+n)33、若不带头结点的单链表的头指针为head，则该链表为空的判定条件是(A)。A．head==NULLB．head-next==NULLC．head!=NULLD．head-next==head34、某线性表中