青 岛 科 技 大 学
二○一七年硕士研究生入学考试试题
考试科目：数据结构
注意事项：1．本试卷共 三 道大题（共计22 个小题），满分 150  分；
2．本卷属试题卷，答题另有答题卷，答案一律写在答题卷上，写在该试题卷上或草纸上均无效。要注意试卷清洁，不要在试卷上涂划；
3．必须用蓝、黑钢笔或签字笔答题，其它均无效。           
﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡﹡
一．选择题(每题2分，共30分)
1．数据结构通常是研究数据结构的（  ）以及它们的操作。
A）理想与逻辑  B）存储和抽象  C）理想和抽象  D）逻辑结构和存储结构
2．指出下面程序段的时间复杂度（  ）。
i=1;
While(i<n)i=i*2;
A）O(1)      B)O(log2n)    C)O(n)    D)O(nlog2n)
3．下列叙述中正确的是（）。
A）线性表的线性存储结构优于链式存储结构 
B）栈的操作特点是先进先出
C）二维数组是每个数据元素本身为一个线性表的线性表
D）队列的操作特点是后进先出
4．链栈和顺序栈相比一个比较明显的优势是（）。
    A）插入操作更加方便                B）删除操作更加方便
C）不会出现栈空的情况              D）通常不会出现栈满的情况
5．元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可以停留，可出栈，直到所有的元素都出栈，则在所有可能的出栈序列中，以元素d开头的出栈序列有（）。
    A）3      B）4          C）5        D）6
6．在一个单链表中，若P所指结点是最后结点，在P之后插入S所指结点，则执行（）。
    A）S->next=P; P->next=S;              B）S->next=P->next; P=S;
C）S->next=P->next; P->next=S;        D）P->next=S;  S->next=P;
7．具有n个叶子结点的哈夫曼树，所有结点个数为（）。
    A）2n          B） 2n+1              C） 2n-2          D） 2n-1
8．一棵深度为K的完全二叉树至少有(  )结点。
A）2k+1        B） 2k-1                        C） 2k-1 -1                      D） 2k+1
9． 平面上有五个点A(5,3),B(3,5),C(2,1),D(3,3),E(5,1)。以这五点作为完全图G的
点，每两点之间的距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的（）。
A）EA          B） AD            C）DE            D）BD
10． 二叉树T的层次遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点为（）。
A） B            B）  E          C）  D            D）  C
11．设栈的初始状态为空，元素a,b,c,d,e,f,g依次进栈，以下出栈序列不可能出现的是（）。
  A）a,b,c,e,d,f,g  B）g,e,f,d,c,b,a  C）b,c,a,f,e,g,d  D）d,c,f,e,b,a,g
12．一个n阶对称矩阵，如果以行或列为主序存入内存，则容量为（）。
A) n*n        B) n*n/2            C) n*(n+1)/2      D) (n+1)*(n+1)/2
13．n个顶点的强连通图至少有( )条边，其形状是（）。
    A)n*（n-1)，树状       B)n+1，有回路      C) n-1，无回路    D)n，环状
14．若用冒泡法对序列(10,14,26,29,41,52)从大到小排序，则需要进行（）次比较。
    A) 3            B) 15          数据结构与算法考研真题C) 10        D)25
15．具有12个关键字的有序表，若查每个元素的概率相同，进行二分查的平均查长度为( )。
    A)4              B)2.5              C)3.1              D)5
二．应用题（60分）
1．（15分）什么是最优树？假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
  试为这8个字母设计赫夫曼编码。
  试设计另一种由二进制表示的等长编码方案。
  对于上述实例，比较两种方案的优缺点。
2.（15分）什么是关键路径？什么是关键活动？试对下图所示的AOE-网：
求这个工程最早可能在什么时间结束；   
求每个活动的最早开始时间和最迟开始时间；
确定哪些活动是关键活动
3．（15分）假设线性表的关键字集合为key={32,75,31,63,48,94,25,47,18,70},散列地址空间为HT[11]，若采用除留余数法构造散列函数和链地址法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，并求出等概率下查成功的平均查长度。
4. (15分)阅读以下算法：
①该算法是什么样排序算法；该算法待排序记录的存储结构是什么？
②简述该排序算法的思想；
    ③设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试写出使用该排序方法，每趟排序结束后关键字序列的状态；
  void  Sort ( SqList &L )
    { for ( i = 2;  i <= L.length ; ++i )

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。