1、全国自考（计算机软件基础）-试卷 8及答案解析(总分：62.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.与所使用的计算机无关的是数据的【 】结构。（分数：2.00）A.存储B.物理C.逻辑D.物理和逻辑2.数据的逻辑结构又分为 【 】（分数：2.00）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构3.在以下叙述中，不正确的是 【 】（分数：2.00）A.数据的逻辑结构是数据元素之间的逻辑关系，是依赖于计算机语言的B.存储结构不仅涉及数据元素的机内表示，还包括数据之间关联方式的表示C.顺序存储方式使用的是一段连续的
2、存储区D.算法的时间复杂度与算法中语句的频度有关4.某算法的时间复杂度为 O(n 2 )，表明该算法的 【 】（分数：2.00）A.问题规模是 n 2B.执行时间等于 n 2C.执行时间与 n 2 成正比D.问题规模与 n 2 成正比5.下列程序的功能是计算两个矩阵的乘积，其算法的时间复杂度是 【 】 void mul_matrix(int n，int a 5，int b 5，int c 5) int i，j，k，x； for(i=0；iA.O(n)B.O(log 3 n)C.O(n 2 )D.O(n 3 )6.下面程序段的时间复杂度为 【 】 for(int i=0；iA.O(m 2 )B.
3、O(n)C.0(m*n)D.O(m+n)7.已知指针 p和 q分别指向某单链表中第一个节点和最后一个节点。假设指针 s指向另一个单链表中某个节点，则在 s所指节点之后插入 p所指向的链表应执行的操作是 【 】（分数：2.00）A.q一next=s 一next；s 一next=p；B.s一next=p；q 一next=s 一nextC.p一next=s 一next；s 一next=q；D.s一next=q；p 一next=s 一next；8.在一个具有 n个节点的有序单链表中插入一个新节点并使其仍然有序的时间复杂度为 【 】（分数：2.00）A.O(1)B.O(n)C.O(n 2 )D.O(lo
4、g 3 n)9.在一个单链表中，已知 q所指节点是 p所指节点的前趋节点，若在 q和 p之间插入 s所指向的节点，则执行的操作是 【 】（分数：2.00）A.snext=pnext；pnext=s；B.qnext=s；snext=p；C.pnext=s；snext=q；D.pnext=snext；snext=p；10.设在一个单链表中指针 p指向节点 a，若要删除 a之后的一个节点(若存在)，则需执行的修改指针的操作为 【 】（分数：2.00）A.p一next=p 一next 一nextB.p=p一nextC.p=p一next 一nextD.next=p11.带头节点的单链表 heald为空的
5、判定条件是 【 】（分数：2.00）A.head=NULLB.headnext=NULLC.headnext=headD.head!=NULL12.按照 1、2、3、4、5 的次序依次入栈时，出栈序列不可能是 【 】（分数：2.00）A.1、2、3、4、5B.2、3、4、5、1C.5、4、3、2、1D.5、4、1、2、313.在一个链队列中，假设 f和 r分别为队头和队尾指针，则插入指针 s所指节点的运算是 【 】（分数：2.00）A.fnext=s；f=s；B.rnext=s；r=s；C.snext=r；r=s；D.s一next=f；f=s；14.假定一个顺序队列的队头和队尾指针分别用 fr
6、ont和 rear表示，则判断队列为空的条件是 【 】（分数：2.00）A.front+1=rearB.rear+1=frontC.front=0D.front=rear15.假定利用数组 aN顺序存储一个栈，用 top表示栈顶指针，top=一 1表示栈空，并已知栈未满，当元素 x进栈时所执行的操作为 【 】（分数：2.00）A.a-top=xB.atop-=xC.a+top=xD.atop+=x二、填空题(总题数：10，分数：20.00)16.在 C语言中，表示换行的转义字符是 1。（分数：2.00）填空项 1:_17.执行 for(j=k=0；j1。（分数：2.00）填空项 1:_18.已
7、知：char str15；str 数组的最后一个元素是 1。（分数：2.00）填空项 1:_19.数据的逻辑结构又分为两类：线性结构和 1。（分数：2.00）填空项 1:_20.n阶三对角阵压缩存储至少需要 1 个存储空间。（分数：2.00）填空项 1:_21.在带有表头节点的单链表 L中，若要删除第一个节点，则需执行的三条语句是： 1；L 一next=pnext；free(p)；。（分数：2.00）填空项 1:_22.对于一棵具有 n个节点的树，该树中所有节点的度数之和为 1。（分数：2.00）填空项 1:_23.拓扑排序是针对 1 图的。（分数：2.00）填空项 1:_24. 1是按某种顺
8、序将数据元素的无序序列调整成有序序列的过程。（分数：2.00）填空项 1:_25.黑盒测试法包括等价划分、 1 以及错误推测法等。（分数：2.00）填空项 1:_三、程序分析题(总题数：4，分数：8.00)26.以下程序是用来统计从键盘输入的一个正整数的各位数字中零的个数，并求各位数字中的最大者。例如：1080 的各位数字中零的个数是 2，各位数字中的最大者是 8。请将程序补充完整。 #includestdioh main() unsigned long num，max，t； int count； count=max=0； scanf(“old“，num)； do t=_； if(t=0)+c
9、ount； else if(maxt)max=t； num=10； while(num)； printf(“count=d，max=ldn“，count，max)； （分数：2.00）_27.下列程序的功能是输出 100以内能被 3整除且个位数为 6的所有整数，填空完成程序。 #include main() int i，j； for(i=0；i_28.下列程序的运行结果是_。 #include main() int i=1，j=1； for(；j10)break； if(j2!=0) j+=3； continue； j 一=1； printf(“d，dn“，i，j)； （分数：2.00）_29
10、.以下程序的输出结果是_。 #include main() int arr10，i，k=0； for(i=0；i_四、程序设计题(总题数：2，分数：4.00)30.从键盘输入任意一个 3位正整数(即在 100999 之间的整数)，求其各位上数字之和。如输入 123，则结果应输出 6(即 1+2+3=6)。（分数：2.00）_31.假设二叉树采用二叉链存储结构，设计一个算法把二叉树 b复制到二叉树 t中。（分数：2.00）_全国自考（计算机软件基础）-试卷 8答案解析(总分：62.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.与所使用的计算机无关的是数据的【 】
11、结构。（分数：2.00）A.存储B.物理C.逻辑 D.物理和逻辑解析：解析：数据的逻辑结构是从逻辑关系上描述数据，它与计算机存储无关，是独立于计算机的。2.数据的逻辑结构又分为 【 】（分数：2.00）A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构解析：解析：数据的逻辑结构是数据之间的外在联系，可以分为两类：线性结构和非线性结构。3.在以下叙述中，不正确的是 【 】（分数：2.00）A.数据的逻辑结构是数据元素之间的逻辑关系，是依赖于计算机语言的 B.存储结构不仅涉及数据元素的机内表示，还包括数据之间关联方式的表示C.顺序存储方式使用的是一段连续
12、的存储区D.算法的时间复杂度与算法中语句的频度有关解析：解析：数据的逻辑结构是数据之间的外在联系，它与计算机存储无关，是不依赖于计算机语言的。4.某算法的时间复杂度为 O(n 2 )，表明该算法的 【 】（分数：2.00）A.问题规模是 n 2B.执行时间等于 n 2C.执行时间与 n 2 成正比 D.问题规模与 n 2 成正比解析：5.下列程序的功能是计算两个矩阵的乘积，其算法的时间复杂度是 【 】 void mul_matrix(int n，int a 5，int b 5，int c 5) int i，j，k，x； for(i=0；iA.O(n)B.O(log 3 n)C.O(n 2 )D
13、.O(n 3 ) 解析：6.下面程序段的时间复杂度为 【 】 for(int i=0；iA.O(m 2 )B.O(n)C.0(m*n) D.O(m+n)解析：7.已知指针 p和 q分别指向某单链表中第一个节点和最后一个节点。假设指针 s指向另一个单链表中某个节点，则在 s所指节点之后插入 p所指向的链表应执行的操作是 【 】（分数：2.00）A.q一next=s 一next；s 一next=p； B.s一next=p；q 一next=s 一nextC.p一next=s 一next；s 一next=q；D.s一next=q；p 一next=s 一next；解析：解析：插入 p所指向的链表时，应首
14、先将单链表的最后一个节点 q指向节点 s的下一个节点，最后将 s指向单链表的第一个节点 p。8.在一个具有 n个节点的有序单链表中插入一个新节点并使其仍然有序的时间复杂度为 【 】（分数：2.00）A.O(1)B.O(n) C.O(n 2 )D.O(log 3 n)解析：解析：在有序单链表中插入一个节点并使其保持有序，花费时间最多的是查找插入位置。对具有 n个节点的单链表来说，查找位置的平均比较次数是(n+1)2，故时间复杂度为 O(n)。9.在一个单链表中，已知 q所指节点是 p所指节点的前趋节点，若在 q和 p之间插入 s所指向的节点，则执行的操作是 【 】（分数：2.00）A.snext
15、=pnext；pnext=s；B.qnext=s；snext=p； C.pnext=s；snext=q；D.pnext=snext；snext=p；解析：10.设在一个单链表中指针 p指向节点 a，若要删除 a之后的一个节点(若存在)，则需执行的修改指针的操作为 【 】（分数：2.00）A.p一next=p 一next 一next B.p=p一nextC.p=p一next 一nextD.next=p解析：11.带头节点的单链表 heald为空的判定条件是 【 】（分数：2.00）A.head=NULLB.headnext=NULL C.headnext=headD.head!=NULL解析：解
16、析：带头节点的单链表 head，head 指向单链表的头节点，头节点的指针域 head一next 指向第一个数据节点，如果 head一next 的值为空，则单链表为空。12.按照 1、2、3、4、5 的次序依次入栈时，出栈序列不可能是 【 】（分数：2.00）A.1、2、3、4、5B.2、3、4、5、1C.5、4、3、2、1D.5、4、1、2、3 解析：解析：栈是按“先进后出”的原则组织数据的，所以选项 D中若 5先出栈，出栈的顺序只能是5、4、3、2、1，1 是不可能在 2、3 的前面出栈的。13.在一个链队列中，假设 f和 r分别为队头和队尾指针，则插入指针 s所指节点的运算是 【 】（分
17、数：2.00）A.fnext=s；f=s；B.rnext=s；r=s； C.snext=r；r=s；D.s一next=f；f=s；解析：解析：链队列的插入操作在队尾进行，若队列未满，只需要在链队列尾部增加新节点，并让队尾指针指向新节点即可。14.假定一个顺序队列的队头和队尾指针分别用 front和 rear表示，则判断队列为空的条件是 【 】（分数：2.00）A.front+1=rearB.rear+1=frontC.front=0D.front=rear 解析：15.假定利用数组 aN顺序存储一个栈，用 top表示栈顶指针，top=一 1表示栈空，并已知栈未满，当元素 x进栈时所执行的操作为
18、 【 】（分数：2.00）A.a-top=xB.atop-=xC.a+top=x D.atop+=x解析：解析：若栈未满，则进栈的步骤是：(1)栈顶指针上移 1个节点。(2)将数据加入到 top所指位置。二、填空题(总题数：10，分数：20.00)16.在 C语言中，表示换行的转义字符是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n）解析：17.执行 for(j=k=0；j1。（分数：2.00）填空项 1:_ （正确答案：正确答案：45）解析：18.已知：char str15；str 数组的最后一个元素是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：str14
19、）解析：19.数据的逻辑结构又分为两类：线性结构和 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：非线性结构）解析：20.n阶三对角阵压缩存储至少需要 1 个存储空间。（分数：2.00）填空项 1:_ （正确答案：正确答案：3n 一 2）解析：21.在带有表头节点的单链表 L中，若要删除第一个节点，则需执行的三条语句是： 1；L 一next=pnext；free(p)；。（分数：2.00）填空项 1:_ （正确答案：正确答案：p=L 一next）解析：22.对于一棵具有 n个节点的树，该树中所有节点的度数之和为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n1）解
20、析：23.拓扑排序是针对 1 图的。（分数：2.00）填空项 1:_ （正确答案：正确答案：有向无环）解析：24. 1是按某种顺序将数据元素的无序序列调整成有序序列的过程。（分数：2.00）填空项 1:_ （正确答案：正确答案：排序）解析：25.黑盒测试法包括等价划分、 1 以及错误推测法等。（分数：2.00）填空项 1:_ （正确答案：正确答案：边界值分析）解析：三、程序分析题(总题数：4，分数：8.00)26.以下程序是用来统计从键盘输入的一个正整数的各位数字中零的个数，并求各位数字中的最大者。例如：1080 的各位数字中零的个数是 2，各位数字中的最大者是 8。请将程序补充完整。 #in
21、cludestdioh main() unsigned long num，max，t； int count； count=max=0； scanf(“old“，num)； do t=_； if(t=0)+count； else if(maxt)max=t； num=10； while(num)； printf(“count=d，max=ldn“，count，max)； （分数：2.00）_正确答案：(正确答案：num10)解析：27.下列程序的功能是输出 100以内能被 3整除且个位数为 6的所有整数，填空完成程序。 #include main() int i，j； for(i=0；i_正确答
22、案：(正确答案：j3!=0)解析：28.下列程序的运行结果是_。 #include main() int i=1，j=1； for(；j10)break； if(j2!=0) j+=3； continue； j 一=1； printf(“d，dn“，i，j)； （分数：2.00）_正确答案：(正确答案：10，12)解析：29.以下程序的输出结果是_。 #include main() int arr10，i，k=0； for(i=0；i_正确答案：(正确答案：12)解析：四、程序设计题(总题数：2，分数：4.00)30.从键盘输入任意一个 3位正整数(即在 100999 之间的整数)，求其各位上
23、数字之和。如输入 123，则结果应输出 6(即 1+2+3=6)。（分数：2.00）_正确答案：(正确答案：#includestdioh main() int num； int sum； scanf(“d“，&num)； sum=num100+num1010+num10； printf(“您输入的数据是：d，它各位上数字之和是：dn“，hum，sum)； )解析：31.假设二叉树采用二叉链存储结构，设计一个算法把二叉树 b复制到二叉树 t中。（分数：2.00）_正确答案：(正确答案：void Copy(BTNode*b，BTNode*&t) if(b=NULL) t=NULL； else t=(BTNode*)malloc(sizeof(BTNode)； tdata=b 一data； Copy(b 一lchild，t 一lchild)； Copy(b 一rchild，t 一rehild)； )解析：
