一、选择题(20分)
1．下面关于线性表的叙述错误的是（ D  ）。
    (A) 线性表采用顺序存储必须占用一片连续的存储空间   
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A  ）。
    (A) BADC    (B) BCDA    (C) CDAB    (D) CBDA
3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。
    (A) 9    (B) 10    (C) 11    (D) 12
4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查长度为（ B ）。
    (A) O(1)    (B) O(log2n)    (C)    (D) O(n2)
5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ B ）方法可以达到此目的。
    (A) 快速排序    (B) 堆排序    (C) 归并排序    (D) 插入排序
第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。
6.下列四种排序中（ D ）的空间复杂度最大。
    (A) 插入排序    (B) 冒泡排序    (C) 堆排序    (D) 归并排序
7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C  ）。
    (A) O(n)    (B) O(nlog2n)    (C) O(1)    (D) O(n2)
8．设一棵二叉树的深度为k，则该二叉树中最多有（D  ）个结点。
    (A) 2k-1    (B) 2k    (C) 2k-1    (D) 2k-1
9．在二叉排序树中插入一个结点的时间复杂度为（B  ）。
    (A) O(1)    (B) O(n)    (C) O(log2n)    (D) O(n2)
10．设用链表作为栈的存储结构则退栈操作（ B ）。
    (A) 必须判别栈是否为满    (B) 必须判别栈是否为空
    (C) 判别栈元素的类型    (D) 对栈不作任何判别
11．下列四种排序中（A  ）的空间复杂度最大。
    (A) 快速排序    (B) 冒泡排序    (C) 希尔排序    (D) 堆
12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。
    (A) N0=N1+1    (B) N0=Nl+N2    (C) N0=N2+1    (D) N0=2N1+l
13.设有序顺序表中有n个数据元素，则利用二分查法查数据元素X的最多比较次数不超过（A  ）。
    (A) log2n+1    (B) log2n-1    (C) log2n    (D) log2(n+1)
14．数据的最小单位是（ A ）。
    (A) 数据项    (B) 数据类型    (C) 数据元素    (D) 数据变量
15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D ）。
    (A) O(log2n)    (B) O(1)    (C) O(n2)    (D) O(n)
16．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（B  ）。
    (A) Nl+N2+……+Nm        (B) l+N2+2N3+3N4+……+(m-1)Nm
    (C) N2+2N3+3N4+……+(m-1)Nm    (D) 2Nl+3N2+……+(m+1)Nm
17．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（C  ）。
    (A) n-i    (B) n-1-i    (C) n+1-i        (D) 不能确定
18．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ A ）。
    (A) 堆排序    (B) 冒泡排序    (C) 希尔排序    (D) 快速排序
19．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D  ）。
    (A) 空或只有一个结点    (B) 高度等于其结点数
    (C) 任一结点无左孩子    (D) 任一结点无右孩子
20．顺序查不论在顺序线性表中还是在链式线性表中的时间复杂度为（A  ）。
    (A) O(n)    (B) O(n2)    (C) O(n1/2)    (D) O(1og2n)
21．二路归并排序的时间复杂度为（ C ）。
    (A) O(n)    (B) O(n2)    (C) O(nlog2n)    (D) O(1og2n)
22. 深度为k的完全二叉树中最少有（B  ）个结点。
    (A) 2k-1-1    (B) 2k-1    (C) 2k-1+1    (D) 2k-1
23.设二叉排序树上有n个结点，则在二叉排序树上查结点的平均时间复杂度为（D  ）。
    (A) O(n)    (B) O(n2)    (C) O(nlog2n)    (D) O(1og2二叉树公式n)
24．（ B ）二叉排序树可以得到一个从小到大的有序序列。
    (A) 先序遍历    (B) 中序遍历    (C) 后序遍历    (D) 层次遍历
25．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（B  ）。
    (A) 2i+1    (B) 2i    (C) i/2    (D) 2i-1
26．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（A  ）。
    (A) O(n)    (B) O(nlog2n)    (C) O(n2)    (D) O(n3/2)
27.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ D ）。
    (A) top=top+1;        (B) top=top-1;
    (C) top->next=top;    (D) top=top->next;
28.建立一个长度为n的有序单链表的时间复杂度为（ C ）
    (A) O(n)    (B) O(1)    (C) O(n2)    (D) O(log2n)
29.在二叉排序树中插入一个关键字值的平均时间复杂度为（ B ）。
    (A) O(n)    (B) O(1og2n)    (C) O(nlog2n)    (D) O(n2)
30.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。
    (A) 8    (B) 7    (C) 6    (D) 5
31.队列是一种（A  ）的线性表。
    (A) 先进先出    (B) 先进后出    (C) 只能插入    (D) 只能删除
32.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ C ）。
  (A) O(n)    (B) O(nlog2n)    (C) O(n2)    (D) O(1og2n)
33．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D  ）。
    (A) p->right=s； s->left=p； p->right->left=s； s->right=p->right；
    (B) s->left=p；s->right=p->right；p->right=s； p->right->left=s；
    (C) p->right=s； p->right->left=s； s->left=p； s->right=p->right；
    (D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；
34.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。
A．edcba B．decba C．dceab D．Abcde
A：a,b,c,d,e进，之后依次出栈
B：a,b,c,d,进，d出，e进，e,c,b,a出
D：a进a出，b进b出……e进e出
C：的话dce都好办，之后的ab做不到
这道题就是没告诉你进栈的同时可以随时出栈==
二、填空题
1.数据的物理结构主要包括顺序存储结构和链式存储结构两种情况。
2.数据结构从逻辑上划分为三种基本类型：线性结构、树型结构和图型结构。
3.
4.公式：二维数组A中任一元素aij的存储位置：（LOC（0，0）是a00的存储位置）
    LOC(i，j)=LOC（0，0）+（b2*i+j）L
5.快速排序的时间性能分析
最好情况：
每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。
最坏情况：
每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。
                     
平均情况：为O(nlog2n)。
6.在快速排序、堆排序、归并排序中，___归并______排序是稳定的。
7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_O(log2n)_____，整个堆排序过程的时间复杂度为___ O(nlog2n)_____。
8.快速排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(nlog2n)。
9.散列表中解决冲突的两种方法是开放定址法和链地址法。
10.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择___快速_____排序，如果从节省存储空间的角度来考虑则最好选择__堆______排序。
三、判断题
全对或全错得5分
1．调用一次深度优先遍历可以访问到图中的所有顶点。（×  ）
2．分块查的平均查长度不仅与索引表的长度有关，而且与块的长度有关。（ √ ）
3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（√  ）
4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ √ ）
5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ×  ）
6．层次遍历初始堆可以得到一个有序的序列。（×  ）
7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ √ ）
8．线性表的顺序存储结构比链式存储结构更好。（ ×  ）
9．中序遍历二叉排序树可以得到一个有序的序列。（ √ ）
10.快速排序是排序算法中平均性能最好的一种排序。（√  ）
11．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（√  ）
12．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ √  ）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。