Day5 刷题总结
选择题
- 在需要经常查找结点的先驱与后继的场合中，使用（B ）比较合适。
A.单链表
B.双向链表
C.循环链表
D.链栈
解析：单链表的实现只有一个指向后继的指针。
想要查询前驱和后继，就要两个指针，使用双向链表比较合适 - 给出以下定义：
Char x[]=”abcdefg”;
Char y[]={‘a’,’b’,’c’,’d’,’e’,’f’,’g’};
（C）
A.数组X和数组Y等价
B.数组X和数组Y的长度相同
C.数组X的sizeof运算值大于数组Y的sizeof运算值
D.数组X的sizeof运算值小于数组Y的sizeof运算值
解析：
x如此定义会在后面添加\0,所以x比y多一个结束符号 - 对稀疏矩阵进行压缩存储,常用的两种方法是( B )。
A.三元组和散列表
B.三元组和十字链表
C.三角矩阵和对角矩阵
D.对角矩阵和十字链表
解析： - 声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，参数是int*，正确的是（C）
A.（int p[10]）（int）
B.int [10]*p（int ）
C.int ((*p)[10])(int )
D.int ((int )[10])p
解析：
先看未定义标识符p，p的左边是，p表示一个指针，跳出括号，由于[]的结合性大于，所以p指向一个大小为10的数组，即(p)[10]。左边又有一个号，修释数组的元素，(p)[10]表示p指向一个大小为10的数组，且每个数组的元素为一个指针。跳出括号，根据右边（int ）可以判断（(p)[10]）是一个函数指针，该函数的参数是int,返回值是int。 - 使用KMP算法在文本串S中找模式串P是一种常见的方法。假设S=P={xyxyyxxyx}，亦即将S对自己进行匹配，匹配过程中正确的next数组是__C__。
A.0,1,1,2,2,1,2,2,3
B.0,1,2,2,3,1,2,2,3
C.0,1,1,2,3,1,2,2,3
D.0,1,1,2,3,1,1,2,3
E.0,1,2,2,3,1,1,2,3
F.0,1,2,2,2,1,1,2,3
解析： - 在154个元素组成有序表进行二分法查找，可能的比较次数为（BCD）
A.10
B.8
C.4
D.1
解析：
折半查找过程可用二叉树来描述，把有序表中间位置上的结点作为树的根结点，左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径，比较的次数就是该路径中结点的个数，即，该结点在树中的层数。 所以该题可以转换为求有154个结点的二叉树有几层，小于等于这个层数的数值就是答案。 又知，深度为K的二叉树最多有2的K次方-1个结点，深度为7的二叉树最多有127个结点，深度为8的二叉树最多有255个结点，所以154个结点的二叉树有8层。 - 以下关于单向链表说法正确的是（ABC）
A.如果两个单向链表相交，那他们的尾结点一定相同
B.快慢指针是判断一个单向链表有没有环的一种方法
C.有环的单向链表跟无环的单向链表不可能相交
D.如果两个单向链表相交，那这两个链表都一定不存在环
解析：
A.单链表的没个节点都具有唯一的前驱节点和唯一的后继节点，所以当两个单链表存在相交的节点时，这两个链表则同时拥有这个节点，以及这个节点的所有后继节点，当这个公共节点是尾节点时，他们则只含有公共一个节点-------尾节点。
B.快慢指针是判断单链表是否有环的一种方法：两个指针，每次移动的步长为2叫做快指针，每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发，当快指针率先到达NULL的时候，则说明此单链表中不存在环，当快指针追上慢指针的时候，说明此单链表中存在环。
C.有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点。
D.两个单向链表之间相交可以存在环。 - 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间()
A.对
B.错
解析：若左子树全部为空或者右子树为空，此时和顺序表的效率是一样的。 - 设指针变量p指向单链表的某中间结点，则删除该结点的后序结点需要的操作为（D）
A.p-next=p-next;free(p-next)
B.free(p-next);p-next=p-next-next
C.p-next=p-next-next
D.t=p-next;p-next=t-next;free(t) - 判定一个队列 QU(最多元素为 m0)为满队列的条件是（A）
A.QU->rear - QU->front = = m0
B.QU->rear - QU->front -1= = m0
C.QU->front = = QU->rear
D.QU->front = = QU->rear+1
编程题
统计一个数字在排序数组中出现的次数。