哈工程计算机试题

哈工程计算机试题.txt什么叫神话？请听男人向你表达爱意；什么叫传说？请听男人对你的承诺；什么叫梦境？请看你自己听到前两者时的反应。哈尔滨工程大学计算机考研笔记与真题一填空（每空一分，共14分）1数据元素是数据结构的基本单位，数据项是数据的不可分割的最小单位。2深度是k的完全二叉树至少有2^（k－1）个结点，至多有2^k-1个结点。3哈希表的查找效率主要取决于造表时选取的哈希函数和处理冲突的方法。4对100个记录进行折半查找，最多比较7次，最少比较1次。5有n个顶点的无向图，最少有0条边，最多有n(n-1)/2条边。6AOE网中，从源点到汇点的最长路径上的活动叫做关键活动。有环的图不能进行拓扑排序。7对于堆排序，常用的建堆算法是筛选法，堆的形状是一棵完全二叉树。二判断题（每小题1分，共5分）1线性表的链式存储结构优于顺序存储结构。错2链表的每个节点中都帢包含一个指针。错例如双向链表3栈和队列都是顺序存储结构的线性结构。错链栈4若数的度为2时，则该树为二叉树。错5若广义表中的每个元素都是原子，则广义表为线性表。对三问答题（每小题4分，共16分）1一棵3阶4层（根为第一层，叶子为第四层）的B－树，至少有多少个关键字，至多有多少个关键字？答：7个26个2利用栈秋表达式（（A-B）-C）-(D-(E-F))的值，运算符栈和操作数栈各必须具有多少项？答：5项4项3以行序为主序存储10阶对称矩阵A，采用下三角的压缩存储方式，若起始地址是d，则A85的存储地址是多少？答：32＋d4设哈希表中以存在无个记录（如图一所示）。哈希函数为H(K)=KMOD11，用二次探测再散列处理冲突。请问关键字为94的记录的存储地址是多少？012345678910图一4516396276答：存储地址是2四综合题（每小题5分，共35分）1给定一组权值{9，6，14，17，2，15，3，16}，请构造哈夫曼树，并计算其带权路径长度。答：带权路径长度1862已知二叉树的先序遍历的结果为ABCDEFGHIJ，中序遍历的结果为CBEDAHGIJF，请画出这颗二叉树。3对图二所示的无向图，（1）请用邻接表表示，且顶点链接按序号从小到大链接。（2）请写出从V0出发的深度优先遍历和广度优先遍历的结果。图二：012345674将图三所示的树转换为二叉树，并使其成为后序线索树。图三:ABCDEFGHIJKLMN5对关键字序列{44，12，53，13，37，88，24，61}构造一棵平衡二叉树。6已知一个OE网，如图四所示，求其关键路径，并给出时间4的最迟发生时间和事件5最早发生时间？图四：144125269115100918146353577887对序列{50，77，64，98，39，12，26，48，44，35}创建初始堆。五（8分）设指针head指向无表头结点单链表的首结点。试设一算法，删除链表中值为X的结点，若X结点不存在，则输出“不存在”信息。六（10分）已知一个有向图的邻接表，试编写一个算法求每个结点的出度和入度。七（12分）已知一个二叉树存储于二叉链表中，其结点结构为lcdatarc其中lc和rc分别为指向左子树和右子树根的指针域。试编写一个非递归算法，求二叉树的结点总数及其深度。UID2813帖子13精华17积分1641威望401K币1152宣传0阅读权限100在线时间18小时注册时间2007-4-25最后登录2008-3-2查看详细资料TOP亮剑版主UID2813帖子13精华17积分1641威望401K币1152宣传0阅读权限100个人空间发短消息加为好友当前离线2#大中小发表于2007-7-2223:04只看该作者一填空题（13分）1数据结构从逻辑上分（线性）结构和（非线性）结构。2若广义表中的每个元素都是（原子），则广义表变成为线性表。3连通图的极小连通子图称为改图的（生成树）。4哈希（hash）法存储的基本思想是根据（关键字）来决定（存储地址）。5迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。6两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。7哈夫曼树是叶子节点（带权路径长度）最短的二叉树。8稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。9N个结点的线索树有（n+1）根线索。二选择题（12分）1一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输入序列是dceab2深度为h的4阶B-树（根在第一层，叶子在第h层），叶子结点的数目最少为2^h-13广义表(a,b,(c,(d,e)))的尾是（b,(c,(d,e))）。4具有5层结点的平衡二叉树至少有12个结点。5设二叉树是由森林变换得来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点有n＋1个。6下列不属于内部排序的算法是BA归并排序B拓扑排序C树型排序D折半插入排序三回答问题（20分）1对n个结点的二叉树进行中序遍历，算法中所设的栈，栈中元素最少时可能是多少个？最多时可能是多少个？答：2个，n+1个2对n个记录进行简单的插入排序，最少共需要比较多少次？最多共需要比较多少次？答最少n－1次最多1＋2＋3…………＋（n－1）次3对13个有序记录进行折半查找，查找成功和不成功的平均查找长度各为多少？4采用上三角压缩存储10阶对称矩阵A，若以行序为主存储，且起始地址为d则A3，8的存储地址为多少？它与以列序为主序存储时的哪一个元素的起始位置一致？答：d＋24A4,75设循环队列最大空间为m（0，…，m－1），头，尾指针为front，rear。加入判别队列空的条件是（front＋1）MODm＝rear，那么判别队列满的条件是什么？front，rear的初值应是多少？答front＝rear初值front＝0rear＝1四应用题（25分）1对一组记录的关键字（49，38，66，80，75，19，22）进行快速排序，请写出各趟排序后的状态，并说明总共比较了多少次？2设哈希表的地址空间为0－6，哈希函数H(K)=KMOD7。请对关键字序列（32，13，49，18，22，38，21）按链地址法解决冲突的办法构造哈希表。并求出查找成功的平均查找长度。3已知二叉树的左，右子树各含3个结点。试分别构造满足如下要求的二叉树：（1）左子树的先序序列与中序序列相同，右子树的先序序列与中序序列相同。（2）左子树的中序序列与后序序列相同，右子树的先序序列与中序序列相同。4对关键字（67，49，80，14，22，31，95，38，43，56，73）构造平衡二叉树。5请写出表达式a+b*(c-d)-e/f的二叉树表示，并使其成为后序线索树。五算法题（30分）1设计一算法，在单链表中删除数据元素的值相同的多余结点。2设计一算法，在中序线索树上求指针P所指结点的前驱结点。3将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。UID2813帖子13精华17积分1641威望401K币1152宣传0阅读权限100在线时间18小时注册时间2007-4-25最后登录2008-3-2查看详细资料TOP亮剑版主UID2813帖子13精华17积分1641威望401K币1152宣传0阅读权限100个人空间发短消息加为好友当前离线3#大中小发表于2007-7-2223:04只看该作者一判断题(每小题一分，共十分)1数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。对2线性表的逻辑顺序与存储顺序总是一致的。错3广义表的表头或是元素或是一个广义表，而表尾总是一个广义表。对4拓扑排序是一种内部排序的算法。错5字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。对6若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索。错7稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。对8在AOE网中，一定有不止一条关键路径。错9二维数组是其数据元素为线性表的线性表。对10一个栈的输入序列是12345，则输出序列43512是可能的。错二单项选择（每小题2分，共20分）1数据结构从逻辑上可以分成线性和非线性两种结构。2哈希（Hash）法查找的基本思想是根据关键字值来决定记录的存储位置。3利用栈求表达式（（A-B）-C）-(D-(E-F)),操作数栈须有4项。4图的广度优先搜索算法类似于二叉树的按层遍历操作。5在所有排序方法中关键字比较次数与记录初始排列次序有关的是插入排序。6二维数组A的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，A[5][8]的起始位置是1807表达式a*(b+c)-d的后缀表示（逆波兰式）是abc+*d－8在一个具有n个结点的单链表中查找，查找成功时需要平均计较(n+1)/2结点。9设Q[0……n-1]为循环队列，front,rear分别为队列的头，尾，则队列中的元素个数为(rear-front+n)MODn10在各种查找方法中，平均查找长度与结点个数无关的查找方法是二叉树查找三计算题（每小题6分，共30分）1一颗树有N1个度为1的结点，N2个度为2的结点…………，Nm个度为m的结点，求：该树中终端（叶）结点的个数N02对长度为12的有序表进行折半查找，求查找成功与不成功时各平均比较次数。3已知一颗3阶的B－树中含有25个关键字，求该B－树的最小高度和最大高度（不包含叶子层）4已知一棵平衡二叉树的深度为6，求树中最少可能的结点数和最多可能的结点数。5对n个结点的平衡二叉树，请分别求出当二叉树具有最小深度K和最大深度K时，第K层上的结点数。四综合题（每小题8分，共40分）1广义表A＝((a),(b,(c,d,e)),()),请写出其链式存储结构。设链表中有两类结点，表结点形式为tag=1hptp,其中指针hp和tp分别指向表头和表尾，元素（原子）结点形式为tag＝0元素值2对关键字序列（49，38，65，97，75，13，27，51，55，10）进行希尔排序。若排序三趟，各趟的增量分别为d1=5,d2=3,d3=1，则请写出每趟的结果及元素移动次数。3电文中使用字符a,b,c,d,e,f,他们出现的频率为（4,7,5,2,9,8）,请画出对应的编码哈夫曼树，并求出传送电文的总长度。4已知一棵二叉树的中序序列为DAJFBGICEHK，后序序列为DAFBJCIKHEG,请画出该二叉树，并使其成为先序线索树。5对于加权图1268151341610920105用克鲁斯卡尔(Kruskal)方法构造最小生成树，并写出选边的次序。五算法题（1，2小题各13分，3，4小题各12分，共50分）1设用二叉链表表示的二叉树不空，其根指针为root，结点形式为：lchilddatarchild请写出将二叉树中所有结点的左，右子树相互交换的非递归算法。2利用两个栈S1和S2来模拟一个队列。若不存在栈溢出问题，则请写出用栈的操作来实现队列的插入和删除的算法。3设计一个算法，在长度为n的（小顶）堆R[1………n]中删除一个元素R[s]（s=n）产生一个长度为n－1的(小顶)堆，并将R[s]存放于R[n]中。4假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指节点的前驱结点变为p所指结点的后继结点。答案：三、计算题（每小题6分，共30分）m1．n0=1+∑((i-1)*ni)i=22．查找成功平均比较次数：37/12查找不成功平均比较次数：49/133．最小高度：3最大高度：44．最少结点数：20最多结点数：635．最小深度时：n+1-2k-1最大深度时：1四、综合题（每小题8分，共40分）111Λ1．A1ΛΛ1Λ11Λ0d0a0c0b2．第1趟：13275155104938659776移动5次第2趟：13104938275155659776移动3次第3趟：10132738495155657697移动5次3．电文总度：8701010101014．5．选边的顺序：（1，6）（2，3）（0，1）（2，6）（3，4）（0，5）五