数据结构考试习题试卷A.doc

南通大学20062007学年第二学期 数据结构(闭卷) 试卷（A）第1页 共3页试题一二三四五 总分装订线密 封 线 内 答 题 无 效学院： 专业： 班级： 学号： 本人承诺：在本次考试中，自觉遵守考场规则，诚信考试，绝不作弊。 学生姓名（签名）： 密 封 线 得分得分评卷人一、单项选择题（每小题1分，共20分）下列各小题的候选答案中只有一个答案是正确的，请把正确答案的字母代号填写在题后括号内。1. 下面程序段的时间复杂性为（ ）。 for(int i=0; in; i+) k+;AO（1） BO（n） CO(log2n) DO（n2）2. 以下数据结构中，（ ）是线性结构。 A广义表 B 二叉树 C 稀疏矩阵 D 串3. 对于一个线性表，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( )。A 以顺序方式存储 B 以链接方式存储 C 以散列方式存储 D 以上均可4. 设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（ ）个元素。An-i Bn-i -1 Cni+l Di5. 通常同一逻辑结构中所有数据元素都具有相同的特性，这意味着（ ）。A数据元素长度相同B不仅数据元素所包含的数据项的个数相同，而且对应数据项的类型要一致C每个数据元素都相同D数据元素所包含的数据项的个数要相等6. 在一个具有n个单元的顺序栈Sn中，假设以地址高端n-1作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为（ ）。Atop不变 Btop=0 Ctop=top-1 Dtop=top+17. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。 A(rear+1)% n=front B rear=front Crear+1=front D (rear-l) % n=front8. 不属于队列的基本运算是（ ）。A从队尾插入一个新元素 B从队列中删除第i个元素C判断一个队列是否为空 D取队头元素的值9. 若串S=software,其子串的数目是（ ）。A8 B37 C36 D910. 在下列存储形式中，（ ）不是树的存储形式。A双亲表示法 B孩子链表表示法C孩子兄弟表示法 D顺序存储表示11. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足 ( )。 A只有一个叶子结点 B 所有的结点均无右孩子C所有的结点均无左孩子D 是任意一棵二叉树12. 按照二叉树的定义，具有3个结点的二叉树有( )种。A3种 B4种 C5种 D8种13. 一个有n个顶点的无向图最多有 ( ) 条边。A n B n(n-1) C 2n D n (n-1)/214. 对右图所示有向图进行拓扑排序不可能得到的拓扑序列是（ ）A 1 2 3 4 7 5 6 B 1 2 4 3 5 7 6C 2 1 7 3 4 5 6 D 1 2 7 3 4 5 615. 设哈希地址空间为0m-1, 用函数H(k)=k % p作为散列函数，即，为了减少发生冲突的概率，一般取p为（ ）。A小于m的最大奇数 Bm C小于m的最大素数 D大于m的最大素数16. 50个元素用二分法查找时，最大比较次数是（ ） A25 B50 C10 D617. 冲突指的是（ ）。A不同的关键字值对应相同的存储地址 B两个元素具有相同序号C两个元素的关键字值不同，而属性相同 D装填因子过大18. 每次把待排序的区间划分为左，右两个子区间，其中左区间中元素的排序码不大于基准元素的排序码，右区间中元素的排序码均不小于基准元素的排序码，此种排序方法称作（ ）。A堆排序 B快速排序 C冒泡排序 D希尔排序19. 一组记录的关键字为45,80,55,40,42,85,则利用堆排序的方法建立的初始堆为 （ ）。A80,45,55,40,42,85 B85,55,80,42,45,40C85,80,55,45,42,40 D85,80,55,40,42,4520. 一般情况下，以下四种排序方法中，平均时间复杂度最小的是（ ）A冒泡排序 B快速排序 C直接选择排序 D直接插入排序使用班级计51,052,053,054,计师051,软051,052出卷日期 2007年6月21日南通大学20062007学年第二学期 数据结构（闭卷） 试卷（A）第2页 共3页装订线学院： 专业： 班级： 姓名： 学号： 密 封 线 得分评卷人二、判断题（每小题1分，共10分）请判断下各命题，如正确的，请在前面括号内填上，否则填上。1.（ ）队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。2.（ ）二叉树中所有结点个数是2k-1，其中k是二叉树的深度。 3.（ ）栈和队列的存储方式既可是顺序方式，也可是链接方式。 4.（ ）二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 5.（ ）对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。 6.（ ）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 7.（ ）用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 8.（ ）具有12个结点的完全二叉树有5个度为2的结点。9.（ ）线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。10.（ ）顺序表结构适宜于进行查找操作，而链表适宜于进行插入与删除操作。得分评卷人三、填空题(每小题1分，共10分) 请将下列各题的正确答案填写在空白处。1. 从逻辑关系上讲，数据结构主要分为两大类： 和非线性结构。2. 平衡二叉树中各结点左右子树深度之差的绝对值不超过_。3一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1in）个元素是_。4. 假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=_。 5. 数据结构中评价算法的两个重要指标是 和空间复杂度。 6. Hash表的平均查找长度与处理冲突的方法 关。7. 堆排序的算法时间复杂度为_ _。8. 若一棵二叉树有2个度为2的结点，1个度为1的结点，则度为0的结点个数是 。 9. 100个顶点的无向连通图至少有 条边。 10设有两个串p和q，其中q是p的子串，求q在p中首次出现位置的算法称为 。得分评卷人四、应用题（每小题10分，共40分）请运用所学的数据结构知识解答下列各题。1设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。2设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。南通大学20062007学年第二学期 数据结构（闭卷） 试卷（A）第 3页 共3页3设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。4设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。装订线学院：