一、单选题（共 30 道试题，共 60 分。）V
1. 设完全无向图中有n个顶点，则该完全无向图中有（）条边。
A. n(n-1)/2
B. n(n-1)
C. n(n+1)/2
D. (n-1)/2
满分：2 分
2. 在一棵具有5层的满二叉树中结点数为（）
A. 31
B. 32
C. 33
D. 16
满分：2 分
3. 设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。
A. 1
B. 2
C. 3
D. 4
满分：2 分
4. 设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。
A. 5
B. 6
C. 7
D. 8
满分：2 分
5. 树最适合用来表示（）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：2 分
6. 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A. n-i
B. n+l-i
C. n-1-i
D. i
满分：2 分
7. 若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）
A. O（1）
B. O（n）
C. O（n^2)
D. O（n^3）
满分：2 分
8. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为（）
A. A[1]，A[2]，A[3]，A[4]
B. A[1]，A[14]，A[7]，A[4]
C. A[7]，A[3]，A[5]，A[4]
D. A[7]，A[5]，A[3]，A[4]
满分：2 分
9. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
A. N0=N1+1
B. N0=Nl+N2
C. N0=N2+1
D. N0=2N1+l
满分：2 分
10. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）
A. 直接选择排序
B. 直接插入排序
C. 快速排序
D. 起泡排序
满分：2 分
11. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
A. 9
B. 10
C. 11
D. 12
满分：2 分
12. 在二叉排序树中插入一个结点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(log2n)
D. O(n)
满分：2 分
13. 设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
满分：2 分
14. 设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
满分：2 分
15. 设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
A. n-1
B. n
C. n+1
D. 2n-1
满分：2 分
16. 以下数据结构中哪一个是非线性结构？（）
A. 队列
B. 栈
C. 线性表
D. 二叉树
满分：2 分
17. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。
A. q=p->next；p->data=q->data；p->next=q->next；free(q)；
B. q=p->next；q->data=p->data；p->next=q->next；free(q)；
C. q=p->next；p->next=q->next；free(q)；
D. q=p->next；p->data=q->data；free(q)；
满分：2 分
18. 设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。
A. 20
B. 256
C. 512
D. 1024
满分：2 分
19. 下面关于线性表的叙述错误的是（）。
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
满分：2 分
20. 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。
A. 1
B. 2
C. 3
D. 4
满分：2 分
21. 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。
A. 堆排序
B. 冒泡排序
C. 快速排序
D. 希尔排序
满分：2 分
22. 用链接方式存储的队列，在进行插入运算时（）.
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
满分：2 分
23. 队列是一种（）的线性表。
A. 先进先出
B. 先进后出
C. 只能插入
D. 只能删除
满分：2 分
24. 下列程序段的时间复杂度为（）。i=0，s=0；while(s<n){s=s+i；i++；}
A. O(n)
B. O(n)
C. O(n)
D. O(n)
满分：2 分
25. 下列四种排序中（）的空间复杂度最大。
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
满分：2 分
26. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）
A. front=front+1
B. front=(front+1)%(m-1)
C. front=(front-1)%m
D. front=(front+1)%m
满分：2 分
27. 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。
A. 6
B. 11
C. 5
D. 6.5
满分：2 分
28. 栈和队列的共同特点是（）。
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
满分：2 分
29. 设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
A. 99
B. 100
C. 101
D. 102
满分：2 分
30. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。
A. 1，2，3，4
B. 2，3，4，1
C. 1，4，2，3
D. 1，2，4，3
满分：2 分
发表于 2017-5-7 11:36:04
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
收藏