《数据结构习题集(2023》由会员分享，可在线阅读，更多相关《数据结构习题集(2023（7页珍藏版）》请在金锄头文库上搜索。
1、数据构造习题集(2023-2023)doc - 第一章概论 一、填空题 1、数据的存储构造可用四种根本的存储方法表示，分别是顺序、 链式 、 索引 和 散列。 2、一个算法具有有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出5个特性。 3、数据构造包括数据的 逻辑构造 、存储构造 和 运算或根本操作三个方面的内容。 4、数据构造中评价算法的两个重要指标是 时间 效率和 空间 效率。 5、一个数据构造在计算机中的表示称为 存储构造 。 6、从逻辑上可以把数据构造分为线性构造、非线性构造两大类 7、数据项是数据中不可再分割的最小单位；数据元素是数据集合中的一个“个体”，是计算机程序中加工
2、处理的根本单位。 8、强健性指算法对非法输入能适当地做出反响或进展处理，而不会产生莫名其妙的输出结果。 9、以下语句的时间复杂度是On2 for(i=1;inext=p-next; _ p-next=q 4、在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取的数据构造。 5、链式存储构造的特点是利用_指针 来表示数据元素之间的逻辑关系。在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示，查找结点都必须从头结点开场，因此，链表也称为 顺序存取 的数据构造。 6、指针p指向单链表L中的某结点，u是P的直接后继，删除u的语句是：p-nex
3、t=u-next; free(u); 7、带头结点的双循环链表L中只有一个元素结点的条件是：L-next-next=L； 8、在顺序表L=a1,a2,?,an中，假定删除表中任一元素的概率一样，那么删除一个元素平均需要挪动元素的个数是n-1/2_；第i个元素1prior)-next=p=(p-next)-prior 二、判断正误 1、线性表的特点是每个元素都有一个前驱和一个后继。 2、链表的物理存储构造具有同链表一样的顺序。 3、链表的删除算法很简单，因为当删除链中某个结点后，计算时机自动地将后续的各个单元向前挪动。 4、取线性表的第i个元素的时间同i的大小有关。 3 5、顺序表构造适宜于进展
4、顺序存取，而链表适宜于进展随机存取。 6、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 7、链表是采用链式存储构造的线性表,进展插入、删除操作时，在链表中比在顺序存储构造中效率高。() 8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 9、顺序存储方式只能用于存储线性构造。 10、线性表的逻辑顺序与存储顺序总是一致的。 11、链表中的头结点仅起到标识的作用。 12、顺序存储构造的主要缺点是不利于插入或删除操作。() 13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。() 14、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 1
5、5、对任何数据构造链式存储构造一定优于顺序存储构造。 16、顺序存储的线性表，优点是空间利用率很高。() 17、在单链表上插入、删除一个结点，必须知道其前驱结点。() 18、遍历操作时，循环链表和非循环链表的终止条件判断是一样的。()19、顺序表能按元素序号随机访问，而链表只能顺序查找。() 20、在顺序表中做插入删除操作时，平均挪动大约表中一半的元素，因此对n较大的顺序表效率低。() 三、单项选择题 1、数据在计算机存储器内表示时，物理地址与逻辑地址一样并且是连续的，称之为 C 。 A、存储构造 B、逻辑构造 C、顺序存储构造 D、链式存储构造 2、一个向量第一个元素的存储地址是100，每个
6、元素的长度为2，那么第5个元素的地址是 B A、110 B、108 C、100 D、120 3、在n个结点的顺序表中，算法的时间复杂度是O1的操作是 A 。 A、访问第i个结点1in和求第i个结点的直接前驱2in B、在第i个结点后插入一个新结点1in C、删除第i个结点1in D、将n个结点从小到大排序 4、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要挪动 B 个元素。 A、8 B、63.5 C、63 D、7 5、线性表 a1,a2,?,an以链接方式存储时，访问第i位置元素的时间复杂性为 C 。 A、Oi B、O1 C、On D、Oi-1 6、链表是一种采用 B
7、存储构造存储的线性表。 4 A、顺序 B、链式 C、星式 D、网状 7、线性表假设采用链式存储构造时，要求内存中可用存储单元的地址 D 。 A、必须是连续的 B、局部地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 8、线性表在 B 情况下适用于使用链式构造实现。 A、需经常修改中的结点值 B、需不断对进展删除插入 C、中含有大量的结点 D、中结点构造复杂 9、单链表的存储密度 C 。 A、大于1 B、等于1 C、小于1 D、不能确定 10、对于一个头指针为head的带头结点的单链表，断定该表为空表的条件是 B A、head=NULL B、headnext=NULL C、heade
8、xt=head D、head!=NULL 11、下面关于线性表的表达中，错误的选项是哪一个？ B A、线性表采用顺序存储，必须占用一片连续的存储单元。 B、线性表采用顺序存储，便于进展插入和删除操作。 C、线性表采用链接存储，不必占用一片连续的存储单元。 D、线性表采用链接存储，便于插入和删除操作。 12、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采用 D 存储方式最节省运算时间。 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 13、链表不具有的特点是 B 。 A、插入、删除不需要挪动元素 B、可随机访问任一元素 C、不必事先估计存储空间 D、所需空间与线性长度成正比 14、设一个链表最常用的操作是在末尾插入结点和删除尾结点，那么选用( D )最节省时间。 A、单链表 B、单循环链表 C、带尾指针的单循环链表 D、带头结点的双循环链表 15、假设长度为n的线性表采用顺序存储构造，在其第i个位置插入一个新元素的算法的时间复杂度为 C (1next=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; 18、线性表是具有n个 C 的有限序列n0。 25 第 页 共 页
