昆明理工大学2011年硕士研究生招生入学考试试题a卷

《昆明理工大学2011年硕士研究生招生入学考试试题a卷》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、昆明理工大学2011年硕士研究生招生入学考试试题(A卷)考试科目代码：835考试科目名称：数据结构教程试题适用招生专业：071101系统理论、071102系统分析与集成考生答题须知1．所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。请考生务必在答题纸上写清题号。2．评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。3．答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。4．答题时不准使用涂改液等具有明显标记的涂改用品。一、单项选择题：（每题3分，共30分）1．在数据结构中，

2、从逻辑上可以把数据结构分为______两类。　Ａ：动态结构和静态结构　　　Ｂ：紧凑结构和非紧凑结构　Ｃ：线性结构和非线性结构　　Ｄ：内部结构和外部结构2．数据采用链式存储结构时，要求_________。Ａ：每个结点占用一片连续的存储区域Ｂ：所有结点占用一片连续的存储区域Ｃ：结点的最后一个数据域是指针类型Ｄ：每个结点有多少个后继，就没多少个指针域3．某算法的时间复杂度为O（），表明该算法的_________。A：问题规模是B：执行时间等于C：执行时间与成正比D：问题规模与成正比4.在一个长度为n的顺序表中向第i个元素（0

3、____个元素。A：n-1B：n-i+1C：n-i-1D：i5.在单链表中，若*P结点不是末尾结点，在其后插入*S结点的操作是____。A：s—>next=p;p—>next=s;B：s—>next=p—>next;p—>next=s;C：s—>next=p—>next;p=s;D：p—>next=s;s—>next=p;6．设一个栈的输入序列为A，B，C，D，则借助栈所得到的输出序列不可能是。A：A,B,C,DB：D,C,B,AC：A,C,D,BD：D,A,B,C7．一个n×n的对称矩阵，如果以行或列为主序放入内存，则存储容量为______。A：n2B：n2/2C：n(n+

4、1)/2D：(n+1)2/28.一棵有124个叶结点的完全二叉树，最多有______个结点。第4页共4页A：247B：248C：249D：2509.采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。A：先序遍历B：中序遍历C：后序遍历D：层次遍历10.设哈希表长m=14，哈希函数H（key）=keymod11。表中已有4个结点addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如用二次探测再散列法处理冲突，则关键字为49的结点地址是______。A：8B：3C：5D：9二、判断题（每题2分，共20分）1．任何

5、数据结构都具备三个基本运算：插入、删除和查找。（）2.在循环单链表中，任何一个结点的指针字段值都不可能为空。（）3.顺序队列中有多少元素，可以根据队首指针和队尾指针的值来计算。（）4.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（）5.递归算法的执行效率比功能相同的非递归算法的执行效率高。（）6.当二叉树中的结点数多于1个时，不可能根据结点的先序序列和后序序列唯一地确定该二叉树的逻辑结构。（）7.若一个树叶是某二叉树先序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。（）8.哈夫曼树是带权路径长度最短

6、的树，路径上权值较大的结点离根较近。（）9.一个广义表的表尾总是一个广义表。（）10.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。（）三、简答题（共60分）1．线性表有两种存储结构：一是顺序表，二是链表，试问：（共12分）（1）如果有n个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。在此情况下应选用哪种存储结构？为什么？（6分）（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（6分）2.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出

7、来。试求出空格处的内容，并画出该二叉树。（每个序列3分，画出二叉树6分，共15分）先序序列：_B_F_ICEH_G中序序列：D_KFIA_EJC_后序序列：_K_FBHJ_G_A3.有如下图二所示的带权有向图G，试回答以下问题：（共18分）（1）给出从顶点1出发的深度优先遍历序列和广度优先遍历序列。（6分）（2）给出G的一个拓扑序列。（4分）第4页共4页（3）给出从顶点1到顶点8的最短路径和关键路径。（8分）图二4.设用于通讯的电文仅由8个字母构成，字母在电文中出现的频率分别为：7、19、2、6、32、