数据结构选择题答案及相关知识点.doc

1、在一棵具有5层的满二叉树中结点总数为（ A ）。
A) 31 B）32
C）33 D）16
(2^n) - 1,

N = 2k-1(N总结点数，k层数)
2、串的逻辑结构与（ A ）的逻辑结构不相同。
A）线性表 B）栈
C）队列 D）集合
串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。
P71
3、下列序列中，执行第一趟快速排序后得到的序列是（A）。
A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]
C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]
左大右小
4、n个顶点的强连通图至少有（ C ）条边。
A）n B）n+1 C）n-1 D）n(n-1)
单节点除外，so,-1

5、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。
A）p->next=p->next->next B）p=p->next
C）p=p->nexe->next D）p->next=p
无限删除
6、对下图V4的度为（ C ）。
A）1 B）2 C）3 D）4

v1

v2 v3

v4

7、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A）4 B）5
C）6 D）7
图1-7
设度为0的结点个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，度为3的个数n3
树中结点总数n0+ n1 + n2 + n3，所有边的数量为0 * n0 + 1 * n1 + 2 * n2 + 3 * n3
树中结点比边多1个，合并这两个式子就可以得到：n0 = 1 + n2 + 2 * n3

8、在数据结构中，从逻辑上可以把数据结构分为（ C ）。
A）动态结构和静态结构 B）紧凑结构和非紧凑结构
C）线性结构和非线性结构 D）内部结构和外部结构
数据的逻辑结构分两大类： 线性结构 和 非线性结构
数据的存储方法有四种： 顺序存储方法 、 链接存储方法 、 索引存储方法和散列存储方法(hash存储)

9、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
A）loc(A1)+i*c B）loc(A1)+(i-1)*c
C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c
10、（ C ）在进行插入操作时，常产生假溢出现象。
A）顺序栈 B）循环队列
C）顺序队列 D）链队列
循环队列产生是为了解决顺序队列的假溢出
11、下列各种数据结构中属于线性结构的有（ A ）。
A）栈 B) 二叉树
C) 广义表 D) 图
数据元素之间的关系称为结构：1.集合；2.线性结构；3.树形结构；4.图/网状结构
12、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ B ）。
A）顺序表示法 B）单字符为结点的单链表表示法
C）等量分块表示法 D）不等量分块表示法
13、广义表head(((a,b),(c,d)))的运算结果为（ D ）。
A）(a,b) B）(c,d)
C）空表 D）（（a,b）,(c,d)）
14、 n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一
C）不含回路 D）有n条边
15、采用链结构存储线性表时，其地址（ B ）。
A）必须是连续的 B）连续不连续都可以
C）部分地址必须是连续 D）必须是不连续的
16、队列的操作的原则是（ A ）。
A）先进先出 B) 后进先出
C) 只能进行插入 D) 只能进行删除
U字走法，不是Y
17、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。
A）一个数量级别 B）一个平均值
C）一个最大值 D）一个均方值
18、线性表的链接实现有利于（ A ）运算。
A）插入 B）读元素
C）查找 D）定位
20、下面程序段的时间复杂度是( A )。
s =0;
for( i =0; i<n; i++)
for(j=0;j<n;j++)
s +=B[i][j];
sum = s ;
A） O(n2) B） O(n)
C） O(m*n) D）O(1)
21、二叉树第i(i≥1)层上至多有（ C ）结点。
A）2i B）2i C）2i-1 D）2i-1
满二叉树的时候结点最多
23、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。
A）3，2，5，6，4，1 B）1，5，4，6，2，3
C）2，4，3，5，1，6 D）4，5，3，6，2，1
,堆栈遵循后进先出,B.2.3交换
24、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。
A）9 B）11 C）15 D）不能确定
n2 +1 = n0
N = n0+n1+n2
N = 1+n1+2*n2
N:节点总数;ni:度为i的节点数
25、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ）。
A）直接选择排序 B）直接插入排序
C）快速排序 D）起泡排序
26、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。
A）13 B）33 C）18 D）40
首先，你要明白什么是压缩存储，对于这个对称矩阵来说，等于是存对角线的右上半加对角线的元素，或者是左下半加对角线的元素，其他位置一概不存，这题是使用行优先存储，即先存a11，再a12，再a22，再a13，再a23，再a33，以此类推，一直到a85，所以a85的位置计算为：（1+2+3+4+5+6+7）+5=33，即可。
1+ (2+7)(7-2+1)/2 +5 = 33
27、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。
A）3 B）4 C）5 D）1
度的定义是: 结点拥有的子树的个数。
结点A有3个兄弟，那么算上本身，双亲B存在的3个子树。度为4.28、线索二叉树中某结点D，没有左孩子的条件是（ B ）。
A）D->Lchild=Null B) D->ltag=1
C) D->Rchild=Null D) D->ltag=0
L Tag{0 lchild域指示节点的左孩子;1 lchild域指示节点的前驱}
R tag{0 rchild域指示节点的左孩子;1 rchild域指示节点的前驱}
没有前趋结点并没有左子树就没有左孩子，通常没有头结点的情况下，中序遍历的第一个结点就满足条件。
29、栈进行插入和删除操作的特点是（ A ）。
A）LIFO B）FIFO
C）FCFS D）HPF
LIFO = “last in first out”
30、与无向图相关的术语有（ C ）。
A）强连通图 B）入度
C）路径 D）弧
32、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。
A）上三角矩阵 B) 稀疏矩阵
C) 对角矩阵 D) 对称矩阵
34、栈进行插入和删除操作的特点是（ A ）。
A）LIFO B）FIFO
C）FCFS D）HPF
39、在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是( C )。
A）front==rear+1 B）rear==front+1
C）front==rear D）front==0
此时我们约定：少用一个元素，“队列头指针在队列尾指针的下一位置”作为队列呈“满”状态的标志。
43、在有n个叶结点的哈夫曼树中其结点总数为：（ D ）。
（A）不确定 （B）2 n （C）2 n + 1 （D）2 n – 1
无论哈夫曼树是几叉，其特点是一致的（假设为m叉），即树中只存在度为0的结点（即叶结点）和度为m的结点。不妨设度为0的结点个数为x，度为m的结点个数为y，则存在一个等式x+y=my+1，即x=(m-1)y+1，x+y是树的总结点个数。

就这道题来说，假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。
44、（ C ）在进行插入操作时，常产生假溢出现象。
A）顺序栈 B）循环队列
C）顺序队列 D）链队列
1-10这个要记一下,重复就重复
48、某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为：( C )
A）3 B）2 C）4 D）5
后序最后一个为根节点
49、在数据结构中假定在一棵二叉树中，度为2的结点数为15个，度为1的结点数为32个，则叶子结点数为（ B ）个。
A）15 B）16 C）17 D）47
每个分枝下面都有一个结点，所以总结点数N=2*15+1*32+0*叶子数+1(根节点）=63
二叉树中除了双分支结点，单分支结点就是叶子结点。
所以叶子数=63-15-32=16.

50、树最适合用来表示( C )。
A）有序数据元素 B）无序数据元素
C）元素之间具有分支层次关系的数据 D）元素之间无联系的数据

51、在顺序存储结构的线性表中第i个元素(1<=i<=n)前插入一个元素时，需要向后移动（ C ）个元素。
A）n-i-2 B） n-i-1 C）n-i+1 D）n
52、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（　D　）
A）插入                    B）删除
C）排序                    D）定位
53、对一个满二叉树，m个叶子，n个结点，深度为h，则( D )。
A）n = h+m B） h+m = 2n
C）m = h-1 D） n = 2h-1（n=2m-1）
m = 2h-1 ; n = 2h-1
54、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（　C 　）
A）单链表                    B）仅有头指针的单循环链表
C）双链表                    D）仅有尾指针的单循环链表
55、从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（　A　）。
A）n-i                           B）n-i+1
C）n-i-1                         D）i
56、在决定选取何种存储结构时，一般不考虑（ A ）。
A）各结点的值如何 B）结点个数的多少
C）对数据有哪些运算 D）所用的编程语言实现这种结构是否方便。
57、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（　D　）。
A）s.elem［top］=e；                   B）s.elem［top+1］=e；
s.top=s.top+1；                           s.top=s.top+1；
C）s.top=s.top+1；                     D）s.top=s.top+1；
s.elem［top+1］=e；                   s.elem［top］=e；
先进后出
58、循环队列sq中，用数组elem［26］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（　D　）。
A）8                             B）16
C）17                            D）18
12+26-20
队空：front＝＝rear
队满： (rear+1) % maxsize ==front
队中元素个数n＝（rear-front+maxsize )% maxsize
入队：rear=(rear+1) % maxsize ;
出队：front=(front+1) % maxsize ;
59、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　B　）
A）3，2，6，1，4，5                        B）3，4，2，1，6，5
C）1，2，5，3，4，6                        D）5，6，4，2，3，1
先进后出
60、不带头结点的单链表head为空的判定条件是( A )。
A）head == NULL B）head->next ==NULL
C）head->next ==head D）head!=NULL
61、二维数组A[3][3]按行优先顺序存储，若数组元素A[1][1]的存储地址为1087，A[2][2]的存储地址为1095，则数组元素A[0][0]的存储地址为（　A　）。
A）1079                                B）1080
C）1078                                D）1060
（1095-1087）/4 =2； A[0][0] = A[1][1]-8 = 1079
62、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（　A　）
A）队列                                      B）栈
C）线性表                                   D）有序表
63、对线性表进行折半查找时，要求线性表必须（ B ）。
A）以顺序方式存储 B）以顺序方式存储，且结点按关键字有序排列
C）以链式方式存储 D）以链式方式存储，且结点按关键字有序排列
64、节点的带权路径是指从根节点到该节点的路径长度乘以该节点的权值，树的带权路径长度是指树中所有叶子节点的带权路径长度之和，已知叶子节点a,b,c的权分别是2,5,7
左边给出的树的带权路径长度为（ A ）
A）21 B）14
C）22 D）28
(2+5)*2+7=21

c

a

b

A
65、对一棵有n个节点的二叉树按上述方法对节点进行编号，如果编号为i(i<=n)的节点与相同深度的满二叉树中编号为i的节点在二叉树中的位置相同，则称这棵二叉树为完全二叉树，下面是完全二叉树的是（ C ）
A
A
A

A B C D
(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。
(3) 平衡二叉树——一棵空树或左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
66、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（　B　）。
A）图中每个顶点的入度                    B）图中每个顶点的出度
C）图中弧的条数                          D）图中连通分量的数目

67、非空的循环单链表head的尾结点（由p所指向）满足( C )。
A）p->next == NULL B）p == NULL
C）p->next ==head D）p == head

68、设无向图的邻接链表如图所示，则该图的边的数目是（　B　）

A）4                B）5
C）10              D）20
V2
V1

V4
V3

69、下面的算法中（ A ）是用来构造最小生成树的算法。
A）普里姆（Prim）算法 B）迪杰斯特拉（Dijkstra）算法
C）弗洛伊德（Floyd）算法 D）拓扑排序
B: 是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。
C: 是一种用于寻找给定的加权图中多源点之间最短路径的算法。
D: 对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边+
-
(u,v)∈E(G)，则u在线性序列中出现在v之前。
70、设有一个栈，元素依次进栈的顺序为A、B、C、D、E。下列( C )是不可能的出栈序列。
A）A,B,C,D,E B）B,C,D,E,A C）E,A,B,C,D D）E,D,C,B,A
71、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（　A　）
A）f,c,b                                B）f,d,b
C）g,c,b                                D）g,d,b
72、排序算法中，不稳定的排序是（　D　）
A）直接插入排序                          B）冒泡排序
C）堆排序                                D）归并排序
若待排序列中两数据元素具有相同值,在排序前后它们位置发生颠倒,则称该排序算法是不稳定的。
73、堆排序是一种（ B ）排序。
A）插入 B）选择 C）交换 D）归并