当前位置：文档之家 › 青岛大学数据结构2004

青岛大学数据结构2004

  • 格式：pdf
  • 大小：101.44 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

数据结构--第二章考试题库(含答案)

数据结构--第二章考试题库(含答案)

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

数据结构第三章考试题库(含答案)

数据结构第三章考试题库(含答案)

第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。

【青岛大学2001 五、2（2分）】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ①),在作退栈运算时应先判别栈是否( ②)。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③)。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④)分别设在这片内存空间的两端,这样,当( ⑤)时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.【上海海运学院1997 二、1（5分）】【上海海运学院1999 二、1（5分）】3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i【中山大学1999 一、9(1分)】4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉大学2000 二、3】5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。

A. iB. n-iC. n-i+1D. 不确定【南京理工大学2001 一、1（1.5分）】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 34 15 6【北方交通大学2001 一、3（2分）】7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

数据结构习题第六章树和二叉树

数据结构习题第六章树和二叉树

第六章 树和二叉树一、选择题1．已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，其前缀形式为( )A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D.-+A*BC/DE【北京航空航天大学 1999 一、3 （2分)】2．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ ）【中山大学 1999 一、5】A ．ab+cde/*B ．abcde/+*+C ．abcde/*++D 3. 设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ） 【南京理工大学1999 一、20（2分）】 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 4. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）A ．5B ．6C ．7D ．8【南京理工大学 2000 一、8 （1.5分）】5. 在下述结论中，正确的是（ ）【南京理工大学 1999 一、4 （1分）】①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A ．①②③B ．②③④C ．②④D ．①④6. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）A ．m-nB ．m-n-1C ．n+1D ．条件不足，无法确定 【南京理工大学2000一、17（1.5分）】7. 树是结点的有限集合，它（ (1）)根结点，记为T 。

其余结点分成为m （m>0）个(（2）)的集合T1，T2， …，Ｔm ，每个集合又都是树，此时结点T 称为Ti 的父结点，Ti 称为T的子结点（1≤i ≤m ）。

青岛大学10数据结构911计算机专业综合

青岛大学10数据结构911计算机专业综合
4
） 。
读出/写入一个数据，需要访问 2 次内存；同样，在分区存储管理系统中， 也需要访问 2 次内存。 D. 分页存储管理系统中用户程序装入之前的逻辑地址是一维的；分段 存储管理系统中用户程序装入之前的逻辑地址是二维的。 5．有关死锁的叙述正确的是（ ） 。 A．死锁的产生与资源分配策略无关，与进程并发执行的速度有关。 B．对资源采用按序分配策略就不会出现循环等待资源的情况了。 C．通过破坏“互斥使用资源”的条件就能防止死锁。 D．资源请求分配图中有环路则可断定有死锁。 6．在动态多分区分配方案中，某一作业完成后，系统收回其主存空间并 与相邻空闲区合并，为此需修改空闲区表 , 造成空闲区数减 1 的情况是 （ ） 。 A. 无上邻空闲区也无下邻空闲区 B. 有上邻空闲区但无下邻空闲区 C. 有下邻空闲区但无上邻空闲区 D. 有上邻空闲区也有下邻空闲区 7．一个分段存储管理系统中，地址字长度为 32 位，其中段号占 8 位， 则 允许的进程的最大长度是（ A. 232 字节 C. 216 字节 8．系统采用中断和通道技术，使得（ A. CPU 与外设紧密结合 C. CPU 速度提高 9. 磁盘调度算法中, （ A. 先来先服务和电梯调度 C. 电梯调度和单向扫描 10. 对物理结构为（ A. 连续存储结构 C. 显式链接存储结构 二．简答题（每小题 5 分，共 25 分）
2
1.对于图 ds-1 所示的有向图，试给出：
图 ds-1 (1) 邻接矩阵； (2) 邻接表； (3) 强连通分量； (4) 从顶点 v1 出发的深度优先遍历序列。 2.已知一个长度为 12 的线性表 List＝（7，2，5，8，12，3，10，4，1，6， 9，11） ，试回答下面的问题： (1) 将线性表中的元素依次插入到一个空的平衡二叉排序树中，画出所得 的平衡二叉排序树。假设查找每一个元素的概率相同，查找此平衡二叉排 序树中任一结点的平均查找长度为多少？ (2) 若对线性表中的元素排序之后，再用折半查找算法，画出描述折半查 找过程的判定树。假设查找每个元素的概率相同，计算查找成功时的平均 查找长度。 3.某整型数组 A 的 10 个元素值依次为： {6、2、9、7、3、8、4、5、0、 10}，用下列各排序方法，将 A 中元素由小到大排序。 (1) 取第一个元素 6 作为枢轴。试写出快速排序第一趟后 A 中的结果。 (2) 用堆排序（大根堆） ，试写出将第一个选出的数据放在 A 的最后位置 上，将 A 调整成堆后的 A 中结果。 4.已知元素数据类型为整数的顺序表 SL＝（a1，a2，…，am，bl，b2，…， bn） ， 试设计算法将 SL 中元素的两部分互换为 （bl， b2， …， bn ， a1， a2， …， am） 。要求：不能使用额外的数组空间。 （ 1）用文字给出你的算法思想； （2）用 C 语言写出算法的实现。

数据结构(山东联盟-青岛大学)知到章节答案智慧树2023年

数据结构(山东联盟-青岛大学)知到章节答案智慧树2023年

数据结构（山东联盟-青岛大学）知到章节测试答案智慧树2023年最新第一章测试1.在Data_Structure=(D，R)中，D是（）的有限集合。

参考答案:数据元素2.计算机所处理的数据一般具有某种关系，这是指（）。

参考答案:数据元素与数据元素之间存在的某种关系3.算法的时间复杂度与（）有关。

参考答案:问题规模4.以下关于数据结构的说法正确的是（）。

参考答案:数据结构的逻辑结构独立于其存储结构5.某算法的时间复杂度是O(n2)，表明该算法（）。

参考答案:执行时间与n^2成正比6.从逻辑上可将数据结构分为（）。

参考答案:线性结构和非线性结构7.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。

参考答案:对8.数据的物理结构是指数据结构在计算机内的实际存储形式。

参考答案:对9.每种数据结构都具备三种基本运算：插入、删除和查找。

参考答案:错10.算法的时间效率和空间效率往往相互冲突，有时很难两全其美。

参考答案:对第二章测试1.线性表是一个（）。

参考答案:数据元素的有限序列，元素不可以是线性表2.以下关于线性表的说法中正确的是（）。

参考答案:除第一个元素和最后一个元素外，其他每个元素有且仅有一个直接前趋元素和一个直接后继元素3.以下关于线性表的说法中正确的是（)。

参考答案:每个元素最多有一个直接前趋和一个直接后继4.如果线性表中的表元素既没有直接前趋，也没有直接后继，则该线性表中应有（）个表元素。

参考答案:15.在线性表中的每一个表元素都是数据对象，它们是不可再分的（）。

参考答案:数据元素6.顺序表是线性表的（）表示。

参考答案:顺序存储7.以下关于顺序表的说法中正确的是（）。

参考答案:顺序表和一维数组一样，都可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问8.顺序表的优点是（）。

参考答案:存储密度（存储利用率）高9.以下关于单链表的叙述中错误的是（）。

《数据结构》期末考试复习题 第10章 排序

《数据结构》期末考试复习题 第10章 排序
已知待排序的n个元素可分为nk个组每个组包含k个元素且任一组内的各元素均分别大亍前一组内的所有元素和小亍后一组内的所有元素若采用基亍比较的排序其时间下界应为oklog2k中国科技大学1998类似本题的另外叙述有
第 10 章
排序
一、选择题 1．某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2 分） 】 A． 该排序算法不允许有相同的关键字记录 B． 该排序算法允许有相同的关键字 记录 C．平均时间为 0（n log n）的排序方法 D．以上都不对 2． 下面给出的四种排序法中( )排序法是不稳定性排序法。 【北京航空航天大学 1999 一、 10 （2 分） 】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2 分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2 分） 】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和 shell 排序 5．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学 2001 一、8 （2 分） 】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序 6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒 泡排序） 。 【北京邮电大学 2001 一、5（2 分） 】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒， 则称该排序算法是不稳定的。 （ ）就是不稳定的排序方法。 【清华大学 1998 一、3 (2 分） 】 A．起泡排序 B．归并排序 C．Shell 排序 D．直接插入排序 E．简单选 择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数 【中科院计算所 2000 一、 5（2 分） 】 9．若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方 法是（ ） 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 【中国科技大学 1998 二、4（2 分） 】 【中科院计算所 1998 二、4（2 分） 】 10．下面的排序算法中，不稳定的是（ ） 【北京工业大学 1999 一、2 (2 分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆 排序。 11．下列内部排序算法中： 【北京工业大学 2000 一、1 (10 分 每问 2 分)】 A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ） （3）在初始序列已基本有序（除去 n 个元素中的某 k 个元素后即呈有序，k<<n）的情况下， 排序效率最高的算法是（ ） （4）排序的平均时间复杂度为 O(n•logn)的算法是（ ）为 O(n•n)的算法是（ ）

新版青岛科技大学软件工程考研经验考研参考书考研真题（附真题）

新版青岛科技大学软件工程考研经验考研参考书考研真题（附真题）一年前的今天自己在宿舍为了是否要考研而辗转反侧，直到现在当初试结果跟复试结果都出来之后，自己才意识到自己真的考上了。

其实在初试考完就想写一篇关于考研的经验，毕竟这也是对自己一年来努力做一个好的总结，也希望我的经验，可以帮助奋斗在考研路上的你们。

首先当你决定考研的时候，请先想想自己是为了什么才决定要考研，并且要先想一下为什么非要选这个专业，作为你今后职业的发展方向，学习的动机决定了之后备考路上努力的成功还有克服一切困难的决心。

考研是一个很重要的决定，所以大家一定要慎重，千万不要随波逐流盲目跟风。

我选择这所学校的原因，一是因为这里是我的本校，二是因为这里离家也比较近。

所一大家一定更要个根据自己的实际情况来做出选择。

好啦，接下来跟大家好好介绍一下我的复习经验吧，希望对你们有所帮助。

另外还要说一句，这篇经验贴分为三个部分，先说英语政治，再说专业课，并且文章结尾分享了资料和真题，大家可以放心阅读。

青岛科技大学软件工程初试科目：(101)思想政治理论(201)英语一(301)数学一(861)数据结构或(101)思想政治理论(201)英语一(301)数学一(862)计算机网络或(101)思想政治理论(201)英语一(302)数学二(861)数据结构或(101)思想政治理论(201)英语一(302)数学二(862)计算机网络(861)数据结构参考书《数据结构》（C语言版）谢希仁电子工业出版社2008(862)计算机网络参考书《计算机网络》茆诗松等编高等教育出版社2004跟大家先说一下英语的复习吧。

学英语免不了背单词这个难关，词汇量上不去，影响的不仅是考试成绩，更是整体英语能力的提升；背单词也是学习者最感到头痛的过程，不是背完了转身就忘，就是背的单词不会用，重点单词主要是在做阅读的时候总结的，我把不认识不熟悉的单词全都挑出来写到旁边，记下来反复背直至考前，总之单词这一块贵在坚持，背单词的日程一定要坚持到考研前一天。

青岛大学921数据结构与算法基础 考试大纲2021年考研专业课初试大纲

软件工程专业硕士入学考试大纲考试科目代码及名称：921数据结构与算法基础一、考试要求1.掌握数据结构的基本概念、基本原理和基本方法；2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；3.能应用数据结构基本原理和方法进行问题的分析与求解，具备采用计算机程序设计语言实现算法的能力。

二、考试内容一、基本概念（一）数据结构的基本概念（二）算法的基本概念（三）算法分析的基本方法二、线性结构 （一）线性表、栈和队列的基本概念 （二）线性表、栈和队列的顺序存储结构 （三）线性表、栈和队列的链式存储结构 （四）线性表、栈和队列的应用三、树与二叉树 （一）树的定义、表示和基本术语 （二）二叉树 1.二叉树的定义及其主要性质 2.二叉树的存储结构 3.二叉树的遍历　（三）树与二叉树的应用 1.二叉搜索树 2.堆结构 3.哈夫曼（Huffman）树和哈夫曼编码4.集合及其运算四、图 （一）图的基本概念 （二）图的存储结构 1.邻接矩阵 2.邻接表 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用 1.最小（代价）生成树 2.最短路径 3.拓扑排序4.关键路径计算五、动态查找 （一）平衡二叉树(AVL树) （二）散列（Hash）表 （三）查找算法的分析及应用六、排序 （一）插入排序 （二）交换排序 （三）选择排序 （四）归并排序 （五）基数排序 （六）各种内部排序算法的比较和应用三、试卷结构（题型分值）1.本科目满分为150分，考试时间为180分钟。

2.题型结构（1）选择题： 30分（2）填空题: 20分（3）应用题： 55分（4）算法分析与设计题：45分四、参考书目《数据结构（第2版）》：陈越主编，高等教育出版社，2016年《计算机算法设计与分析（第5版）》王晓东编著,电子工业出版社,2018年。

青岛大学-数据结构-2014年-考研真题

青岛大学 2014 年硕士研究生入学考试试题
科目代码： 910 科目名称： 数据结构 （共 5 页）
请考生写明题号，将答案全部答在答题纸上，答在试卷上无效 一、单项选择题（本大题共 10 道小题，每小题 2 分，共 20 分） 1．数据结构被形式定义为 DS=(D，S)，S 是 D 上的（ ）有限的集合。 A．存储 B．映像 C．数据操作 D．关系 2．下列函数中渐近时间复杂度 T(n)最小的是（
） 。
4．递归过程或者函数调用时，处理参数及返回地址要用一种称为（ 的数据结构。 A．线性表 B．栈 C．队列 D．二维数组 5． 设有两个串 S1 和 S2， 求 S2 在 S1 中首次出现的位置的运算称作 （ A．连接 B．求子串 C．求串长 D．模式匹配
）
） 。
6．将一个 int A[5][5]的下三角矩阵，按以行为主序存入一维数组 int B[16] 中，A 中元素 A[2][3]在 B 数组中的位置 k 为（ ） 。 A．6 B．11 C．15 D．16 7． 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组 R[1..n]中， 结点 R[i]若有右子树，则右子树是结点（ ） 。 A．R[i/2] B．R[2i] C．R[2i+1] D．R[2i-1] 8． 用邻接表存储图进行广度优先遍历时， 通常采用 （ ） 来实现算法的。 A．二叉树 B．二维数组 C．栈 D．队列 9． 已知一个有序表为 ｛1,4,6,11,13,19,22,27,36,39,44｝ ，当采用二分 （折半）
A．T(n) = 10000n log2 n 5000n C．T(n) = 200nlog2 n 6000n
） 。
B．T(n) = 5000n2 8000n D．T(n) = 200*2n 3000n

(完整版)青岛大学05数据结构

青岛大学 2005 年硕士研究生入学考试一试题学科代码：407科目名称：数据结构（共4页）请考生写明题号，将答案所有答在答题纸上，答在试卷上无效一．单项选择题（本大题共10 道小路小题，每题 3 分，共 30 分）1. 算法的时间复杂度取决于【】A. 问题的规模B. 待办理数据的初始状态C. 软件和硬件的组合D. 操作系统2. 向一个栈顶指针为top 的链栈中插入一个s 结点，则履行【】A. top->next=s;B. s->next=top->next; top->next=s;C. s->next=top; top=s;D. s->next=top; top=top->next;3. 广义表（（ a））的表头是【】A. aB. (a)C. ()D. ((a))4. 由带权为8、 2、 5、 7 的叶子结点结构一棵哈夫曼树，该树的带权路径长度为【】A. 37B. 32C. 46D. 435. 采纳毗邻表储存的图，其BFS 算法近似于二叉树的【】A. 中序遍历B. 先序遍历C. 后序遍历D. 按层遍历6. 在非空 m 阶 B_ 树上，除根结点以外的所有其余非终端结点【】A. 起码有m / 2 棵子树B. 至多有m / 2 棵子树C. 起码有m / 2 棵子树D. 至多有 m / 2 棵子树7. 对线性表进行次序查找时，要求线性表的储存结构为【】A. 散列储存B. 次序储存或许链式储存C. 压缩储存D. 索引储存8. 在重点字“基本有序”的状况下，最正确排序算法为【】A. 迅速排序B. 冒泡排序C. 直接插入排序D. 基数排序9. 折半查找法和二叉排序树的时间性能【】A. 与办理数据量相关B. 同样C. 不同样D. 不确立10. 串是一种特别的线性表，其特别性表此刻【】A. 能够次序储存B. 数据元素是一个字符C. 能够链接储存D. 数据元素能够是多个字符二、填空题（本大题共10 小题，每题 2 分，共 20 分）1. 在拥有 n 个单元的循环行列中，队满时共有____________个元素。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

·- 4 -算法是将所有奇数放到所有偶数之前。请在空白处填入正确的语句，使之完善。并 且给出该算法的时间复杂度。 Void OddEven(int a[], int n) { int i = 0, j = n-1, temp; while(____①____) { while((a[i]%2 != 0)&&(i<j)) i++; while(____②___) _____③______; if(i < j){ temp = a[i]; a[i] = a[j]; a[j] = temp; ____④___; ____⑤___; } } } 五、算法设计题（本大题共 3 道小题，每小题 7 分，共 21 分） 1. 已知在两个单链表 ListA 和 ListB 中均不存在相同的元素值，试设计算法：求出由仅在 A 中出现而不在 B 中出现的元素值所组成的单链表。 【说明】假设结点值为整型数。 Void isLisA(struct ListNode *LA, struct ListNode *LB) { 2. 假设二叉树采用二叉链表作为存储结构，试编写一个算法：求任意一个指定结点所在的层 次。 【说明】 ：假设二叉树中无结点值相同的，且要求采用非递归算法。 Int AnyTreeNodeLevel(struct BtreeNode *root, elemtype x) { /* x 为结点中的值*/ 3. 证明：二叉排序树的中序遍历序列是一个升序序列。
青岛大学 2004 年硕士研究生入学考试试题
科目代码：407 科目名称：数据结构（共 4 页） 请考生写明题号，将答案全部答在答题纸上，答在试卷上无效。 考试时间 180 分钟。 一、单项选择题（本大题共 15 小题，每小题 3 分，共 45 分） 在每小题列出的四个选项中，只有一个是符合题目要求的。错选或未选均无分。 1. 一个算法的时间复杂度为（3n2+2nlog2n+4n-7）/（10n） ，其数量级为 【 】 2 A. O (3n ) B. O (2nlog2n) C. O (3n/10) D. O（n） 2. 铁道进行火车调度时，总是把站台设成栈式站台，如果火车进站序列为 123456，下面哪种 出站序列不能得到： 【 】 A. 325641 B. 165432 C. 435612 D. 135426 3. 设有广义表 D(a, b, D)，其长度为： 【 】 A. 2 B. 3 C. ∞ D. 不确定 4. 某二叉树的中序遍历序列为 CBEDAHGIJF，后序遍历序列为 CEDBHJIGFA，则前序序列 为 【 】 A. ABCDEFGHIJ B. ABCDGHIJEF C. ACDEBHJIGF D. ACBDEFGHIJ 5. 就平均时间而言，什么排序方法最好。 【 】 A. 希尔排序 B. 快速排序 C. 堆排序 D. 归并排序 6. 线性表若采用链式存储，所有的存储单元的地址 【 】 A. 可连续可不连续 B. 一定连续 C. 一定不连续 D. 以上都不对 7. 对长度为 10 的有序表进行二分查找（折半查找） ，在等概率的情况下，查找成功的平均查 找长度（ASL）为 【 】 A. 3.2 B. 1.7 C. 2.9 D. 不确定 8. 图的 BFS 生成树的树高比 DFS 生成树的树高 【 】 A. 小或相等 B. 小 C. 大或相等 D. 大 9. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求， 则可采用什么查找方 法 【 】 A. 有序表 B. 线性链表 C. AVL D. 分块有序表 10. 实现任意二叉树的后序遍历的非递归算法而不使用栈，最佳方案是二叉树采用什么存储 结构 【 】 A. 二叉链表 B. 三叉链表 C. 广义表 D. 顺序存储结构 11. 对包含 n 个元素的哈希表进行查找时，平均查找长度 【 】 B. 为O(n) C. 不直接依赖于n D. 以上都不对 A. 为O（log2n） 12. 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以使用 【 】 A. 求关键路径的方法 B. 求最短路径的 Dijkstra 方法 C. DFS 算法 D. BFS 算法 13. 广义表 Glist(a)，则表尾为： 【 】 A. 空表 B. a C. ( ) D. (( )) 14. 对于含有 n 个顶点 e 条边的无向连通图，利用 Kruskal 算法产生最小生成树时，其时间复 杂度为 【 】 2 A. O (n ) B. O (n*e) C. O (nlog2n) D. O(elog2e)
四、算法阅读题（本大题共 3 道小题，每小题 8 分，共 24 题）
·- 2 -·
【说明】结构定义 struct ListNode{ elemtype data; struct ListNode *next; }; struct BtreeNode{ elemtype data; struct BtreeNode *lchild, *rchild; }; 1. 阅读下面的算法，试说明算法的功能。 int unknown(struct BTreeNode *root, int K, int tag) { //假设 K 的初始值为－∞ if(root = =NULL) tag = 1; else { tag = unkown(root－>lchild,K,tag); if(tag = = 0 ||root－>data <K) tag = 0; else { K = root－>data; tag = unknown(root－>rchild,K,tag); } } return tag; } 2. 下面算法的功能是删除所有相邻结点数据域值相同的结点，只保留最后一个结点。请在空 白处填入正确的语句，使之完善。其中，Head 为带头结点的单链表指针。 Void DelMulNode(struct ListNode *head) { struct ListNode *q, *s, _______①________; while(___________②________){ s = p; ______________③_______; while(q != NULL) if(q－>data = =p－>data){ s－>next = q－>next; _______④_________; }else{ _________⑤________; q = q－>next; } ______________⑥___________; } }
·- 1 -·
15. 设哈希表长 m = 18，哈希函数 H (K) ＝ K ％ 17。关键字序列为： ｛53、17、12、61、 98、70、87、25、63、46、14、59、67、75｝ ，如果使用二次探测再散列处理冲突，则查找成 功的平均查找长度约为 【 】 A. 2.18 B. 1.71 C. 2.96 D. 1.06 二、填空题（本大题共 10 小题，每小题 2 分，共 20 分） 1. 每种数据结构都应具备三种基本运算：_______________________________。 2. 在 n 个结点的顺序表中插入一个结点，具体移动结点的次数取决于______________。 3. 设长度为 n 的链队列用单循环链表表示，若只设头指针，则出队列操作的时间复杂度为 ___________。 4. 在链栈中执行入栈操作时，不必考虑______________。 5. 含有 n 个结点的二叉树，使用二叉链表表示时，空链域的个数为___________。 6. DFS 遍历类似于二叉树的_________遍历。 7. 有回路的有向图________________拓扑排序。 8. 使用二分查找法（折半查找）搜索一个线性表时，该线性表必须是__________表。 9. 设一组记录的关键字为｛3、7、6、9、8、1、4、5、2｝ ，进行排序的最小交换次数为 _________________次。 10. 若一些单词仅由 ABCDE 组成，在这些单词中，5 个字符出现的频率依次为 23, 2, 16, 18 和 16，则这 5 个字符的哈夫曼编码为：_____________________________。 三、解答题（本大题共 4 小题，每小题 10 分，共 40 分） 1. 如果使用一维数组 Array[MAX]来存储循环队列的元素时，如何设置一个标志 flag 来区分 头指针(front)和尾指针(rear)相等时，队列的状态是“空”还是“满”？ 2. 简述递归思想。现有两个正整数 M 和 N，如果采用递归方法解决 M×N 运算，试结合递 归思想，说明其终止条件和递归语句是什么？ 3. 试给出一个关键字个数最少的序列， 使得构造平衡二叉树时， 四种调整平衡操作 （LL、 LR、 RR、RL）各只执行一次，并且画出其构造过程。 4. 对于如下所示的有向图，试给出： (1) 邻接矩阵; (2) 邻接表; (3) 逆邻接表; (4) 强连通分量; (5) 从顶点 V1 出发，给出 DFS 序列。 (6) 从顶点 V3 出发，给出 BFS 序列。