吉大网院20190903学期《数据结构》课程清考
20190903学期《数据结构》课程清考1.[单选题]按照二叉树的定义,具有3个结点的二叉树有( )种。 (满分:4)
A.3
B.4
C.5
D.6
2.[单选题]若已知一个栈的输入序列为1,2,3,4,……,n，其输出序列p1, p2, …..,pn。若p1＝n,则pi为 (满分:4)
A.i
B.n-i
C.n-i+1
D.不确定
3.[单选题]如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。（ ）就是不稳定的排序方法。 (满分:4)
A.起泡排序
B.归并排序
C.直接插入法排序
D.简单选择排序
4.[单选题]二分查找法要求查找表中各元素的键值必须是()排列。 (满分:4)
A.递增或递减
B.递增
C.递减
D.无序
5.[单选题]数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )排序算法最节省空间。 (满分:4)
A.堆排序
B.希尔排序
C.快速排序
D.直接选择排序
6.[单选题]在单链表中增加头结点的目的是为了( )。 (满分:4)
A.方便运算的实现
B.用于标识单链表
C.使单链表中至少有一个结点
D.用于标识起始结点的位置
7.[单选题]线性链表中各结点之间的地址（ ）。 (满分:4)
A.必须连续
B.一定不连续
C.部分地址必须连续
D.连续与否无所谓
8.[单选题]在一个单链表中，已知(*q)结点是(*p)结点的前驱结点，若在(*q)和(*p)之间插入(*s) 结点,则执行( )。 (满分:4)
A.s->next=p->next ; p->next=s ;
B.p->next=s->next ; s->next=p ;
C.q->next=s ; s->next=p ;
D.p->next=s ; s->next=q ;
9.[单选题]单链表的存储密度（）。 (满分:4)
A.大于1
B.等于1
C.小于1
D.不能确定
10.[单选题]具有n个顶点的有向图最多可包含()条有向边。 (满分:4)
A.n-1
B.n
C.n(n-1)/2
D.n(n-1)
11.[单选题]邻接表的存储结构下图的广度优先遍历类似于二叉树（树）的()。 (满分:4)
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历
12.[单选题]用分划交换排序方法对包含有n个关键的序列进行排序，最坏情况下执行的时间杂度为()。 (满分:4)
A.O(n)
B.O(log2n)
C.O(nlog2n)
D.O(n2)
13.[单选题]下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是( )。 (满分:4)
A.归并排序
B.直接插入排序
C.快速排序
D.冒泡排序
14.[单选题]在一个具有n个顶点的无向图中,要连通全部顶点至少需要( )边。 (满分:4)
A.n
B.n+1
C.n-1
D.n/2
15.[单选题]不带头结点的单链表head为空的判断条件是( )。 (满分:4)
A.head==NULL
B.head->next==NULL
C.head->next==head
D..head!=NULL
16.[单选题]使具有9个顶点的无向图成为一个连通图至少应有边的条数是（）。 (满分:4)
A.6
B.8
C.5
D.4
17.[单选题]对有n个记录的表按记录键值有序建立二叉排序树，在这种情况下，其平均查找长度的量级为（ ）。 (满分:4)
A.O(n)
B.O(nlog2n)
C.O(1)
D.O(log2n)
18.[单选题]某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。 (满分:4)
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
19.[单选题]若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。（1≦i ≦n+1） (满分:4)
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
20.[单选题]栈和队列都是（ ） (满分:4)
A.顺序存储的线性表
B.链式存储的线性表
C.限制存取点的线性结构
D.限制存取点的非线性结构
21.[单选题]设输入序列为1,2,3,4,5，借助一个栈可以得到的输出序列是( )。 (满分:4)
A.2,4,1,3,5
B.3,4,1,5,2
C.3,2,4,1,5
D.4,1,3,2,5
22.[单选题]任何一个无向连通图的最小生成树( )。 (满分:4)
A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.可能不存在
23.[单选题]某数组第一个元素的存储地址为200，每个元素的长度为4，则第五个元素的地址是（ ）。 (满分:4)
A.210
B.208
C.216
D.220
24.[单选题]若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省空间。 (满分:4)
A.单链表
B.双链表
C.带头结点的双循环链表
D.单循环链表
25.[单选题]当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为()。 (满分:4)
A.n2
B.nlog2n
C.log2n
D.n-1
页:
[1]