数据结构考试题库含答案(6)

4. 单链式存储结构的优缺点有哪些? (中等)

单链式存储结构的优点:（2.5分） 不需预先分配空间，空间利用充分 插入、删除操作简单, 无需移动大量的元素 表容量易于扩充 缺点:（2.5分）

每个数据元素，除存储本身信息外，还需空间存储其直接后继的信息 逻辑相邻，物理不一定相邻

不可随机存取任一元素, 只能从链表头依次查找.

5. 有顺序表A=(a0, a1, a2,...a8,a9,…a19)，要在a8,a9之间插入一个元素a20，

请描述其操作(思想)步骤。(中等)

插入思想或步骤：根据顺序表的存储特点，要在表中某位置10插入一新数据元素,则要进行如下两步操作：

（1）、从位置10到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第10个位置。（2分）

（2）、将新结点插入到空余位置10处。2分） （3）表长度加1. （1分）

6. 有顺序表A=(a0, a1, a2,...a8,a9,…a19)，要删除一个元素a9，请描述其操作(思想)步骤。(中等)

（1）然后将从位置11到表尾的所有数据元素依次向前移一个存储位置。（3分） （2）表长度减1. （2分）

7. 请描述在顺序表中第i个位置插入新的数据x操作过程。

根据顺序表的存储特点，要在表中某位置i插入一新数据元素，则要进行如下两步操作： （1）从位置i到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第i个位置；（2分）

（2）将新数据x插入到空余位置i处。（2分） （3）表长度加1. （1分）

8. 请描述在顺序表中删除第i个位置的数据的过程。

（1）然后将从位置i到表尾的所有数据元素依次向前移一个存储位置。（3分） （2）表长度减1. （2分）

9. 请描述在一个单链表中插入一个数据q的插入过程。

（1）找到将插入数据位置的前一个结点p; （1分） （2）q的next值等于p的next值;（2分） （3）p的next值等于q；（2分）

10. 请描述从一个单链表中删除一个数据的删除过程。

（1）找到将被删除数据的前一个结点p; （2分） （2）p的next指针指向被删除数据的后一个结点；（2分） （3）将被删除数据原来的next指针指向null; （1分）

第三章 栈和队列

1. 请简述线性表、栈和队列三者之间的联系。（简单）

（1）线性表、栈和队列都属于线性结构。（2分）

（2）栈和队列都是特殊的线性表，并且都有顺序存储、链式存储两种存储方式。（1分） （3）栈是一种先进后出的线性表，队列是一种先进先出的线性表（2分）

2. 在计算机进行运算时，需要把十进制转换为二进制。请问答：这种数制转换

可以借助于哪种数据结构实现、及原因。

答:栈。（2分） 原因：（3分）

在进行数值转换时，其实质是求余的过程，并且余数的倒序序列正是所求结果。 栈是一种先进后出的线性结构，能够满足这种操作。

3. 有一字符序列abcde依次按照某一线性结构存储，请回答以下问题：

（1）、如果该线性结构是队列，那么，写出出队序列。 （2）、如果该线性结构是栈，那么，输出序列可能是d,c,e,a,b吗，为什么？ （3）、如果该线性结构是栈，且输出序列是abcde。请写出操作过程。（push (x)：表示把x压入栈内；pop (x)：表示把x弹出栈） 答：