单元练习2
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
╳）（1）线性表的链式存储结构不一定优于顺序存储。
╳）（2）链表的每个结点都恰好包含一个（或多個）指针域。
√）（3）**性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
╳）（4）顺序存储方式的优点是存储密度大，插入、删除效率低。查詢效率高。
╳）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机不会自动地将后续的各个单元向前移动。必須用程序實現。
╳）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个簡單类型。
√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。
╳）（9）顺序表结构适宜于进行随机存取，而链表适宜于进行順序存取。
╳）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。不能以偏概全。
二．填空题。
1） 顺序表中逻辑上相邻的元素在物理位置上必須相连。
2） 线性表中结点的集合是有限的，结点间的关系是一對一关系。
3） 顺序表相对于链表的优点是： 节省存储和随机存取。
4） 链表相对于顺序表的优点是： 插入、删除方便。
5） 采用順序存储结构的线性表叫顺序表。
6） 顺序表中访问任意一个结点的时间复杂度均为 o（1） 。
7） 链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小 。
8） 在双链表中要删除已知结点*p，其时间复杂度为 o（1） 。
9） 在单链表中要在已知结点*p之前插入一个新结点，需找到*p的直接前趋结点的地址，其查找的时间复杂度为 o（n） 。
10） 单链表中需知道頭指針才能遍历整个链表。
11） 线性表中第一个结点没有直接前趋，称为頭（開始） 结点。
12） 在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素。
13） 在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1 个元素。
14） 在无头结点的单链表中， 第一个结点的地址存放在头指针中，而其它结点的存储地址存放在前趋结点的指针域中。
15） 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用順序存储结构。
16） **性表的链式存储中，元素之间的逻辑关系是通过指针决定的。
17） 在双向链表中，每个结点都有两个指针域，它们一个指向其前驅结点，另一个指向其后继结点。
18） 对一个需要经常进行插入和删除操作的线性表，采用鏈式存储结构为宜。
19） 双链表中，设p是指向其中待删除的结点，则需要执行的操作为： p->prior->next=p->next; p->next->prior=p->prior
20） 在如图所示的链表中，若在指针p所在的结点之后插入数据域值为a和b的两个结点，则可用下列两个语句： s->next->next= p->next 和p->next=s来实现该操作。
三．选择题。
1）在具有n个结点的单链表中，实现（ a ）的操作，其算法的时间复杂度都是o（n）。
a．遍历链表或求链表的第i个结点 o（n）b．在地址为p的结点之后插入一个结点o（1）
c．删除开始结点 o（1d．删除地址为p的结点的后继结点o（1）
2）设a、b、c为三个结点，p分别代表它们的地址，则如下的存储结构称为（ b ）。
a． 循环链表b． 单链表 c．双向循环链表 d． 双向链表。
3）单链表的存储密度（ c）。
a． 大于1b． 等于1c．小于1d． 不能确定。
4）已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为b，则第i个结点的地址为（ a ）。
a． b+(i-1)*mb．b+i*mc． b-i*md． b+(i+1)*m
5）在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（ b ）。
a．o（1b．o（nc．o（n2d．o（log2n）
6）设llink、rlink分别为循环双链表结点的左指针和右指针，则指针p所指的元素是双循环链表l的尾元素的条件是（ d ）。
a．p== lb．p->llink== l c．p== nulld．p->rlink==l
7） 两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素前驱的条件是（ b）。
a．p->next==q->next b．p->next== q c．q->next== p d．p== q
8）用链表存储的线性表，其优点是（ c ）。
a． 便于随机存取b． 花费的存储空间比顺序表少。
c． 便于插入和删除d． 数据元素的物理顺序与逻辑顺序相同。
9）在单链表中，增加头结点的目的是（ c ）。
a． 使单链表至少有一个结点b． 标志表中首结点的位置。
c． 方便运算的实现d． 说明该单链表是线性表的链式存储结构。
10）下面关于线性表的叙述中，错误的是（ d ）关系。
a．顺序表必须占一片地址连续的存储单元 b．顺序表可以随机存取任一元素。
c．链表不必占用一片地址连续的存储单元 d．链表可以随机存取任一元素
11）l是线性表，已知lengthlist（l）的值是5，经dellist（l，2）运算后，lengthlist（l）的值是（ c ）。
a．2b．3c．4d．5
12）单链表的示意图如下：
l指向链表q结点的前趋的指针是（ b ）。
a．lb．pc．qd．r
13）设p为指向单循环链表上某结点的指针，则*p的直接前驱（ c ）。
a．找不到b．查找时间复杂度为o（1）
c．查找时间复杂度为o（nd．查找结点的次数约为n
14）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ c ）。
a．nb．(n-1)/2 c． n/2d．(n+1)/2
15）在下列链表中不能从当前结点出发访问到其余各结点的是（ c ）。
a．双向链表b．单循环链表 c．单链表d．双向循环链表。
16）在顺序表中，只要知道（ d ），就可以求出任一结点的存储地址。
a．基地址b．结点大小 c． 向量大小 d．基地址和结点大小
17）在双链表中做插入运算的时间复杂度为（ a ）。
a．o（1b．o（nc．o（n2d．o（log2n）
18）链表不具备的特点是（ a ）。
a．随机访问b．不必事先估计存储空间。
c．插入删除时不需移动元素d．所需空间与线性表成正比。
19）以下关于线性表的论述，不正确的为（ c ）。
a．线性表中的元素可以是数字、字符、记录等不同类型。
b．线性顺序表中包含的元素个数不是任意的。
c．线性表中的每个结点都有且仅有一个直接前趋和一个直接后继。
d．存在这样的线性表，即表中没有任何结点
20）在（ b ）的运算中，使用顺序表比链表好。
a．插入b．根据序号查找 c． 删除d．根据元素查找
四．下述算法的功能是什么？
解：1）返回结点*p的直接前趋结点地址。
2）交换结点*p和结点*q（p和q的值不变）。
五． 程序填空
1．已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于min，小于max的元素，试完成下列程序填空。
void delete (lklist head; datatype min, max)
{ q=head->next;
while (p!=null)
{ if ((p->data<=minp->data>=max
q=p; p= p->next
else{ q->next= p->next ;
delete (p
p= q->next
2． 在带头结点head的单链表的结点a之后插入新元素x，试完成下列程序填空。
struct node
elemtype data;
node *next;
数据结构练习
一 选择题 1 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动 个数据元素。a 2.在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b a.q next p s next p b.s next p q nex...
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...