国家二级C语言机试（公共基础知识）模拟试卷12
选择题
1.某系统总体结构图如下图所示：
(C)
A. 7
B. 6
C. 3
D. 2
解析：这个系统总体结构图是一棵树结构。在树结构中，根节点在第1层，同一层上所有子节点都在下一层，由系统总体结构图可知，这棵树共3层。在树结构中，树的最大层次称为树的深度。所以这棵树的深度为3。
2.对于循环队列，下列叙述中正确的是( )。(D)
A. 队头指针是固定不变的
B. 队头指针一定大于队尾指针
C. 队头指针一定小于队尾指针
D. 队头指针可以大于队尾指针，也可以小于队尾指针
解析：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置。循环队列的主要操作是：入队运算和退队运算。每进行一次入队运算，队尾指针就进一。每进行一次退队运算，队头指针就进一。当rear或front等于队列的长度加1时，就把rear或front值置为1。所以在循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针。
3.下列关于栈的叙述正确的是( )。(D)
A. 栈是非线性结构
B. 栈是一种树状结构
C. 栈具有“先进先出”的特征
D. 栈具有“后进先出”的特征
解析：栈是限定在一端进行插入和删除的线性表。允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的。
4.下列叙述中正确的是( )。(D)
A. 在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B. 在栈中，栈中元素不随栈底指针与栈顶指针的变化而动态变化
C. 在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
D. 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
解析：在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。栈跟队列不同，元素只能在栈顶压人或弹出，栈底指针不变，栈中元素随栈顶指针的变化而动态变化，遵循后进先出的规则。
5.下列对队列的描述中正确的是( )。(D)
A. 队列属于非线性表
B. 队列按“先进后出”原则组织数据
C. 队列在队尾删除数据
D. 队列按“先进先出”原则组织数据
解析：队列(queue)是指允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾；允许删除的一端称为队头。在队列这种数据结构中，最先插入的元素将最先能够被删除；反之，最后插入的元素将最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。
6.下列描述中正确的是( )。(D)
A. 数据的逻辑结构与存储结构必定是一一对应的
B. 由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构
C. 程序设计语言中的数据一般是顺序存储结构，因此，利用数组只能处理线性结构
D. 以上三种说法都不对
解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。
7.设一棵完全二叉树共有700个节点，则此二叉树中的叶子节点数为( )。(D)
A. 85
B. 120
C. 250
D. 350
解析：(1)具有n个节点的完全二叉树的深度为[log2n]+1，计算出该完全二叉树的深度为10。
(2)设度为0的节点(叶子节点)为n0，度为1的节点为n1，度为2的节点为n2，总节点数为n，深度为k。n=n1+n2+n0，由于n0=n2+1则n2=n0一1，故n=n1+n0一1+n0=n1+2n0一1。由于完全二叉树中度为1的节点数只有两种可能：0或1。
(3)假设度为1的节点数为0即满二叉树，根据满二叉树的定义，其2m一1个节点，根据以上计算所得的深度10来计算，应有210—1=1024一1=1023个节点，显然与题目中700个节点不符。因此，度为1的节点数必然为1。故n=n1+2n0－1=1+2n0－1=2n0，则n0=n／2=700／2=350。
8.下列叙述中正确的是( )。(B)
A. 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B. 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C. 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D. 以上都不正确
解析：线性表的存储分为顺序存储和链式存储。在顺序存储中，所有元素所占的存储空间是连续的。而在链式存储的方式中，将存储空间的每一个存储节点分为两部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储下一个元素的存储序号。称为指针域。所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
9.算法的时间复杂度是指( )。(D)
A. 算法的执行时间
B. 算法所处理的数据量
C. 算法程序中的语句或指令条数
D. 算法在执行过程中所需要的基本运算次数
解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。
10.一棵二叉树中共有80个叶子节点与70个度为1的节点，则该二叉树中的总节点数为( )。(B)
A. 219
B. 229
C. 230
D. 231
解析：根据二叉树的性质，在任意二叉树中，度为0的节点(叶子节点)总是比度为2的节点多一个，总节点数=叶子节点数+度为2的节点数+度为1的节点数=80+79+70=229。
11.下列叙述中正确的是( )。(D)
A. 栈是“先进先出”的线性表
B. 队列是“先进后出”的线性表
C. 循环队列是线性结构
D. 有序线性表不可以采用顺序存储结构
解析：栈是“先进后出”队列是“先进先出”。栈和队列都是一种线性表，属于线性结构。有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。采用链式存储结构的线性表称之为线性链表。
12.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为( )。(B)
A. 63
B. 64
C. 6
D. 7
解析：顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素进行比较，若相等则表示找到(即查找成
本文档预览：3600字符，共7741字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
