湖南大学2001年数据结构试题（计算机应用）

来源：时间：2007-06-06 14:42:13

湖南大学 2001 年招收攻读硕士学位研究生
入学考试命题专用纸
招生专业：计算机应用技术
考试科目：数据结构试题编号：41026
注：答题（包括填空题、选择题）必须答在专用答题纸上，否则无效)
一、填空题（每空1.5分，共15分）
1．在有n个元素的顺序表中，若想在第i个元素（1≤i≤n 1）之前插入一个元素时，需向表尾方向移动元素。
2．在一个循环队列中，队头指针指向队头元素的
3．在双向链表中，每个结点有两个指针域，一个指向其结点，另一个指向其结点。
4．设n行n列的下三角矩阵A已压缩到一维数组s[1..n*(n 1)/2]中，若按行序为主存储，则元素 A[i,j]在S中的存储位置是。
5．若某二叉树中有30个叶结点，另有30个结点仅有一个孩子结点，则该二叉树中总共有个结点。
6．具有n个顶点的无向连通图至少有条边。
7．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数为。
8．利用插入排序算法对n个记录进行排序，最佳情况下，对关键字进行的比较次数为次。
9．在散列存储中装填因子的值越小，则。
二、判断题（判断下列各题是否正确，若正确打“√“，否则打“×”，每小题⒈5分，共15分）
l．线性表的唯一存储形式是数组。
2．线性表的逻辑顺序与存储顺序总是一致的。
3．二维数组是它的每个数据元素为一个线性表的线性表。
4．每种数据结构都具备三个基本运算：插入、删除和查找。
5．删除二叉排序树中的一个结点，再重新插人进去，一定能得到原来的二叉排序树。
6．若一个叶结点是某二叉树的中序遍历序列的最后一个结点，则它也是该二叉树的前序遍历序列的最后一个结点。
7．无向图用邻接矩阵表示后，该矩阵一定是对称矩阵。
8．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历，可访问到该图的每一个结点。
9．快速排序算法在每一趟排序中都能找到一个元素放到其最终位置上。
10．理想情况下，在散列表中查找一个元素的时间复杂度为O(1)。
三、单选题（在本题的每一小题的备选答案中，只有一个答案是正确的，请选择你认为正确的答案的标号，多选不给分。每小题⒈5分，共15分）
1．算法分析的目的是。
A．找出数据结构的合理性 B．研究算法中的输入和输出关系
C．分析算法的效率以求改邀 D．分析算法的易读性和文档性
2．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是。
A．edcba B．decba C．dceab D．abcde
3．将两个各有n个元素的有序表归并成一个有序表，最少需要比较次。
A．n -1 B．n C． 2n-1 D．2n
4．对一棵二叉排序树进行遍历得到的结点序列是一个有序序列。
A．前序 B．中序 C．后序 D．层序
5．某二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树一定是。
A．空或只有一个结点 B．完全二叉数
C．二又排序树 D．高度等于结点数
6．任何一个无向连通图的最小生成树。
A．有一棵或多棵 B．只有一棵
C．一定有多课 D．可能不存在
7．下列排序算法中算法占用的辅助空间最多。
A．堆排序 B．shell排序 C．快速排序 D．归并排序
8．若数据表中每个元素己距其最终位置不远，则采用算法进行排序时间最省。
A．选择排序 B．快速排序 C．堆排序 D．插入排序
9．有一长度为12的有序表，按二分查找法对该表进行查找，且查找每个元素的概率相同，则查找成功所需的平均比较次数为。
A．35／12 B．37／12 C．39/12 D．43/12
10．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用
查找方法。
A．二分 B．顺序 C．分块 D．散列