软件技术基础试题库.docx

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

2、k(p)s，link(s)q答案：B3高度为h(h0) 的二叉树最少有_个结点。（ ）A. hB. h-1 C. h+1D. 2h答案：A4n个顶点的带权无向连通图的最小生成树包含 _ 个顶点。（ ）A.n-1 B.n C.n/2 D.n+1答案：B5采用拉链法解决冲突的散列表中，查找的平均查找长度( )。A. 直接与关键字个数有关 B. 直接与装填因子 a 有关 C. 直接与表的容量有关 D. 直接与散列函数有关答案：D6树型结构最适合用来描述( )A.有序的数据元素 B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：C7若二叉树中度为2的结点有15个

3、，度为1的结点有10个_个叶结点。( )A.25 B.10C.16 D.41答案：C 度0的结点比度2的结点多18若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有_个结点。( )A.32 B.33C.34 D.25答案：C9若某完全二叉树的深度为h，则该完全二叉树中至少有_个结点。( )A.2h B.2h-1C.2h-2D.2h-1+1答案：C10在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该( )A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点 D.只有右子树上的部分结点答案：A11下面关于哈夫曼树的说法，不正确的是( )A.对应于一组权值构

4、造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点答案：D12数据结构是一门研究计算机中 对象及其关系的学科。( )A. 数值运算B.非数值运算C.集合D.非集合答案：B13数据结构的定义为(K，R)，其中K是 的集合。( )A.算法B.数据元素C.数据操作D.逻辑结构答案：B14算法分析的目的是_。( )A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答案：C15数据的不可分割的基本单位是 。( )A.元素B.结点C.数据类型D.数据项

5、答案：D16 是具有相同特性数据元素的集合，是数据的子集。( )A.数据符号B.数据对象C.数据D.数据结构答案：B17数据结构是研究数据的 及它们之间的相互联系。（ ）A.理想结构、物理结构B.理想结构、逻辑结构C.物理结构、逻辑结构D.抽象结构、逻辑结构答案：C18组成数据的基本单位是 。（ ）A.数据项B.数据类型C.数据元素D.数据变量答案：C19数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称为 。（ ）A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构答案：C20算法指的是 。（ ）A计算机程序B解决问题的计算方法C排序算法D解决问题的有限运算序列答案：D2

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

7、.da+i*mC.da-i*mD.da+(i+1)*m答案：A25链表是一种采用 存储结构存储的线性表。（ ） A.顺序B.链式C.星式D.网状答案：B26线性表若采用链式存储结构时，要求内存中可用存储单元的地址 。（ ）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以答案：D27线性表在 情况下适用于使用链式结构实现。 ( )A.需经常修改中的结点值B.需不断对进行删除插入C.中含有大量的结点D.中结点结构复杂答案：B28在长度为 n 的顺序表的第 i (1in+1) 个位置上插入一个元素，元素的移动次数为 。（ ）A.n-i+1B.n-iC.iD.i-1答案

8、：A29线性表是 。（ ）A.一个有限系列，可以为空B.一个有限系列，不能为空C.一个无限系列，可以为空D.一个无限系列，不能为空答案：A30. _是线性表。( )A.(孔子,诸葛亮,曹雪芹)B.A,B,C,DC.10,11,12,13,14D.(1,2,3,.)答案：A31. _ 是表示线性数据结构的。( )A.循环链表B.邻接多重表C.孩子链表D.单链表答案：D32. 将线性表的数据元素以_结构存放, 查找一个数据元素所需时间不依赖于表长。( )A.循环双链表B.哈希(Hash)表C.一维数组D.单链表答案：C33. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行

9、_。( )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是否达到链表表尾的语句是_。( )A.current-link=NULLB.first-link=currentC.first=currentD.current-link=first答案：35. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_个结点。( )A.NB.

10、n/2C.(n-1)/2D.(n+1)/2答案：36. 用链表表示线性表的优点是_。 ( ) A. 便于随机存取B. 花费的存储空间比顺序表少C. 便于插入与删除D. 数据元素的物理顺序与逻辑顺序相同答案：37. 当需要随机查找线性表的元素时,宜采用_作存储结构。( )A.双向链表B.循环链表C.顺序表D.单链表答案：38. 线性表的链接实现有利于 运算。( )A.插入B.读表元C.查找D.定位答案：39. 线性表采用链式存储时，其地址_。 ( ) A.必须是连续的B.部分地址是连续的C.一定是不连续的D.连续与否均可以答案：40. 设单链表中指针p指着结点a，若要删除a之后的结点（若存在），

11、则需要修改指针的操作为_。 ( ) A.p-next=p-next-nextB.p=p-nextC.p= p-next-nextD.p-next=p答案：A41. 向一个有127个元素顺序表中插入一个新元素并保存原来顺序不变，平均要移动 个元素。( )A.64B.63.5C.63D.64.5答案：A42. 向一个有 127 个元素的顺序表中删除一个元素，平均要移动 个元素。( )A.8B.63.5C.63D.7答案：C43_又称为FIFO表。( )A.队列B.散列表C.栈D.哈希表答案：A44设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_。( )A.a.b,c,dB.a

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

13、p=maxSizeC.top=maxSizeD.top=-1答案：D49. 在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是_。( )A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front答案：B50. 栈和队列的共同特点是_。( )A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除D.没有共同点答案：C51若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除此时队列的一个元素的操作时依次执行pfront，_ ，

14、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+1B.rare=(rare+1)%(m-1)C.rare=(rare-1)%mD.rare=(rare+1)%m答

15、案：D54. 将递归算法转换成对应的非递归算法时，通常需要使用_。( )A.栈B.队列C.链表D.数组答案：55高度为 h(h0) 的二叉树最少有 _ 个结点。( )A.hB.h-1C.h+1D.2h答案：A56树型结构最适合用来描述_。( )A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据答案：C57有n(n0)个结点的完全二叉树的深度是_。( )A. log2(n)B. log2(n)+1C.log2(n+1)D. log2(n)+1答案：BD58. _ 又是一棵满二叉树。( )A.二叉排序树B.深度为5有31个结点的二叉树C.有15个

16、结点的完全二叉树D.哈夫曼(Huffman)树(没有度为1的结点)答案：C59. 深度为k的满二叉树有_个分枝结点。( )A.2k-1B.2k-1-1C.2k+1D.2k-1+1答案：60. 若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为_。( )A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE答案：A61. 二叉树第i(i=1)层上至多有 结点。( )A.iB.iC.iD.i答案：C62. 在一棵具有5层的满二叉树中结点总数为_。( )A. 31B. 32C. 33D. 16答案：A63. 一个二叉树按顺序方式存储在一个维数组中，如

17、图0 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第 层。( )A.1 B.2 C.3 D.4答案：C64在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为_。( )A4B5C6D7答案：C65n 个顶点的带权无向连通图的最小生成树包含 _ 个顶点。( )A.n-1B.nC.n/2D.n+1答案：B66具有 n 个顶点的有向完全图有 条弧。( )A.nB.n*(n-1)C.n*(n+1)D.n*n答案：B67. n 个顶点的连通图至少有 条边。( )A.n-1 B.n C.n+1 D.0答案：68在一

18、个有向图中，所有顶点的入度之和等于所有顶点出度之和的 倍。( )A1/2B1C2D4答案：69在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为_。( )AeB2eCn2eDn22e答案：D70折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素_进行比较。( )A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37答案：D71对有3600个记录的索引顺序表(分块表)进行查找,最理想的块长为_。( )A.1800B.60C.1200D. log2 3600 答案：B72. 折半查找20个记录的有序表,

19、若查找失败,比较关键字的次数_。( )A.最多为6B.最多为5C.最多为4D.最多为3答案：B73. 中序遍历一棵二叉排序树所得到的结点序列是键值的 序列。( )A.递增或递减B.递减C.递增D.无序答案：C74散列表中的冲突是指_。( )A.两个元素具有相同的序号B.两个元素的键值相同，而其他属性相同C.不同的键值对应相同的存储地址D.数据元素的地址相同答案：75用线形探测法查找散列表，可能要探测多个散列地址，这些位置上的键值_。( )A.一定是同义词B.不一定是同义词C.一定不是同义词D.都相同答案：76在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT

20、，SUN), 杂凑函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为0:6，采用线性再散列法处理冲突。插入后的杂凑表应该如_所示。( )A. 0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6 TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON答案：77设有一个含200个表项的散列表，用线性探查法解决冲突，按关

21、键码查询时找到一个表项的平均探查次数不超过1.5，则散列存储空间应能够至少容纳 个表项。（设搜索成功的平均搜索长度为Snl=(1+1/(1-a)/2,其中a 为装填因子）( )A.400B.526C.624D.676答案：78对长度为10的表作选择(简单选择)排序,共需比较_次关键字。( )A.45B.90C.55D.110答案：79. 设有100个数据元素，采用折半搜索时，最大比较次数为 ( )。A. 6B. 7C. 8D. 10答案：A80. 对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是_。( )

22、A. 选择排序B. 直接插入排序C. 快速排序D. 起泡排序答案：C81. 对5个不同的数据元素进行直接插入排序，最多需要进行 次比较。( )A. 8B. 10C. 15D. 25答案：82. 采用折半查找方法进行查找，数据文件应为 ，且限于 。( )A.有序表 顺序存储结构B.有序表 链式存储结构C.随机表 顺序存储结构D.随机表 链式存储结构答案：A83. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其存放在已排序序列的合适位置，该排序方法称为 排序法。( )A.插入B.选择C.希尔D.二路并归答案：A84. 就平均查找速度而言，下列几种查找速度从慢至快的关系是

23、。( )A.顺序 折半 哈西 分块B.顺序 分块 折半 哈西C.分块 折半 哈西 顺序D.顺序 哈西 分块 折半答案：B85. 在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。( )A.堆排序B.冒泡排序C.插入排序D.快速排序答案：C86堆是一个键值序列( K1, K2, , Kn )，对 I = 1,2n/2, 满足 。( )A.Ki = K2i = K2i+1B.Ki K2i+1 K2i C.Ki = K2i 且 Ki =K2i+1D. Ki = K2i 或 Ki = K2i+1答案：87对于关键字序列 46 ， 58 ， 15 ， 45 ， 9

24、0 ， 18 ， 10 ， 62 ，其快速排序第一趟的结果是 。( )A.15 45 18 46 10 62 58 90B.10 15 18 45 46 58 62 90C.10 18 15 45 46 90 58 62D.15 10 18 45 46 62 58 90答案：88用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是 。( )A.选择排序B.希尔

25、排序C.归并排序D.快速排序答案：89下列关键字序列中 是堆。( )A16，72，31，23，94，53B94，23，31，72，16，53C16，53，23，94，31，72D16，23，53，31，94，72答案：90目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是 。( )A插入排序 B直接选择排序C快速排序 D冒泡排序答案：B91对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 。( )An+1 BnCn-1Dn(n-1)/2答案：D二、多项选择题1根据数据元素之间的不同特性，通常具有 这几种基本数据结构。( )A. 集合B. 线形结构C.

26、 树型结构D. 图型结构答案：ABCD2数据元素之间的关系在计算机中有 两种不同的表示方法。( )A. 顺序存储结构B. 二叉树存储结构C. 链式存储结构D. 网络结构答案：AC3查找哈希(Hash)表,解决冲突的的方法有_。( )A.除留余数法B.线性探测再散列法C.直接地址法D.链地址法答案：BD三、判断题1非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( )答案：F2数组是一种没有插入与删除操作的线性结构。( )答案：T3非空线性表中任意一个数据元素都有且仅有一个直接后继元素。( )答案：F4数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。( )答案：F

27、5线性链表中各个链结点之间的地址不一定要连续。( )答案：T6若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。( )答案：F7.若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。( 100 )答案：F8.若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。( )答案：F9.符号link(p)出现在表达式中表示p所指的那个结点的内容。( )答案：F10.要将指针p移到它所指的结点的下一个结点是执行语句plink(p)。( )答案：T11.在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句：link(q)link(p);link(p)q。( )答案：T12.在非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为：llink(p)q,rlink(p)rli