2002 年招收攻读硕士学位研究生
入学考试命题专用纸
招生专业:计算机科学与应用技术
考试科目:数据结构  试题编号:418
注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效)
－、单选题（每小题2分，共20分）
1.在一个具有n个结点的有序单链表中插入一个新的结点使得单链表仍然有序的时间复杂度为 
  A.O(logn)  B.O(1)  C.O(n2)  D.O(n)
2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用  存储方式节省时间。
  A.单向链表  B.双向链表  C.单循环链表 D.顺序表
3.用单链表表示的链式队列的队头在链表的  位置。
  A.链头  B.链尾  C.链中
4.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用  顺序实现编号。
  A.前序遍历  B.中序遍历 C.后序遍历  D.层序遍历
5.己知一算术表达式的中缀形式为A+ B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为  。
  A.-A+B*C/DE  B.-A+B*CD/E C.- + *ABC/DE  D.- +A*BC/DE
6.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对的二叉排序树以后，查元素35要进行  次元素间的比较。
  A.4  B.5  C.7  D.10
7.对于一个具有n个顶点和e条边的图，来用邻接矩阵表示的空间复杂度为 。
  A.O(n)  B.O(e)  C. O(n2) D. (n+e)
8.设连通图G的顶点数n，则G的生成树的边数为  。
  A.n  B.n-1  C.2n    D，2n-1
  9.下列排序算法中，  算法可能出现下面的情况:在最后一趟排序开始之前，所有元素都不在最终的位置上。
  A.堆排序  B.冒泡排序  C.快速排序  D.插入排序
10.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 
A.n在m右方  B.n是m祖先  C.n在m左方 D.n是m子孙
二、判断题（判断下列各小题的叙述是否正确，若正确打“√”，否则打“×”，每小题1分，共10分）
1. 线性表中每个元素都有一个前驱和一个后继。
2. 顺序表中逻辑关系上相邻的两个元素在物理位置上也相邻。
3. 在栈为空的情况下，不能作出栈操作，否则会产生“下溢”。
4. 对广义表A=（a，（b，c），d）的运算head（tail（A））的结果不是b。
5. 图G的一棵最小生成树的代价未必小于G的其他任何一棵生成树的代价。
6. 若从某顶点开始对含有n个顶点的有向图G迸行深度优化先遍历，所得到的遍历序列唯一，则可断定起弧数为n－1。
7. 二叉树不能存储在数组中。
8. 理想情况，在散列表中查一个元素的时间复杂度为O(1)。
9. 最优二叉树是AVL树（平衡二叉树）
10.序列（101，88，46，70，34，39，45，58，66，10）是堆。
二、填空题（每空2分，共20分）
1. 在有n个元素的顺序表中，如果要删除第i个元素（1≤i≤n）,那么有 
个元素必须向表头方向移动。
2.栈的插入和删除只能在栈顶一端进行，后进栈的元素必定先被删除，所以栈又被称为  表。
3.已知一棵完全二叉树的第八层有8个结点（根结点在第0层），则该完全二叉树的叶结点数是  。
4.具有64个结点的完全二又树共有  层。
5.设n行n列的下三角矩阵A已压缩到一维数组*(n+1)/2]中，若按行序为主存储，则元素 A[i,j]在S中的存储位置是  。
6.要将序列{50，16，23，68，94，70，73}建成堆，只需把16与  相互交换。
先序中序后序遍历二叉树7.具有n个顶点的有向连通图最多有  条边，最少有  条边。
8.冒泡排序算法在最佳情况下的元素交换次数为  。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。