计算机专业基础综合数据结构（线性表）模拟试卷1
单选题
1.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。(D)
A. 单链表
B. 带有头指针的单循环链表
C. 双链表
D. 带有尾指针的单循环链表
解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。
2.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。(D)
A. O(l)
B. O(ls)
C. O(min(l，s))
D. O(max(l，s))
解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。
3.线性表中存放的主要是( )。(C)
A. 整型常量
B. 字符
C. 数据元素
D. 信息元素
解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。
4.下面的叙述中正确的是( )。
I．线性表在链式存储时，查找第i个元素的时间同i的值成正比
Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关
Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比(A)
A. 仅I
B. 仅Ⅱ
C. 仅Ⅲ
D. I、Ⅱ、Ⅲ
解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。
5.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。(A)
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
解析：线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。
6.若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式中最节省时间的是( )。(D)
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
解析：本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下：
(1)顺序表可以实现随机存取，其时间复杂度为O(1)。但在顺序表中，进行插入和删除操作需要移动大量的元素，其时间复杂度为O(n)；
(2)链表中只能实现顺序查找，其时间复杂度为O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为O(1)。
本题中，线性表中常用的操作是取第i个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第i个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便：双链表虽然能快速查找第i个元素的前驱，但不能实现随机存取。
7.如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( )存储方式最节省运算时间。(D)
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
解析：最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。
8.算法的时间复杂度取决于( )。(C)
A. 问题的规模
B. 待处理数据的初态
C. A和B
D. 以上都不正确
解析：此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选C。A和B都不全面。
9.关于链表的特点，下面的叙述中不正确的是( )。(B)
A. 插入、删除运算方便
B. 可实现随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
解析：链表的特点包括：事先不需要申请存储空间，插入和删除运算方便，但不能实现随机存取。
10.设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是( )。(A)
A. 删除指定元素
B. 在最后一个元素的后面插入一个新元素
C. 顺序输出前k个元素
D. 交换第i个元素和第2n—i-1个元素的值(i=0，1，…，n—1)
解析：对于A，删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。
对于B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。
对于C，顺序输出前k个元素，单链表和顺序表的效率几乎相同。
对于D，交换第i个元素和第2n—i一1个元素的值(i=0，1，…，n一1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。
11.下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。
void reverse(pointer h){ ／／h为附加头结点指针
pointer p，q；
P=h一＞next；h一＞next=NULL；
while(P|=null){
q=P：
P=P一＞next：
q一＞next=h一＞next；
h一＞next=(_____)；
}
}(C)
A. h
B. P
C. q
D. q一＞next
本文档预览：3000字符，共20455字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
