发布时间 : 星期四 文章数据结构专升本模拟题及参考答案更新完毕开始阅读
算法的易懂性和文档性
5. 下面程序段的时间复杂性的量极为（ ）。 Int fun(int n) { int i=1,s=1; While(s 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的元素时需要比较元素和移动元素的总次数为（ ）。 ． O(n/2) 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和 B A C D E Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。 4. 已知完全二叉树的第8层有8个结点，则其叶子结点是多少？ 5. 画出如图所示中树的二叉树的表示形式。 作业题（四） 一、单项选择题 1. 将两个各有n个元素的有序表归并成一个有序表，其最少得比较次数是（ ）。 A ． n