2018年北京服装学院服装设计与工程917程序设计与算法之数据结构考研核心题库
● 摘要
目录
2018年北京服装学院服装设计与工程917程序设计与算法之数据结构考研核心题库（一） ... 2 2018年北京服装学院服装设计与工程917程序设计与算法之数据结构考研核心题库（二） . 15 2018年北京服装学院服装设计与工程917程序设计与算法之数据结构考研核心题库（三） . 29 2018年北京服装学院服装设计与工程917程序设计与算法之数据结构考研核心题库（四） . 44 2018年北京服装学院服装设计与工程917程序设计与算法之数据结构考研核心题库（五） . 56
一、填空题
1． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。 2． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)
3． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
4． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
5．
给定一组数据WPL 的值为_____。
【答案】5；96
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
【解析】每次找两个最小的权值构建哈夫曼树:
6． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
7． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
8． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。
【答案】480+8=488，480－32=448
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:
根据上述公式起始地址就为488。
9． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
10．有向图G=(V, E) ，其中权d 。E(G)为
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
11．设有N 个结点的完全二叉树顺序存放在向量
【答案】
中，其下标值最大的分支结点为_____。，用
三元组表示弧
及弧上的
【解析】最大的分支结点是最后一个叶子结点的父结点。
12．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
二、单项选择题
13．在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
A.O(2n) B.O(n) C.O(n2) D.O(log2n ) 【答案】C
【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。
14．下列有关RAM 和ROM 的叙述中, 正确的是（ ）。
2
Ⅰ.RAM 是易失性存储器, ROM 是非易失性存储器 Ⅱ.RAM 和ROM 都采用随机存取方式进行信息访问 Ⅲ.RAM 和ROM 都可用作Cache Ⅳ.RAM 和ROM 都需要进行刷新 A. 仅Ⅰ和Ⅱ B. 仅Ⅱ和Ⅲ C. 仅Ⅰ、Ⅱ和Ⅳ D. 仅Ⅱ、Ⅲ和Ⅳ 【答案】A
【解析】RAM 中的内容断电后即丢失(易失性) , ROM 中的内容断电后不会丢失(非易失性) , 同时RAM 和ROM 都采用随机存取方式(即CPU 对任何一个存储单元的存取时间相同) , 区别在于RAM 可读可写, ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新, 所以Ⅲ和Ⅳ的叙述都是错误的。
15．算法的计算量的大小称为计算的（ ）。
A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复
相关内容
相关标签