计算机专业基础综合（数据结构）模拟试卷35
单选题
1.在计算机的存储器中表示时，各元素的物理地址和逻辑地址的相对顺序相同并且是连续的称之为( )。(B)
A. 逻辑结构
B. 顺序存储结构
C. 链式存储结构
D. 以上都对
解析：顺序存储结构是一种直接映射。这种结构把逻辑上相邻的元素存储在物理位置上相邻的存储单元里，直接反映数据元素之间的逻辑关系。
2.以下算法中加下划线语句的执行次数为( )。
int m=0，i，j；
for(i=1；i＜=n；j++)
for(j=1；j＜=2*i；j++)
m++；(A)
A. n(n+1)
B. n
C. n+1
D. n2
解析：m++语句的执行次数为：
3.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )。(B)
A. head==NULL
B. head→next==NULL
C. head→next==head
D. head!=NULL
解析：带头结点的单链表为空的条件就是头结点的指针域为空，用语句表示就是head→next==NULL。
4.非空的循环单链表head的尾结点P满足的条件是( )。(A)
A. P．link=head
B. P．link=NIL
C. P=NIL
D. P=head
解析：对于循环单链表来说尾结点的指针指向第一个元素。
5.输入序列为ABC，可以变为CBA时。经过的栈操作为( )。(B)
A. push，pop，push，pop，push，pop
B. push，push，push，pop，pop，pop
C. push，push，pop，pop，push，pop
D. push，pop，push，push，pop，pop
解析：栈的特点是后进先出，可以实现序列的倒置，具体操作就是push，push，push，pop，pop，pop。
6.一个循环队列Q最多可存储m个元素。己知其头尾指针分别是front和rear，则判定该循环队列为满的条件是( )。(C)
A. Q．rear-Q．front==m
B. Q．rear!=Q．front
C. Q．front==(Q．rear+1)％m
D. Q．front==Q．rear／m+1
解析：少用一个元素空间和空队区别开： 每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列己满，这种情况下队满的条件是：(Q．rear+1)％MAXSIZE==Q．front。
7.若对n阶对称矩阵A[1…n，1…n]以行序为主序方式将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B1…(n+1)／2]中，则在B中确定aij(i＜j)的位置k的关系为( )(B)
A. i×(i-1) ／2+j
B. j× (j-1) ／2+i
C. i× (i+1) ／2+j
D. j×(j+1) ／2+i
解析：只考虑A的下三角阵，依照行序为主序是指先存完第i行的元素，才能存储第i+1行的元素。aij(i＜j) 在第i行第j列，因为A是对称的，aij(i＜j)也可看作是aij，第j行共有j个元素，从第1行到第j-1行共有j×(j-1)／2个元素，再加上第j行的i个元素就是aij在 B[1…(n+1)／2]中的位置，即k=j×(j-1)12+i。
8.如果一棵完全二叉树共有26个结点，则必定有( )个结点的度为1。(B)
A. 0
B. 1
C. 3
D. 13
解析：26个结点，可知该二叉树有5层。由于前4层组成一棵满二叉树，共15个结点，则共有11个叶子结点，可知只有1个结点的度为1。
9.一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )。(D)
A. 250
B. 500
C. 505
D. 501
解析：二叉树结点总数n=n0+n1+n2 (n0，n1，n2分别代表度为0，度为1，度为2的结点数)，在二叉树中：n0=n2+1。又因为完全二叉树度为1的结点数为1或0，结合两个关系式，当n1=1 时，n0=500．5，不成立：当n1=0 时，n0=501，所以有1001个结点完全二叉树上，叶子结点数为501。
10.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。(C)
A. 先序
B. 中序
C. 后序
D. 从根开始按层次遍历
解析：每个结点编号大于其左右孩子的编号，因此，需要在左右孩子访问完毕后才访问该结点，同一结点中左孩子的编号小右孩子的编号，故左孩子先于右孩子被访问。这些符合后序遍历的特点。
11.在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为( )。(B)
A. 20
B. 29
C. 30
D. 35
解析：
本文档预览：3000字符，共7095字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
