计算机专业基础综合（数据结构）模拟试卷39
单选题
1.下面程序段中，执行S语句的次数为( )。
for(int i=1；i＜=n；i++)
for(int j=1；j＜=i；j++)
S：(D)
A. n2
B. n2／2
C. n(n+1)
D. n(n+1)／2
解析：i的变化范围是从1到n，对于每个己确定值的i，j的变化范围是从1到i，相当于求一个公差为1的等差数列1，2，…，n的前n项和，即为n(n+1)／2。
2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则下面最合适的存储方式是( )。(B)
A. 单链表
B. 循环双链表
C. 单循环链表
D. 带有尾指针的单循环链表
解析：在链表中的最后一个结点之后插入个结点要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点要知道终端结点的前驱结点的地址，所以，带有尾指针的单循环链表不合适，而循环双链表满足条件。
3.链表不具备的特点是( )。(A)
A. 可随机访问任一结点
B. 插入、删除不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与其长度成正比
解析：链式存储结点间通过指针连接，存储位置比较灵活，不必事先估计存储空间。根据表长来确定存储空间即可；插入和删除不需要移动元素，只要改变指针域值；但链表不具备随机访问任一结点的特点，这是顺序表的特点。
4.若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式最节省时间的是( )。(D)
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
解析：在顺序表中查找第i个元素的前驱很方便。双链表虽然能快速查找第i个元素的前驱，但不能实现随机存取。单链表和单循环链表既不能实现随机存取，查找第i个元素的前驱也不方便。
5.设有n个元素进栈序列是P1，P2，P3，*…*，Pn，其输出序列是1，2，3，***，n，若P3=3，则PT的值( )。(A)
A. 可能是2
B. 一定是2
C. 不可能是1
D. 一定是1
解析：栈序列是P1，P2，P3，***，Pn，当P3=3时，由输出序列可知，只有以下两种情况：P1进栈后出栈，P2进栈后出栈，或P1、P2都进栈然后出栈，因此P1的值可能为1，也可能为2。
6.设数组re[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为( )。(D)
A. front=front+1
B. front=(front+1)％(m-1)
C. front=(front-1)％in
D. front=(front+1)％M
解析：对于循环队列出队的操作就是队头指针后移，即+1。但对于循环队列要对队列长度求余才能得到指针的位置。具体的操作语句为front=(front+1)％m。
7.将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置等于( )。(D)
A. 198
B. 197
C. 196
D. 195
解析：将三对角矩阵a[i][j]存入 b[k]中，矩阵压缩地址计算公式为k=2i 十j。所以 a[65][64]对应的k=2×65+64=194，194是一维数组b的下标，而数组下标是从0开始计数的，所以元素的位置应该是195。
8.树最适合用来表示( )。(D)
A. 有序数据元素
B. 无序数据元素
C. 元素之间无联系的数据
D. 元素之间有分支层次关系
解析：树是由一个集合以及在该集合上定义的一种关系构成的，集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。从树的定义可以看出树最适合用来表示元素之间有分支(兄弟)层次(父子)关系。
9.某高度为k的完全二叉树中，所含叶子结点的个数最少为( )。(C)
A. 2k
B. k
C. 2k-2
D. 2k-1
解析：完全二叉树只有高度最大的那一层可能不满，k-1层应都是满的。k-1层最少有2k-2个节点，k层最少有一个节点，所以最少有2k-2个叶子节点。
10.若二叉树的前序序列为DABCEFG，中序序列为BACDFGE，则其层次序列为( )。(B)
A. BCAGFED
B. DAEBCFG
C. ABCDEFG
D. BCAEFGD
解析：由前序序列和中序序列先构造出二叉树，然后按层次序列进行访问。
11.由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为( )。(D)
A. 27
B. 38
C. 51
D. 75
解析：由元素序列(27，16，75，38，51)构造平衡二叉树的过程如下图所示，将元素51加入树中之前，二叉树保持平衡，加入结点51后，结点38的平衡因子由0变为-1，75所在结点的平衡因子由1变为2，27所在结点的平衡因子由-1变为-2。因此，75所在结点是离插入结点最近且平衡因子的绝对值为2的结点。
平衡二叉树的构造过程如下图所示：
12.若将数据结构中的数据元素称为结点，则一般没有开始结点和终端结点的数据结构是(
本文档预览：3000字符，共6290字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
