2018年天津大学计算机科学与技术学院901数据结构与程序设计之数据结构考研核心题库
● 摘要
一、填空题
1． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
2． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
的地址为l ＋2＋... ＋i ﹣l ＋j
＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
3． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
4． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
5． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
6．
给定一组数据WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
第 2 页，共 58 页
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
7． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
10．二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
11．当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
12．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
【答案】
left 指向其前驱；，
right 指向其后继。
，
right 指向其右孩子，，
，
第 3 页，共 58 页
13．数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
14．外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
15．在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
二、单项选择题
16．栈和队的共同点是（ ）。
A. 都是先进后出 B. 都是后进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点 【答案】C
【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。
17．图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 【答案】A 【解析】顶点
到顶点
之间的一条路径是指顶点序列
。路径上边的
数目称为路径的长度。
18．下列介质访问控制方法中, 可能发生冲突的是（ ）
A.CDMA B.CSMA C.TDMAC D.FDMA 【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议, 答案为B 。
第 4 页，共 58 页