计算机专业基础综合（数据结构）模拟试卷29
单选题
1.以下与数据的存储结构无关的术语是( )。(D)
A. 循环队列
B. 链表
C. 哈希表
D. 栈
解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构，它们是数据的两种最基本的存储结构。ABC三项，都属于链式存储结构。D项，栈则是指从应用的角度来说的一种后进先出的线性表结构，与具体的存储结构无关。
2.一个算法的执行时间为T(n)=(3n2+2nlog2n+4n-7)／(10n)，其时间复杂度为( )。(D)
A. O(3n2)
B. O(2nlog2n)
C. O(3n2／10)
D. O(n)
解析：当n足够大时，T(n)→3n／10=O(n)。
3.在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移( )个元素。(A)
A. n-1
B. n-i+1
C. n-i-1
D. i
解析：顺序表中的删除操作是通过将当前结点用后面结点的值覆盖来实现的，因此删除第i个元素主要是前移第i个元素后的所有的元素，即n-i个元素。
4.在单链表指针为P的结点之后插入指针为S的结点，正确的操作是( )。(B)
A. p-＞next=s；s-＞next=p-＞next
B. s-＞next=p-＞next；p-＞next=s
C. p-＞next=s；p-＞next=s-＞next
D. p-＞next=s-＞next；p-＞next=s
解析：在单链表结点P后插入结点s，要先改变s结点的指针域，指向P的后继结点。然后将s的地址赋给P的指针域。具体的操作语句为s-＞next=p-＞next；p-＞next=s。
5.已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。(B)
A. dacb
B. cadb
C. dbca
D. 以上答案都不对
解析：输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。
A项，输入序列为abed，输出序列为dacb，由输出受限性质可知以da开头的结果只有dabc。
B项，输入序列为abed，输出序列为cadb，其输入输出顺序为：先在输出端输入a，然后在非输出端输入b，这时队列中的序列为ba，再在输出端输入c，这时队列中的序列为bac；输出c，再输出a；再在输出端输入d，这时队列中的序列为bd；输出d，再输出b。最后得到输出序列为cadb。
c项，输入序列为abcd，输出序列为dbca，由输出受限性质可知以db开头的结果只有dbac。
6.设计一个判别表达式中左右括号是否配对出现的算法，采用( )数据结构最佳。(D)
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
解析：使用栈解决此问题的方法是：把表达式依次压入栈，当压入的是右括号时，就退栈直到退出一个左括号，若最终栈空，则表示配对出现。
7.按照二叉树的定义，具有3个结点的二叉树有( )种。(C)
A. 3
B. 4
C. 5
D. 6
解析：n个结点构成的二叉树共有(C2nn／(n+1) =C63／4=) 5种。
8.已知一算术表达式的中缀形式为A+B*C-D／E，后缀形式为ABC*+DE／-，其前缀形式为( )。(D)
A. -A+B*C／DE
B. -A+B*CD／E
C. -+*ABC／DE
D. -+A*BC／DE
解析：将算术表达式的前缀形式、中缀形式和后缀形式分别看成二叉树的前序遍历、中序遍历和后序遍历，本题可转化成已知二叉树的中序遍历和后序遍历序列，如何求出其前序遍历序列。前序遍历的顺序是根结点，左子树，右子树；中序遍历的顺序是左子树，根结点，右子树：后序遍历的顺序是左子树，右子树，根结点：因此后序遍历中最后访问的结点是根结点，该结点将中序遍历分成两个子序列，分别为其左右子树的中序序列，之后递归应用这个过程，构造出一个二叉树，前序遍历该序列，叩可得到表达式的前缀形式。
9.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是( )。
I、父子关系
Ⅱ、兄弟关系
Ⅲ、u的父结点与v的父结点是兄弟关系(B)
A. 只有Ⅱ
B. I和Ⅱ
C. I和Ⅲ
D. I、Ⅱ和Ⅲ
解析：若u和v的关系如图a所示，则根据左孩子右兄弟的原则，v跟自己的父结点是兄弟关系，都是u的孩子。所以图a对应的是1：父子关系。
若u和v的关系如图所示，则根据左孩子右兄弟原则，v跟自己的父结点以及u是兄弟关系，都是u的父结点的孩子，所以图对应的是Ⅱ兄弟关系。
10.如下图所示一棵二叉排序树，其不成功的平均查找长度为( )
(B)
A. 21／7
B. 28／7
本文档预览：3000字符，共8807字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
