《2017年上海海事大学信息工程学院821数据结构考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年上海海事大学信息工程学院821数据结构考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海事大学信息工程学院821数据结构考研导师圈点必考题汇编一、填空题1 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_、_、_、_。【答案】 2 棵有个结点的满二叉树有_个度为1的结点、有_个分支（非终端）结点和_个叶子，该满二叉树的深度为_。【答案】或 【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。3 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）/2。 4 关键码
2、序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_。【答案】（Q ，A ，C ，S ，Q ，D ，F ，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。快速排序（quicksort ）的基本思想是，通过一趟
3、排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 5 设二维数组A 的行和列的下标范围分别为【答案】时，则i=2，j=3。 当其值为和每个元素占2个单元，按行优先顺处的元素为_。序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是6 在n 个顶点的非空无向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。7 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存
4、储区域时，【答案】1196【解析】设元素的行标为i ，列标为j 。则它的存储位置为： 8 VSAM 系统是由_、_、_构成的。【答案】索引集；顺序集；数据集9 在一棵m阶的个数是_。【答案】 最少 【解析】m阶树除根结点和叶子结点外，结点中关键字个数最多是10栈是_的线性表，其运算遵循_的原则。；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）11建立索引文件的目的是_。【答案】提高查找速度 12设为哈夫曼树的叶结点数日，则该哈夫曼树共有_个结点。【答案】 【解析】哈夫曼树只有度为0和2的节点。树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的 的地址是：_。关
5、键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字二、选择题13程序P 在机器M 上的执行时间是20秒，编译优化后，P 执行的指令数减少到原来的CPI 増加到原来的1.2倍，则P 在M 上的执行时间是（ ）A.8.4 秒 B.11.7 秒 C.14 秒 D.16.8 秒 【答案】D 【解析】 而14假设某计算机的存储系统由Cache 和主存组成。某程序执行过程中访存1000次，其中访问Cache 缺失（未命中）50次，则Cache 的命中率是（ ）。A.5% B.9.5% C.50% D.95%【答案】D【解析】Cache 的命中率次数，程序总访存次数，其中为访问
6、Cache 的次数，为访存主存的所以根据公, 程序访存次数减去失效次数就是访问Cache 的次数式可得：H=（1000-50）/1000=95%。 15主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）A .10 Mbps B. 20 Mbps C.80 Mbps D.100 Mbps 【答案】C【解析】 16协议对A.011111000011111010B.0
7、11111000111110101111110 C.01111100011111010D.011111000111111001111101 【答案】AHDLC 协议对比特串进行组帧时，HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】开始和结束，因此在帧数据中凡是出现了 5个连续的位“1”的时候，就会在输出的位流中填充一个“0”。所以答案为A 。 17某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。 组帧后对应的比特串为（ ） 则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ） A.0153180H一、填空题考研试题
