数据结构单选题57道（含答案与解析）｜逻辑结构/线性表/栈队列/树/图/查找/排序
练习一 单选题
1. 数据结构中，与所使用的计算机无关的是数据的（ ）。D
A. 存储结构 B. 物理和存储结构
C. 物理结构 D. 逻辑结构
2．在数据结构中，从逻辑上可以把数据结构分为（ ）。D
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.内部结构和外部结构 D.线性结构和非线性结构
3．设有一个长度为n的顺序表，要删除第i个元素,则需移动元素的个数为（ ）。C
A. i B. n-i-1
C. n-i D. n-i+1
4． 设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（ )可使其成为单向循环链表。D
A. head = p; B. p=head;
C. p->next = NULL ; D. p->next=head;
5． 一个栈的进栈序列是10，20，30，40，50，则栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。B
A．10,20,30,40,50 B．40,30,50,10,20
C．40,50,30,20,10 D．50,40,30,20,10
6．在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ ）。D
A．x=top;top=top->next;
B．x=top->data;
C．top=top->next; x=top->data;
D．x=top->data; top=top->next;
7．判断一个顺序队列sq（最多元素为m）为空的条件是（ ）。C
A．sq->rear-sq->front==m
B．sq->rear-sq->front-1==m
C．sq->front==sq->rear
D．sq->front==sq->rear+1
8．串函数Strcat（a,b）的功能是进行串（ ）。D
A．比较 B．复制
C．赋值 D．连接
9．稀疏矩阵采用压缩存储的目的主要是（ ）。D
A．表达变得简单
B．对矩阵元素的存取变得简单
C．去掉矩阵中的多余元素
D．减少不必要的存储空间的开销
10. 深度为5的二叉树至多有（ ）个结点。C
A. 16 B. 32
C. 31 D. 10
11. 如图所示二叉树的中序遍历序列是（ ）。B
A. abdgcefh B. dgbaechf
C. gdbehfca D. abcdefgh
12. 一个具有n个顶点的无向完全图包含（ ）条边。C
A．n（n-1） B．n（n+1）
C．n（n-1）/2D．n（n+1）/2
解析：无向完全图中，任意两个不同顶点之间都有且仅有一条边。
n个顶点中，每个顶点跟其它n-1个顶点间都有一条边，总共n(n-1）条边，由于每条边被计算了2次，所以要除以2，因此结果为n（n-1）/2
13. 图的深度优先遍历算法类似于二叉树的（ ）遍历。A
A．先序B．中序
C．后序 D．层次
14. 在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ ）次比较后查找成功。B
A．3 B．4
C．6 D．8
15. 依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ ）。D
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
16. 下面程序段的时间复杂度是（ ）。D
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
A. O(1) B. O(log2n)
C. O(n) D. O(n3)
17．在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执行（ ）。 A
A．p->next=q->next ; B．p=q->next;
C．p->next=q; D．p->next=q;
18．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（ ）。C
A. n-i B. n-i-1
C. n-i+1 D. i
19．一个队列的入队序列是1，2，3，4。则队列的输出序列是（ ）。B
A．4，3，2，1 B．1，2，3，4
C．1，4，3，2 D．3，2，4，1
20．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（ ）。C
A．top->next=p;
B．p->next=top->next; top->next=p;
C．p->next=top; top=p;
D．p->next=top->next; top=top->next;
21．判断一个循环队列Q（最多元素为m）为满的条件是（ ）。C
A．Q->front==Q->rear B．Q->front!=Q->rear
C．Q->front==(Q->rear+1)% m D．Q->front!=(Q->rear+1)% m
22．设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（ ）。C
A．求子串 B．连接
C．模式匹配 D．求串长
23．一个非空广义表的表头（ ）。D
A．不可能是原子 B．只能是子表
C．只能是原子 D．可以是子表或原子
24. 树中所有结点的度等于所有结点数加（ ）。D
A. 1 B. 0
C. 2 D. -1
解析：这里的“度”是指所有结点的分支数（相当于计算连接结点的边）
25. 在一棵二叉树上，第5层的结点数最多为（ ）。 C
A．8 B．15
C．16 D．32
26. 在一个图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。C
A．1/2 B．1
C．2 D．4
27. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。D
A．n B．e
C．2n D．2e
解析：每条边对应2个邻接表结点（每个端点各一个）。边数为e，所有邻接表中的结点总数=2e
28.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。A
A．37/12 B．39/12
C．41/12 D．35/12
解析：二叉判定树如下：第一层1个，第二层2个，第三层4个，第四层最多可以有8个，但只剩5个，所以第四层是5个。因此，平均比较次数=(1*1+2*2+4*3+5*4)/12=37/12
29.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（ ）。A
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
30．数据的存储结构包括数据元素的表示和（ ）。D
A. 数据处理的方法 B. 相关算法
C. 数据元素的类型 D. 数据元素间的关系的表示
31．在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ ）。D
A．p->next=s;s->next=p->next; B．p->next=s->next;
C．p=s->next; D．s->next=p->next;p->next=s;
32．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。C
A．p=q->next; B．p->next=q;
C．p->next=q->next; D．q->next=NULL;
33．表达式a*(b+c)-d的后缀表达式是（ ）。B
A．abcd*+- B．abc+*d-
C．abc*++d- D．-+*abcd
34．判断顺序栈s满（元素个数最多n个）的条件是（ ）。C
A．s->top==0 B．s->top!=0
C．s->top==n-1 D．s->top!=n-1
35．串的长度是指（ ）。B
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
36．广义表(a,(d,a,b),h,(e,((i,j),k)))深度是( )。D
A．6 B．10
C．8 D．4
37. 在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（ ）。D
A．18 B．16
C．15 D．17
38. 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ ）。B
A．以顺序存储方式 B．以链接存储方式
C．以索引存储方式 D．以散列存储方式
39. 从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为（ ）。C
A. 插入排序 B. 交换排序
C.选择排序D. 归并排序
40. 每个存储结点只存储一个数据元素，各结点存储在连续的存储空间，该存储方式是（ ）存储方式。A
A．顺序 B．链接
C．索引 D．散列
41．元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（ ）（进栈出栈可以交替进行）。D
A．10，8，4，6 B．10，6，4，8
C．8，4，6，10 D．10，8，6，4
42．如果以链表作为栈的存储结构，则退栈操作时（ ）。C
A．必须判断栈是否满 B．判断栈元素类型
C．必须判断栈是否空 D．对栈不作任何判断
43．串与普通的线性表相比较，它的特殊性体现在（ ）。C
A．顺序的存储结构 B．链接的存储结构
C．数据元素是一个字符 D．数据元素可以任意
44．设有一个广义表A (a)，其表尾为（ ）。C
A．a B．(( ))
C．（）D．(a)
45. 权值为{1，2，6，8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。D
A．18 B．28
C．19 D．29
解析：哈夫曼树如下：
带权路径长度=1*3+2*3+6*2+8*1=29
46. 一个具有n个顶点的有向完全图包含（ ）条边。A
A．n（n-1） B．n（n+1）
C． n（n-1）/2 D．n（n+1）/2
解析：如是是无向完全图，则包含n（n-1）/2条边
47. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。C
A．n B．n/2
C．(n+1)/2D．(n-1)/2
解析：不要急于选择n/2。
第1个查找一次，第2个查找2次，…第n个查找n次。
总查找长度=(1+2+3+…+n) =n(n+1)/2
平均查找长度=总查找长度/n=(n+1)/2
48. 当两个元素出现逆序的时候就交换位置，这种排序方法称为（ ）。B
A. 插入排序 B. 交换排序
C. 选择排序 D. 归并排序
49．下列说法中，不正确的是（ ）。D
A．数据元素是数据的基本单位
B．数据项是数据中不可分割的最小可标识单位
C．数据可有若干个数据元素构成
D．数据项可由若干个数据元素构成
50. 每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ ）存储方式。B
A．顺序 B．链接
C．索引 D．散列
51．向顺序栈中压入新元素时，应当（ ）。A
A．先移动栈顶指针，再存入元素
B．先存入元素，再移动栈顶指针
C．先后次序无关紧要
D．同时进行
52．一般情况下，将递归算法转换成等价的非递归算法应该设置（ ）。A
A．栈 B．队列
C．堆栈或队列 D．数组
53．空串与空格串（ ）。B
A．相同 B．不相同
C．可能相同 D．无法确定
54．广义表(f,h,(a,b,d,c),d,e,((i,j),k))的长度是( )。A
A．6 B．10
C．8 D．4
55. 二叉树第k层上最多有（ ）个结点。B
A．2k B．2k-1
C．2k-1 D．2k-1
56. 对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。B
A．n B．n2
C．n-1 D．(n-1)2
57.采用折半查找方法查找长度为n的线性表时，其算法的时间复杂度为（ ）。D
A．O(n2) B．O(nlog2n)
C．O(n) D．O(log2n)