上海海事大学2017考研真题828数据结构及程序设计.pdf
- 2017 试题 1/6 - 2017年上海海事大学攻读硕士学位研究生入学考试试题 ( 重要提示 :答案必须做在答题纸上,做在试题上不给分) 考试科目 代码 828 考试科目名称 数据结构 及程序设计 一判断题(本题 10 分,每小题 1 分) 1 链式栈与顺序栈相比 , 一个明显的优点是通常不会出现栈满的情况。 2 能够在链 式 存储的有序表上进行折半查找,其时间复杂度与在顺序存储的有序表上相同。 3 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 4 任何一棵二叉树的叶结点在 先序、中序、后序 三种遍历中的相对次序是 相同 的。 5 数据结构的抽象操作的定义与具体实现有关。 6 对一个有向图进行拓扑排序,一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。 7 如果无向图中每个顶点的度都大于等于 2,则该图中必有回路。 8 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。 9 若让元素 1、 2、 3 依次进栈,则出栈次序 1、 3、 2 是不可能出现的情况。 10 对平衡二叉树进行中序 遍历,可得到结点的有序排列。 二填空题(本题 20 分,每空 2 分) 1下面程序的功能是实现冒泡 排序算法,请在下划线处填上正确的语句。 void bubble(int rn) for ( i=1; irj+1) temp=rj+1; ; rj=temp; exchange=1; if (exchange=0) return; 2 设查找表中有 100 个元素,如果用二分法查找方法查找数据元素 X,则最多需要比较 次就可以断定数据元素 X 是否在查找表中。 3 设有一空栈,现有输入序列 1、 2、 3、 4、 5,经过 push, pop, push, push, pop, push, pop, pop, push, pop 后,输出序列是 。 4 一个广义表为 (a,(a,b),(a,b),c),则 它 的长度为 ,深度为 。 5 设有向图 G 的二元组形式表示为 G =( D, R), D=1, 2, 3, 4, 5, R=r, r=, , , , ,则给出该图的一种拓扑排序序列 。 6 在有序表( 12, 24, 36, 48, 60, 72, 84)中二分查找关键字 72 时所需进行的关键字比较次数为 。 7 设无向图 G 中有 n 个顶点和 e 条边,则其对应的邻接表中有 个表头结点和 个表结点。 三选择题(本题 30 分,每空 2 分) 1 若 int a=1, b=2, c=3, d=4, m=2, n=2; 执行 (m=ab) - 2017 试题 3/6 - A 2.500000 B 2.750000 C 3.375000 D 3.000000 3 下面程序的输出结果是 ( ) 。 main( ) char a7= “abcdef“, b4= “ABC“; strcpy(a, b); printf(“%c“, a5); A B 0 C e D f 4 计算机 算法指的是( )。 A计算方法 B排序方法 C调度方法 D解决问题的步骤序列 5 链表不具有的特点是 ( ) 。 A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比 6 循环队列存储在数组 A0.m中,则入队时的操作为( )。 A rear = rear+1 B rear = (rear+1) % (m-1) C rear = (rear+1) % m D rear = (rear+1) % (m+1) 7 有一个 100*90 的稀疏矩阵,非 0 元素有 10 个,设每个整型数占 2 字节,则用三元组表示该矩阵时,所需的字节数是 ( ) 。 A 60 B 66 C 18000 D 33 8 一棵三 叉 树中度为 3 的结点 有 2 个,度为 2 的结点 有 1 个,度为 1 的结点 有 2 个,则度为 0 的结点 有 ( ) 个 。 A 4 B 5 C 6 D 7 9 将有关二叉树的概念推广到三叉树,则一棵有 244 个结点的完全三叉树的高度 为- 2017 试题 4/6 - ( ) 。 A 4 B 5 C 6 D 7 10 无向图 G=(V, E), 其中: V=a,b,c,d,e,f, E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d),对该图进行深度优先遍历,得到的顶点序列正确的是 ( ) 。 A a,e,d,f,c,b B a,c,f,e,b,d C a,e,b,c,f,d D a,b,e,c,d,f 11 用二分( 折 半) 法 查找表的元素的速度比用顺序法 ( ) 。 A 必然快 B必然慢 C相等 D不能确定 12 具有 12 个关键字的有序表,折半查找的平均查找长度 为 ( ) 。 A 3.1 B 4 C 2.5 D 5 13 就排序算法所用的辅助空间而言,堆排序 、 快速排序 、 归并排序的关系是 ( ) 。 A 堆排序 快速排序 归并排序 B 堆排序 归并排序 快速排序 14 比较次数与排序的初始状态无关的排序方法是 ( ) 。 A 快速排序 B起泡排序 C简单选择排序 D直接插入排序 15 算术表达式 a+b*(c+d/e)转为后缀表达式后为 ( ) 。 A abcde/+*+ B abcde/*+ C abcde*/+ D ab+cde/* 四应用题(本题 60 分,每小题 10 分) 1已知一棵二叉树的 中 根 序序列和 后 根 序序列分别为, 中根序序列: EBCDAFHG 后 根序序列: EDCBHGFA 试 画出该 二叉 树 , 并写出其 先 根 序序 列。 - 2017 试题 5/6 - 2 请 画出 按 64, 79, 34, 47, 93, 40, 13, 22, 56, 95, 83序列 顺序输入 建立 的 二叉排序树, 再 画出 从 该二叉排序树 中 删除结点 34 后的二叉排序树。 3某通信系统中共包含 九 个字 母 : C、 E、 D、 A、 S、 H、 M、 T、 U, 各个字符 出现频 率分别为: 12%、 6%、 14%、 9%、 20%、 16%、 8%、 5%、 10%,试为它们构造一棵 Huffman树(哈夫曼树),并 设计 这些字符的哈夫曼编码。 4右图是一个无向 网 , 请 分别用下列两种方法求它的最小生成树, 给出最小生成树中各条边加入的先后顺序( 连接顶 点 x 和 y 的 边用 形式表示 ),并求出最小生成树 的代价(即 各条边权值之和 ) 。 1) 用普里姆算法从顶点 A 开始; 2) 用克鲁斯卡尔算法 ; 3) 最小生成树的代价 。 5 设关键码序列 18、 93、 35、 24、 67、 55、 72、 49、 43、 86 , 散列表为 HT0.12,散列函数为: H(key) = key % 13,采用 平方 探测再散列法解决冲突, 试回答下列问题: 1)求依次 插入这 10 个关键码后的散列表。 2)计算在等概率情况下查找成功 时 的平均查找长度。 6 设有 一组 待排序记录的关键字序列为 249、 375、 168、 356、 268、 124、 327、 136、362、 216、 286、 385、 112、 270 ,需要按关键字值递增的次序进行排序 , 试 求: 1) 堆 排序 初始建堆后的结果 ; 2)以第一个元素为基准的快速排序 第一趟扫描后的结果。 A BEFDGC475 6 6 103 8 15812- 2017 试题 6/6 - 五编程题(本题 30 分,每小题 10 分) 1编写一个函数 sum( )计算: S = 1+(1+2)+(1+2+3)+(1+2+3+4)+.+(1+2+3+.+100) 2设有一个带头结点的链表,表头指针为 h, 存储结构为: typedef struct Node int data; struct Node *next; Node, *List; 其中, data 为整型数域, next 为指针域,编写函数 delneg 将 链表 中 data 域 值小于 1 的所有 结点删除 。 3设树的存储采用孩子 -兄弟表示法表示,定义为: typedef struct TNode char data; struct TNode *firstchild,*nextsibling; TNode,*Tree; 编写函数 nodedepth( )计算 并输出 树中 每个叶子 结点 的 data 域值与所在的层 数(根结点所在的层数为 1)。