2017年江西农业大学计算机与信息工程学院819数据结构考研导师圈点必考题汇编
● 摘要
目录
2017年江西农业大学计算机与信息工程学院819数据结构考研导师圈点必考题汇编（一）.... 2
2017年江西农业大学计算机与信息工程学院819数据结构考研导师圈点必考题汇编（二）.. 14
2017年江西农业大学计算机与信息工程学院819数据结构考研导师圈点必考题汇编（三）.. 27
2017年江西农业大学计算机与信息工程学院819数据结构考研导师圈点必考题汇编（四）.. 42
2017年江西农业大学计算机与信息工程学院819数据结构考研导师圈点必考题汇编（五）.. 58
一、填空题
1． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
2． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。
【答案】单链表；双链表；（动态）链表；静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。
3． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
4． 设有两个算法在同一机器上运行，其执行时闻分别为要使前者快于后者，n 至少为_____。
【答案】15
【解析】当时，而
，时，
5． 当两个栈共享一存储区时，栈利用一维数组
当栈1空时
，
【答案】为_____，栈2空时
， 表示，两栈顶指针为则为_____，栈满时为_____。 【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
7． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
8． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
9． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
10．—棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
树。故结点个数为
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉二、选择题
11．将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.N
B.2N-1
C.2N
D.N-1
【答案】A
【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为
12．由3个结点可以构造出多少种不同的有向树？（ ）
A.2
B.3
C.4
D.5
【答案】A
【解析】满足以下条件的有向图称为有向树：①有且仅有一个结点的入度为0; ②除树根外结点的入度为1; ③从树根到任一结点有一有向通路。
13．对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
14．对于栈操作数据的原则是（ ）。
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
15．用户在删除某文件的过程中，操作系统不可能执行是（ ）
A. 删除此文件所在的目录
B. 删除与此文件关联的目录项
C. 删除与此文件对应的控制块
D. 释放与此文件关联的内存级冲区
【答案】A
【解析】删除文件不需要删除文件所在的目录，而文件的关联目录项和文件控制块需要随着文件一同删除，同时释放文件的关联缓冲区。
16．下列选项中，操作系统提供的给应用程序的接口是（ ）。
A. 系统调用
B. 中断
C. 库函数
D. 原语
【答案】A
【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种，以及包含在）自然命令用户接口等，而系统调用中除了常规的一些传统的系统调用（例如read （ ））以外，还有经过扩展的
库中的各种封装好的过程调用（最终都是通过系统调用陷入到操作系统中去的）等。
17．一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107
B.108
C.214
D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有
以
所
也就是说若对其进行哈夫曼编码，共能得到108个码字。
相关内容
相关标签