2005年专升本测验真题 数据结构.docVIP

2005年吉林省普通高校专升本教育试点考试 计算机科学与技术专业综合试卷 （数据结构部分 共90分） 一、填空题（每小题2分，共26分） 1. 栈的主要特点是_ _ ；队列的主要特点是____ 。 2. 在一长度为n的向量中的第i个元素（1≤i≤n）之前插入一个元素时，需向后移动__ 个元素。 3. 对于一个具有n个结点的单链表，在已知P所指结点都插入一个新结点的时间复杂度为__ _ ；在给定值为x的结点后插入一个新结点的时间复杂度为__ ___。 4. 设n行n列的下三角矩阵A已压缩到一维数组s[0 … n*(n+1)/2]中，若按行序为主存储，则A[i][j]对应的s中的存储位置为___ 。 5. 将f=1+1/2+1/3+ … +1/n转化成递归函数，其递归出口是 __ __，递归体是 __ __ 。 6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为___ 。 7. 具有n个叶子结点的哈夫曼树中，其结点总数为___ 。 8. 对一个满二叉树，m个树叶，n个结点，深度为h，则n = ___ 。 9. 判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用__ __ 算法。 10. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____ 。 11. 快速排序在最坏情况下的时间复杂度为 __ 。 12. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为__ 。 13. 直接存取文件是用__ __ 方法组织的。 二、单项选择题（每小题2分，共20分） 1. 线性表的顺序存储结构是一种（ ）的存储结构；线性表的链式存储结构是一种（ ）的存储结构。 A. 随机存取，顺序存取 B. 顺序存取，随机存取 C. 索引存取，散列存取 D. 散列存取，随机存取 2. 表达式a*(b+c)-d的后缀表达式为（ ）。 A. abcd+-* B. abc+*d- C. abc*+d- D. -+*abcd 3. 在一个单链中，若P所指结点不是最后的结点，在P之后插入S所指结点，则执行（ ）。 A. S-next=P ; P-next = S ; B. S-next=P-next ; P-next=S; C. S-next=P-next ; P=S ; D. P-next=S ; S-next=P ; 4. 一个栈的入栈序列为1，2，… ，n，其输出序列为P1，P2，…，Pn，若P1=n，则Pi为（ ）。 A. i B. n-iI C. n-i+1 D. 不确定 5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址为SA开始连续存放在存储器内，该数组按行序存放时，元素A[8][5]的起始地址为（ ）。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 6. 将递归算法换成对应的非递归算法时，通常需要使用（ ）。 A. 栈 B. 队列 C. 链表 D. 树 7. 任何一棵二叉树的叶结点在前序、中序和后序遍历中的相对次序是（ ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 8. 已知一有向图的邻接表存储结构如图所示，根据有向图的深度优先遍历算法，从顶点V1出发，所得到的顶点序列为（ ）。 34 3 4 2 5 ∧ 2 4 ∧ 4 ∧ 1 2 ∧ 3 4 ∧ 5 A. V1 , V2 , V3 , V5 , V4 B. V1 , V2 , V3 , V4 , V5 C. V1 , V3 , V4 , V5 , V2 D. V1 , V4 , V3 , V5 , V2 9. 快速排序方法在（ ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 10. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 三、算法设计与解答（共44分） 1. 设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H ( key ) = key%13，采用开放地址法的二次探测再散列方法解决冲突，试在0~18的散列地址空间中对该关键字序列构造哈希表。（7分） 2. 试用普里姆法构造如图所示的一棵最小生成树。（要求每加入一个结点，画一个图