数据结构模拟试题答案.pdfVIP

数据结构模拟题答案 一、单项选择填空题： 对于下列各题，在备选答案中选出一个正确的，并将其编号填在“ ” 位置上。 1. 若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用 存储方式最节省运算时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表 2. 在有n个叶子结点的哈夫曼树中结点总数为 。 A. 不确定 B. 2n-1 C. 2n D. 2n+1 注：非叶子节点数为 n-1 3. 折半查找法要求查找表中各元素的键值必须是 。 A. 递增或递减 B. 递增 C. 递减 D. 无序 4. 对于键值序列（11，13，18，60，15，7，19，25，12，80），用筛选法建 堆，必须从键值为 的结点开始。 A. 80 B. 12 C. 60 D. 15 注：筛选法建堆，必须从=n/2 个元素开始，或者说从建立的堆中第一个内部节 点开始，以上面为例：15 为第一个内部节点。 11 13 18 60 15 7 19 25 12 80 5. 设图 G 用邻接表存储，则求每个顶点入度的时间复杂度为 。 A. O(n) B. O(n+e) C. O(n*n) D. O(n*e) 注：有哪些信誉好的足球投注网站顶点的入度有两重循环嵌套，但是内层循环会有 if 语句。 6. 链表不具有的特点是 。 A. 不必事先估计存储空间 B. 可随机访问任一元素 C. 插入删除不需要移动元素 D. 所需空间与线性表长度成正比 7. 设输入序列为1、2、3、4，则借助栈所得到的输出序列不可能是 。 A. 1、2、3、4 B. 4、3、2、1 C. 1、3、4、2 D. 4、1、2、3 8. 在具有 n 个结点的二叉链表中，非空的链域个数为 。 A. n-1 B. 2n-1 C. n+1 D. 2n+1 9. 在有 n 个结点的二叉排序树中查找一个键值，其最坏比较次数的数量级为 。 2 A. O(log n) B. O(n) C. O(nlog n) D. O(n ) 2 2 10. 下列序列中， 是执行第一趟快速排序后得到的序列（关键字为 字符串）。 A. [da,ax,eb,cd,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] 11.下列排序算法中， 算法在进行一趟相应的排序处理结束后不一定能 选出一个元素放到其最终位置上。 A. 直选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序 12.队列的操作原则是 。 A. 先进后出 B. 先进先出 C. 只能进行插入 D. 只能进行删 除 二、填空题： 1. 已知完全二叉树的第 5 层有 8 个结点(根结点在 1 层)，则其叶子