数据结构试卷A

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

2、则下列语句正确的是（ ）（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） 根结点只有一个孩子结点的二叉树5设二叉树的根为第一层,则深

3、度为i的二叉树结点数最多为（）（1）i（2）i +1 （3）i-（4）i16. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()（1)前序遍历(2）后序遍历（3)中序遍历(4)层次遍历7给定下列有向图，从顶点1出发，其广度优先搜索序列为（）（1)12534 (2)12435 （3） 14325 （4）123458散列表中的冲突是指(）（1)  两个元素具有相同的序号（2)两个元素的关键字相同，而其他属性相同（3）不同的关键字对应相同的存储地址 （4）数据元素的地址相同9。 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:( )（1)必须

4、是连续的 （2）部分地址必须是连续的（3)一定是不连续的 （4）连续或不连续都可以10下面程序段的时间复杂度为( ） for (int i=1；im；i+) for （int j=1；jn;j+） aij=i*j; (1） O(m2） (2）O(n2) （3） O（mn) (4） O（m+n）11当利用大小位的数组顺序存储一个队列时,该队列的最大长度为（ ）(1)n2 (2) n-1 （3） n （4)n+112对线性表进行折半搜索时，要求线性表必须（ ）（1)顺序存储 （2)顺序存储且结点按关键字有序(3)链式存储 （4）链式存储且结点按关键字有序13采用线性探查法解决冲突时所产生的一系列后

5、续地址（ ）（1)必须大于等于原散列地址 (2）必须小于等于原散列地址(3)可以大于或小于但不等于原散列地址 (4) 对地址在何处没有限制14栈的插入和删除操作在（ )进行。（1）栈顶 （2）栈底 (3)任意位置 （4)指定位置15在一个顺序存储的循环队列中，对头指针指向队列的（ ）位置。(1）前一个 （2）后一个 （3)当前 (4)后面得分评卷人毋小省二、填空题(每空1分，共20分）1。数据的逻辑结构被分为_0_,_，_,_。2。单链表与循环链表的区别是_。3。在一个循环队列中，判断对空的条件是串是_,判断对满的条件是串是_4.从有序表（12，18，30，43，56，78,82，95）中一次

6、折半搜索43和56元素是,其比较次数分别为_和_。5。与哈西表的平均查找长度有关的三个因素分别是_，_ ，_。6。对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数个边数分别为_和_。7。在二叉排序树中,左子树所有结点的关键字值都_该结点的关键码值，而右子树中所有结点的关键字值都_该结点的关键码值.8。在一个小顶堆中,堆顶元素的值是所有结点中的_，在一个大顶堆中，堆顶元素的值是所有结点中的_。9。假定一组纪录的关键字为（46,79,56，38，40，80），对其进行快速排序的一次划分的结果为_.10.在一个网络的所有生成树中,各边权值之和最小的生成树，称为该网络的_.得分评卷人毋小省三、

7、判断题（判断下列各题是否正确，若正确在（）内打“”，否则“×"。每小题1分，共10分）( ）1。 栈和队列的存储方式既可是顺序方式,也可是链接方式。（ )2。 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。（     ）3.二叉树中任何一个结点的度都是2。（     ）4。有回路的有向图不能完成拓扑排序.( ）5.按先根次序遍历森林等同于按先序法遍历对应的二叉树。（     ）6.n（n1)个顶点的无向连通图最少由n1条边.（ )7。有向图的邻接

8、表表示中边表中结点的总数与有向图中有向边的条数相等。（     )8.一个无向图的邻接矩阵中各元素之和与图中边的条数相等。（ ）9。归并排序要求待排序文件已部分排序.（ ）10.顺序检索时数据的存储方式可以是顺序的,也可以是链接的。得分评卷人毋小省四、综合题（共40分）1已知某系统在通信联络中只可能出现8种字符,其概率分别为0。05,0.29，0.07，0。08，0.14，0。23，0。03，0.11,试设计哈夫曼编码。（7分)2设待排序的记录的关键字序列为12，2，16，30，10，20,18，写出使用链式基数排序每趟的结果。(6分）3、拓扑排序的结果

9、不是唯一的,对于下图的结点进行拓扑排序，试写出其中的任意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至Rn1进行二分查找,成功时返回记录在表中的位置，失败时返回0。Struct sqlist keytype key;；int binsrch（sqlist R ,keytype k）/在表R中查找关键字k i