数据结构试卷A

《数据结构试卷A》由会员分享，可在线阅读，更多相关《数据结构试卷A（6页珍藏版）》请在装配图网上搜索。

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;im;i+) for (int j=1;j1）个顶点的无向连通图最少由n-1条边。（ ）7.有向图的邻接表表示中边表中结点的总数与有向图中有向边的条数相等。（ ）8.一个无向图的邻接矩阵中各元素之和与图中边的条数相等。（ ）9.归并排序要求待排序文件已部分排序。（ ）10.顺序检索时数据的存储方式可以是顺序的，也可以是链接的。得分评卷人 毋小省四、综合题（共40分）1已知某系统在通信联络中只可能出现8种字符，

5、其概率分别为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、拓扑排序的结果不是唯一的，对于下图的结点进行拓扑排序，试写出其中的任意5个。(5分)V1V3V4V6V5V7V8V9V2A4分别按前序、后序、对称序列写出下图二叉树的结点，并转化为树林，分别按先根次序、后根次序列出其结点。(6分)IFDEABCGH5.已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key

6、)=key MOD 13,表长为13，分别用线性探查法和链地址法处理冲突构造哈希表，并计算各平均查找长度。(10分)6.程序填空(6分)对有序表R0至Rn-1进行二分查找，成功时返回记录在表中的位置，失败时返回0.Struct sqlist keytype key; int binsrch(sqlist R ,keytype k) /在表R中查找关键字k int low ,high,mid; low=0; high=n-1; while( ) mid=(low+high)/2; if (k=Rmid.key) return mid; else if( kRmid.key ) ; else ; return 0;