数据结构与算法：22 精选练习50题
精选练习50
马上就要期末考试或者考研了。为了大家复习的方便，我精选了有关数据结构与算法的50道选择题，大家可以抽空练习一下。公众号后台回复“答案”可以获取该50道题目的答案。
01、数据在计算机中的表示称为数据的______。
（A）存储结构 （B）抽象结构 （C）顺序结构 （D）逻辑结构
02、哪一个不是算法的特性______。
（A）有穷性 （B）确定性 （C）必须有输入 （D）必须有输出
03、以下对于链式存储结构的叙述中错误的是______。
（A）逻辑上相邻的结点，物理上不必相邻 （B）可以通过计算，直接确定第i个结点的存储地址 （C）插入、删除运算操作方便，不必大量移动结点 （D）结点包括指针域，存储密度小于顺序存储结构
04、下面对于线性表的叙述中，不正确的是______。
（A）线性表采用顺序存储时，必须占用一片连续的存储单元 （B）线性表采用链式存储时，不需要占用一片连续的存储单元 （C）线性表采用顺序存储时，便于进行插入和删除操作 （D）线性表采用链式存储时，便于进行插入和删除操作
05、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行______。
（A）S.Next=P; P.Next=S; （B）S.Next=P.Next; P.Next=S; （C）S.Next=P.Next; P =S; （D）P.Next=S; S.Next=P;
06、在双向链表中，删除P所指的结点，则执行______。
（A）P.Next.Prior=P.Prior; P.Prior.Next=P.Next; （B）P.Next.Prior=P.Prior; P.Prior=P.Next; （C）P.Prior.Next=P; P.Prior =P.Prior.Prior; （D）P.Prior=P.Next.Next; P.Next=P.Prior.Prior;
07、在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动______个元素。
（A）n-i （B）n-i+1 （C）n-i-1 （D）i
08、栈的特点是______。
（A）先进先出 （B）后进先出 （C）进优于出 （D）出优于进
09、队的特点是______。
（A）先进先出 （B）后进先出 （C）进优于出 （D）出优于进
10、栈和队列的共同点是______。
（A）都是先进后出 （B）都是先进先出 （C）只允许在端点处插入和删除元素 （D）没有共同点
11、以下______不是栈的基本运算。
（A）删除栈顶元素 （B）删除栈底元素 （C）判断栈是否为空 （D）将栈置为空栈
12、设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。假设6个元素出队的顺序是b，d，c，f，e，a则栈S的容量至少应是______。
（A）2 （B）3 （C）4 （D）5
13、1，2，3，4四个元素按顺序进栈，不可能的出栈顺序为______。
（A）1，2，3，4 （B）2，3，4，1 （C）1，4，3，2 （D）3，1，4，2
14、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个______结构。
（A）堆栈 （B）队列 （C）数组 （D）线性表
15、用链表表示线性表的优点是______。
（A）便于随机存取 （B）花费的存储空间较顺序存储少 （C）便于插入和删除 （D）数据元素的物理顺序与逻辑顺序相同
16、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的______个元素。
（A）n/2 （B）(n+1)/2 （C）(n-1)/2 （D）n
17、对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。删除一个元素时平均要移动表中的______个元素。
（A）n/2 （B）(n+1)/2 （C）(n-1)/2 （D）n
18、循环链表的主要优点是______。
（A）不再需要头指针了。 （B）已知某个结点的位置后，能够容易找到它的直接前趋。 （C）在进行插入、删除运算时，能更好的保证链表不断开。 （D）从表中的任意结点出发都能扫描到整个链表。
19、设有两个字符串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中位置的算法称为______。
（A）连接 （B）匹配 （C）求子串 （D）求串长
20、某二维数组A的行下标的范围是0到8，列下标的范围是0到4，数组中的元素用相邻的4个字节存储，存储器按字节编码。假设存储数组元素A[0，0]的第一个字节的地址是0。则存储数组A的最后一个元素第一个字节的地址是______。
（A）175 （B）86 （C）68 （D）176
21、______是“abcd321ABCD”的子串。
（A）abcd （B）321AB （C）“abcABC” （D）“21AB”
22、已知一棵二叉树前序遍历和中序遍历序列分别为ABDEGCFH和DBGEACHF，则该二叉树的后序序列为______。
（A）GEDHFBCA （B）ACBFEDHG （C）ABCDEFGH （D）DGEBHFCA
23、已知某二叉树前序遍历序列为ABDCE，则下面序列中有可能是对该二叉树进行中序遍历来得到的序列是______。
（A）BCADE （B）CBADE （C）BDAEC （D）BEACD
24、二叉树的后序遍历序列是DABEC，中序遍历序列是DEBAC，则此二叉树的前序遍历序列是______。
（A）ACBED （B）DECAB （C）DEABC （D）CEDBA
25、若树的度为4，其中度为1，2，3和4的结点个数分别为5，3，2和1。那么树中叶子结点的个数是______。
（A）8 （B）10 （C）11 （D）12
26、下面几个符号串编码集合中，不是前缀编码的是______。
（A）{0，10，110，1111} （B）{11，10，001，101，0001} （C）{00，010，0110，1000} （D）{B，C，AA，AC，ABA，ABB，ABC}
27、树的基本遍历策略可以分为前序遍历和后序遍历，二叉树的基本遍历策略可分为前序、中序、后序三种遍历。我们把由树转化得到的二叉树称为该树对应的二叉树，则下面正确的是______。
（A）树的前序遍历序列与其对应的二叉树前序遍历序列相同 （B）树的后序遍历序列与其对应的二叉树后序遍历序列相同 （C）树的前序遍历序列与其对应的二叉树中序遍历序列相同 （D）以上都不对
28、n个结点的线索二叉树上含有的线索数为______。
（A）2n （B）n-1 （C）n+1 （D）n
29、具有6个结点的有向图至少应有______条边才能确保是一个强连通图。
（A）5 （B）6 （C）7 （D）8
30、一个具有n个结点的连通无向图的生成树中有______条边。
（A）n-1 （B）n （C）n/2 （D）n+1
31、设无向图的结点数为n，则该无向图最多有______条边。
（A）n-1 （B）n(n-1)/2 （C）n(n+1)/2 （D）n*n
32、设有向图的结点数为n，则该有向图最多有______条边。
（A）n-1 （B）n(n-1) （C）n(n-1)/2 （D）n*n
33、一个有n个顶点的无向连通图，它所包含的连通分量个数为______。
（A）0 （B）1 （C）n （D）n+1
34、一个图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用______次深度优先搜索算法。
（A）k （B）1 （C）k-1 （D）k+1
35、在有向图G的拓扑序列中，若顶点在之前，则下列情况不可能出现的是______。
（A）G中有弧 （B）G中有一条到的路径 （C）G中没有弧 （D）G中有一条到的路径
36、堆是一种有用的数据结构。例如关键码序列______是一个堆。
（A）16，72，31，23，94，53 （B）94，53，31，72，16，53 （C）16，53，23，94，31，72 （D）16，31，23，94，53，72
37、以下序列不是堆的是______。
（A）100，85，98，77，80，60，82，40，20，10，66 （B）100，98，85，82，80，77，66，60，40，20，10 （C）10，20，40，60，66，77，80，82，85，98，100 （D）100，85，40，77，80，60，66，98，82，10，20
38、对关键字序列{72，73，71，23，94，16，5，68，76，103}构建大根堆，必须从键值为______的结点开始。
（A）103 （B）72 （C）94 （D）23
39、在排序算法中两两比较排序记录项，将那些与排序要求不符的记录交换位置，直到排好序为止的排序方法是______。
（A）插入排序 （B）交换排序 （C）选择排序 （D）堆排序
40、在排序算法中把第i个记录插入到前面已排好的记录中，使插入后的前i个记录符合排序要求的排序方法是______。
（A）插入排序 （B）交换排序 （C）选择排序 （D）堆排序
41、在排序算法中每次从全部还未排序的记录项中选择最小或最大的记录项，并把它接在已排好的记录项末尾的排序方法是______。
（A）插入排序 （B）交换排序 （C）选择排序 （D）堆排序
42、在下列序列中，______才可能是执行第一趟快速排序后得到的序列。
（A）{8，6，18} 19 {16，10，50} （B）{6，4，8} 18 {81，19，36，18} （C）{81，1，2} 36 {99，81，69} （D）{2，3，4} 89 {78，98，68}
43、对有8个元素的序列{49，38，65，97，76，13，27，50}按从小到大顺序进行排序，直接选择排序第一趟的排序结果是______。
（A）13，38，65，97，76，49，27，50 （B）13，27，38，49，50，65，76，97 （C）97，76，65，50，49，38，27，13 （D）13，38，65，50，76，49，27，97
44、对序列{72，73，71，23，94，16，5，68，76，103}按照构建大根堆的方式从小到大进行排序，堆排序第一趟的排序结果是______。
（A）103，94，71，76，73，16，5，68，23，72 （B）72，94，71，76，73，16，5，68，23，103 （C）94，76，71，72，73，16，5，68，23，103 （D）23，76，71，72，73，16，5，68，94，103
45、对序列{72，73，71，23，94，16，5，68，76，103}按照delta=5从小到大进行排序，希尔排序第一趟的排序结果是______。
（A）103，94，71，76，73，16，5，68，23，72 （B）16，5，68，23，73，71，76，72，94，103 （C）16，71，68，23，94，72，73，5，76，103 （D）16，5，68，23，94，72，73，71，76，103
46、对线性表进行二分查找时，要求线性表必须______。
（A）以顺序方式存储 （B）以链式方式存储 （C）以顺序方式存储且结点按关键字有序排序 （D）以链式方式存储且结点按关键字有序排序
47、在顺序表{3，6，8，10，12，15，16，18，21，25，30}中，用二分法查找关键码11，所需的关键码比较次数为______。
（A）2 （B）3 （C）4 （D）5
48、在顺序表{2，5，7，10，14，15，18，23，35，41，52}中，用二分法查找关键码18，所需的关键码比较次数为______。
（A）2 （B）3 （C）4 （D）5
49、对于19个元素的有序记录集合Record采用二分查找，则查找Key=Record[3]的比较序列的下标（下标从0开始）为______。
（A）9、5、3 （B）9、5、2、3 （C）9、4、2、3 （D）9、4、1、2、3
50、对搜索二叉树进行______遍历可以得到结点的排序序列。
（A）前序遍历 （B）中序遍历 （C）后序遍历 （D）层次遍历