2024知到答案 数据结构与程序设计（北京航空航天大学） 最新智慧树满分章节测试答案
绪论 单元测试
1、单选题：
设n是描述问题规模的非负整数，下列程序片段的时间复杂度是（ ）x=2；while(x<n/2)x=2*x;
选项：
A:0(nlog2n)
B:O(n)
C:0(n2)
D:O(1og2n)
答案: 【O(1og2n)】
第一章 单元测试
1、单选题：
在一个单向循环链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改 （ ）个指针域的值。
选项：
A:3
B:1
C:4
D:2
答案: 【2】
2、单选题：
在一个以 h 为头节点的单循环链表中，p 指针指向链尾节点的条件是 （ ）。
选项：
A:p->next == h
B:p->next->next == h
C:p->next == NULL
D:p->data == -1
答案: 【p->next == h】
3、单选题：
下面说法错误的是（ ）
选项：
A:数据元素之间具有的逻辑关系为线性关系的数据元素集合称为线性表。
B:线性表采用顺序存储结构时，读取其中某个位置的元素的时间复杂度为O(1)。
C:线性关系是指：除了第一个元素与最后一个元素外，元素序列中任何一个元素有且仅有一个直接前驱元素, 并且有且仅有一个直接后继元素。
D:线性表的有序性是指其中的数据元素是按照由小到大或由大到小的顺序排列的。
答案: 【线性表的有序性是指其中的数据元素是按照由小到大或由大到小的顺序排列的。】
4、单选题：
在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较 （ ）个链结点。
选项：
A:(n-1)/2
B:n
C:(n+1)/2
D:n/2
答案: 【(n+1)/2】
5、单选题：
下面关于线性表的叙述中，错误的是哪一个？（ ）
选项：
A:线性表采用顺序存储，便于进行插入和删除操作。
B:线性表采用链接存储，不必占用一片连续的存储单元。
C:线性表采用链接存储，便于插入和删除操作。
D:线性表采用顺序存储，必须占用一片连续的存储单元。
答案: 【线性表采用顺序存储，便于进行插入和删除操作。】
第二章 单元测试
1、单选题：
栈和队都是 （ ）
选项：
A:限制存取点的线性结构
B:链式存储的非线性结构
C:限制存取点的非线性结构
D:顺序存储的线性结构
答案: 【限制存取点的线性结构】
2、单选题：
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是 （ ）。
选项：
A:2
B:4
C:6
D:3
答案: 【3】
3、单选题：
设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是 （ ）
选项：
A:4 5 1 3 2
B:3 2 1 5 4
C:4 3 1 2 5
D:5 1 2 3 4
答案: 【3 2 1 5 4】
4、单选题：
一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。
选项：
A:edcba
B:dceab
C:decba
D:abcde
答案: 【dceab】
5、单选题：
中缀表达式A-(B+C/D)×E的后缀形式是（ ）。
选项：
A:AB-C+D/E×
B:ABC-+D/E×
C:ABC+D/ ×E-
D:ABCD/+E×-
答案: 【ABCD/+E×-】