【考研真题】青岛理工大学硕士研究生招生初试试题 813数据结构（2020）

1、B.在队尾插入元素D.删除队头元素:机密启用前青岛理工大学2020年硕士研究生招生考试（初试）科目代码：813科目名称：数据结构满分150分 TOC o 1-5 h z ;!:j注意事项：；认真阅读答题纸上的注意事项;!；所有答案必须注明题号且写在答题纸上,写在本试题纸或草稿纸上一律不给分;|!|本试题纸须随答题纸一起装入试题袋,按要求封装后交回。|一、单项选择题：每小题2分，共20分。下列每题给出的四个选项中，只有一个选j;lJf1项最符合试题要求。；r:;1.数据结构中，与所使用计算机无关的是数据的结构。-A.存储B.物理C.逻辑D.物理和存储掘1 2.在线性表的下列运算中，不改变数据元素

2、之间结构关系的运算是。,1 ki A.插入B.删除C.排序D.定位毬:3在一个单链表中,ql为q2的前驱结点,要删除p所指结点时，应执行以下操作o !A ql二q2一next;B ql-next二q2一next;C q2一next二ql;D q2一next二ql一next;将递归算法转换成非递归算法时，通常要借助的数据结构是.A.线性表B.栈C.队列D.树不允许对队列进行的操作有oA.对队列中的元素遍历B.C.在队列第一个元素之前插入元素D.下列结构具有较高的查找和删除性能。D. Hash 表A.有序数组B.有序链表 C.二叉树D.I 10.设有两个串p和q,求q在p中首次出现的位置的运算称作

3、A.连接 B.求子串 C.模式匹配D.求串长深度优先遍历类似于二叉树的。A.先序遍历 B.中序遍历C.后序遍历D.层次遍历：二、填空题：每小题2分，共20分。1.算法的效率可分为效率。i2.在一个长度为n的顺序表中删除第i个元素，要移动个元素。 TOC o 1-5 h z 表达式a* （b+c） -d的后缀表达式是o有一个二维数组AL20H10L每个数据元素占一个字节，且A00的存储地址是I1000,则Aij的地址是o：5.某棵二叉树有360个结点，该二叉树的最小高度是o6.设有一稠密图G,则G釆用存储较省空间。!7.在一个具有n个结点的单链表中查找结点值为m的某结点，査找成功的平均比较!个结

4、点。&现有一个包含m个结点的三叉树，在3m个结点指针中有个空指针。9.某二叉树的后序遍历顺序DBEFCA,中序遍历顺序为DBAECF,那么其先序遍历顺序C语言中，若数组定义如下：char A =”abdedf”,则数组A所占用的空间为字节。三、应用题：共50分。1.（15分）已知一个连通图如下图1所示，请完成以下问题：（1）试给出该图的邻接矩阵和邻接表；（2）若从顶点A出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。i 2. （20分）假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别 i 为 0. 07, 0.19, 0. 02, 0. 06, 0. 32

5、, 0. 03, 0.21, 0.10。试为这 8 个字母设计哈夫曼 ；编码（左子树结点的权重值小于右子树结点的权重值），并求出哈夫曼编码的平均码长。 j 3. （15分）已知待散列的线性表为（36, 15, 40, 63, 22）,散列用的一维地址空间 I为0.6,假定选用的散列函数是H （K）=Kmod 7,若发生冲突采用线性探査法处理，I试写出每一个元素的散列地址，并求出在査找每一个元素概率相等情况下的平均査找 TOC o 1-5 h z !长度 i四、编程题：共60分。；丨:i 1.（15分）设栈S中存放n个正整数，借助栈S1对栈S中元素进行从小到大排序， ；i要求栈底存放最大数。j:|2. （15分）已知两个字符串strl和str2,编程判断两个字符串是否相等，如相等j:输出Y,否则输岀N。（要求不能使用库函数）i:i 3. （15分）假设二叉树各结点含有一个整数值域，编写算