计算机软件技术基础期中考试题.ppt

期中考试题 一、填空 1. 线性表是具有n个 的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 E. 信息项 2. 若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为 。（1≤I≤n+1） A. O(0) B. O(1) C. O(n) D. O(n2) 3 .一棵有124个叶结点的完全二叉树，最多有 个结点。 A. 247 B. 248 C. 249 D. 251 4.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为 ，至多为 。高为h的完全二叉树的结点数至少为 ，至多为 。 A． 2h B. 2h-1 C. 2h+1 D.h+1 E. 2h-1 F. 2h-1 G. 2h+1-1 H. 2h+1 5. Hash技术广泛应用于查找过程，选择Hash函数的标准是 和 。处理冲突的技术有优有劣，其共同标准是 。 6. 在下述排序算法中，所需辅助存储空间最多的是 ，所需辅助存储空间最小是 ，平均速度最快的是 。 A.快速排序 B. 归并排序 C. 堆排序 7. 阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中(从下标1处开始存储)，删除所有值相等的多余元素。 #define MAXSIZE 30 typedef struct{ int elem[MAXSIZE]; int length;/*表长*/ }sqlisttype; void exam21(sqlisttype *L){ int I,j; I=2,j=1; while( (1) ){ if(L-elem[I]L-elem[j]){ (2) ; (3) ;} I++;} (4) ;} 二、举例说明数据结构与算法的关系。 三、试写一算法，自大到小依次输出顺序读入 的三个数X、Y和Z的值。你的算法的执行 时间是多少？ 四、描述以下三个概念的区别：头指针、头结 点、首元结点。并说明头指针和头结点的 作用。 五、已知线性表中的元素以值递增有序排列，并 以单链表作存储结构。试写一高效的算法， 删除表中所有值大于Kmin且小于Kmax的 元素（若表中存在这样的元素），同时释 放被删除结点空间，并分析你的算法的时 间复杂度。 六、设有编号为1、2、3、4的四辆列车，顺序进 入一个栈式结构的站台，具体写出这四辆列 车开出站的所有可能的顺序。 七、二维数组A的元素是6个字符组成的串，行 下标i的范围从0到8，列下标j的范围从1到 10 。试问： 存放A至少需要多少字节？ A的第8列和第5行共占多少字节？ 若A按行存放，元素A[8，5]的起始地址与当A按列存放时的哪个元素的起始地址一致？（必须有计算分析过程） 八、试找出分别满足下面条件的所有二叉树： 先序遍历序列与中序遍历序列相同； 中序遍历序列与后序遍历序列相同； 先序遍历序列与后序遍历序列相同。 九、设有序序列中数据元素的关键字分别为 3,10,13,17,40,43,50,70.要求查找关键字 为43和5的元素,使用二分查找,写出其计 算步骤即每步的low,high,mind的值。 * *