西安交大计算机考研软件工程章节测试（二）

• 鄙人今年备考，主要目的在于记录学习历程，望道友们勿喷~
• 官方的考研资料给的过于草率，还是自己做出来的用的踏实，觉得有用的道友自取~
• 使用方法说明：当卷子做，下方统一给答案与一点愚见，应用题除外~
• 开始炼丹~

上篇链接：西安交大计算机考研软件工程章节测试（一）
下篇链接：西安交大计算机考研软件工程章节测试（三）

文章目录

• 西安交大计算机考研软件工程章节测试（二）
• 一、选择题
• 二、判断题
• 三、填空
• 四、应用题
• 五、算法设计题
• 六、答案与解析

一、选择题

1. 下述哪一条是顺序存储结构的优点li>

• A.存储密度大
• B. 插入运算方便
• C. 删除运算方便
• D.可方便地用于各种逻辑结构的存储表示

2. 下面关于线性表的叙述中，错误的是哪一个li>

• A.线性表采用顺序存储，必须占用一片连续的存储单元。
• B.线性表采用顺序存储，便于进行插入和删除操作。
• C.线性表采用链式存储，不必占用一片连续的存储单元。
• D.线性表采用链式存储，便于插入和删除操作。

3. 线性表是具有n个( )的有限序列(n>0)。

• A.表元素
• B.字符
• C.数据元素
• D.数据项
• E.信息项

4. 若某线性表最常用的操作是存取任一指定序 的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。

• A.顺序表
• B.双链表
• C.带头结点的双循环链表
• D.单循环链表

5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。

• A.单链表
• B.仅有头指针的单循环链表
• C.双链表
• D.仅有尾指针的单循环链表

6. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

• A.单链表
• B.单循环链表
• C.带尾指针的单循环链表
• D.带头结点的双循环链表

7. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( )存储方式最节省运算时间。

• A.单链表
• B.双链表
• C.单循环链表
• D.带头结点的双循环链表

8. 静态链表中指针表示的是( )。

• A.内存地址
• B.数组下标
• C.下一元素地址
• D.左、右孩子地址

9. 链表不具有的特点是()。

• A.插入、删除不需要移动元素
• B.可随机访问任一元素
• C.不必事先估计存储空间
• D.所需空间与线性长度成正比

10. 下面的叙述不正确的是 ()。(多选)

• A.线性表在链式存储时，查找第i个元索的时间同i的值成正比
• B.线性表在链式存储时，查找第i个元素的时间同i的值无关
• C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比
• D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

11. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。

• A.O(n) O(n)
• B.O(n) O(1)
• C.O(1) O(n)
• D.O(1) O(1)

二、判断题

1. 链表中的头结点仅起到标识的作用。

• 对
• 错

2. 顺序存储结构的主要缺点是不利于插入或删除操作。

• 对
• 错

3. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

• 对
• 错

4. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。

• 对
• 错

5.对任何数据结构链式存储结构一定优于顺序存储结构。

• 对
• 错

6. 顺序存储方式只能用于存储线性结构。(X)

• 对
• 错

7. 集合与线性表的区别在于是否按关键字排序。

• 对
• 错

8. 所谓静态链表就是一直不发生变化的链表。 (X)

• 对
• 错

9. 线性表的特点是每个元素都有一个前驱和一个后继。

• 对
• 错

10. 取线性表的第i个元素的时间同i的大小有关。

• 对
• 错

11. 循环链表不是线性表。

• 对
• 错

12. 线性表只能用顺序存储结构实现。

• 对
• 错

13. 线性表就是顺序存储的表。

• 对
• 错

14. 为了很方便的插入和删除数据，可以使用双向链表存放数据。

• 对
• 错

15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

• 对
• 错

16. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

• 对
• 错

三、填空

1. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2. 线性表L= (a1,a2,……,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是。

3. 设单链表的结点结构为(data,next)，next 为指针域。已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句。

4. 在一个长度为n的顺序表中第i个元素(1

5. 在单链表中设置头结点的作用主要是使，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。

6. 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为,在给定值为x的结点后插入一个新结点的时间复杂度为。

7. 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成和；而又根据指针的连接方式，链表又可分成和。

8. 在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是。

四、应用题

1. 线性表有两种存储结构:一是顺序表，二是链表。试问:

• 如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构么r> 答:选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为O(1)。
• 若线性表的总数基本稳定，且很少进行插入和刑除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构么r> 答:选顺序存储结构。顺序表可以随机存取，时间复杂度为O(1)。

2. 线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

• 答:一般来说，链式存储结构克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

3. 若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构么li>

• 答:采用链式存储结构。它根据实际需要申请内存空间，而当不需要时又可将不用的结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

4. 线性衣(al, a2,…,an)用顺序映射表示时，ai 和ai+1 (1

• 答:顺序映射时，ai 与ai+1的物理位置相邻；链接表示时，ai与ai+1的物理位置不要求相邻。

5. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。

• 答:在线性表的链式存储结构中，头指针是指向链表的指针，若链表有头结点，则是链表的头结点的指针，头指针具有标识作用。故常用头针冠以链表的名字。
  头结点是为了操作的统一、方便而设立的，放在第一元素结点之前。其数据域一般无意义（当然有些情况下也可以存放链表的长度、用做监视哨等等)，有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。
  首元结点也就是第一元素结点。它是头结点后的第一个结点。

五、算法设计题

1. 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
2. 试编写在头结点的单链表中删除（一个）最小值节点的（高效）算法。
3. 已知非空线性链表由list指出，链结点的构造为。请写一个算法将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
4. 已知p指向双向循环链表中的一个结点，其结点的结构为三个域，写出算法，交换p所指向的结点和它的前缀（前驱）结点的顺序。
5. 线性表(a1, a2,…,an)中元素递增有序且按顺序存储于在计算机内。要求设计一算法完成：

• 用最少的时间在表中查找数值为x的元素；
• 若找到将其与后继元素位置交换；
• 若找不到将其插入表中并使表中元素仍递增有序。

六、答案与解析

Ps：
计划改变，答案与解析部分待试卷整理完毕后统一更新~

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34639 人正在系统学习中