软件技术基础总复习题及参考答案..docx

一、 选择题 软件技术基础 总复习题及参考答案1、 线性表若是采用链式存储结构时，要求内存中可用存储单元的地址 D 。 A、必须是连续的B、部分地址必须是连续的 C、一定是不连续的D、连续或不连续都可以 2、 栈和队列都是B。 A、顺序存贮的线性结构B、限制存取点的线性结构 C、链接存贮的线性结构D、限制存取点的非线性结构 3、 与线性表的链接存贮不相符合的特性是 C。 A、便于插、删运算B、存贮空间动态分配 C、需要连续的存贮空间 D、只能顺序查找 4、 设二叉树的根为第一层，则第 i 层上的结点数最多有B 。 ii A、２B、２+1C、２i -１D、２i -1 5、 如将一棵有 n 个结点的完全二叉树按顺序存放方式，存放在下标编号为 0, 1,…, n-1 的一维数组中，设某结点下标为 k(k0)，则其双亲结点的下标是 A。 A、(k-1)/2 B、(k+1)/2C、k/2 D、k-1 6、 由权值分别为 3,8,6,2,5 的叶子结点生成一棵霍夫曼树，它的带权路径长度为 A。 A、53B、48C、72D、24 7、 设 I 和 O 分别表示入栈和出栈操作，栈的初态和终态都为空，则下列操作序列 合法的有_ D_ _。 A、IOIOOIOI B、IOOIOIIO C、IIIOIOIOO D、IIOIIOOO 8、 二叉树的前序序列为 EFHIGJK，中序序列为 HFIEJKG，则二叉树的根为 C。 A、KB、G C、ED、H 9、 对有序表{ -1, 0, 1, 3, 4, 6, 8, 10, 12 }进行折半查找，则查找 12 需要 比较的次数为 B。 A、3B、4 C、5D、6 10、 在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与 p 之间插入结点 s， 则执行D。 A、s→link = p→link; p→link = s; B、p→link = s; s→link = q; C、p→link = s→link; s→link = p; D、q→link = s; s→link = p; 11、 一个栈的入栈序列为 a，b，c，则出栈序列不可能的是 C 。 A、c,b,a B、b,a,cC、c,a,b D、a,c,b 12、 如果将一棵有 n 个结点的完全二叉树按层次遍历次序，存放在下标编号为 0, 1, … , n-1 的一维数组中，设某结点下标为 k( k 0 )，如果其左孩子存在， 则其左孩子结点的下标是 C。 A、2k– 1 B、2k C、2k + 1 D、2k + 2 13、 用整数 5, 7, 3, 6, 4 作为五个树叶的权值，可以构造一棵带权路径长度值为 C的霍夫曼树。 A、78 B、62 C、57 D、25 14、 设单链表中结点结构为(data,link)，若想删除结点*p 的直接后继，则应执行 下列哪一个操作A。 A、p-link=p-link-link; B、p=p-link; p-link=p-link-link; C、p-link=p-link; D、p=p-link-link; 15、 顺序表是线性表的B。 A、链式存储结构 B、顺序存储结构C、索引存储结构 D、散列存储结构 16、 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用A存储方式最节省时间。 A、顺序表 B、单链表 C、双链表 D、单循环链表 17、 当利用大小为 n 的数组顺序存储一个栈时，假定用 top= =n 表示栈空，则向这 个栈插入一个元素时，首先应执行B语句修改 top 指针。 A、top++;B、top--; C、top=0;D、top; 18、 对于任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点为 n2.,则 A A、n0= n2+1 B、n2= n0+1C、n0= 2n2+1 D、n2=2n0+1 19、 具有 35 个结点的完全二