中央民族大学信息工程学院856计算机学科专业综合之数据结构考研冲刺密押题.pdf

2017年中央民族大学信息工程学院856计算机学科专业综合之数据结构考研冲刺密 押题（一）注意:本试题所有答案应写在答题纸上,不必抄题,写清题号，写在试卷上不得分；答卷需用黑色笔（钢笔，签字笔，圆珠笔）书写，用铅笔、红色笔等其他颜色笔答题，试题作废；答卷上不得做任何与答题无关的特殊符号或者标记，否则按零分处理；考试结束后试题随答题纸一起装入试题袋中交回。_、选择题1 对矩阵压缩存储是为了（1A方便运算B方便存储C.提高运算速度D.减少存储空间【答案】D解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素 放在一个存储空间，目的就是为了节省空间。2.在TCP/IP体系结构中，直接为ICMP提供服务的协议是（1A.PPPB.IPC.UDPD.TCP【答案】B。【解析】首先明确ICMP是网络层的协议，由于服务必须是下一层向上一层提供服务的，因 此选项C项中的UDP和选项D项中的TCP属于传输层，在网络层上面，所以显然错误，而PPP 协议是广域网数据链路层协议，直接为网络层，也就是IP层提供服务，ICMP协议是封装在网络 层，因此PPP不能直接为ICMP提供服务，ICMP报文直接封装在IP分组中，故答案是B。3.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（1A直接插入排序B起泡排序C.基数排序D.快速排序【答案】C解析】C项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD三项都 依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则 不用移动，最坏情况元素反序，则需要移动n（n-1）/2次（为元素个数4.浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数 X=27x29/32,Y=25x5/8,则用浮点加法计算X+Y的最终结果是（1A.001111100010B.001110100010C.010000010001D.发生溢出【答案】D解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点 在对阶、规格化、判溢出这三步。X和Y的阶码不同，所以应该先对阶，对阶原则为：小阶向大 阶看齐。因此将Y对阶后得到：Y=2x5/32.然后将尾数相加，得到尾数之和为：34/32。因为这 是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号 位，即阶码的表示范围在-8+7之间。而阶码本身等于7,再加1就等于8。因此，最终结果发生 溢出。5.每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.|典2 B.C.flog;（+l）D.【答案】D解析二叉树结点总数村队+叫+垣（no,ni，a分别代表度为0,度为1,度为2的结点数 又在非空二叉树中：瞄m+l，且本题所给树为正则二叉树，叫=0,所以n=2*n-l.因此 11|=（04-1）/2 O6.现在有一颗无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（1A根节点的度一定为2B.树中最小元素一定是叶节点C.最后插入的元素一定是叶节点D.树中最大元素一定是无左子树【答案】D解析二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：中序遍历左子树；访问根节点；中序遍历右子树”。A项错误，当树中仅有一个或者两个结点时，根节点的度就可 能不为2；B项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问 的节点是根节点；C项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间 节点；D项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子 树。7.某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令 对应的微程序平均由4条微指令组成，采用断定法(下址字段法)确定下条微指令的地址，则微 指令中下址字段的位数至少是：()A.5B.6C.8D.9【答案】c【解析】32*4+2=130,27=128130ltag-a0)p-p-lchild;/沿左分支向下if(p-lchild1null)return(p-lchild);else return(null);/LeftMostBiThrTree RightMost(BiThrTree j/求结点 t 最右子孙的右线索 BiThrTree p=t；while(p-rtag=0)pp-rchild；沿右分支向下if(p-rchild!null)return(p-rchild);else return(mil 1);/RightMostint IsRightChild(BiThrTree tr father)若 t 是 father 的右孩子，返回 1,否则返回 0(father=LeftMost(t)；if(father&f ather-rchild=8t)return(1);else return(0);/Is RiqhtChild;void PostOrder InThr/BiThrTree卜七)后序遍历中序线索二叉树btBiThrTree father,p=bt;int flag;while(p!=null)(while(p-ltag=O)p=p-lchild；沿左分支向下if(p-rtag=O)flaq=O 左孩子为线索，右孩子为链，相当从左返回else fia*p为叶子，相当从右返回while(flag=l),访问结点if(IsRightChild(p,father)p=f ather;f lag=l;修改 P 指向双亲me/P是左子女，用最右子孙的右线索找双亲(p=RightMost(p);if(p&p-rtag=l)flag=l;else flag=O;)/while(f139=1)if(flaq-=C&pl=nulll p=p-rchii 转向当前结点右分支 结束 PostOrderlnThr28.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可 表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。(1)下面所示的序列中哪些是合法的？a.lonoioo b.rooiono c.moioio d.mooio(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true,否则返回false(假定被判定的操作序列已存入一维数组中【答案】(1)A和D是合法序列，B和C是非法序列。(2)设被判定的操作序列已存入一维数组A中，算法如下：int Judge(char All)/判断字符数组A中的输入输出序歹!是否是合法序列。(i=0/i为下标j=k=O;/j和k分别为T和字母O的个数while(A(il1=0)switch(Ai)(case 1 11:j+；break;/入栈次数增 1case O :k+;if(kj)printf(序列非法n);exit(0);i+；/不论Ai是，I，或，0,，指针i均后移)if(j!=k)printf(序列非法n);return(false);else printf(序列合法n”);return(true);/算法结束29.已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的 数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序)并且第一数组中所 有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进 行排序操作。例如：第一个数组为：4,12,28第二个数组为：1-7,9,29,45输出结果为：1，4,7.第一个数组9,12,28,29,45.第二个数组【答案】算法如下：void ReArranger(int/A和B是各有m个和n个整数的非降序数组，本算法将B数组元素逐个插入到A中使A中务元素均不大于B中各元素，H两数组仍保持非降序排列 while(Am-lB0)x=Am-l ;Am-l=B 0 ;/交换Am-1和B 0 j=l；wkile(jn&B j =0&A ix)A i+1 =A i-;/M找B 0 的插入位置Ai+1=x;算法结束30.编与递归算法，从大到小输出给定二叉排序树中所有关踵字不小于X的数据元素。要求你的 算法的时间复杂度为0(1理2(x+m).其中，2为排序树中所含结点数，m为输出的关键字个数。【答案】算法如下：void output(BSTree bst,int x)/从大到小输出二叉排序树bst中所有关键字不小Fx的数据元素 if(bs-t)(if(bst-data=x)output(bst-rchild,x);if(bst-data=x)printf(H%4dM/bst-xdata);if(bst-data=x)output(bst-lchild,x);/if/output31.给出以十字链表作存储结构，建立图的算法，输入(i，j，V,其中I,j为顶点号，V为权值。【答案】算法如下：uci.d Creator-hl m、L i s,-i 建立有向图的十字链表存储结构 int 假定权值为整型scanf(%d,&n);for(i=0,iheadvex=j;p-tailvex=i;p-weight=v;弧结点中杈值域p-headlink=gj.firstin;gj.firstin=p;p-tailink=g i).f irst-out;g i.f irstoutp;scanf(M%d%d%di,&j,&v);wZle算法结束32.已知无向图采用邻接表存储方式，试写出删除边(i，j)的算法。【答案】算法如下：void DeletEdge(AdjList g,int i,j)在用邻接表方式存储的无向图g中，)p=gi).firstarc；pre=nul：/删顶点 i 白他蕙(i,j)pre 是前驱指针while(p)if(p-adjvex=j)(if(pre=null)g i.f irstarc=sp-next.;else pre-next=p-next；free e=;:/沿 链 表 继 续 查 找删顶点(j,i)while(p)if(p-adjvex=i)if(pre=null)g j).f iratarc=p-next;else pre-next=p-next；free(p);释 放空间else pre=p；p-p-next;沿链表继续查找/DeletEdge33.以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算 法的时间复杂度。【答 案】算 法 如 下：int LongestString(char s)/串用一维数组s在储，本算法求最长重复子串，返回找长度int index=0 rmax=0;/index记最长的串在s串中的开始位置rmaxi其长度int length=l r i=0,start=0;/lengthi己局部重复子串长度，i为字符数组下标while(s(iI=*01)if(si=si+1J)i+;length+;else fl h-个重复子串结束 if(maxnextI=headl)p=p-next;q=head2;while(q-next!=head2)q=q-next;p-next=head2;q-next=headl;return(headl)；【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Headl最后一个结 点的链域指向head2,head2最后一个结点的链域指向headl,headl为结果循环链表的指针。37.设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame 1在时刻260前的该进程访问情况如下表所示(访问位即使用位1页号页框号装入时刻访问位07130142301222001391601当该进程执行到时刻260时，要访问的逻辑地址为17CAH的数据，请回答下列问题:(1)该逻辑地址对应的页号是多少？(2)若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少?要求给出计算 过程。(3)若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过 程。(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示)答案】(1)由题可知计算机的逻辑地址空间和物理地址空间均为64KB=216B,按字节编址,并且页的大小为IK=210,故逻辑地址和物理地址的地址格式均为：页号/页框号(6bil)页内偏移量(lObit)地址17CA=0001011111001010B,故可知其逻辑页号为000101B=5o(2)根据FIFO算法，需要替换出最早装入的页，故需置换。号页，将5号页装入7号页框 中，所以物理地址为0001111 U1001010B=lFCAHo(3)根据CLOCK算法，如果当前指针所指页框的使用位为0,则替换该页，否则将使用位 清零，并将指针指向下一个页框，继续查找。由题可知，将从2号页框开始，前4次查找页框号 的顺序为2、4、7、9,并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2 号页框的使用位已经为0,故将2号页框的页将5号装入2号页框，并将其对应使用位设置为1,所以对应的物理地址为0000101111001010B=0BCAHo38主机H通过快速以太网连接Internet,IP地址为192.168.0.8,服务器S的IP地址为211.68.71.80。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题a表所示。题a表编号IP分组的前40字节内容(十六进制)45000030019b400080061de8coa80008J344475010bd91388846b41c500()00000700243805db00000450000300000400031066e833d3444750cOa8(X)08213880bd9e0599fef846b41c667012I6d037e10000245000028019c400080061defc0a800083444750bd91388846b41c6e0599ff0501043802b32(X)OOA4500003801940008006Iddec0a80008(134447500bd91388846b41c6eO599ffO50184380C655000045000028681140003106067ad3444750c0a8000813880bd9eO599ffO846b41d65010l6d057d20000请回答下列问题。(1)题a表中的IP分组中，哪几个是由H发送的?哪几个完成了 TCP连接建立过程?哪几个 在通过快速以太网传输时进行了填充？(2)根据题a表中的IP分组，分析S已经收到的应用层数据字节数是多少？(3)若题a表中的某个IP分组在S发出时的前40字节如题b表所列，则该IP分组到达H 时经过了多少个路由器？题b表来自s发出的分组45000028 68114000 4006eCad(3444750 ca760106 1388alO8 e0599ff0 846b41d6 501016dO b7d6000()注：IP分组头和TCP段头结构分别如题a图、题b图所示:题a图IP分组头结构版本头部长度服务类型(8-15)总长度(16-31)标识标志片偏移生存时(TTL)协议头部校验和源IP地址目的IP地址题b图TCP段头结构源端口(0-15)目的端口(16-31)序号(seq)确认号(ack)数据偏移保留URGACKPSHRSTSYFlN窗口校验和紧急指分选项(长度可变)填充【答案】(1)由于题a表中1、3、4号分组的源IP地址(第1316字节)均为192.168.0.8(coa80008H),所以1、3、4号分组是由H发送的。题 a 表中 1 号分组封装的 TCP 段的 FLAG 为 02H(即 SYN=1,ACK=0),seq=846b41c5H,2 号分组封装的 TCP 段的 FLAG 为 12H(即 SY=1,ACK=1),seq=e059 9feffl,ack=846b41c6H,3 号分组封装的 TCP 段的 FLAG 为 10H(即 ACK=1),seq=846b41c6H,ack=e059 9ffOH,所以 1、2、3号分组完成了 TCP连接建立过程。由于快速以太网数据帧有效载荷的最小长度为46字节,表中3、5号分组的总长度为40(28H)字节，小于46字节，其余分组总长度均大于46字节，所以3、5号分组在通过快速以太网传输时 进行了填充。(2)由3号分组封装的TCP段可知，发送应用层数据初始序号为846b 41c6H,由5号分组封 装的TCP段可知，ack为846b所以5号已经收到的应用层数据的字节数为 846b 41d6H-846b 41c6H=10H=16B(3)由于S发出的IP分组的标识=6811H,所以该分组所对应的是题47-a表中的5号分组。S发出的IP分组的TTL=40H=64,5号分组的TTL=31H=49,64-49=15。所以，可以推断该IP分组 到达H时经过了 15个路由器。39.文件存储结构的基本形式有哪些?一个文件采用何种存储结构应考虑哪些因素？答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺 序结构、索引结构、散列结构。(1)顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本 质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指 针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺 序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。(2)带索弓|的结构，相应文件为索引文件。索引文件包括索引表和数据表，索弓I表中的索引 项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实 现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。(3)散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希 函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键 字的数目以及对文件作何种操作。2017年中央民族大学信息工程学院856计算机学科专业综合之数据结构考研冲刺密 押题(二)注意:本试题所有答案应写在答题纸上,不必抄题,写清题号，写在试卷上不得分；答卷需用黑色笔(钢笔，签字笔，圆珠笔)书写，用铅笔、红色笔等其他颜色笔答题，试题作废；答卷上不得做任何与答题无关的特殊符号或者标记，否则按零分处理；考试结束后试题随答题纸一起装入试题袋中交回。_、选择题1 若无向G=(V,E)中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是(1A.6B.15C.16D.21【答案】C【解析】要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连 通。首先需要图G的任意6个结点构成完全连通子图Gi，需n(n-l)/2=6x(6-1)/2=15条边，然后再添加一条边将第7个结点与G,连接起来，共需16条边。本题非常容易错误地选择选项A,主要原因是对保证图G在任何情况下都是连通的的理解，分析选项A,在图G中，具有7个 顶点6条边并不能保证其一定是连通图，即有n-l条边的图不一定是连通图。分析选项D,图G 有7个顶点21条边，那么图G-定是无向完全图，无向完全图能保证其在任何情况下都是连通 的，但是这不符合题目中所需边数最少的要求。2.若用户1与用户2之间发送和接收电子邮件的过程如图所示，则图中、阶段分别使用的应用层协议可以是(X用户1的 用户2的用户1 邮件服务常邮件服务器 用户2图电子邮件发送接收示意图A.SMTP、SMTP、SMTPB.POP3、SMTP、POP3C.POP3、SMTP、SMTPD.SMTP、SMTPs POP3【答案】D。解析】题中电子邮件的工作过程如下：用户1调用用户代理来编辑要发送的邮件，用户代理用SMTP将邮件传送给用户1的发送 端邮件服务器。发送端邮件服务器也就是用户的邮件服务器将邮件放入邮件缓存队列中，等待发送。运行在发送端邮件服务器的SMTP客户进程，发现在邮件缓存中有待发送的邮件，就向运 行在接收端邮件服务器也就是用户2的邮件服务器的SMTP服务器进程发起TCP连接建立。当 TCP连接建立后，SMTP客户进程开始向远程的SMTP服务器发送邮件。当所有的待发邮件发完 了,SMTP就关闭所建立的TCP连接。运行在接收端邮件服务器中的SMTP服务器进程收到邮件后，将邮件放人收信人的用户邮 箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用pop协议将 自己的邮件从接收端邮件服务器的用户邮箱中取回（如果由B箱中有来信的话）。因此题中1，2,3阶段分别使用的应用层协议可以是SMTP,SMTP,POP3,因此答案是D。SMTP采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮 件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。3.对线性表进行折半查找时，要求线性表必须（1A以顺序方式存储B以顺序方式存储，且数据元素有序C以链接方式存储D以链接方式存储，且数据元素有序【答案】B【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是 要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有 序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。4.相对于微程序控制器，硬布线控制器的特点是（1A.指令执行速度慢，指令功能的修改和扩展容易B.指令执行速度慢，指令功能的修改和扩展难C.指令执行速度快，指令功能的修改和扩展容易D.指令执行速度快，指令功能的修改和扩展难【答案】D解析在同样的半导体工艺条件下，硬布线（组合逻辑）控制器的速度比微程序控制器的 速度快。这是因为硬布线控制器的速度主要取决于逻辑电路的延迟，而微程序控制器增加了一级 控制存储器，执行的每条微指令都要从控制存储器中读取，影响了速度。由于硬布线控制器一旦 设计完成就很难改变，所以指令功能的修改和扩展难。因此，硬布线控制器的特点是指令执行速 度快，指令功能的修改和扩展难。5.将森林转换为对应的二叉树，若在二叉树中，结点u是结点V的父结点的父结点，则在原来 的森林中，U和V可能具有的关系是（XI父子关系II.兄弟关系III.U的父结点与V的父结点是兄弟关系A.只有B.I 和 IIC.I 和 IIID.I、II 和 III【答案】B【解析】首先，在二叉树中，若结点U是结点V的父结点的父结点，那么u*v的关系有如下 4种情况：接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中:情况（1），在原来的森林中U是V的父结点的父结点；情况（2）,在森林中u是V的父结点；情况（3）,在森林中u是V的父结点的兄弟；情况（4）,在森林中u与V是兄弟关系。由此可知，题目中的I、II是正确的。6.下列关于虚拟存储的叙述中，正确的是（1A.虚拟存储只能基于连续分配技术B.虚拟存储只能基于非连续分配技术C虚拟存储容量只受外存容量的限制D.虚拟存储容量只受内存容量的限制【答案】D。解析所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运 行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断 技术），将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以 非连续分配，虚拟存储器和外存大小没有关系，所以选项中的A,B,C都是错误的，所以答案 是D项。7.假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为1/()时 间。若CPU速度提高50%.I/O速度不变，则运行基准程序A所耗费的时间是(XA.55 秒B.60 秒C.65 秒D.70 秒【答案】D。解析CPU速度提高5。%.即CRJ性能提高比为1.5,改进之后的CPU运行时间=905.5=60 秒。UO速度不变，仍维持10秒，所以运行基准程序A所耗费的时间为70秒。8.有向带权图如题图所示，若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短 路径，则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其 余各最短路径的目标顶点依次是(XA.d,e,fB.e,d,fC.f,d,eD.f,e,d【答案】Co【解析】本题主要考查Dijkstra算法的思想和解题步骤。题目执行算法过程中各步的状态如 下表所示。执行Dijkstra算法过程中各步的状态表，故后续目标顶点依次为f，d,%点 越虻、bcdef集合Sk=l2(a,b)5(a,c)(a b)k=2(a.b.c)(a,b.d)(a.b,c|k=3(a.b.d)4(a,b c f)(a.b,c,e.)(a,b,c,f,d)k=5(a,b.c,f.d,e)9.排序过程中，对尚未确定最终位置的所有元素诳行一遍处理称为一趟排序。下列排序方法中,每一趟排序结束时都至少能够确定一个元素最终位置的方法是（1I.简单选择排序II希尔排序III.快速排序IV.堆排V.二路归并排序A.仅 I、III、IVB.仅 I、II、IIIC.仅 II、III、IVD仅 III、IV、V【答案】Ao【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最 小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。10,本地用户通过键盘登录系统时，首先获得的键盘输入信息的程序是（1A.命令解释程序B.中断处理程序C.系统调用服务程序D.用户登录程序【答案】B解析夕卜部设备在与计算机连接时有多种方式，中断技术就是一种常用方式。其工作原理 是：利用处理机中断信号线，夕卜部设备在需要服务的时候将该线设置为有效，计算机若同意接受 中断则会停止当前进程的运行，转而服务发出中断的物理设备（注意与陷阱，即软中断有区别）,那么对不同外部设备进行服务的程序代码是不同的，如何找到这些代码呢?这就要借助中断向量，中断向量一般是由硬件根据中断的类型（不同外设不同）计算所得，或计算机系统在开机配置时 所配置的。处理机取得中断向量，其实就是一个物理地址，该地址下存放的是为此中断服务的代 码的起始地址。所以，当键盘按下的时候，键盘控制器获得该操作动作，先】各键盘扫描码读入键 盘缓冲区，再向处理机发出键盘中断，适当的时候（一条指令的末尾或一条原语结束）处理机会 响应中断，调用指定服务程序将键盘缓冲区中的键盘扫描码输入到登录进程中去。如此，最先响 应键盘的必然是中断处理程序。本题中，像命令解释器（例如cmd窗口 系统调用服务和用户 登录程序都在中断处理程序后面。二、判断题11 两个长度不相同的串有可能相等。（）【答案】X【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才 相等。12.若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序札()【答案】X解析堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性 质。13.栈的输入序列是1,2,n,输出序列是w，2，an a=n(li%.an。()【答案】X【解析】出栈序歹U不一定满足aiai+i.a”，比如1进栈，然后出栈，街=1。箱为。14.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。()【答案】V【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无 序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的 查找长度。15.通常使用队列来处理函数或过程的调用。()【答案】X【解析】经常使用栈来处理函数或过程的调用。16.树中的结点和图中的顶点就是指数据结构中的数据元素。()【答案】V解析树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之 间的关系。17.一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。()【答案】V解析树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。18.稀疏矩阵压缩存储后，必会失去随机存取功能。()【答案】V解析稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素 的分布是没有规律的，为了压缩存储，就1各每一个非零元素的值和它所在的行、列号做为一个结 点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标 直接存取矩阵中的元素。19.在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。()【答案】X解析不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会 引起平衡旋转20.栈和队列都是限制存取点的线性结构。()【答案】21.有n个数顺序(依次)入栈，出栈序列有Cn种，Cn=l/n+l)*(2n)!/【(n!)*(n!)。()【答案】V22.树形结构中元素之间存在一对多的关系。()【答案】V解析树形结构是非线性结构，存在一对多的关系。23.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。()【答案】X解析队列是一种先入先出型结构，而栈才是先进后出的线性结构。24.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。()【答案】V解析可以有长度无穷大的广义表，只是在计算机中不能实现。25.在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空 间的碎片。()【答案】V【解析】最佳适配法：将可利用空间表中一个不小于n且最接近n的空闲块的一部分分配给 用户；最先适配法：从表头指针开始查找可利用空间表，将找到的第一个大小不小于n的空闲块 的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。三、算法设计题26.已知关键字序列N，K2(Km Ri)是大根堆。(1)试写出一算法将(K”K2.K,，Km KQ调整为大根堆；(2)利用(1)的算法写一个建大根堆的算法。【答案】(1)算法如下：void sift(RecType R,int n)=l;i=i/2)if(R(0.keyRi.key)Rj=Ri；j=i；else break;R(j)=R(O;)/sift(2)void HeapBuilder(RecType Rrint n)for(i=2;i=n;)sift(Rf i);)27.二路插入排序是将待排关键字序列ril.nJ中关键字分二路分别按序插入到辅助向量d|l.n 前半部和后半部(注：向量d可视为循环表)，其原则为，先将rl赋给dl，再从r记录开始分 二路插入。编写实现2-路插入排序算法。【答案】算法如下：void BiInsertSort(RecType R(,int n)/:路插人排序的算法int dn+l;/辅助存储d 1 1for(i=2;i=n;i+)=d 11.key)/插人后都 low=l;high=f inal;while(low=high)/折半查找插入位置何=(low+high)/2;if(R i .key*high+l;j一)d j+1=d j;/移动元素dhigh+l=R i;f inal+;/插入有序位置/ifelse/插入前部if(firstl)firstn;dn-Ri;elselow=first;high=n;while(low=high)(m=(low+high)/2;if(Ri.keyd(m).key)high=m-1；else low-m+1;/whilefor(j=first;j=high;j+)d(j;/移动元素d(high=Ri;first一;/if/if/forR11=dfirst 1;for(i=f irst%n-hl,j=2;i!=f isrt;i=i%n+l,j+)R(j next;/设链表有头结点q=p-next;/q指向待处理结点while(q)if(q-datap-data)p=q;/p记数据域值最大的结点q=q-next;p-prior-next=p-next;p-next-prior=p-prior;/将P摘卜p-next=d-next;p-prior=d;d-next-prior=p;d-next=p;/插入p结点 return d;)29.编写算法，求二叉树的宽度。【答案】算法如下：int Width(BiTree bt)(if(bt=null)return(0);BiTree Q;front=l;rear=l;last=l;temp=0;maxw=0;Qrear=bt;while(frontlchild!=rull)if(p-rchild!=null)if(frontlast)(last=rear;If(tempmaxw)temp=0;/if/while return(maxw);结束 Width求二叉树bt的最大宽度空二叉树宽度为0Q是队列，元素为二叉树结点指针，容量足够大/front为队头指针，rear为队尾指针/last为同层最右结点在队歹中的位置/temp记当前层宽度，maxw记最大宽度根结点入队Q+rear=p-lchild;左子女入队Q+rear=p-rchild;右子女入队 一层结束/last指向下层最右元素maxw=temp;更新当前最大宽度30.设给定关键字输入序列为(100,90,120,60,78,35,42,31,15)用哈希法散列0-10的 地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表,在等概率查找情况下查找成功的平均查找长度是多少？【答案】算法如下：#define m 11typedef struct nodeElemType key；/关键字struct node fext;/链指针Lnode,*LinkedList;typedef ElemType int;typedef struct node*HLK;void Creat(HLK HTm)/用链地址法解决冲突，构造哈希表，哈希函数用H(key)=key%11for(i=0;im;)H i=null;/初始化for(i=0;ikey=x;p-next=HT j ;HT(j =p;/将插入结点链入同义词表/Creat构造的哈希表如图所示：图构造的哈希表查找成功时的平均查找长度ASL=12/9。31.设计算法将一棵以二叉链表存储的二叉树按II贿方式存储到一维数组中(注：按层从上到下,由左到右1【答案】算法如下：typedef struc(DiTree data;int num;tnode/num 是结点在一维数组中的编号 tnodc Qmaxsize;队列，容量足够大void BiToSeqt BiTree t,ELemType seq本算法将二叉树的二叉链表存储结构转换为顺序存储结构seq(int front=0,rear：=0;tnode q;Bitree p;if(!t)exit(0);for(i=l;imaxsize;i+)seqi=#;初始化，#代表虚结点tq.data=t;tq.num=l;Q+rear=tq;根结点入队while(frontdata;存入顺序存储结构if(p-lch