数据结构C语言及解答.doc

第二章 习题与解答 一 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 二 单选题 请从下列A，B，C，D选项中选择一项 1．线性表是 。 A 一个有限序列，可以为空； B 一个有限序列，不能为空； C 一个无限序列，可以为空； D 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ ）个元素。 A n/2 B n+1/2 C n -1/2 D n 3．线性表采用链式存储时，其地址 。 A 必须是连续的； B 部分地址必须是连续的； C 一定是不连续的； D 连续与否均可以。 4．用链表表示线性表的优点是（ ）。 A 便于随机存取 B 花费的存储空间较顺序存储少 C 便于插入和删除 D 数据元素的物理顺序与逻辑顺序相同 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用 存储方式最节省运算时间。 A 单链表 B 双链表 C 单循环链表 D 带头结点的双循环链表 循环链表的主要优点是 。 A 不在需要头指针了 B 已知某个结点的位置后，能够容易找到他的直接前趋 C 在进行插入、删除运算时，能更好的保证链表不断开 D 从表中的任意结点出发都能扫描到整个链表 下面关于线性表的叙述错误的是 。 线性表采用顺序存储，必须占用一片地址连续的单元； 线性表采用顺序存储，便于进行插入和删除操作； 线性表采用链式存储，不必占用一片地址连续的单元； 线性表采用链式存储，不便于进行插入和删除操作； 单链表中，增加一个头结点的目的是为了（　）。 A 使单链表至少有一个结点 B 标识表结点中首结点的位置 （C）方便运算的实现 D 说明单链表是线性表的链式存储 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A 单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾指针的单循环链表 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（ ）。 A 单链表 B 顺序表 C 双链表 D 单循环链表 三 填空题 1．带头结点的单链表H为空的条件是__________________。 非空单循环链表L中*p是尾结点的条件是__________________。 3．在一个单链表中p所指结点之后插入一个由指针f所指结点，应执行s- next ________;和p- next _____________的操作。 4．在一个单链表中p所指结点之前插入一个由指针f所指结点，可执行以下操作： s- next ________; p- next s; t p- data; p- data ___________; s- data ___________; 5．在顺序表中做插入操作时首先检查_________________。 四 算法设计题 设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。 编写一个函数，从一给定的顺序表A中删除值在x~y x y 之间的所有元素，要求以较高的效率来实现。 提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。 线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54） 线性表用顺