(北航13.12复习题——整合版.docxVIP

北航《算法与数据结构》复习题单选题（每小题2分，总分10分）1、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（D ）A、必需是联系的B、部分地址必须是连续的C、一定是不连续的D、连续不连续都可以2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以什么为标准操作（ B）A、条件判断B、结点移动C、算术表达式D、赋值语句3、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B ）A、p-next=s;s-next=p-next;B、s-next=p-next;p-next=s;C、p-next=s;p-next=s-next;D、p-next=s-next;p-next=s;4、 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（C ）A、(2,5,12,16)26(60,32,72)B、(5,16,2,12)28(60,32,72)C、(2,16,12,5)28(60,32,72)D、(5,16,2,12)28(32,60,72)5、稀疏矩阵的压缩存储方法是只存储（A ）A、非零元素B、三元组（i,j, aij）C、aijD、i,j1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ A）排序法。A、插入B、选择C、希尔D、二路归并2、用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（D ）A、一定都是同义词B、一定都不是同义词C、都相同D、不一定都是同义词3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为（D ）A、42 B、40 C、21 D、204、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B ）A、不确定 B、n-i+1 C、I D、n-i5、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（ C）个A、k+1 B、2k C、2k-1 D、2k+1判断题（每小题1分，总分10分）(A==对，B==错)6、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。（ B）7、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（ B）8、任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（ A）9、在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。（B ）10、线索二叉树中的每个结点通常包含有5个数据成员。（A ）11、从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为选择排序（B ） 12、在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序（A ） 13、不是所有的AOV网都有一个拓朴序列（A ） 14、对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树（A ） 15、邻接多重表示法对于有向图和无向图的存储都适用（A ） 6、在顺序表中进行顺序有哪些信誉好的足球投注网站时，若各元素的有哪些信誉好的足球投注网站概率不等，则各元素应按照有哪些信誉好的足球投注网站概率的降序排列存放，则可得到最小的平均有哪些信誉好的足球投注网站长度。（A ）7、排序算法中的比较次数与初始元素序列的排列无关（B ）8、队列逻辑上是一个下端和上端既能增加又能减少的线性表（A ）。9、对于两棵具有相同记录集合而具有不同形态的二叉有哪些信誉好的足球投注网站树，按中序遍历得到的结点序列是相同的。（A ）10、给定一棵树，可以找到唯一的一棵二叉树与之对应（A ）11、字符串是一种线性表，其特殊性表现在它的数据元素是一个字符（A ） 12、由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44 （A ）13、判断一个表达式中左右括号是否匹配，采用栈实现较为方便（A ）14、算法在发生非法操作时可以作出处理的特性称为健壮性（ A）15、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少（B ）多选题（每小题2分，总分10分）16、对于单链表表示法，以下说法正确的是（ABC ）A、指向链表的第一个结点的指针，称为头指针B、单链表的每一个结点都被一个指针所指C、任何结点只能通过指向它的指针才能引用D、尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表17、对有序表的查找方式有以下几种（ABC ）A、折半查找B、斐波那契查找C、插值查找D、二叉树查找18、递归过程中要保存的信息包括（ABC ）A、返回地址B、本次调用中与形参结合的实参值C、本次递归调用中的局部变量值