学习资料
C．可读性和文档性 D．数据复杂性和程序复杂性 4．算法分析的目的是（ ）。
A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 5. 下面程序段的时间复杂性的量极为（ ）。 Int fun(int n) { int i=1,s=1; While(s A．O(n/2) B．O(lbn) C．O(n) D．O( ) 6. 线性表是（ ）。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 7. 带头结点的单链表L为空的判定条件是（ ）。 A．L= =NULL B．L-〉next= =NULL C．L-〉next= =L D．L! =NULL 8. 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。 A．（n+1）/2 B．n/2 C．n D．n+1 9. 一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ ）。 A．98 B．100 C．102 D．106 10. 如果某链表中最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。 A．单链表 B．双向链表 C．单循环链表 D．顺序表 二、填空题 1. 高度为2的二叉树的结点数至少有________个，高度为3的二叉树的结点数至少有________个。 2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找关键字值20，需做的关键字比较次数为________。 3.在有n个顶点的无向图中，每个顶点的度最大可达________。 4．已知广义表A=（（a，b，c），（d，e，f）），则广义表运算head（tail（tail（A）））= 。 5、数组（Array）是n（n≥1）个 的有序组合，数组中的数据是按顺序存储在一块 的存储单元中。 6. 采用顺序存储结构表示三元组表（Triple Table），来实现对稀疏矩阵的一种压缩存储形式，就称仅供学习与参考 学习资料 为 ，简称 表。 7. 运算是矩阵运算中最基本的一项，它是将一个m x n的矩阵变成另外一个n x m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。 三、应用题 1、对于下图所示的二叉树，画出二叉链表存储结构图。 2、请画出下图所示的树所对应的二叉树。 3. 已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。 B A C D E 4. 已知完全二叉树的第8层有8个结点，则其叶子结点是多少？ 5. 画出如图所示中树的二叉树的表示形式。 仅供学习与参考 学习资料 作业题（四） 一、单项选择题 1. 将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（ ）。 A．n B．2n-1 C．2n D．n-1 2. 一个有n个顶点的无向连通图，它所包含的连通分量个数为（ ）。 A．0 B．1 C．n D．n+1 3. 数据文件的基本操作中最重要的操作是（ ）。 A．插入 B．删除 C．修改 D．检索 4. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（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. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ A．堆排序 B．快速排序 C．插入排序 D．归并排序 6．算法分析的目的是（ ）。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 7. 二叉树的第I层上最多含有结点数为（ ） A．2I B． 2I-1 -1 C． 2I-1 D．2I -1 8．循环队列存储在数组A中，长度为m，则入队时的操作为（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 9. 广义表满足Head(A)=Tail(A)，则A为（ ）。 A．（） B．（（）） C．（（），（）） D．（（），（），（）） 仅供学习与参考 ）。 方法最快。 ） 学习资料 10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。 A．3 B．4 C．5 D．6 二、填空题 1. 在一个循环队列中，队首指针指向队首元素的_________。 2. 数组中每一个数据通常称为 ， 用下标区分，其中下标的个数由数组的 决定。 3. 一个图的 表示法是唯一的，而 表示法是不唯一的。 4. 在一个10阶的B-树上，每个数根结点中所含的关键字数目最多允许 个，最少允许 个 5. 对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后的得到结果为 。 10.高度为1的平衡二叉树的结点数至少有________个，高度为2的平衡二叉树的结点数至少有________个。 三 判断 1. 顺序存储结构属于静态结构，链式结构属于动态结构。 （ ） 2. 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。 （ ） 3. 带权无向图的最小生成树必是唯一的。（ ） 4. B-树和B+树都可用于文件的索引结构。（ ） 5. 在用堆排序算法排序时，如果要进行增序排序，则需要采用\大根堆\。（ ） 四、应用题 1. 模式串p=\的next函数值序列为多少？ 2. 设二维数组A[5][6]的每个元素占4个字节，已知LOC（a0,0）=1000，A共占多少个字节？A的终端结点a4,5的起始地址为多少？按行和按列优先存储时，a2,5的起始地址分别为多少？ 3. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。 （1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。写出上述各关键字在表中位置。 仅供学习与参考 学习资料 4. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？ 作业题（五） 一、单项选择题 1. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 A．(38,40,46,56,79,84) C．（40,38,46,56,79,84) 2．广义表 B．(40,38,46,79,56,84) D．(40,38,46,84,56,79) A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 GetHead(GetTail(GetHead(GetTail(GetTail(A))))) A. (g) B. (d) C. c D. d 3．对于有n 个结点的二叉树, 其高度为（ ） A．nlog2n B．log2n C．?log2n?+1 D．不确定 4. 如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是（ ）。 A．1 3 5 4 2 6 7 C．1 5 3 4 2 7 6 B．1 3 4 7 6 2 5 D．1 2 4 7 6 5 3 5. 采用邻接表存储的图，其深度优先遍历类似于二叉树的（ ）。 仅供学习与参考
数据结构专升本模拟题及参考答案讲课讲稿
