数据结构与算法练习题

简介：
本书为《数据结构与算法》课程设计，包含大量精选练习题和实例解析，旨在帮助学生加深对核心概念的理解及应用能力。 一.单选题（共10题,5） 1线性表采用链式存储结构时，其地址（ ）。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续与否均可以 正确答案： D 2带头结点的单链表head为空的判断条件是（ ）。 A、head=NULL B、head->next=NULL C、head->next=head D、head！=NULL 正确答案： B 3将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A、n B、2n-1 C、 2n D、n-1 正确答案： A 4在一个单链表中，已知q所指结点是p所指结点的前趋结点，若在q和p之间插入s结点，则执行（ ）。 A、 s->next=p->next;p->next=s B、p->next=s->next;s->next=p C、q->next=s;s->next=p D、p->next=s;s->next=q 正确答案： C 5向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 A、64 B、63 C、63.5 D、7 正确答案： C 6若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 正确答案： D 7若长度为n的线性表采用顺序存储结构，在其第个i位置插入一个新元素算法的时间复杂度为（ ）。 A、 O(log2n) B、O(1) C、O(n) D、O(n^2) 正确答案： C 8线性表的静态链表存储结构与顺序存储结构相比优点是（ ）。 A、所有的操作算法简单 B、便于插入和删除 C、便于利用零散的存储空间 D、便于随机存取 正确答案： B 9在一个单链表中，若删除p所指结点的后续结点，则执行（ ） A、s->next=p;p->next=s; B、s->next=p->next;p=s; C、s->next=p->next;p->next=s; D、p->next=s;s->next=p; 正确答案： B 10一个线性表第一个元素的存储地址是 100, 每个元素的长度为2，则第5个元素的地址是( ) A、110 B、108 C、100 D、120 正确答案： B ### 数据结构与算法知识点梳理 #### 单项选择题解析 **链式存储结构的特点** - 选项解析： - A 错误，因为节点地址可以不连续。 - B 错误，不要求部分地址连续。 - C 不准确，过于绝对化表述。 - D 正确，允许节点地址连续或不连续。 **单链表为空的条件** - 选项解析： - A 错误，头指针指向头结点而非NULL表示非空； - B 正确，next指针为NULL代表链表为空； - C 错误，用于循环链表判断。 - D 错误，并不意味着链表非空。 **归并有序表的最少比较次数** - 选项解析： - A 正确，在两序列首元素大小始终不同的情况下； - B 错误，超过最小情况； - C 错误，最多比较次数； - D 错误，少于最小情况。 **在单链表中插入节点** - 选项解析： - A、B 错误，p或s没有指向原来的节点。 - C 正确，q的next指针指向新节点s, s的next指针指向原位置； - D 错误，形成环路。 **保持顺序不变时插入元素** - 选项解析： - A、B 错误； - C 正确，平均移动63.5个元素。 - D 错误，明显偏小。 **最节省运算时间的存储方式** - 选项解析： - A 错误，需要遍历操作； - B 错