《计算机专业基础综合数据结构》由会员分享，可在线阅读，更多相关《计算机专业基础综合数据结构（8页珍藏版）》请在金锄头文库上搜索。
1、计算机专业基础综合数据结构(线性表)-试卷 1(总分：72.00，做题时间：90 分钟)一、 单项选择题(总题数：21，分数：42.00)1. 单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。2. 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算 时间的存储方式是( )。A. 单链表B. 带有头指针的单循环链表C. 双链表D. 带有尾指针的单循环链表丿 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环 链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其
2、时间性能是0(1)，所以答 案是 D。3已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的 时间复杂度是( )。A. 0(l)B. 0(ls)C. 0(min(l， s)D. 0(max(l，s)丿在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。4. 线性表中存放的主要是( )。A. 整型常量B. 字符C. 数据元素丿D. 信息元素 线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有 的数据元素的类型必须相同。5下面的叙述中正确的是()。I线性表在链式存储时，查找第i个
3、元素的时间同i的值成正比II.线 性表在链式存储时，查找第i个元素的时间同i的值无关III线性表在顺序存储时，查找第i个元素的时 间同 i 的值成正比A. 仅I丿B. 仅 IIC. 仅IIID. I、I、I在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元 素的时间与i的位置无关。6. 对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( ) 存储方式最节省时间。A. 顺序表丿B. 双链表C. 带头结点的双循环链表D. 单循环链表 线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表
4、不利于 插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。7若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式中最节省时间的是()。A. 单链表B. 双链表C. 单循环链表D. 顺序表丿本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下： (1)顺序表可以实现随机存取，其时间复杂度为0(1)。但在顺序表中，进行插入和删除操作需要移动大量 的元素，其时间复杂度为0(n)；(2)链表中只能实现顺序查找，其时间复杂度为0(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为0(1)。
5、本题中，线性表中常用的操作是 取第i个元素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第i个元素的前驱也很方便。 单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便：双链表虽然能快速查找第i 个元素的前驱，但不能实现随机存取。8. 如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式 最节省运算时间。A. 单链表B. 仅有头指针的单循环链表C. 双链表D. 仅有尾指针的单循环链表丿 最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。9. 算法的时间复杂度取决于( )。A. 问题的规模B. 待处
6、理数据的初态C. A和B 丿D. 以上都不正确 此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初 态，所以选 C。 A 和 B 都不全面。10. 关于链表的特点，下面的叙述中不正确的是( )。A. 插入、删除运算方便B. 可实现随机访问任一元素丿C. 不必事先估计存储空间D. 所需空间与线性长度成正比 链表的特点包括：事先不需要申请存储空间，插入和删除运算方便，但不能实现随机存取。11. 设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是()。A. 删除指定元素丿B. 在最后一个元素的后面插入一个新元素C. 顺序输出前
7、k 个元素D. 交换第i个元素和第2ni-1个元素的值(i=0, 1,，n1)对于A,删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素， 因此单链表的效率要高一些。对于B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的 效率和单链表相同。对于C，顺序输出前k个元素，单链表和顺序表的效率几乎相同。对于D，交换第i 个元素和第2ni 一 1个元素的值(i=0, 1，n 1)，由于顺序表可以实现随机查找，因此顺序表的效 率会更高一些。12. 下面的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填入( )。 voidreverse(point
8、er 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=() ； A. hB. PC. q 丿D. q 一nexth 一next=q；表示将当前结点作为头结点后的第一元素结点插入。13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1 WiWn+1)。A. O(0)B. O(1)C. O(n)丿D. O(n 2 ) 此题考查的知识点是线性表基本操作的时间复杂度。顺序存储的线性表插入
9、元素时需要从插入位置开始向 后移动元素，腾出位置以便插入，平均移动次数为(n+1)/2，所以复杂度为0(n),选C。14. 线性表(a ，a ，a )以链式存储方式存储时，访问第i位置元素的时间复杂度为()。12nA. O(i)B. O(1)C. O(n)丿D. O(i 一 1)此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第i个位置的元素时需要从头 开始向后查找，平均查找次数为(n+1)/2，所以时间复杂度为0(n),选C。15. 非空的循环单链表head的尾结点P满足()。A. p next=head 丿B. p 一next=NULLC. p=NULLD. p=head
10、此题考查的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选AB、 C、D 均不能构成非空的循环单链表。16. 双向链表中有两个指针域，即prior和next，分别指向前驱及后继，设P指向链表中的一个结点，q指 向一个待插入结点，现要求在P前插入q，则正确的插入为()。A. P 一prior=q； q 一next=P； p 一prior next=q； q 一prior=p prior；丿B. q 一prior=p 一prior； p 一 prior 一next=q； q 一next=P； p 一prior=q；C. q 一 next=P； p 一 next=q；
11、p 一 prior 一next=q； q 一 next=P；D. p 一 prior 一 next=q； q 一 next=P； q 一 prior=p 一 prior； p 一 prior=q；此题考查的知识点是双向链表的插入操作。在p前插入，要修改p的prior指针、p的prior所指结点的 next指针，所以选A。B、C、D都将使地址丢失，连接失败。17. 静态链表中指针表示的是( )。A. 内存地址B. 数组下标C. 下一元素数组下标丿D. 左、右孩子地址 静态链表中指针表示的是下一元素的数组下标。18. 在单链表指针为P的结点之后插入指针为s的结点，正确的操作是()。A. p nex
12、t二s； s 一next二p next；B. s next二p next； p 一next二s； VC. p next二s； p 一next二s next；D. p next二s next； p 一next二s；此题考查的知识点是单链表的插入操作。要先保存p的后继结点，再连入s结点，所以选B。A、C、D都将 使地址丢失，连接失败。19. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是()。A. head=NULLB. head 一next=NULL VC. head-next=headD. head!=NULL此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候
13、表示只有一个结点存在，但没有存信息。所以选B。A表示没有结点，C表示循环单链表，D表示有一个指针不为空，所以都不对。20. 以下与数据的存储结构无关的术语是( )。A. 循环队列B. 链表C. 哈希表D. 栈丿此题考查的知识点是对数据结构和存储结构的理解。A、B、C描述的均为物理结构即数据的存储结构，D是 逻辑结构，所以选D。21. 以下数据结构中， ( )是线性数据结构。A. 广义表B. 二叉树C. 稀疏矩阵D. 串丿 此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而 A、B、C有多个后继，均错，所以选D。二、 综合应用题(总题数：15，分数：30
14、.00)22. 综合应用题41-47 小题。23有两个集合A和B,利用带头结点链表表示，设头指针分别为la和lb。两集合的链表元素皆为递增有 序。设计一个算法，将A与B合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空 间，只能在A和B的原有结点空间上完成。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采 用c或C+或Java语言描述算法，关键之处给出注释。(3)分别给出算法各部分的时间复杂度。正确答案：(正确答案：(1)算法的基本设计思想：分别从A、B的头结点开始，依次比较A、B中元素的内 容，如果A中的元素值大于B中的元素值，则将B中的结点插入结果链表，反之将A中
15、的结点插入结果链 表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果A、B中两个元素值 相同，只将其中的一个加入结果链表。(2)算法的设计如下： typedef structLNode int data： structLNode * next：* Linkedlist； LinkedList Union(LinkedList la， lb) pa=la next； pb=lb 一next；/设工作指针pa和pb pc=la；/ pc为结果链表当前结点的前驱指针while(pa&pb)if(pa一 datanext； else /处理 pa 一data=pb data, pc一 next=pa； pc=pa； p
