2011年云南昆明理工大学数据结构教程考研真题A卷.doc

发布时间：2022-09-17 发布人：admin 分类：说明书资料大小：0.08M 资料格式：doc 举报版权申诉

第1页 / 共3页

2011年云南昆明理工大学数据结构教程考研真题A卷.doc.pdf-第2页.jpg

第2页 / 共3页

2011年云南昆明理工大学数据结构教程考研真题A卷.doc.pdf-第3页.jpg

第3页 / 共3页

文本预览

2011 年云南昆明理工大学数据结构教程考研真题 A 卷一、单项选择题：（每题 3 分，共 30 分） 1．在数据结构中，从逻辑上可以把数据结构分为______两类。Ａ：动态结构和静态结构Ｃ：线性结构和非线性结构Ｂ：紧凑结构和非紧凑结构Ｄ：内部结构和外部结构 2．数据采用链式存储结构时，要求_________。Ａ：每个结点占用一片连续的存储区域Ｃ：结点的最后一个数据域是指针类型Ｂ：所有结点占用一片连续的存储区域Ｄ：每个结点有多少个后继，就没多少个指针域 3．某算法的时间复杂度为 O（ 2n ），表明该算法的_________。 A：问题规模是 2n B：执行时间等于 2n C：执行时间与 2n 成正比 D：问题规模与 2n 成正比 4. 在一个长度为 n 的顺序表中向第 i 个元素（0next=p; C：s—>next=p—>next; p—>next=s; p=s; B： s—>next=p—>next; D： p—>next=s; s—>next=p; p—>next=s; 6．设一个栈的输入序列为 A，B，C，D，则借助栈所得到的输出序列不可能是。 A：A,B,C,D B：D,C,B,A C：A,C,D,B D：D,A,B,C 7．一个 n×n 的对称矩阵，如果以行或列为主序放入内存，则存储容量为______。 A：n2 B：n2/2 C：n(n+1)/2 D：(n+1)2 /2 8. 一棵有 124 个叶结点的完全二叉树，最多有______个结点。 A：247 B：248 C：249 D：250 9. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A：先序遍历 B：中序遍历 C：后序遍历 D：层次遍历 10. 设哈希表长 m=14，哈希函数 H（key）=key mod 11。表中已有 4 个结点 addr(15)=4，

addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空。如用二次探测再散列法处理冲突，则关键字为 49 的结点地址是______。 A：8 B：3 C：5 D：9 二、判断题（每题 2 分，共 20 分） 1．任何数据结构都具备三个基本运算：插入、删除和查找。（） 2. 在循环单链表中，任何一个结点的指针字段值都不可能为空。（） 3. 顺序队列中有多少元素，可以根据队首指针和队尾指针的值来计算。（） 4. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（） 5. 递归算法的执行效率比功能相同的非递归算法的执行效率高。（） 6. 当二叉树中的结点数多于 1 个时，不可能根据结点的先序序列和后序序列唯一地确定该二叉树的逻辑结构。（） 7. 若一个树叶是某二叉树先序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点。（） 8. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（） 9. 一个广义表的表尾总是一个广义表。（） 10. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点。（）三、简答题（共 60 分） 1．线性表有两种存储结构：一是顺序表，二是链表，试问：（共 12 分）（1）如果有 n 个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地改变。在此情况下应选用哪种存储结构？为什么？（6 分）（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（6 分） 2. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。（每个序列 3 分，画出二叉树 6 分，共 15 分）先序序列： _B _F_ ICEH_ G 中序序列：D _KFIA _EJC _ 后序序列：_ K _FBHJ _G_ A 3. 有如下图二所示的带权有向图 G，试回答以下问题：（共 18 分）（1）给出从顶点 1 出发的深度优先遍历序列和广度优先遍历序列。（6 分）（2）给出 G 的一个拓扑序列。（4 分）（3）给出从顶点 1 到顶点 8 的最短路径和关键路径。（8 分）

图二 4. 设用于通讯的电文仅由 8 个字母构成，字母在电文中出现的频率分别为：7、19、2、6、 32、3、21、10。试为这 8 个字母设计哈夫曼编码。（画图 10 分，写出编码 5 分，共 15 分）四、以关键字序列{265，301，751，129，937，863，742，694，076，438}为例，试写出执行大根堆排序算法的各趟排序结果时，关键字序列的状态。（10 分）五、设计一个算法，将一个带头节点的数据域依次为 a1，a2，a3，…..，an (n>=3)的单链表中所有节点逆置，即第一个节点的数据域变为 an，最后一个节点的数据域变为 a1。算法可用 C 或 pascal 语言进行描述。（10 分）六、有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数为 count，那么，这个纪录在新的有序表中的合适的存放位置为 count。（共 20 分） (1) 给出适合用于计数排序的数据表定义。（5 分）（2）使用 C 或 pascal 语言编写实现计数排序的算法。（10 分）（3）对于有 n 个记录的表，关键字比较次数是多少？（5 分）

分享到：

赞收藏

资料库

2011年云南昆明理工大学数据结构教程考研真题A卷.doc

相关推荐

考研

热门标签

最新资料