数据结构第2章-答案

第2章线性表数据结构作业答案1一、填空题01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。02、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。03、在有n个元素的顺序表中插入一个新元素，需要平均移动n/2元素，具体移动的元素个数与表长和该元素在表中的位置有关。04、线性表中结点的集合是有限的，结点间的关系是一对一的。05、向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。06、向一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。07、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。08、顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置未必相邻。09、在单链表中，除了首结点外，任一结点的存储位置由其直接前驱结点的链域值指示。10、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O(n)。11、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data域为x的结点，指针py指向data域为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：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所指的结点，则需执行下列语句：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所指结点有后继结点的条件是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、线性表在物理存储空间中也一定是连续的。×08、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。×09、顺序存储方式只能用于存储线性结构。×10、线性表的逻辑顺序与存储顺序总是一致的。×11、链表中的头结点仅起到标识的作用。√12、顺序存储结构的主要缺点是不利于插入或删除操作。√13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。×14、对任何数据结构链式存储结构一定优于顺序存储结构。×15、集合与线性表的区别在于是否按关键字排序。×16、所谓静态链表就是一直不发生变化的链表。×17、线性表的特点是每个元素都有一个前驱和一个后继。×18、取线性表的第i个元素的时间同i的大小有关。×19、循环链表不是线性表。√20、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。第2章线性表数据结构作业答案2三、单项选择题C01、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___。A)存储结构B)逻辑结构C)顺序存储结构D)链式存储结构B02、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是。A)110B)108C)100D)120A03、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是___。A)访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B)在第i个结点后插入一个新结点(1≤i≤n)C)删除第i个结点(1≤i≤n)D)将n个结点从小到大排序B04、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动_个元素。A)8B)63.5C)63D)7A05、链式存储的存储结构所占存储空间___。A)分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B)只有一部分，存放结点值C)只有一部分，存储表示结点间关系的指针D)分两部分，一部分存放结点值，另一部分存放结点所占单元数A06、下述___是顺序存储结构的优点。A)存储密度大B)插入运算方便C)删除运算方便D)可方便地用于各种逻辑结构的存储表示D07、线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。A)必须是连续的B)部分地址必须是连续的C)一定是不连续的D)连续或不连续都可以B08、线性表L在情况下适用于使用链式结构实现。A)需经常修改L中的结点值B)需不断对L进行删除插入C)L中含有大量的结点D)L中结点结构复杂C09、单链表的存储密度___。A)大于1B)等于1C)小于1D)不能确定D10、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___存储方式最节省运算时间。A)单向链表B)双向链表C)单向循环链表D)带头结点的双向循环链表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、非空的循环单向链表first的尾结点(由p指向)满足___。A)p-next==NULLB)p==NULLC)p-next==firstD)p=firstC15、下列关于线性表的叙述中，不正确的是___。A)线性表是n个结点的有穷序列第2章线性表数据结构作业答案3B)线性表可以为空表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-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-nextB)p=p-nextC)p=p-next-nextD)next=pB18、带头结点的单链表head为空的判定条件是___。A)head=NULLB)head-next==NULLC)head-next=headD)head!=NULLD19、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较___个结点。A)nB)n/2C)(n-1)/2D)(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、下面程序的功能是___。voiddelete(Linklist*L){p=L;while(p-next!=NULL){m=p-next-data;q=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)带头结点的双循环链表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-next=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;第2章线性表数据结构作业答案4D)q-piror=p-piror;q-next=q;p-piror=q;p-piror=q;B29、占用连续的存储空间，但插入和删除不需要移动元素，这种线性表的存储结构是___。A)单向链表B)静态链表C)双向链表D)顺序表B30、在一个长度为n(n1)的单链表上，设有头和尾两个指针，执行___操作与链表的长度有关。A)删除单链表中的第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)顺序访问相邻结