计算机专业基础综合（数据结构）模拟试卷28
单选题
1.以下属于逻辑结构的是( )。(C)
A. 顺序表
B. 哈希表
C. 有序表
D. 单链表
解析：数据结构分别为逻辑结构、存储结构(物理结构)和数据的运算。数据的逻辑结构是对数据之间关系的描述，与数据元素本身的形式、内容、相对位置、所含结点个数都无关。顺序表、哈希表、单链表都涉及到数据的存储结构，有序表是指表中数据有序，与逻辑结构无关。
2.某算法的时间复杂度为O(n2)，表明该算法的( )。(C)
A. 问题规模是n2
B. 执行时间等于n2
C. 执行时间与n2成正比
D. 问题规模与n2成正比
解析：T(n)=O(n2)表示T(n)=m×n2(m为正常量)，其问题规模仍为n而不是n2
注意：算法时间复杂度是问题规模n的函数，记为T(n)=O(f(n))，表示T(n)=cf(n)，其中c为正常量，所以，T(n)的增长率与f(n)的增长率相同。
3.将两个长度为N的有序表归并到一个长度为2N的有序表，最少需要比较的次数是( )，最多需要比较的次数是( )。(A)
A. N，2N-1
B. N-1，2N
C. N，2N
D. N-1，2N-1
解析：对于此题而言最少的比较次数是，其中一个有序表的最后一个数小于另一表的的第一个数，那么直接合并即可。当一个表递增一个表递减且递减表时，需要比较ZN-1次。
4.在一个长度为n(n＞1)的带头结点单链表h上，另设有尾指针r(指向尾结点)。与链表的长度有关的操作是( )。(B)
A. 删除单链表中的第一个元素
B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素
解析：在单链表中要删除最后一个元素必须找到尾结点的前驱结点的指针。由于单链表只能访问结点的下一个结点，所以根据尾指针不能够直接找到它的前驱结点，只有从头开始依次向下找到尾结点的前驱结点。所以删除单链表中的最后一个元素与链表的长度有关。
5.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是( )。(C)
A. 5，4，3，2，1
B. 4，5，3，2，1
C. 4，3，5，1，2
D. 1，2，3，4，5
解析：存在一种操作序列——“进栈、出栈、进栈、出栈……”——可以使数据通过栈后仍然保持次序不变。一串数据通过一个栈后的次序由每个数据之间的进栈、出栈操作序列决定，只有当所有数据“全部进栈后再全部出栈”才能使数据倒置。
6.栈在( )中应用。(D)
A. 递归调用
B. 子程序调用
C. 表达式求值
D. A，B，C
解析：栈的特点是先入后出。A项，递归调用的特点是最外层的调用最后执行，最内层的调用最先执行，递归调用符合栈的特点，即先将外层的调用依次入栈，然后从最内层调用出栈执行；B项，子程序的调用与递归调用的特点类似；C项，表达式求值将数据入栈，遇到运算符时与栈顶的运算符比较优先级，级别高则数据出栈，进行运算。
7.具有5个叶子结点的二叉树中，度为2的结点的个数为( )(A)
A. 4
B. 6
C. 5
D. 不确定
解析：二叉树的性质1：非空二叉树上叶结点数等于双分支结点数加1。因此度为2的结点的个数为5-1=4。
8.中缀表达式A-(B+C／D)*E的后缀形式是( )。(D)
A. AB-C+D／E*
B. ABC+D／-E*
C. ABCD／E*+-
D. ABCD／+E*-
解析：将中缀表达式表示成二叉树的形状，则这棵二叉树的后序遍历序列即为表达式的后缀形式。
9.线索化的二叉树中，某结点*p没有孩子的充要条件是( )。(B)
A. p-＞lchild=NULL
B. p-＞ltag=|&&p-＞rtag=1
C. p-＞ltag=0
D. p-＞lchild=NULL&&p-＞ltag=1
解析：考查线索二叉树。
10.下列二叉排序树中，满足平衡二叉树定义的是( )。
(B)
A.
B.
C.
D.
解析：平衡二叉树是平衡二又排序树的简称。它或者是一棵空树，或者是具有下列性质的二叉树：
①左、右子树的高度之差不超过1；
②左、右子树也是平衡二叉树。
11.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有( )个结点。(D)
A. 13
B. 12
C. 26
D. 25
解析：哈夫曼树的特点：具有n个叶子结点的哈夫曼树共有2×n-1个结点。
12.要连通具有n个顶点的有向图，至少需要( )条边。(B)
A. n-1
B. n
C. n+1
D. 2n
解析：n个顶点的有向图若连通，至少保证每个项点都有一条边连通它，所以至少需要n条边。
13.判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用( )。(D)
A. 求关键路径的方法
B. 求最短路径的 Dijkstra方法
C. 广度优先遍历算法
D. 深入度优先遍历算法
解析
本文档预览：3000字符，共6970字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
