2022年军事医学科学院放射与辐射医学研究所836计算机应用之数据

目录

2017年军事医学科学院放射与辐射医学研究所836计算机应用之数据结构考研导师圈点必考题汇编（一） (2)

2017年军事医学科学院放射与辐射医学研究所836计算机应用之数据结构考研导师圈点必考题汇编（二） (9)

2017年军事医学科学院放射与辐射医学研究所836计算机应用之数据结构考研导师圈点必考题汇编（三） (15)

2017年军事医学科学院放射与辐射医学研究所836计算机应用之数据结构考研导师圈点必考题汇编（四） (21)

2017年军事医学科学院放射与辐射医学研究所836计算机应用之数据结构考研导师圈点必考题汇编（五） (28)

第1 页，共33 页

第 2 页，共 33 页 2017年军事医学科学院放射与辐射医学研究所836计算机应用之数据结构考研导师

圈点必考题汇编（一）

说明：①本资料为VIP 学员内部使用，整理汇编了历届导师圈点的重点试题及常考试题。

——————————————————————————————————————————

一、填空题

1． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结

点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：

_____；_____; 【答案】

2． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注：（1）图的顶点号从0开始计；

（2）indegree 是有n 个分量的一维数组，放顶点的入度，

（3）函数crein 用于记算顶点入度；

（4）有三个函数push （data ）, pop （ ）, check （ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1,否则0）。

）

.

（“图有回路”）；

【答案】0; j ; i ; 0; indegree[i]=0; [vex][i]; k==l ; indegree[i]=0

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度

减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

3．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3;（10，7，-9，0，47，23，1，8，98，36）

4．顺序栈用存储数据，栈顶指针是top，则值为x的元素入栈的操作是_____。

【答案】

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

5．线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

【答案】（n－1）/2

【解析】删除第一个元素需要移动n－i次，以此类推，删除最后一个元素需要移动0次。平均次数为

6．设有个结点的完全二叉树顺序存放在向量中，其下标值最大的分支结点为_____。

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

7．对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间.复杂度为_____，在给定值为x的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x的结点。

8．在哈希函数中，P值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P的选择很重要。若P选的不好，容易产生同义词。一般情况下，可以选P为质数或不包含小于20的质因素的合数。

9．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n），而快速排序算法需要比较的次数达到最大，时间复杂度为

第3 页，共33 页

第 4 页，共 33 页

10．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶树每个结点至多有_____个儿子，除

根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；

11．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

12．阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。 13．设数组

数组中任一元素

均占内存48个二进制位，从首地址2000开始

连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是_____；

（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素的起始地址是_____。

【答案】270;27;2204 【解析】数组的元素个数为因为每个元素占内存48个二进制位，即6个字节。故总

需要

个字节，因为主内存字长为16位，即2个字节，所以至少需要

个单元数。

第8列有9个元素，共占

个字节，因此至少需要

个单元数。由题知，每个元素占3

本文来源：https://www.bwwdw.com/article/ztbl.html