数据结构B复习题.doc

《数据结构B复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、密封装订线系（部）:专业:班级:姓名:学号:华北科技学院200／20学年第学期数据结构B考试试卷考试科目：数据结构B选用试卷A适用专业：题目一二三四五六七八九十总分得分一、选择题（每题2分，共10题，总计20分）１、算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B２、在下面的程序段中，对x的赋值语句的频度为（）for（i=1;i<=n;i++）for(j=1;j<=n;j++)x=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删

2、除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表4、对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)5、假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。A.808B.818C.1010D.10206、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树

3、上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M37、设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-18、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列（）A.543612B.453126C.346521D.2341569、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数（）A．9B．11C．15D．不确定10、适用于折半查找的表的存储方式及元素排列要求为()A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素

4、无序D．顺序方式存储，元素有序二、填空题（每空2分，共10空，总计20分）1、___________是限定仅在表尾进行插入或删除操作的线性表。2、已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的后序序列为_______________________。3、设无向图的顶点个数为n，则该图最多有______________条边。4、具有256个结点的完全二叉树的深度为________________。1、实现字符串拷贝的函数strcpy为：voidstrcpy(char*s,char*t)/*copytto

5、s*/{while(____________________________)}2、图有两种基本遍历的方法是：_______________和广度遍历。3、己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需比较__________次查找成功，查100时，需__________次才能确定不成功。4、散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是

6、__________________。存放元素59需要探测的次数是_________________。三、应用题（每题6分，共4题，总计24分）1、若一份电文中共使用了A、B、C、D、E五种字符，他们在电文中出现的频率为5、8、3、9、6。试构造哈夫曼树（要求左子树的权值小于或等于右子树根结点的权值），给出每个字符的哈夫曼编码。2、下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f("abba")返回1，f("abab")返回0；intf((1)________){inti=0,j=0;while(s[j])(2)_______

7、_;for(j--;i

8、f19514182716821312六、用普里姆算法算法求下图的最小生成树，要求写出邻接矩阵及求解的详细过程。（本题10分）七、设有下列递归算法:intvol(intn){intx,s;if(