软件技术基础试题库.doc

1、软件技术基础试题库 软件技术基础 试题库 课程名称： 软件技术基础 适用专业：软件技术 、计算机应用、网络、信息等计算机相关 专业 第一章 概述 第二章 数据结构 一、单项选择题 1若长度为 n 的线性表采用顺序存储结构，删除它的第 i 数据元素之前，需要先依次向前移动 _个数据元素。 ( ) A. n-i B. n+i C. n-i-1 D. n-i+1 答案： A 2在单链表中，已知 q 指的结点是 p 指的结点的直接前驱结点，若在 q 和 p 指的结点之间插入一个由 s 指的结点，则需执行 _。 ( ) A. link(s)link(p) ， link(p)s B. link(q)s ，

2、 link(s)p C. link(p)link(s) ， link(s)p D. link(p)s ， link(s)q 答案： B 3 高度为 h(h0) 的二叉树 最少 有 _个结点 。（ ） A. h B. h-1 C. h+1 D. 2h 软件技术基础试题库 答案： A 4 n 个顶点的带权无向连通图的最小生成树包含 _ 个顶点 。（ ） A.n-1 B.n C.n/2 D.n+1 答案： B 5 采用拉链法解决冲突的散 列表中，查找的平均查找长度 ( )。 A. 直接与关键字个数有关 B. 直接与装填因子 a 有关 C. 直接与表的容量有关 D. 直接与散列函数有关 答案： D 6

3、 树型结构最适合用来描述 ( ) A.有序的数据元素 B.无序的数据元素 C.数据元素之间的具有层次关系的数据 D.数据元素之间没有关系的数据 答案： C 7 若二叉树中度为 2 的结点有 15 个，度为 1 的结点有 10 个 _个叶结点。 ( ) A.25 B. 10 C.16 D.41 答案： C 度 0 的结点比度 2 的结点多 1 8 若深度为 6 的完全二叉树的第 6 层有 3 个叶结点，则该二叉树一共有 _个结点。 ( ) A.32 B. 33 C.34 D.25 答案： C 9 若某完全二叉树的深度为 h，则该完全二叉树中至少有 _个结点。 ( ) A.2h 软件技术基础试题库

4、 B.2h-1 C.2h-2 D.2h-1+1 答案： C 10 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该 ( ) A.只有左子树上的所有结点 B.只有左子树上的部分结点 C.只有右子树上的所有结点 D.只有右子树上的部分结点 答案： A 11 下面关 于哈夫曼树的说法， 不正确 的是 ( ) A.对应于一组权值构造出的哈夫曼树一般不是唯一的 B.哈夫曼树具有最小带权路径长度 C.哈夫曼树中没有度为 1 的结点 D.哈夫曼树中除了度为 1 的结点外，还有度为 2 的结点和叶结点 答案： D 12数据结构是一门研究计算机中 对象及其关系的学科。 ( ) A. 数值运算 B.非数值运

5、算 C.集合 D.非集合 答案： B 13数据结构的定义为 (K， R)，其中 K 是 的集合。 ( ) A.算法 B.数据元素 C.数据操作 D.逻辑结构 答案： B 14 算法 分析的目的是 _。 ( ) A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答案： C 软件技术基础试题库 15 数据的不可分割的基本单位是 。 ( ) A.元素 B.结点 C.数据类型 D.数据项 答案： D 16 是具有相同特性数据元素的集合，是数据的子集。 ( ) A.数据符号 B.数据对象 C.数据 D.数据结构 答案： B 17数据结构是

6、研究数据的 及它们之间的相互联系。 （ ） A.理想结构 、 物理结构 B.理想结构 、 逻辑结构 C.物理结构 、 逻辑结构 D.抽象结构 、 逻辑结构 答案： C 18 组成数据的基本单位是 。 （ ） A.数据项 B.数据类型 C.数据元素 D.数据变量 答案： C 19数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为 。（ ） A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 答案： C 20 算法指的是 。（ ） A计算机程序 B解决问题的计算方法 C排序算法 软件技术基础试题库 D解决问 题的有限运算序列 答案： D 21. 由 _组成的集合是一个

7、数据对象。 ( ) A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素 答案： D 22关于顺序存储的叙述中 ,哪一条是不正确的 。 ( ) A.存储密度大 B.逻辑上相邻的节点物理上不必邻接 C.可以通过计算直接确定第 i 个节点的位置 D.插入、删除操作不方便 答案： B 23一个向量第一个元素的存储地址是 100 ，每个元素的长度为 2 ，则第 5 个元素的地址是 。（ ） A.110 B. 108 C.100 D.120 答案： B 24已知一个顺序存储的线性表，设每个结点需要占 m 个存储单元，若第一个结点的地址为 da，则第 i 个结点的地址

8、为 。（ ） A.da+(i-1)*m B. da+i*m C.da-i*m D.da+(i+1)*m 答案： A 25链表是一种采用 存储结构存储的线性表 。（ ） A.顺序 B.链式 C.星式 D.网状 答案： B 26线性表若采用链式存储结构时，要求内存中可用存储单元的地址 。（ ） 软件技术基础试题库 A.必须 是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续或不连续都可以 答案： D 27线性表在 情况下适用于使用链式结构实现。 ( ) A.需经常修改中的结点值 B.需不断对进行删除插入 C.中含有大量的结点 D.中结点结构复杂 答案： B 28在长度为 n 的顺序表

9、的第 i (1in+1) 个位置上插入一个元素，元素的移动次数为 。（ ） A.n-i+1 B.n-i C.i D.i-1 答案： A 29线性表是 。（ ） A.一个有限系列，可以为空 B.一个有限系列，不能为空 C.一个无限系列，可以为空 D.一个无限系列，不能为空 答案： A 30. _是线性表。 ( ) A.(孔子 ,诸葛亮 ,曹雪芹 ) B.A,B,C,D C.10,11,12,13,14 D.(1,2,3,.) 答案： A 31. _ 是表示线性数据结构的。 ( ) A.循环链表 B.邻接多重表 C.孩子链表 D.单链表 答案： D 32. 将线性表的数据元素以 _结构存放 , 查

10、找一个数据元素所需时间不依赖于表长。 ( ) 软件技术基础试题库 A.循环双链 表 B.哈希 (Hash)表 C.一维数组 D.单链表 答案： C 33. 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行 _。( ) A.s-link=p;p-link=s; B. s-link=p-link;p-link=s; C.s-link=p-link;p=s; D.p-link=s;s-link=p; 答案： 34. 在循环链表中 first 为指向链表表头的指针， current 为链表当前指针，在循环链表中检测current 是否达到链表表尾的语句是 _。 (

11、) A.current-link=NULL B. first-link=current C.first=current D.current-link=first 答案： 35. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均比较 _个结点。 ( ) A.N B. n/2 C.(n-1)/2 D.(n+1)/2 答案： 36. 用链表表示线性表的优点是 _。 ( ) A. 便于随机存取 B. 花费的存储空间比顺序表少 C. 便于插入与删除 D. 数 据元素的物理顺序与逻辑顺序相同 答案： 37. 当需要随机查找线性表的元素时 ,宜采用 _作存储结构。 ( )

12、 A.双向链表 B.循环链表 C.顺序表 D.单链表 答案： 38. 线性表的链接实现有利于 运算。 ( ) 软件技术基础试题库 A.插入 B.读表元 C.查找 D.定位 答案： 39. 线性表采用链式存储时，其地址 _。 ( ) A.必须是连续的 B.部分地址是连续的 C.一定是不连续的 D.连续与否均可以 答案： 40. 设单链表中指针 p 指着结点 a，若要删除 a 之后的结点（若存在） ，则需要修改指针的操作为 _。 ( ) A.p-next=p-next-next B. p=p-next C.p= p-next-next D.p-next=p 答案： A 41. 向一个有 127 个

13、元素顺序表中插入一个新元素并保存原来顺序不变，平均要移动 个元素。 ( ) A.64 B.63.5 C.63 D.64.5 答案： A 42. 向一个有 127 个元素的顺序表中删除一个元素，平均要移动 个元素 。 ( ) A.8 B.63.5 C.63 D.7 答案： C 43 _又称为 FIFO 表。 ( ) A.队列 B.散列表 软件技术基础试题库 C.栈 D.哈希表 答案： A 44 设依次进入一个栈的元素序列为 c,a,b,d,不可得到出栈的元素序列有 _。 ( ) A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b 答案： D 45. 链式栈与顺序栈相比

14、，一个比较明显的优点是 _。 ( ) A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便 答案： 46. 在一个顺序存储的循环队列中，队头指针指向队 头元素的 _。 ( ) A. 前一个位置 B. 后一个位置 C. 队头元素位置 D. 队尾元素的前一位置 答案： 47. 若一个栈的输入序列是 1， 2， 3n ，则输出序列的第一个元素是 n，则第 i 个输出元素是 _。 ( ) A.n-i B.i C.n-i+1 D.n-i-1 答案： C 48. 栈的数组表示中， top 为栈顶指针，栈空的条件是 _。 ( ) A.top=0 B. top

15、=maxSize C.top=maxSize D.top=-1 答案： D 软件技术基础试题库 49. 在数组表示的循环队列中， front、 rear 分别为队列的头、尾指针， maxSize 为数组的最大长度，队满的条件是 _。 ( ) A.front=maxSize B. (rear+1)%maxSize=front C.rear=maxSize D.rear=front 答案： B 50. 栈和队列的共同特点是 _。 ( ) A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除 D.没有共同点 答案： C 51若非空队列采用链式存储结构， front 和 rear 分别为队

16、头元素与队列尾元素的指针，删除此时队列的一个元素 的操作时依次执行 pfront ， _ ， call RET(P)。 ( ) A.frontlink(rear) B.rearlink(p) C.rearlink(front) D.frontlink(p) 答案： 52由两个栈共享一个向量空间的好处是 _。 ( ) A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率 C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率 答案： 53 数组 datam为循环队列的存储空间 , front 为队头指针 , rare 为队尾指针 ,则执行入队的操作为 _。 ( ) A.rare=rare+1 B.rare=(rare+1)%(m-1) C.rare=(rare-1)%m D.rare=(rare+1)%m 答案： D 54. 将递归算法转换成对应的非递归算法时，通常需要使用 _。 ( )