1、线性结构题1. 栈和队列的共同特点是( A )。(A) 只允许在端点处插入和删除元素(B) 都是先进后出 (C) 都是先进先出(D) 没有共同点 2. 以下数据结构中哪一个是非线性结构？( D )(A) 队列 (B) 栈 (C) 线性表 (D) 二叉树3. 设有一个二维数组 Amn，假设 A00存放位置在 644(10)，A22 存放位置在676(10)，每个元素占一个空间，问 A33(10)存放在( C )位置。脚注 (10)表示用10 进制表示。(A) 688 (B) 678 (C) 692 (D) 6964设某数据结构的二元组形式表示为 A=(D，R)，D=01，02，03，04，05，
2、06，07，08，09，R=r ，r=， ， ， ，则数据结构 A 是（ B ） 。(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构5下面程序的时间复杂为（ B ）for（i=1，s=0； inext=p-next；p-next=-s； (B) q-next=s； s-next=p；(C) p-next=s-next；s-next=p； (D) p-next=s；s-next=q；非线性结构1.具有 n(n0)个结点的完全二叉树的深度为 C 。() log 2(n) () log 2(n) () log2(n) +1 () log 2(n)+12.树最适合用来表示( C
3、)。(A) 有序数据元素 (B) 无序数据元素(C) 元素之间具有分支层次关系的数据 (D) 元素之间无联系的数据3.二叉树的第 k 层的结点数最多为( D ).(A) 2k-1 (B) 2K+1 (C) 2K-1 (D) 2 k-14设一棵完全二叉树有 700 个结点，则共有( D )个叶子结点。（A）200 （B）250 （C）300 （D）3505.若有 18 个元素的有序表存放在一维数组 A19中，第一个元素放 A1中，现进行二分查找，则查找 A3的比较序列的下标依次为 ( D )(A) 1，2，3 (B) 9，5，2，3(C) 9，5，3 (D) 9，4，2，36.对 n 个记录的文
4、件进行快速排序，所需要的辅助存储空间大致为( C )(A) O（1） (B) O（n） (C) O（1og 2n） (D) O（n2）7设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以 20 为基准记录的一趟快速排序结束后的结果为( A )。(A) 10，15，14，18，20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，218设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ） 。
5、(A) n，e (B) e，n (C) 2n，e (D) n，2e9设有 5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10 个记录关键字，则用下列（ B ）方法可以达到此目的。(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序10.下列四种排序中（ D ）的空间复杂度最大。(A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序11设一棵二叉树的深度为 k，则该二叉树中最多有（ D ）个结点。(A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-112设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36
6、，70) ，其中含有 5 个长度为 2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ） 。(A) 15，25，35 ，50，20，40 ，80，85，36，70(B) 15，25，35，50，80，20 ，85，40，70，36(C) 15，25，35，50，80，85 ，20，36，40，70(D) 15，25，35 ，50，80，20 ，36，40，70，8513设有序表中有 1000 个元素，则用二分查找查找元素 X 最多需要比较（ B ）次。(A) 25 (B) 10 (C) 7 (D) 114设某棵二叉树的高度为 10，则该二叉树上叶子结点最多有（ C
7、） 。(A) 20 (B) 256 (C) 512 (D) 102415在一个具有 n 个顶点的无向连通图中,要连通全部顶点至少需要（ C ）条边。 （A） n （B） n+1 （C） n-1 （D） n/216.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用 H（K）=K %9 作为散列函数，则散列地址为 1 的元素有（ D ）个，(A) 1 (B) 2 (C) 3 (D)417.设有 6 个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。(A) 5 (B) 6 (C) 7 (D) 818. 二叉排序树中左子树上所有结点的值均（ A ）根结点的
8、值。(A) (C) = (D) !=19. 设一组权值集合 W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ） 。(A) 129 (B) 219 (C) 189 (D) 22920.设某棵二叉树中只有度数为 0 和度数为 2 的结点且度数为 0 的结点数为 n，则这棵二叉中共有（ C ）个结点。(A) 2n (B) n+l (C) 2n-1 (D) 2n+l 21.设一组初始记录关键字序列为(Q，H ，C ，Y ，P，A ， M，S，R ，D，F，X) ，则按字母升序的第一趟冒泡排序结束后的结果是（ D ） 。(A)
9、F，H，C，D，P，A，M ，Q，R ，S ，Y，X(B) P， A，C ， S，Q，D，F，X ，R ，H ，M，Y(C) A，D ，C ，R，F，Q，M ，S ，Y ，P，H ，X(D) H，C，Q， P，A，M，S，R，D，F ，X，Y22.设用邻接矩阵 A 表示有向图 G 的存储结构，则有向图 G 中顶点 i 的入度为（B ） 。(A) 第 i 行非 0 元素的个数之和 (B) 第 i 列非 0 元素的个数之和(C) 第 i 行 0 元素的个数之和 (D) 第 i 列 0 元素的个数之和填空题：1. 设 F 和 R 分别表示顺序循环队列的头指针和尾指针，该队列最存储空间为 N 个，则判
10、断该循环队列为空的条件为_F=A_ ，判断队列为满时条件为 (R+1)%N=F 。2. 一个线性表是 n0 个数据元素 a1,a2,a3,an 的有限序列，表中每个数据元素，除第一个和最后一个外，有且仅有一个 直接前驱 和一个 直接后继 。3. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_0(1)_。4. 设输入序列为 1、2、3，则经过栈的作用后可以得到_5_种不同的输出序列。5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n 个结点的二叉树共有_2n_个指针域，其中有_n-1_个指针域是存放了地址，有
11、_n+1_个指针是空指针。6. 对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_ _个和_个。在一个具有 n 个顶点的无向完全图中，包含有_条边，在一个具有 n 个顶点的有向完全图中，包含有_条边。7. 在快速排序、堆排序、归并排序中，_归并_排序是稳定的。8. _中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序） 。9. 设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较_7_次就可以断定数据元素 X 是否在查找表中。10. 设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之
12、和为 d，则 e 和 d的关系为_e=d_。设某无向图中顶点数和边数分别为 n 和 e，所有顶点的度数之和为 d，则 e=_d/2_。11. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为_31,38,44,56,75,80,55,63_。12. 已知一有向图的邻接表存储结构如下：从顶点 1 出发，深度优先搜索（Dfs）的输出序列是 1,3,4,5,2 ，广度优先搜索（BFS）遍历的输出序列是 1,3,2,4,5假定一个线性表为(12,23,74,55,63,40)，若给出哈希函数 H（key）=Key % 4 条件进行划分，使得同一余
13、数的元素成为一个子表，则得到的四个子表分别为_、_、_和_。13.14. 设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则第 i 个结点的双亲结点编号为_i/2_，右孩子结点的编号为_2i+1_。15. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字 72 为基准的一趟快速排序结果为_。16. 设有向图 G 中有向边的集合 E=，则该图的一种拓扑序列为_1,4,2,3_。17. 设哈夫曼树中共有 n 个结点，则该哈夫曼树中有_0_个度数为 1 的结点。18. 设有向图 G 用邻接矩阵 Ann作为存储结构，则该邻接矩阵中第 i
14、行上所有元素之和等于顶点 i 的_行为出度_，第 i 列上所有元素之和等于顶点 i 的_行为入度_。19. 为了能有效地应用 HASH 查找技术，必须解决的两个问题是_构造好的 hash 函数_和_确定解决冲突方法_。20. 中序遍历二叉排序树所得到的序列是_有序_序列（填有序或无序） 。21. 折半查找有序表（4，6，12，20，28，38，50，70，88，100） ，若查找表中元素 20，它将依次与表中元素 28,6,12,20 比较大小。22. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 关系 一对多 ，图形结构中元素之间存在 多对多 关系。问答题1. 设某棵二叉树的
15、中序遍历序列为 DBEAC，前序遍历序列为 ABDEC，要求给出该二叉树的的后序遍历序列并画出该二叉树。2已知待散列的线性表为（36，15，40，63，22） ，散列用的一维地址空间为0.6 ，假定选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试：计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 63 设无向图 G（如右图所示） ，画出该图的最小生成树的结构，并写出该图的最小生成树边的集合及计算最小生成树各边上的权值之和。4已知序列（10，18，4，3，6，12，1，9，18*，8）请用快速排序写出每一趟排序的结果。5设一组初始记录关键字
16、序列为(45，80，48，40，22，78)，则分别给出第 4 趟直接选择排序和第 4 趟直接插入排序后的结果。6给定一组权值2，8，5， 4，3 ，构造相应的哈夫曼树。7下图所示的森林： (1) 求树（a）的先根序列和后根序列；（2）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)8设散列表的地址范围是 0.9 ，散列函数为 H（key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素 7、4、5、3、6、2、8、9 依次插入散列表的存储结构。四、算法填空题1. 折半查找算法：Int BinSrch(Record L,keyType k)/*在有序表 L 中折半查找其关键字等于 K 的元素，若找到，则函数值为该元素在表中的位置*/Low=1 High=L.length;While(Low0)/*若存在非 0 元素*/q=1;/*b 中当前行 */for(col=1;col= n ;col+)/*遍历 M 的列*/for(k=1;k=t;k+)if(ak.j=col)bq.i= (1) ;bq.j= (2) ;bq.val= (3) ;q+;
