数据结构错题汇总（持续更新）
------
有错请指正！！！
------
1.设栈的初始状态为空，当字符序列a3_作为栈的输入时，输出长度为3的且可以用作C语言标识符的字符串序列有（）个
解析：
首先，栈的顺序是先进后出
字符序列为a3_ 1)a入栈，再出栈，然后3入栈，再出栈，—入栈，再出栈 序列是a3_
2)a入栈，再出栈,然后3,—入栈，再出栈，序列是a_3
3)a入栈，3入栈，再出栈，a出栈， —入栈，再出栈 序列是3a_
4) a入栈，3入栈，再出栈, —入栈,序列是3_a
5) a入栈，3入栈,_入栈，序列是_3a
C语言的标识符不能以数字开头，
答案：3
2.某带链的队列初始状态为 front=rear=NULL。经过一系列正常的入队与退队操作后，front=rear=10。该队列中的元素个数为（）
解析：
注意题目 带链的队列而不是循环队列
答案：1
3.(1)静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i有关。
(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加.
(3)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
4.short a[100]，sizeof(a) 返回什么？
解析：
short int : 2个字节
sizeof 返回的值表示的含义如下（单位字节）：
数组——编译时分配的数组空间大小；
指针——存储该指针所用的空间大小（存储该指针的地址的长度，是长整型，应该为4）；
类型——该类型所占的空间大小；
对象——对象的实际占用空间大小；
函数 —— 函数的返回类型所占的空间大小。函数的返回类型不能是 void 。
答案：
shorta[100] 空间100*2
5.在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关()
解析：
由于是单链表，所以即使存在尾指针，删除操作费时还是O(n)，这个时间是找到待删除节点的前一个指针，并把它赋值为尾指针而造成的。
答案: 错
6. 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（ ）存储方式最节省运算时间和存储空间。
A.单链表
B.仅有头指针的单循环链表
C.双向链表
D.仅有尾指针的单循环链表
解析：
单链表：尾插入O(n),尾删O(n)
仅有头的单循环链表：尾插入O(n),尾删O(n)
双向链表：尾插入O(1),尾删O(1)
仅有尾指针的单循环链表：尾插入O(1),尾删O(n)
答案: C
7. 若一序列进栈顺序为e1,e2,e3,e4,e5,问存在多少种可能的出栈序列（）
解析：通过公式求解
答案：42
8.一个有序数列，序列中的每一个值都能够被2或者3或者5所整除，这个序列的初始值从1开始，但是1并不在这个数列中。求第1500个值是多少？
解析：
2、3、5的最小公倍数是30。[ 1, 30]内符合条件的数有22个。周期为30.
第1500个数是：1500/22=68 1500%68=4。第1500个数经过了68个周期，然后再取下一个周期内的第4个数。一个周期内的前4个数：2,3,4,5。故，结果为68*30=2040+5=2045
答案：2045
9.关于 int a[10]; 问下面哪些不可以表示 a[1] 的地址？
A.a+sizeof(int)
B.&a[0]+1
C.(int*)&a[0]+1
D.(int*)((char*)&a[0]+sizeof(int))
解析：
在32位机器上相当于指针运算 a + 4
数组首元素地址加1，根据指针运算就是a[1]的地址
数组地址被强制类型转换为int*，然后加1，这样和B表示的一个意思
数据地址先被转换为char*，然后加4，根据指针运算公式，向前移动4 * sizeof(char)，之后被转换为int*，显然不是a[1]的地址
答案：A,D
10.哈夫曼树中没有度数为1的结点。
解析：
建立霍夫曼树的时候，是从底往上匹配建树，所以每个节点度为2或者是叶节点
答案：对
11.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。
解析：
因为最小生成树不唯一，所以可能相等
答案：对
12.便于插入和删除的容器是（）
Ａ.list
B.vector
C.map
D.set
解析：
1.vector 底层数据结构为数组 ，支持快速随机访问
2.list 底层数据结构为双向链表，支持快速增删
3.deque 底层数据结构为一个*控制器和多个缓冲区.支持首尾（中间不能）快速增删，也支持随机访
4.stack 底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
5.queue 底层一般用23实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
6. 45是适配器,而不叫容器，因为是对容器的再封装
7.priorityQueue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现
8.set 底层数据结构为红黑树，有序，不重复
9.multiSet 底层数据结构为红黑树，有序，可重复
10.map 底层数据结构为红黑树，有序，不重复
11.multiMap 底层数据结构为红黑树，有序，可重复
12.hashSet 底层数据结构为hash表，无序，不重复
13.hashMultiSet 底层数据结构为hash表，无序，可重复
14.hashMap 底层数据结构为hash表，无序，不重复
15.hashMultiMap 底层数据结构为hash表，无序，可重复
答案：ＡＣＤ
13.C#程序段的结果： int[][] array = new int[3][]{ new int[3]{5,6,2}, new int[5]{6,9,7,8,3}, new int[2]{3,2} }; array[2][2] 返回（）
A.9
B.6
C.2
D.溢出
解析：
array[2][2]代表第三个一维数组的第三个元素，故溢出
答案：D
14.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别0和3。当从队列中删除一个元素，再加入两 个元素后，rear和front的值分别为（）
解析：
队列是3 4 5 0，其中front是3，rear是0.
删除一个元素，从front删除，变成了4，
增加两个元素，从rear增加，变成了2
最终变成了 4(front) 5 0 1 2(rear)
答案：2 4
15.数组必须是同类型值的集合()
解析：
有的语言是，有的语言不是的。JavaScript的数组可以是任意object var arr = [function(){alert("")},[0,1,2],{0,"ao",True}];
答案：错
16.广义表的同级元素(直属于同一个表中的各元素)具有线性关系()
解析：
广义表是线性表的扩展，具体定义为n(n>=0)个元素的有限集合。其中元素有以下两种类型：
一个原子元素(指不可再分的元素)
一个可以再分的元素(或称为一个子表)
如果所有元素都是原子元素，则称为线性表，如果含有子表，则是广义表。n的值是广义表的长度，如果n=0，称广义表为空表。
常见的广义表为：
A=(); B=(()); C=(alb); D=(A,B,C); E=(a,E)
广义表中含有元素的个数称为广义表的长度，广义表中含有的括号对数称为广义表的深度。
从上述定义和例子可推出列表的3个重要结论：
列表的元素可以是子表，而子表的元素还可以是子子表…由此，列表是一个多层次的结构。
列表可为其他列表所共享。如列表D可以直接引用其他列表。
列表可以是一个递归的表，即列表也可以是其本身的一个子表。
答案：对
17.用链接方式存储的队列，在进行删除运算时 ( )
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
解析：
当队列中只有一个元素且要删除它时，需要同时修改头尾指针。
答案：需要同时修改头尾指针
18.折半查找与二元查找树的时间性能在最坏的情况下是相同的()
解析：
折半查找最坏情况log2n
但是二元查找树为链式的情况，就需要n次查找
如： 1
4
7
13
答案：对
18.在有向图的邻接表存储结构中,顶点v在链表中出现的次数是()
解析：
无向图邻接表的边表中顶点v出现的次数等于该顶点在无向图中所连接的边数
有向图邻接表的边表中顶点v出现的次数等于该顶点在有向图中顶点的入度
而有向图逆邻接表的边表中顶点v出现的次数等于该顶点在有向图中顶点的出度
答案：顶点的入度
19.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
解析：
带尾指针的单向链表：插入可以，但是删除无法完成，因为p需要前移，但是单向链表无法得到前一个节点。
带尾指针的双向链表：插入和删除都很简单。
带尾指针的单向循环链表：插入很简单，删除则需要遍历整个链表，比较费时。
带头指针的双向循环链表：插入和删除都很简单。
答案：D
20.一个具有513个节点的二叉树，有___种可能的层高。
解析：
最高的情况是每层一个结点，最低则是完全二叉树，513的结点完全二叉树情况下高度是10层。所以从10 到513 共504种情况
答案：504
21.一个二叉树*有80个叶子结点与70个度为1的结点,则该二叉树中的总结点数为
解析 :
二叉树中,度为0的结点数等于度为2的结点数加1,即n2 = n0 - 1,叶子结点即度为0,则n2 = 79,总结点数为n0 + n1 +n2 = 80 + 70+ 79 = 229
答案 : 229
22.节点按中序遍历为xyz的二叉树可能有_____种。
解析：
答案： 5种
23.若有以下定义和语句：
char s1[]="12345",*s2="1234";
printf("%d\n" ,strlen(strcpy(s1,s2)));
则输出结果是
解析：
strcpy(s1,s2)这个函数是把s2字符串拷贝到s1这个字符串，同时也把s2的 '\0' 拷过去，所以覆盖了s1的所有字符（在空间足够的情况下，当然遇到s1的空间不足以存放s2，另考虑），所以strcpy执行完后是“1234” strlen("1234") 就是4了
答案：4
24.若有 18 个元素的有序表存放在一维数组 A[19] 中，第一个元素放 A[1] 中，现进行二分查找，则查找 A ［ 3 ］的比较序列的下标依次为 ( )
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
解析：
二分基本的查询下标的方法为（首下标+尾下标）/2，如果该下标非查询值，要剔除后在左边或右边继续循环。
答案：D
25.一个长度为99的循环链表，指针A和指针B都指向了链表中的同一个节点，A以步长为1向前移动，B以步长为3向前移动，一共需要同时移动多少步A和B才能再次指向同一个节点____。
解析：
设A走x步 那么B久走3x步 两个要碰到 所以有(3x-x)%99=0 x取99才可以
答案：99