2018上海海事大学考研真题828数据结构及程序设计.pdf
- 2018 试题 1/6 - 2018年上海海事大学攻读硕士学位研究生入学考试试题 ( 重要提示 :答案必须做在答题纸上,做在试题上不给分) 考试科目代码 828 考试科目名称 数据结构及程序设计 一判断题(本题 10 分,每小题 1 分) 1 线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存储。 2 单链表从任何一个结点出发,都能访问到所有结点 。 3 单链表形式的队列,头指针 F 指向队列的第一个结点,尾指针 R 指向队列的最后一个结点。 4若在采用链式存储结构线性表中,元素按值有序,则该线性表可以采用折半查找法查 找元素。 5 一个栈的输入序列为 1, 2, 3, , n,其输出序列的第二个元素为 n 的输出序列的个数有 n-1 种。 6 设串 S 的长度为 n, 则 S 的子串个数为 n(n+1)/2。 7若一个广义表的表头为空表,则此广义表亦为空表。 8 二叉树中除叶节点外,任一节点 x,其左子树根节点的值小于该节点 (x)的值,其右子树根节点的值大于该节点 (x)的值,则此二叉树一定是二叉排序树。 9 网络的最小代价生成树是唯一的。 10( 99, 86, 46, 70, 34, 39, 45, 58, 66, 10 )是堆。 二填 空题(本题 20 分,每空 2 分) 1 一个栈的输入序列是: 1、 2、 3, 则不可能的栈输出序列是 。 - 2018 试题 2/6 - 2. 将整型数组 A1.8, 1.8按行优先次序存储在起始地址为 1000的连续内存单元中,则元素 A7, 3的地址是: 。 3 已知广义表 A=( 9, 7, ( 8, 10, ( 99 ) ), 12 ), 取 表头 和表尾的操作为 head( )和 tail( ),则 将原子元素 99 从 A 中取出来 的操作为 。 4已知一棵度为 3 的树有 2 个度为 1 的结点, 3 个度为 2 的结点, 4 个度为3 的结点 ,则该树有 个叶子结点。 5已知二叉树 先根 序 序列 为 ABDEGCF,中 根序序列 为 DBGEACF,则后根序序列为 。 6. 已知一无向图 G=( V, E),其中 V= a, b, c, d, e E= (a, b), (a, d), (a, c), (d, c), (b, e) , 现用某一种图遍历方法从顶点 a 开始遍历图,得到的序列为 abecd,则采用的是 遍历方法。 7. 己知有序表为 ( 11, 18, 25, 32, 46, 50, 62, 85, 90, 115, 134 ), 用二分法查找46 时,需 次查找成功,查 100 时,需 次才能确定不成功。 8分别采用堆排序,快速排序,冒泡排序和归并排序,对初态为有序的表,则最省时间的是 算法,最费时间的是 算法。 三选择题(本题 30 分,每空 2 分) 1 用 二进制文件和文本文件 存储整型数 -8765 时, 各 占用 ( )个 字节 。 A 2 和 2 B 2 和 5 C 5 和 5 D 5 和 2 2设有定义语句 char s=“123“; 则表达式 s3的值是 ( )。 A 1 B 3 C 0 D语法出错 3执行下列程序段后的输出结果是 ( )。 x = 9; while ( x 7 ) printf(“*“); x-; - 2018 试题 3/6 - A * B * C * D * 4设 int m=1, n=2; 则 m+ = = n 的结果是( )。 A 0 B 1 C 2 D 3 5以下程序段( )。 x = -1; do x = x * x; while ( ! x ); A.是死循环 B.循环执行二次 C.循环执行一次 D.有语法错误 6已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为 ABC*+DE/-,其前缀形式为 ( )。 A -A+B*C/DE B -A+B*CD/E C -+*ABC/DE D -+A*BC/DE 7线性表采用链式存储时,结点的存储地址 ( ) 。 A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点 的存储地址相连续 8判定一个循环队列 QU(最多元素为 m0)为满队列的条件是( )。 A QU.front = = (QU.rear+1)%m0 B QU.front != (QU.rear+1)%m0 C QU.front = = QU.rear D QU.front != QU.rear+1 9设广义表 L= ( ( a, b, c ) ),则 L 的长度和深度分别为( )。 A 1 和 1 B 1 和 3 C 1 和 2 D 2 和 3 10 一棵二叉树度为 2 的结点有 10 个, 则 度为 0 的结点有( )个。 A 9 B 11 C 12 D 不确定 11 具有 n ( n 1 ) 个顶点的强连通图至少有( )条弧。 - 2018 试题 4/6 - A n+1 B n C n-1 D 2(n-1) 12 具 有 n 个顶点和 e 条边的无向图 的邻接矩阵中有 ( ) 个零元素 。 A e B 2e C n2-e D n2-2e 13 无向图 G=(V, E)中 V=a, b, c, d, e, f, E=(a, b), (a, c), (a, d), (b, e), (c, f) , (d, e), (d, f) ,对该图进行 广 度优先遍历得到的顶点序列正确的是( )。 A a,e,d,f,c,b B a,c,f,e,b,d C a,e,b,c,f,d D a,b,d,c,e,f 14 直接插入排序在最好情况下的时间复杂度为 ( )。 A O(logN) B O(N) C O(N*logN) D O(N*N) 15若查找每个记录的概率均等,则在具 有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度 ASL 为 ( )。 A (n-1)/2 B n/2 C (n+1)/2 D n 四应用题(本题 60 分,每小题 10 分) 1右图是一个有向图,试回答下列问题: 1)给出它的邻接表存储表示; 2)写出其所有可能的拓扑序列。 2某通信系统中共包含八个字母: G、 U、 Z、 O、 N、 G、 R、 D,各个字符出现频率分别为: 21%、 8%、 15%、 9%、 18%、 10%、 6%、 13%,试为它们构造一棵 Huffman 树(哈夫曼树),并求出这些字符的哈夫曼编码。 3 试 分别用 普里姆算法和克鲁斯卡尔算法求 右图的最小生成树( 给出最小生成树中各条边加入的先后顺序 , 连接顶点 x 和 y 的边用 A BGEDFC4739 7105 811612A BECFD- 2018 试题 5/6 - 形式表示),并求出最小生成树的代价(即各条边权值之和)。 1)普里姆算法从顶点 D 出发 ; 2)克鲁斯卡尔算法; 3)最小生成树的代价。 4有关键码序列 38、 53、 14、 33、 76、 47、 65、 42、 25、 54、 82 ,采用散列函数 H(key) = key % 11 存储在散列表 HT0.12中,并用线性探测再散列法解决 冲突,试解下列问题: 1)画出依次插入以上 11 个关键码后的散列表。 2)计算在等概率情况下查找成功时的平均查找长度。 5右图为一棵二叉树,试回答下列问题: 1)写出该二叉树的中根序序列; 2)画出该二叉树的顺序存储表示; 3)画出该二叉树的中根序线索二叉链表存储表示。 6有一组待排序记录的关键字分别为 495、 725、 321、 682、 586、 216、412、 278、 365、 532、 438、 192、 627 ,试采用下列方法按关键字值递增的次序进行排序: 1)步长为 5、 3、 1 的 Shell 排序; 2)归并排序。 五编程题(本题 30 分,每小题 10 分) 1 试 编写一个函数 sum( n ) 计算 满足 下式的最大 m: ABGED FCH K- 2018 试题 6/6 - 1*2 + 2*3 + 3*4 + . + (m-1)*m = n 2有一个带头结点的链表 存储学生成绩 score,试编写函数 计算 链表 所有记录中的最 高 成绩 max、最低成绩 min 和平均成绩 aver, 链 表 的 存储结构为: typedef struct Node char name; float score; struct Node *next; Node, *List; 3 编写函数 exchange( ) 计算二叉树的高度并将其每一个结点的左孩子与右孩子对调, 设 二叉 树采用 二叉链表存储 : typedef struct BTNode ElemType data; struct BTNode *lchild, *rchild; BTNode,*BTree;