数据结构题库
一、填空题
1.在双链表中要删除已知结点*s，其时间复杂度为 O(1) 。
2.在任何一棵二叉树中，度为0的结点n0和度为2的结点n2之间的关系是 n0=n2+1 。
3.已知完全二叉树的第4层有4个结点，则其叶子结点数是 6 。
4.在仅有尾指针rear指示的单循环链表rear中，在表尾插入一个结点s的语句序列是 s->next=rear->next;rear->next=s 。
5.栈顶的位置是随着 入栈出栈 操作而变化的。
6.数据结构一般包括三个方面的内容：数据的逻辑结构、数据的存储结构及对数据的运算。
7.数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。
8.在带头结点的双链表head中，指针p所指结点是开始结点的条件是p->prior==head。
9.在选择排序、堆排序、快速排序、直接插入排序中，稳定的排序方法是直接插入排序。
10.在具有n个结点的双链表中做插入、删除运算，平均时间复杂度为O(n)。
11.队列的队尾位置随着入队而变化。
12.快速排序在最坏情况下的时间复杂度是O(n2)。
13.n ( n > 0 )个顶点连通无向图的生成树恰有n-1条边。
14.在一个长度为n的顺序表中第i个元素（1 ≤ i ≤ n+1）之前插入一个元素时，需向后移动n-i+1个元素。
15.用数组A[m]来存放循环队列q的元素，且它的头、尾指针分别为front和rear，队列满足条件(q->rear+1)%m==q->front,则队列中当前的元素个数为m-1。
16.一个二叉树中，度为2的结点有3个，则叶结点有4个。
17.顺序栈s存储在数组s->data[max]中，对s进行出栈操作，执行的语句序列是x=s->data[s->top];s->top--;。
18.二叉树通常有顺序存储结构和链式存储结构两种。
19.二叉树在二叉链表表示方式下，p指向二叉树的根结点，经运算s=p；while(s->rchild) s=s->rchild后，s指针指向右子树最右结点。
2、在具有n个结点的二叉链表中，有 n+1 个空链域。
3、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个 对称 矩阵。
4、在n个顶点的无向完全图中，应有 n(n-1)/2 条边，在n个顶点的有向完全图中，应有 n(n-1) 条边。
5、在快速排序、堆排序、归并排序中， 归并 排序是稳定的。
6、设一棵完全二叉树128个结点，则该完全二叉树的深度为 8 ，有 64
个叶子结点。
7、设指针变量p指向单链表中结点A，则删除结点A的语句序列为：
q=p->next；p->data=q->data；p->next= q->next ；feee(q)；
二、选择题
1.下列算法的时间复杂度是（ B ）。
for(i=1;i<=n;i+ +)
c[i]=i；
A、O（1） B、O（n） C、O（log2n） D、O（nlog2n）
2.在表长为n的顺序表上做插入运算，平均要移动的结点数为（ B ）。
A、n B、n/2 C、n/3 D、n/4
3.在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ A ）。
A、S->next=P->next；P->next=S；
B、P->next=S->next；S->next=P；
C、P->next=P；P->next=S；
D、P->next=S；S->next=P；
4.在具有m个结点的完全二叉树中，结点i（i>1）的父结点是（ D ）。
A、2i B、不存在 C、2i+1 D、⌊ i/2⌋
5.在一个具有k个结点的无向图中，要连通全部结点至少需要（ C ）。
A、k条边 B、k+1条边 C、k-1条边 D、k/2条边
6.最小生成树指的是（ C ）。
A、由连通图所得到的边数最少的生成树
B、由连通图所得到的顶点相对较少的生成树
C、连通图的所有生成树中权值之和最小的生成树
D、连通图的极小连通子图
7.二叉排序树中，关键字值最大的结点（ D ）。
A、左指针一定为空 B、右指针一定为空
C、左、右指针均为空 D、左、右指针均不为空
8.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ D ）。
A、索引存储方法 B、顺序存储方法
C、链式存储方法 D、散列存储方法
9.有n个叶结点的哈夫曼树所具有的结点数为（ D ）。
A、n B、n+1 C、2n D、2n - 1
10.图的广度优先搜索遍历类似于树的（ D ）。
A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历
11.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）。
A、1/2倍 B、1倍 C、2倍 D、4倍
12.对n个不同的排序码进行冒泡排序，在元素无序情况下的比较次数为（ D ）。
A、n + 1 B、n C、n - 1 D、n（n - 1）/2
13.链栈与顺序栈相比，比较明显的优点是（ D ）。
A、插入操作更加方便 B、删除操作更加方便
C、不会出现下溢的情况 D、不会出现上溢的情况
14.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ C ）。
A、顺序表 B、用头指针表示的单循环链表
C、用尾指针表示的单循环链表 D、单链表
15.线性表是（ A ）。
A、一个有限序列，可以为空 B、一个有限序列，不能为空
C、一个无限序列，可以为空 D、一个无限序列，不能为空
16.在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ B ）。
26. 线性表采用链式存储时，结点的地址（ C ）。
A、必须是连续的 B、必须是不连续的
C、连续与否均可 D、必须有相等的间隔
27. 栈与一般线性表的区别主要在（ D ）。
A、元素个数 B、元素类型 C、逻辑结构 D、插入、删除元素的位置
28. 从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为（ A ）。
A、选择排序 B、插入排序 C、快速排序 D、冒泡排序
29. 若m个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个（ B ）。
A、一般矩阵 B、对称矩阵 C、对角矩阵 D、稀疏矩阵
32. 在单链表中，增加头结点的目的是（ C ）。
A、使单链表至少有一结点 B、标志表中首结点位置
C、方便运算的实现 D、说明单链表是线性表的链式存储实现
35. 在一棵具有5层的满二叉树中，结点总数为（ A ）。
A、31 B、32 C、33 D、16
36. 带头结点的单链表head为空的判定条件是（ B ）。
A、head = NULL； B、head - > next = NULL；
C、head - > next = head； D、head ! = NULL；
38. 在一个具有m个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ B ）。
A、O（1） B、O（m） C、O（m2） D、O（log2m）
39. 对线性表进行二分查时，要求线性表必须（ B ）。
先序中序后序遍历二叉树A、以顺序方式存储 B、以顺序方式存储且元素有序
C、以链接方式存储 D、以链接方式存储且元素有序
40. 在一棵二叉树中，第5层上的结点数最多为（ C ）。
A、8 B、15 C、16 D、32
41. 在下列排序方法中，不稳定的排序方法是（ B ）。
A、直接插入排序 B、直接选择排序 C、冒泡排序 D、归并排序
42. 快速排序在（ C ）情况下最易发挥其长处。
A、被排序的数据中含有多个相同排序码
B、被排序的数据已基本有序
C、被排序的数据完全无序
D、被排序的数据中的最大值和最小值相差悬殊
44. 下列有关线性表的叙述中，正确的是（ A ）。
A、线性表中的元素之间是线性关系
B、线性表中至少有一个元素
C、线性表中任何一个元素有且仅有一个直接前趋
D、线性表中任何一个元素有且仅有一个直接后继
46. 由二叉树的（ B）遍历，可以惟一确定一棵二叉树。
A、前序和后序 B、前序和中序 C、后序 D、中序
47. 用（ B ）方法遍历一棵二叉排序树，可以得到各结点键值的递增序列。
A、先根遍历 B、中根遍历 C、层次遍历 D、后根遍历
48. 对于一个栈，给定输入序列为1，2，3，则下列不可能为输出序列的是（ C ）。
A、1，2，3 B、3，2，1 C、3，1，2 D、2，1，3
49. 在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，它指向该结点的（ B ）。
A、直接前趋 B、直接后继 C、开始结点 D、终端结点
50. 在链接队列中执行入队操作（ D ）。
A、需判别队列是否为空 B、需判别队列是否为满
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论