作业1 数据结构
- 格式:doc
- 大小:32.00 KB
- 文档页数:2
第一次作业——第一章、第二章
一.判断题:
1.数据元素是数据的最小单位。数据项
2.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。×
3.在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点。头结点
4.顺序存储的线性表可以随机存取。√
5.在单链表中,要访问某个结点,只要知道该结点的指针即可。因此,单链表是一种随机存储结构。×
6.在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。
√
7.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。×
二.填空题:
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. 2n
d. n-1
3.以下说法正确的是 d 。
a. 顺序存储方式的优点是存储密度大且插入、删除运算效率高
b. 链表的每个结点中都恰好包含一个指针
c. 线性表的顺序存储结构优于链式存储
d. 顺序存储结构属于静态结构而链式存储结构属于动态结构
4.以下说法错误的是 a 。
a. 对于循环链表来说,从表中任意结点出发都能通过前后移操作扫描整个循环链表
b. 对于单链表来说,只有从头指针开始才能扫描表中全部结点
c. 双链式的特点是找结点的前趋和后继都很容易
d. 对双链式来说,结点*p 的存储位置既存放在其前趋结点的后继指针域中,也存放在它
的后继结点的前趋指针域中
5.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为 c 。
a .存储结构
b .逻辑结构
c .顺序存储结构
d .链式存储结构
6.在一个单链表中,若删除p所指结点的直接后继结点,则执行 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.在n 个结点的顺序表中,算法的时间复杂度是O(1)的操作是 a 。
a .访问第i 个结点(n i ≤≤1)和求第i 个结点的直接前趋。
b .在第i 个结点后插入一个新结点(n i ≤≤1)。
c .删除第i 个结点(n i ≤≤1)。
d .将n 个结点从小到大排序。
四.应用题:
1.设在等概率的情况下,对有127个数据元素的顺序表进行插入,平均需要移动多少个元
素?删除一个元素,又平均需要移动多少个元素?
2.线性表有两种存储结构:一是顺序表,二是链表。试问:
⑴ 如果有 n 个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的
总数也会自动地改变。在此情况下,应选用哪种存储结构? 为什么?
⑵ 若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性
表中的元素,那么应采用哪种存储结构?为什么?
五.设计算法题:
1. 假定顺序表中有多个零元素,试写出一个算法,将所有的非零元素依次移到顺序表的前
端。
2. 设计算法,实现统计单链表中具有给定值x 的所有元素的个数。
3. 设计算法,实现在非递减有序的单链表中删除值相同的多于结点。