2017年天津财经大学计算机应用技术818计算机专业综合之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
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． 设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则则的地址为若
的地址为将代入得33。
4． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
5． 二进制地址为011011110000，大小为【答案】011011110100；011011100000
011011110000是块的起始地址，【解析】大小分别为第 2 页，共 73 页 ，）则 的地址为_____。和块的伙伴地址分别为：_____ 和其伙伴块的起始地址计算公
式如下：
当大小为4时，起始地址
为当大小为16时，起始地址为
：
6． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
7． 实现字符串拷贝的函数strcpy 为：
【答案】
8． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
9． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
10．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
二、选择题
11．要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1
B.n
C.n+1
D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需
第 3 页，共 73 页
要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
12．下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快
B. 存储元由MOS 管组成，是一种半导体存储器
C. 掉电后信息不丢失，是一种非易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器
【答案】A 。
【解析】考查闪存的特性，闪存是EEPROM 的进一步发展，可读可写，用MOS 管的浮栅上有无电荷来存储信息，它依然是ROM 的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD 固态硬盘就是由flash 芯片组成的，故答案为A 。
13．假定基准程序A 在某计算机上的运行时间为100秒，其中90秒为CPU 时间，其余为间。若CPU
速度提高
A.55秒
B.60秒
C.65秒
D.70秒
【答案】D 。
CPU 速度提高【解析】
秒。即CRJ 性能提高比为1.5, 改进之后的CPU 运行时间速度不变，仍维持10秒，所以运行基准程序A 所耗费的时间为70秒。 速度不变，则运行基准程序A 所耗费的时间是（ ）。 时
14．设有一棵3阶B 树，如题图所示。删除关键字78得到一棵新B 树，其最右叶结点所含的关键字是（ ）。
题图二叉树图
A.60
B.60, 62
C.62, 65
D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于
第 4 页，共 73 页 则需将其兄弟结点中最
相关内容
相关标签