数据结构试卷试题A

1、专业班级： 姓名： 学号： 密封线河南理工大学万方学院 2006-2007学年第 2 学期专业班级： 姓名： 学号： 密封线数据结构试卷（A卷）考试方式： 闭卷 本试卷考试分数占学生总评成绩的 80 %总 分题号一二三四核分人得分 复查总分 总复查人 得分评卷人 毋小省一、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，每小题2分，共30分）1. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。(1in+1) (1) O(0) (2) O(1) (3) O(n) (4) O(n2)2.在单链表中p所指结点后

2、插入s所指结点,则下列语句正确的是( ) (1) pnext=s; snext=p; (2) snext=pnext; pnext=s; (3) snext=p; pnext=s; (4) pnext=snext; snext=p;3. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是( )（1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（ ）（1） 根结点无右子树的二叉树 （2） 根结点无左子树的二叉树（3） 根结点可能有左二叉树和右二叉树 （4） 根结点只有一个孩子结点的

3、二叉树5设二叉树的根为第一层，则深度为i的二叉树结点数最多为（ ）（1）i （2） i +1 （3）i - （4）i -1 6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()（1）前序遍历 （2）后序遍历 （3）中序遍历 （4）层次遍历7给定下列有向图，从顶点1出发，其广度优先搜索序列为（ ）（1）12534 （2）12435 （3） 14325 （4）123458散列表中的冲突是指（ ）（1）  两个元素具有相同的序号 （2） 两个元素的关键字相同，而其他属性相同（3） 不同的关键字对应相同的存储地址 （4） 数据元素的地址相同9. 线性表

4、若采用链式存储结构时，要求内存中可用存储单元的地址:（ ）（1）必须是连续的 （2）部分地址必须是连续的（3）一定是不连续的 （4）连续或不连续都可以10下面程序段的时间复杂度为（ ） for (int i=1;i<m;i+) for (int j=1;j<n;j+) aij=i*j; (1) O(m2) (2) O(n2) (3) O(m*n) (4) O(m+n)11当利用大小位的数组顺序存储一个队列时，该队列的最大长度为（ ）（1）n-2 (2) n-1 (3) n (4)n+112对线性表进行折半搜索时，要求线性表必须（ ）（1）顺序存储 （2）顺序存储且结点按关键字有序（

5、3）链式存储 （4）链式存储且结点按关键字有序13采用线性探查法解决冲突时所产生的一系列后续地址（ ）（1）必须大于等于原散列地址 （2）必须小于等于原散列地址（3）可以大于或小于但不等于原散列地址 （4） 对地址在何处没有限制14栈的插入和删除操作在（ ）进行。（1）栈顶 （2）栈底 （3）任意位置 （4）指定位置15在一个顺序存储的循环队列中，对头指针指向队列的（ ）位置。（1）前一个 （2）后一个 （3）当前 （4）后面得分评卷人 毋小省二、填空题（每空1分，共20分）1.数据的逻辑结构被分为_0_，_，_，_。2.单链表与循环链表的区别是_。3.在一个循环队列中，判断对空的条件是串是_

6、，判断对满的条件是串是_4. 从有序表（12，18，30，43，56，78，82，95）中一次折半搜索43和56元素是，其比较次数分别为_和_。5.与哈西表的平均查找长度有关的三个因素分别是_，_ ，_。6.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数个边数分别为_和_。7.在二叉排序树中，左子树所有结点的关键字值都_该结点的关键码值，而右子树中所有结点的关键字值都_该结点的关键码值。8.在一个小顶堆中，堆顶元素的值是所有结点中的_，在一个大顶堆中，堆顶元素的值是所有结点中的_。9.假定一组纪录的关键字为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为_。

7、10.在一个网络的所有生成树中，各边权值之和最小的生成树，称为该网络的_。得分评卷人 毋小省三、判断题（判断下列各题是否正确，若正确在（）内打“”，否则“×”。每小题1分，共10分）（ ）1. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（ ）2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（     ）3.二叉树中任何一个结点的度都是2。（     ）4.有回路的有向图不能完成拓扑排序。（ ）5.按先根次序遍历森林等同于按先序法遍历对应的二叉树。（   

8、  ）6.n（n>1）个顶点的无向连通图最少由n-1条边。（ ）7.有向图的邻接表表示中边表中结点的总数与有向图中有向边的条数相等。（     ）8.一个无向图的邻接矩阵中各元素之和与图中边的条数相等。（ ）9.归并排序要求待排序文件已部分排序。（ ）10.顺序检索时数据的存储方式可以是顺序的，也可以是链接的。得分评卷人 毋小省四、综合题（共40分）1已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。(7分) 2设待排序的记录的关键字序列

9、为12，2，16，30，10，20，18，写出使用链式基数排序每趟的结果。(6分)3、拓扑排序的结果不是唯一的，对于下图的结点进行拓扑排序，试写出其中的任意5个。(5分)V1V3V4V6V5V7V8V9V2A4分别按前序、后序、对称序列写出下图二叉树的结点，并转化为树林，分别按先根次序、后根次序列出其结点。(6分)IFDEABCGH5.已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key)=key MOD 13,表长为13，分别用线性探查法和链地址法处理冲突构造哈希表，并计算各平均查找长度。(10分)6.程序填空(6分)对有序表R0至Rn-1进行二分查找，成功时返回记录在表中的位置，失败时返回0.Struct sqlist keytype key; int binsrch(sqlist R ,keytype k) /