- 单项选择题
1．算法必须具备的三个特性是( B )。
A．可执行性、可移植性、可扩充性
B．可执行性、确定性、有穷性
C．确定性、有穷性、稳定性
D．易读性、稳定性、安全性
2．下列数据中，( C )是非线性数据结构。
A．栈
B．队列
C．完全二叉树
D．顺序表
3．算法分析的两个方面是( A )。
A．空间复杂度和时间复杂度
B．正确性和简明性
C．可读性和文档性
D．数据复杂性和程序复杂性
4．非空的循环单链表head的尾结点p满足( A )。
A．p->next==head
B．p->next==NULL
C．p==NULL
D．p==head
5．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是( B )。
A．p->next=s;s->next=p->next;
B．s->next=p->next;p->next=s;
C．p->next=s;p->next=s->next;
D．p->next=s->next;p->next=s;
6．按照二叉树的定义，具有3个结点的二叉树有( C )种。
A．3
B．4
C．5
D．6
7．在一个有向图中，所有顶点的入度之和是所有顶点的出度之和的( B )倍。
A．1/2 B．1
C．2 D．4
8．二叉排序树是( B )。
A．每一分支结点的度均为2的二叉树（错误）
解析：【二叉树是度数最大为2的树，不是度数就是2的树，可能二叉树只有一个子树或者没有子树，那么这时二叉树度数为1或者0】
B．中序遍历得到一升序序列的二叉树
C．按从左到右顺序编号的二叉树
D．每一分支结点的值均小于左子树上所有结点的值，大于右子树上所有结点的值
9．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是( C )。
A．1和 5
B．2和4
C．4和2
D．5和1
10．下列说法中正确的是( D )。
A．堆栈是在两端操作、先进后出的线性表
B．堆栈是在一端操作、先进先出的线性表
C．队列是在一端操作、先进先出的线性表
D．队列是在两端操作、先进先出的线性表
11．不带头结点的单链表head为空的判定条件是( A )。
A．head==NULL
B．head->next==NULL
C．head->next==head
D．head!=NULL
12．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( D )。
A．M1
B．M1+M2
C．M3
D．M2+M3
13．具有10个叶结点的二叉树中有( B )个度为2的结点。
A．8
B．9
C．10
D．ll
14．有n个叶子的哈夫曼树的结点总数为( D )。
A．不确定
B．2n
C．2n+1
D．2n-1
15．利用二叉链表存储树，则根结点的右指针是( C )。
A．指向最左孩子
B．指向最右孩子
C．空
D．非空
16．要连通具有n个顶点的无向图，至少需要( A )条边。
A．n-l
B．n
C．n+l
D．2n
17．对线性表进行二分查找时，要求线性表必须( C )。
A．以顺序方式存储
B．以链式方式存储
C．以顺序方式存储，且结点关键字有序排列。
D．以链式方式存储，且结点关键字有序排列。
18．静态查找表与动态查找表的根本区别在于( C )。
A．它们的逻辑结构不同
B．施加在其上的操作不同
C．所包含的数据元素类型不同
D．存储实现不一样
19．一个有n个顶点的有向图最多有( D )条边。
A．n
B．n(n-1)
C．2n
D．n(n-1)/2
- 从逻辑结构上可以把数据结构分为 ( C )。
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
C、线性结构和非线性结构
D、内部结构和外部结构
21.在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）之前插入一个新元素时，需要从后向前依次后移 ( B )个元素。
A、n-i
B、n-i+1
C、n-i-1
D、i
22.链表结构不具有下列（ B ）特点。
A、插入和删除无需移动元素
B、可随机访问链表中的任意元素
C、无需实现分配存储空间
D、所需空间与结点个数成正比。
23.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ C ）
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;
24.一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【 C 】
A、54321
B、45321
C、43512
D、12345
25、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。
A、Q->rear – Q->front = M B、Q->rear – Q->front -1 ==M
C、Q->rear == Q->front D、Q->rear + 1 == Q->front
26、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】
A、r->next = s; r=s; B、f->next = s; f=s;
C、s->next = r; r=s; D、s->next = f; f=s;
27、深度为5的二叉树至多有【 A 】个结点
A、31
B、32
C、16
D、10
解析：
可以看看这里的解释
知识点：
1.`结点：包含一个数据元素及若干指向子树分支的信息。`
2.`结点的度：一个结点拥有子树的数目称为结点的度。`
3.`叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。`
4.`分支结点：也称为非终端结点，度不为零的结点称为非终端结点。`
5.`满二叉树是2^k-1个。`(即2的k次方-1个。)
6.` 完全二叉树最少2^k个,最多2^k-1个。`
7.`如果既不是满二叉树，也不是完全二叉树，那普通二叉树深度为k时的结点数量就是最少k个，最多2^k-1个。`
28、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。
A、只有右子树上的所有结点 B、只有右子树上的部分结点
C、只有左子树上的所有结点 B、只有左子树上的部分结点
29、如果一棵完全二叉树有1001个结点，则其叶子结点个数为【 D 】。
A、250
B、500
C、502
D、490
解析：
深度为9的节点数是511,深度为10的节点数是1023,该树为10层,
最后一层节点是1001-511=490（均是叶子节点）,最后一层490个节点对应的第9层得父节点有245个,第9层节点共有256个节点,所以第9层叶子节点有256-245=11个
总的叶子节点数为490+11=501
30.在一个图中，所有顶点的度数之和是所有边数的【 C 】倍。
A、1/2
B、1
C、2
D、4
31.采用邻接表存储的图的深度优先遍历算法类似于二叉树的【 A 】。
A、先序遍历
B、中序遍历
C、后序遍历
D、按层遍历
网友评论