黑龙江大学2014年《903数据结构与程序设计》考研专业课真题试卷
- 格式：pdf
- 大小：1.40 MB
- 文档页数：4
下载文档原格式
合集下载
天勤论坛_2014年全国硕士研究生计算机专业考试真题及答案解析与评分点
交换机 1 2 3
目的地址
00-e1-d5-00-23-b1
端口 2
00-e1-d5-00-23-a1
00-e1-d5-00-23-b1
00-e1-d5-00-23-c1
A． {3}和 {1} B．{2,3}和{1} C．{2,3}和{1,2} 35．下列因素中，不会影响信道数据传输速率的是（ ） 。 A．信噪比 B．频率带宽 C．调制速率
2
） 。
附
录
B．队空：end1 = = end2；队满：end2 = = (end1+1) mod (M-1) C．队空：end2 = = (end1+1) mod M；队满： end1 = = (end2+1) mod M D．队空：end1 = = (end2+1) mod M；队满：end2 = = (end1+1) mod (M-1) 4． 若对如下的二叉树进行中序线索化， 则结点 x 的左、 右线索指向的结点分别是 （ ） 。
） 。 ） 。
12．程序 P 在机器 M 上的执行时间是 20 秒，编译优化后，P 执行的指令数减少到原来 的 70%，而 CPI 增加到原来的 1.2 倍，则 P 在 M 上的执行时间是（ ） 。 A． 8.4 秒 B．11.7 秒 C．14.0 秒 D．16.8 秒 13． 若 x=103,y=-25，则下列表达式采用 8 位定点补码运算实现时，会发生溢出的是 （ ） 。 A． x+y B．-x+y C．x-y D．-x-y 14．float 型数据通常采用 IEEE 754 单精度浮点格式表示。假定两个 float 型变量 x 和 y 分别存放在 32 位寄存器 f1 和 f2 中， 若(f1)=CC90 0000H,(f2)=B0C0 0000H, 则 x 和 y 之间的关 系为（ ） 。 A．x<y 且符号相同 B．x<y 且符号不同 C．x>y 且符号相同 D．x>y 且符号不同 15．某容量为 256MB 的存储器由若干 4M 8 位 DRAM 芯片构成，该 DRAM 芯片的地 址引脚和数据引脚总数是（ ） 。 A．19 B．22 C．30 D．36 16． 采用指令 Cache 和数据 Cache 分离的主要目的是（ ） 。 A．降低 Cache 的缺失损失 B．提高 Cache 的命中率 C．降低 CPU 平均访问时间 D．减少指令流水线资源冲突 17．某计算机有 16 个通用寄存器，采用 32 位定长指令字，操作码字段（含寻址方式位） 为 8 位，Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基 址寄存器可使用任一通用寄存器，且偏移量用补码表示，则 Store 指令中偏移量的取值范围 是（ ） 。 A．-32768~+32767 C．-65536~+65535 B．-32767~+32768 D．-65535~+65536
2014年考研计算机统考真题及答案解析
2014考研统考考研统考计算机基础综合真题解析计算机基础综合真题解析【回忆版】一、单项选择题单项选择题：：第1～40小题小题，，每小题2分，共80分。
下列每题给出的四个选项中下列每题给出的四个选项中，，只有一个选项是最符合题目要求的只有一个选项是最符合题目要求的。
2、假设栈初始为空，将中缀表达式a/b-(c*d+e*f)/g 转化为等价后缀表达式过程中，当扫描到f 时，栈中的元素依次为：A 、+（*-B 、+（-*C 、/+(*-*D 、/+-*涉及考点涉及考点：：考察中缀和后缀表达式的转化，并考察栈这种数据结构4、如下图二叉树进行中序线索化，则元素X 的左、右线索指向的元素为A 、 ecB 、 eaC 、 dcD 、 ba涉及考点涉及考点：：中序线索化二叉树，找出左右线索5、森林F 转化为对应二叉树T ，则F 的叶结点个数是（）A 、T 的叶结点个数B 、T 中度为1的结点个数C 、T 的左孩子指向为空的个数D 、T 的右孩子指向为空的个数涉及考点涉及考点：：森林转化为二叉树做法：第一，断开除最左孩子的孩子节点，第二，连接孩子节点中各兄弟节点，第三，将树顺时针旋转45度第四，同理处理其他树。
第五，将所有树按照先后顺序依次作为右子树连接。
6、5个元素有4种编码方案，下列不是前缀编码的是A 、01,0000,0001,001,1B 、011,000,001,010,1C 、000,001,010,011,100D 、0,100,110,1110,1100涉及考点涉及考点：：字符的前缀编码8、用哈希（散列）方法处理冲突（碰撞）时可能发生堆积（聚集)现象，则下列会直接受到堆积现象影响的是A 、存储效率B 、散列函数C 、载运因子D 、平均查找长度涉及考点涉及考点：：哈希（三列）方法处理冲突堆积现象影响的因素9、存一棵具有15个关键词的4阶B 树，则含有关键词的结点可能有A 、5B 、6C 、10D 、15涉及考点涉及考点：：B 树10、用希尔排序法，对一列数据序列排序时，若第一次排序结果为：9,1,4,13,7,8,20,23,15，则该排序可能的间隔是：A 、2B 、3C 、4D 、5涉及考点涉及考点：：希尔排序法中的间隔11、下列最不可能是快速排序第二轮的结果是A 、2,3,5,4,6,7,9B 、2,7,5,6,4,3,9C 、3,2,5,4,7,6,9D 、4,2,3,5,7,6,9涉及考点涉及考点：：快速排序法12、程序P 在装置M 执行时间为20秒，编译优化后，P 执行的指令数是以前的70%，但CPI 为以前的1.2倍，则现在P 在M 上的执行时间为A 、8.4秒B 、11.7秒C 、14.0秒D 、16.8秒涉及考点涉及考点：：cpu 计算时间的计算方法。
数据结构考研真题及其答案完整版
数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。
通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。
为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。
一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。
入栈和出栈操作都是在栈顶进行的，而不是同一端。
2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。
二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。
答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。
2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。
答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。
三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。
答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。
它通常适用于具有重叠子问题和最优子结构性质的问题。
动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。
它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。
2. 请简要介绍红黑树的特点和应用场景。
答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。
黑龙江大学数据结构考试题
《数据结构课程设计》讲义一、表达式求值问题1.1 问题定义及设计要求表达式求值是程序设计语言编译中的一个最基本问题。
人们在书写表达式时通常采用将运算符放在两个操作数中间的“中缀”表示形式，称为中缀表达式。
但是这种表达式形式对计算机处理来说是不太适合的。
在计算机领域，经常将算术表达式表示成“后缀”表示形式，称为后缀表达式。
如: 中缀表达式3+2*(7-5)对应的后缀表达式为3275-*+。
要求实现（1）算数四则运算中缀表达式到后缀表达式的转换；（2）后缀表达式的求值；（3）中缀表达式的求值。
要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。
要求演示在求值过程中运算符栈、操作数栈、输入字符和主要操作过程及运算结果。
要求配备菜单，含如下选项：------------------------------------------------------1. 中缀表达式到后缀表达式的转换2. 后缀表达式的计算3. 中缀表达式的计算4. 退出-------------------------------------------------------1.2 中缀表达式到后缀表达式的转换（1）问题分析假设在算术表达式中只含四种基本运算符，操作数是10以内的整数。
假设一个中缀表达式中没有括号（如4+2*3，它的后缀表达式为423*+）。
在扫描到中缀表达式中的2后，能立即输出+，因为*具有较高优先级，必须必须先运算，因此需先保存+。
也就是说，新扫描运算符优先级必须与前一个运算符的优先级做比较，如果新的运算符优先级高，就要像前一个运算符那样保存它，直到扫描到第二个操作数，将它输出后才能将该运算符输出。
因此，在转化中必须保存两个运算符，后保存的运算符先输出。
用计算机来实现这个转化过程，就需要用到能后进先出的数据结构----栈。
如果在中缀表达式中含小括号，那么由于括号隔离了优先级规则，它在整个表达式的内部产生了完全独立的子表达式。
2014年计算机统考真题及解析
A．{3}和{1} B．{2,3}和{1} C．{2,3}和{1,2} D．{1,2,3}和{1} 35．下列因素中，不会影响信道数据传输速率的是 。 A．信噪比 B．频率宽带 C．调制速率 D．信号传播速度 36． 主机甲与主机乙之间使用后退 N 帧协议(GBN)传输数据， 甲的发送窗口尺寸为 1000， 数据帧长为 1000 字节，信道带宽为 100Mbps，乙每收到一个数据帧立即利用一个短帧(忽略 其传输延迟)进行确认，若甲乙之间的单向传播延迟是 50ms，则甲可以达到的最大平均数据 传输速率约为 。 A．10Mbps B．20Mbps C．80Mbps D．100Mbps 37．站点 A、B、C 通过 CDMA 共享链路，A、B、C 的码片序列(chipping sequence)分 别是(1,1,1,1)、(1,-1,1,-1)和(1,1,-1,-1)。若 C 从链路上收到的序列是(2,0,2,0,0,-2,0,-2,0,2,0,2)， 则 C 收到 A 发送的数据是 。 A．000 B．101 C．110 D．111 38．主机甲和主机乙已建立了 TCP 连接，甲始终以 MSS=1KB 大小的段发送数据，并 一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为 10KB 的确认段。若甲在 t 时刻发生超时时拥塞窗口为 8KB，则从 t 时刻起，不再发生超时的情况下，经过 10 个 RTT 后，甲的发送窗口是 。 A．10KB B．12KB C．14KB D．15KB 39．下列关于 UDP 协议的叙述中，正确 的是 。 ．． I．提供无连接服务 II．提供复用/分用服务 III．通过差错校验，保障可靠数据传输 A．仅 I B．仅 I、II C．仅 II、III D．I、II、III 40．使用浏览器访问某大学 Web 网站主页时，不可能 使用到的协议是 。 ．．．
《数据结构》历年考研真题及解答
《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。
若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。
设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。
若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。
2014年黑龙江省数据结构(C++)试题及答案
连续存放，则元素a[8][5]的起始地址是
A．SA+141 B．SA+144 C．SA+222 D．SA+255
10、在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何 B．结点个数的多少
C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。
A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系
45、在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理
46、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。
34、长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为
A．n—i B．n—i—l C．i D．i+1
35、向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。
A．O(n) B．O(1)
C．O(n2) D．O(10g2n)
C．分析算法的效率以求改进 C．分析算法的易读性和文档性
（2）A．空间复杂度和时间复杂度 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
3、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
A.n—l条有向边 B.n条有向边
C.n(n—1)／2条有向边 D.n(n一1)条有向边
33、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
A．SA+141 B．SA+144 C．SA+222 D．SA+255
10、在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何 B．结点个数的多少
C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。
A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系
45、在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理
46、当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。
34、长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为
A．n—i B．n—i—l C．i D．i+1
35、向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。
A．O(n) B．O(1)
C．O(n2) D．O(10g2n)
C．分析算法的效率以求改进 C．分析算法的易读性和文档性
（2）A．空间复杂度和时间复杂度 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
3、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
A.n—l条有向边 B.n条有向边
C.n(n—1)／2条有向边 D.n(n一1)条有向边
33、在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（ ）型调整以使其平衡
数据结构903
A STRUCTURE
用VC++编写有关模板程序的知识
在编译阶段，抽象的模板在没有实例化（用具体的 数据类型替代typename）前是不产生实际代码的。 每一种实例化都需要把有关模板的头文件和实现文 件用include方式包含进来。 模板中typename可以是已有的数据类型，也可以 是用类的方式定义的新的数据类型。但这个新的数 据类型必须定义有关的函数和运算。
渐近时间复杂度是
2*n= O(n)
p. 14 习题 1-20
DATA STRUCTURE
1-20 确定画线语句的执行次数，计算它们的渐近 时间复杂度。
（2）i = 1; x=0; do { x++; i = 2*i; } while (i < n);
渐近时间复杂度是
2*log2(n)= O(log2(n))
数 据 结 构
第3讲
DATA STRUCTURE
§二级考试公共基础数据结构部分
DATA STRUCTURE
1. 在计算机中，算法是指（ ）
2. 在下列选项中，（ ）不是一个算法一般应该具有的基 本特征。 3. 下列叙述中正确的是（ ）。
A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的时间复杂度大，则其空间复杂度必定小 C）一个算法的空间复杂度大，则其时间复杂度必定小 D）上述三种说法都不对
… … n ∑n(n+1)/2
∑ n(n+1)/2 =
n*(n+1)*(n+2)/6
渐近时间复杂度是
O(n3)
p. 14 习题 1-20
DATA STRUCTURE
1-20 确定画线语句的执行次数，计算它们的渐近 时间复杂度。
用VC++编写有关模板程序的知识
在编译阶段，抽象的模板在没有实例化（用具体的 数据类型替代typename）前是不产生实际代码的。 每一种实例化都需要把有关模板的头文件和实现文 件用include方式包含进来。 模板中typename可以是已有的数据类型，也可以 是用类的方式定义的新的数据类型。但这个新的数 据类型必须定义有关的函数和运算。
渐近时间复杂度是
2*n= O(n)
p. 14 习题 1-20
DATA STRUCTURE
1-20 确定画线语句的执行次数，计算它们的渐近 时间复杂度。
（2）i = 1; x=0; do { x++; i = 2*i; } while (i < n);
渐近时间复杂度是
2*log2(n)= O(log2(n))
数 据 结 构
第3讲
DATA STRUCTURE
§二级考试公共基础数据结构部分
DATA STRUCTURE
1. 在计算机中，算法是指（ ）
2. 在下列选项中，（ ）不是一个算法一般应该具有的基 本特征。 3. 下列叙述中正确的是（ ）。
A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的时间复杂度大，则其空间复杂度必定小 C）一个算法的空间复杂度大，则其时间复杂度必定小 D）上述三种说法都不对
… … n ∑n(n+1)/2
∑ n(n+1)/2 =
n*(n+1)*(n+2)/6
渐近时间复杂度是
O(n3)
p. 14 习题 1-20
DATA STRUCTURE
1-20 确定画线语句的执行次数，计算它们的渐近 时间复杂度。
2014年考研计算机专业基础综合真题试卷_真题-无答案
2014年考研计算机专业（基础综合）真题试卷(总分120,考试时间90分钟)1. 单项选择题单项选择题1-40小题。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
1. 下列程序段的时间复杂度是_______。
count=0；for(k=1；k＜=n，k*=2)for(j=1；j＜=n，j++)count++；A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)2. 假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是_______。
A. +(*-B. +(-*C. ／+(*-*D. ／+-*3. 循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。
初始时为空。
下列判断队空和队满的条件中，正确的是_______。
A. 队空：end1==end2；队满：end1==(end2+1)mod MB. 队空：end1==end2；队满：end2==(end1+1)mod (M-1)C. 队空：end2==(end1+1)mod M；队满：end1==(end2+1)mod MD. 队空：end1==(end2+1)mod M；队满：end2==(end1+1)mod (M-1)4. 若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是_______。
A. e、cB. e、aC. d、cD. b、a5. 将森林F转换为对应的二叉树T，F中叶结点的个数等于_______。
A. T中叶结点的个数B. T中度为1的结点个数C. T中左孩子指针为空的结点个数D. T中右孩子指针为空的结点个数6. 5个字符有如下4种编码方案，不是前缀编码的是_______。
A. 01，0000，0001，001，1B. 011，000，001，010，1C. 000，001，010，011，100D. 0，100，110，1110，11007. 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是_______。