2017年山东青岛科技大学数据结构考研真题.doc

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

第1页 / 共4页

第2页 / 共4页

第3页 / 共4页

第4页 / 共4页

文本预览

2017 年山东青岛科技大学数据结构考研真题 n) 一．选择题(每题 2 分，共 30 分) 1．数据结构通常是研究数据结构的（）以及它们的操作。 A）理想与逻辑 B）存储和抽象 C）理想和抽象 D）逻辑结构和存储结构 2．指出下面程序段的时间复杂度（）。 i=1; While(inext=P; P->next=S; B）S->next=P->next; P=S; C）S->next=P->next; P->next=S; D）P->next=S; 7．具有 n 个叶子结点的哈夫曼树，所有结点个数为（）。 A）2n B）2n+1 C）2n-2 D） 2n-1 8．一棵深度为 K 的完全二叉树至少有( S->next=P; )结点。

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 ) { L.r[0] = L.r[i]; low = 1 ; high = i-1 ; while ( low <= high ) { if m = ( low + high ) / 2 ; ( L.r[0].key < L.r[m]. key ) high = m -1 ; else low = m + 1; } for ( j=i-1; j>=high+1; - - j ) L.r[j+1] = L.r[j]; L.r[high+1] = L.r[0]; } // Sort } 三．算法设计题（60 分） 1.（20 分）已知 head 是指向带头结点的单链表的头指针，试编写以下算法： ①统计单链表中结点个数的算法； ②删除单链表中值为 x 的算法； 2．（20 分）设以二叉链表作为二叉树的存储结构，写出如下算法： ①用先序遍历的方法，统计二叉树中度为 1 的结点的个数； ②用层次遍历的方法，统计二叉树中度为 1 的结点的个数； 3．（20 分）写出如下算法： ①创建一个有向图邻接表的存储结构的算法；

②写出利用该存储结构实现对有向图进行拓扑排序的算法；

分享到：

赞收藏

资料库

2017年山东青岛科技大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料