第一次作业——第一章、第二章。
一．判断题：
数据元素是数据的最小单位。数据项。
线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。×
在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。头结点。
顺序存储的线性表可以随机存取。√
在单链表中，要访问某个结点，只要知道该结点的指针即可。因此，单链表是一种随机存储结构。×
**性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。√
顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。×
二．填空题：
1．在一个循环单链表中，表尾结点的指针域和头指针的值相等 。
2．对于双向链表，在两个结点之间插入一个新结点时需修改或建立的指针共有 4 个，单链表为 2个。
3．求顺序表和单链表长度的时间复杂性分别为 o（1） 和 o（n） 。
4．在一个不带头结点的单链表中，在表头插入或删除与其他位置插入或删除其操作过程不同 。
5．**性表的顺序存储中，元素之间的逻辑关系是通过物理位置的邻接关系决定的；**性表的链式存储中，元素之间的逻辑关系是通过指针域（或链域）决定的。
6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 o（1在给定值为x的结点后插入一个新结点的时间复杂度为 o(n) 。
三．选择题：
1．在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时需向后移动 b 个元素。
a. n-i b. n-i+1 c. n-i-1 d. i
2．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 a 。
a. n b. 2n-1 c. 2nd. n-1
3．以下说法正确的是 d 。
a. 顺序存储方式的优点是存储密度大且插入、删除运算效率高。
b. 链表的每个结点中都恰好包含一个指针。
c. 线性表的顺序存储结构优于链式存储。
d. 顺序存储结构属于静态结构而链式存储结构属于动态结构。
4．以下说法错误的是 a 。
a. 对于循环链表来说，从表中任意结点出发都能通过前后移操作扫描整个循环链表。
b. 对于单链表来说，只有从头指针开始才能扫描表中全部结点。
c. 双链式的特点是找结点的前趋和后继都很容易。
d. 对双链式来说，结点*p的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。
5．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为 c 。
a．存储结构 b．逻辑结构 c．顺序存储结构 d．链式存储结构。
6．在一个单链表中，若删除ｐ所指结点的直接后继结点，则执行 a 。
a．p－＞next＝p－＞next－＞next；
b．p＝p－＞next；p－＞next＝p－＞next－＞next；
c．p－＞next＝p；
d．p＝p－＞next－＞next；
7．在个结点的顺序表中，算法的时间复杂度是ｏ（1）的操作是 a 。
a．访问第i个结点（）和求第i个结点的直接前趋。
b．在第i个结点后插入一个新结点（）。
c．删除第i个结点（）。
d．将个结点从小到大排序。
四．应用题：
1．设在等概率的情况下，对有127个数据元素的顺序表进行插入，平均需要移动多少个元素？删除一个元素，又平均需要移动多少个元素？
2．线性表有两种存储结构：一是顺序表，二是链表。试问：
如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？
若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
五．设计算法题：
假定顺序表中有多个零元素，试写出一个算法，将所有的非零元素依次移到顺序表的前端。
设计算法，实现统计单链表中具有给定值x的所有元素的个数。
设计算法，实现在非递减有序的单链表中删除值相同的多于结点。
作业1数据结构
第一次作业 第一章 第二章。一 判断题 1 数据元素是数据的最小单位。数据项。2 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。3 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。头结点。4 顺序存储的线性表可以随机存取。5 在单链表中，要访问某个结点，只要知道该结点...
作业1数据结构
第一次作业 第一章 第二章。一 判断题 1 数据元素是数据的最小单位。数据项。2 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。3 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。头结点。4 顺序存储的线性表可以随机存取。5 在单链表中，要访问某个结点，只要知道该结点...
数据结构作业
数据结构作业 下周三交。题目描述 二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树 1.若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值 2.若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值 3.左 右子树本身也是一颗二叉排序树。现在...