《数据结构》模拟试卷一.doc

《数据结构》模拟试卷一 单项选择题： 1、若某链表中最常用的操作是在最后一个节点之后插入一个节点和删除一个节点，则采用 D 存储方式最节省运算时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 带头节点的双循环链表 2、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 D 。 A. A，B，C，D B. D，C，B，A C. A，C，D，B D. D，A，B，C 3、串是 D 。 A. 不少于一个字母的序列 B. 任意个字母的序列 C. 不少于一个字符的序列 D. 有限个字符的序列 4、链表不具有的特点是 A 。 A. 可随机访问任一元素 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比 5、在有n个叶子节点的哈夫曼树中，其节点总数为 D 。 A. 不确定 B. 2n C. 2n+1 D. 2n-1 6、任何一个无向连通图的最小生成树 A 。 A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 7、将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子的编号为 A 。 A. 98 B. 99 C. 50 D. 48 8、下列序列中， A 是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。 A. [da , ax , eb , de , bb] ff [ha , gc] B. [cd , eb , ax , da] ff [ha , gc , bb] C. [gc , ax , eb , cd , bb] ff [da , ha] D. [ax , bb , cd , da] ff [eb , gc , ha] 9、用n个键值构造一棵二叉排序树，最低高度为 D 。 A. n/2 B. n C. [log2n] D. [log2n+1] 10、二分查找法要求查找表中各元素的键值必须是 A 排列。 A. 递增或递减 B. 递增 C. 递减 D. 无序 11、对于关键值序列{12，13，11，18，60，15，7，18，25，100}，用筛选法建堆，必须从关键值为 的节点开始。 A. 100 B. 12 C. 60 D. 15 判断题： 1、串长度是指串中不同字符的个数。（ × ） 2、数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。（ × ） 3、在顺序表中取出第i 个元素所花费的时间与i 成正比。（ × ） 4、在栈满的情况下，不能作进栈运算，否则产生“上溢”。（ √ ） 5、二路归并排序的核心操作是将两个有序序列归并为一个有序序列。（ √ ） 6、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先有哪些信誉好的足球投注网站遍历可访问到该图的每个顶点。（ × ） 7、一个有向图的邻接表和逆邻接表中的节点个数一定相等。（ ） 8、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。（ √ ） 9、二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根节点的值大于其左孩子的值；若它的右子树非空，则根节点的值小于其右孩子的值。（ × ） 10、在执行某个排序算法的过程中，出现了