计算机专业基础综合（数据结构）模拟试卷26
单选题
1.每个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明存储位置的表，该存储方式是( )存储方式。(C)
A. 顺序
B. 链接
C. 索引
D. 散列
解析：根据索引的定义，除表本身以外，还需建立一个“索引表”，这个表指明存储位置加快结点的查找过程。
2.分析以下程序段时间复杂度( )。
for(i=0；i＜n；i++)／／①
{
y=y+1； ／／②
for(j=0；j＜=2*n；j++)／／③
x++； ／／④
}(D)
A. O(1)
B. O(log n)
C. O(n)
D. O(n2)
解析：在考虑程序段时间复杂度时，可以用算法中的基本操作重复执行的频度作为度量标准。本程序段中的基本操作应选取为语句④，所以该算法的时间复杂度=2n2+n=O(n2)。
3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。(A)
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
解析：在线性表的顺序存储中，可以存取任一指定序号的元素。当插入和删除运算是在最后操作时，顺序表的实现也非常方便。BCD三项都不同时具备这两个特点。
4.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
以上错误的是( )。(B)
A. (1)，(2)
B. (1)
C. (1)，(2)，(3)
D. (2)
解析：静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点，同时使用游标(指示器cur)代替指针以指示结点在数组中的相对位置。这种存储结构仍然需要预先分配一个较大空间，但是在进行线性表的插入和删除操作时不需要移动元素，仅需要修改“指针”，因此仍然具有链式存储结构的主要优点，(2)，(3)是正确的，但它不具备直接存取数据的特性，所以只有(1)是错误的。
5.不是栈的基本运算的是( )。(B)
A. 删除栈顶元素
B. 删除栈底元素
C. 判断栈是否为空
D. 将栈置空
解析：栈的删除操作只能在栈顶进行，可以删除栈顶元素，但无法删除栈底元素。通过栈顶指针和栈底指针的位置可以判断栈是否为空，同时也可以对栈进行置空操作。所以只有删除栈底元素不是栈的基本运算。
6.有A，B，C，D，E 5个元素按次序入栈，在各种可能的出栈次序中，以元素C，D最先出栈的序列中，下列正确的一组是( )。(B)
A. CDBAE CDABE
B. CDEBA CDBEA
C. CDEAB CDABE
D. CEBAE CDAEB
解析：只有A、B、C先入栈，才能CD作为第一、二个元素出栈。C出栈，D入栈，D出栈：接着就剩下A、B在栈中，E未入栈，共3个元素，此三者序列为BAE，BEA，EBA。
7.在一个顺序循环队列中删除元素时，首先需要( )。(B)
A. 前移队首指针
B. 后移队首指针
C. 取出队首指针所指位置上的元素
D. 取出队尾指针所指位置上的元素
解析：
8.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k(起始下标为1)，采用顺序存储更节省空间的情况是( )。(A)
A. d＜12n／(k-n)
B. d＞12n／(k-n)
C. d＜12n／(k+n)
D. d＞12n／(k+n)
解析：顺序存储所需空间为：kd，三叉链表每个结点需要3个指针空间和1个数据空间，即存储所需空间为：n(d+4×3)，当kd＜n(d+12)，即d＜12n／(k-n)时，顺序存储更节省空间。
9.设结点x和y是二叉树中的任意两结点，若在该树的先根、中根和后根序列里，x和y中的一个结点皆在另一个结点之前，则它们的关系是( )。(B)
A. x和y必互为兄弟
B. x和y必是树叶
C. 一个是另一个的祖先
D. 彼此无祖先和后代的关系
解析：在二叉树的三种遍历中，无论是先序遍历、中序遍历，还是后序遍历，左边结点总是先于右边结点的访问，所以叶子结点间的相对访问次序不变。所以x和y必是树叶。
10.在线索化二叉树中，t所指结点没有左子树的充要条件是( )。(B)
A. t-＞left=NULL
B. t＞ltag=1
C. t＞ltag=1 且 t-＞left=NULL
D. 以上都不对
解析：由线索二叉树的定义得知，若结点没有左子树，则左标志域为1，该指针域中存放的是线索，而非左子树信息，此时左指针指向前驱结点；若结点的左标志域为1，则结点没有左子树。
11.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0。右孩子的平衡因子为1，则应作( )型调整以使其平衡。(C)
A. LL
B. LR
C. RL
D. RR
解析：平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中
本文档预览：3000字符，共8380字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
