东北大学1996年考研题.doc

Size: px

Start display at page:

Download "东北大学1996年考研题.doc"

马禹
7 years ago
Views:

1 1996 年考研题一 ( 25 分 ) 每小题 5 分 1. 根据下图完成 : (1) 画出该图的十字链表存储结构图 (2) 写出其拓扑排序的输出序列 (3) 写出图的强连通分量 ( 支 ) ( 4 ) 写出到的所有路径及简单路径 2. 给定 8 个权值集合 (2,5,3,10,4,7,9,18) 画出含有 8 个叶子结点的最佳三叉归并树, 并计算出 3. 已知含有 8 个结点的一棵二叉树, 按先序中序后序进行遍历后, 有些结点序号不清楚如下图示要求构造出一棵符合条件的二叉树先根序遍历中根序遍历后根序遍历根据给定的关键字集合 (20,15,40,35,45,25,50,30,10) 顺序输入 (1) 构造一棵完全二叉树 ; (2) 画出整理好的一棵堆树 ; (3) 画出一棵输出一个排序记录后的二叉树 ; (4) 画出重新调整好的堆树 5. 下图给出的是一棵三阶 B 树, 处理时每次只能读一个结点到内存要求 : (1) 计算出由图中结构用计算机查找到关键字 (35) 的记录并将其删掉, 需进行多少次读 / 写才能完成? (2) 画出删除关键字为 (35) 和关键字为 (50) 的记录后的三阶 B 树

2 二已知 L1 L2 分别为两循环单链表的头结点指针,m,n 分别为 L1 L2 表中数据结点个数要求设计一算法, 用最快速度将两表合并成一个带头结点的循环单链表 ( 10 分 ) 三线性表 (a1,a2,a3 an) 中元素递增有序且按顺序存于计算机内要求设计一算法完成 (12 分 ): 1. 用最少的时间在表中查找数值为的元素 2. 若找到将其与后继元素位置交换 3. 若找不到将其插入表中并使表中元素仍递增有序四设给定关键字输入序列为 (100,90,120,60,78,35,42,31,15) 用散列法散列 0 10 的地址区间要求设计一合理的散列函数 ; 冲突时用链表法解决, 写出散列算法, 并构造出散列表在等概率查找情况下查找成功的平均查找长度是多少?(12 分 ) 五设为 t 一棵二叉树的根结点地址指针, 试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换 ( 10 分 ) 六设 L 为单链表的头结点地址, 其数据结点的数据都是正整数且无相同的, 试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法 ( 14 分 ) 七设 t 是一棵按后序遍历方式构成的线索二叉树的根结点指针, 试设计一个非递归的算法, 把一个地址为 x 的新结点插到 t 树中, 已知地址为 y 的结点有侧作为结点 y 的右孩子, 并把插入后的二叉树仍为后序线索二叉树 ( 15 分 )

3 1997 年考研题一按要求完成下题 (25 分 ) 1. 已知 U= xyxyxyxxyxy ;t= xxy ; ASSIGN(S,U; ASSIGN(V,SUBSTR(S,INDEX(s,t), LEN(T)+1)); ASSIGN(m, ww ) 求 REPLACE(S,V,m)= 2. 已知广义表 A=((( a )),( b ), c,( a ),((( d, e )))) ( 1 ) 写出其一种存贮结构图 ; (2) 写出表的长度与深度 ; (3) 用求头部, 尾部的方式求出 e 3. 画出同时满足下列两条件的两棵相同的二叉树 (1) 按先根序遍历二叉树顺序为 ABCDE (2) 高度为 5 其对应的树 ( 森林 ) 的高度最大为 4 4. 下图为一棵二叉排序树完成 : (1) 写出平衡因子绝对值为 2 的结点 ; (2) 为何种类型的不平衡树 ; (3) 画出调整好的平衡二叉树, 写出相应的指针变化式 5. 一个有向图的邻接表存贮如下 (1) 画出其邻接矩阵存贮 ;

4 (2) 写出图的所有强连通分量 ; (3) 写出顶点 a 到顶点 I 的全部简单路径二断正误 (10 分 ) 1. 二叉排序树查找总是比顺序查找速度快 2. 堆排序与快速排序相比堆比快速省时间 K-2 3. 深度为 k 且具有 n 个结点的二叉树其编号最小的结点序号为在 m 阶 B 一树中每个结点上至少 m/2 有个关键字最多 m 有个关键字 5. 影响外排序的时间因素主要是内存与外设交换信息的总次数三线性表 (a1 a2a3 an) 按顺序存贮, 且每个元素都是整数不相同, 设计把所有奇数指到所有偶数前边的算法 ( 要求时间最少, 辅助空间最少 ) (15 分 ) 四 1 与 L2 分别为两单链表头结点, 地址指针, 且两表中数据结点的数据域均为一个字母设计把 L1 中与 L2 中数据相同的连续结点顺序完全倒置的算法例 : (15 分 ) 五知输入关键字序列为 (100,90,120,60,78,35,42,31,15) 址区向为 0~11 设计一个哈希表函数把上述关键字散到 0~11 中画出散列表 ( 冲突用线性探测法 ); 写出查找算法, 计算在等概率情况下查找长度 (15 分 ) 六一棵高度 K 具有 n 个结点的二叉树, 按顺序方式存贮 : 1. 编写用先根遍历树中每个结点的递归算法 ; 2. 编写将树中最大序号叶子结点的祖先结点全部打印输出的算法 (20 分 )

5 1998 年考研题一完成下列各小题 ( 每小题 10 分, 共计 30 分 ) 1. 已知三个字符分别为 s= ab abcaabcbca a s = caab, s = bcb 利用所学字符串基本运算的函数得到结果串为 s = caabcbca aca a 要求写出得到上结果串 S 所用的函数及执行算法 2. 已知记录关键字集合为 (53,17,19,61,98,75,79 63,49,46) 要求散列到地址区间 (100,101,102,103,104,105,106,107,108,109) 内, 若产生冲突用开型寻址法的线性探测法解决要求写出选用的散列函数 ; 形成的散列表 ; 计算出查找成功时平均查找长度与查找不成功的平均查找长度 ( 设等概率情况 ) 3. 已知一棵 3 阶 B- 树如下图所示 : (1) 画出查入 (18) 的 3 阶 B- 树计算读结点 / 写结点次数 (2) 画处在插入 (18) 后的 3 阶 B- 树中删除 (78) 后的 3 阶 B- 树并计算读 / 写次数二已知线性表 (a1 a2 a3 an) 按顺序存于内存, 每个元素都是整数, 试设计用最少时间把所有值为负数的元素移到全部正数元素前边的算法 :( 15 分 ) 例 :( x, -x, -x, x, x, -x -x) 变为 (-x,-x, -x x x x) 三已知 L 为链表的头结地址, 表中共有 m(m>3) 个结点, 从表中第 i 个结点 (1<i<m) 起到第 m 个结点构成一个循环部分链表, 设计将这部分循环链表所有结点顺序完全倒置的算法 ( 15 分 ) 四设有字母数字共 m 个混合传输从甲站到乙站存储, 字母数字的个数不知, 且不相等, 希望从乙站输出时将字母与数字分开且字母保持原输入顺序, 而数字与输入倒序, 要求在任何时刻只要已存元素个数之和小于 M 便能存储, 试设计能满足上述要求的存储结构, 并设计完成上述功能的算法, 即乙接收甲传输及从乙输出的算法 ( 20 分 ) 五一棵高度为 K 且有 n 个结点的二叉排序树, 同时又是一棵完全二叉树存于向量 t 中, 试设计删除树中序号为 i 且具有左右孩子的一个结点, 而不使存储量增加保证仍为二叉排序树 ( 不一定是完全二叉树 ) 的算法 ( 20 分 )

6 1999 年考研试题一回答下列各题 :( 27 分 ) 1. 已知一棵满二叉树的结点个数为 2040 之间的素数, 此二叉树的叶子结点有多少个?(3 分 ) 2. 设有五对角矩阵 A=(aij)20*20, 按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组 [-10: m] 中, 计算元素 A[15,16] 的存储位置 ( 4 分 ) 3. 已知一组关键字为 (26,36,41,38,44,15,68,12,06,51,25), 用链地址法解决冲突假设装填因子 a=0.75 散列函数的形式为 H(K)=K MOD P, 回答下列问题 : (1) 构造出散列函数 ;(3 分 ) (2) 计算出等概率情况下查找成功的平均查找长度 ;(3 分 ) (3) 计算出等概率情况下查找失败的平均查找长度 ;(3 分 ) 4. 判别一下序列是否为堆, 若不是, 则把他调整为堆 (1)( 100,86,48,73,35,39,42,57,66,21)( 4 分 ) (2)( 12,70,33,65,24,56,48,92,86,33)( 4 分 ) 5. 设有 1000 个无序的元素, 希望用最大的速度挑选出其中前十个最大的元素, 在以下的方法中采用哪一种最好? 为什么?(3 分 ) ( 快速排序, 归并排序, 堆排序, 基数排序,shell 排序 ) 二两个正数序列 A=a1,a2,a3,..am 和 B=b1,b2,b3, bn 已经存入两个单链表中, 设计一个算法, 判别序列 B 是否是序列 A 的子序列 ( 10 分 ) 三编写算法判别二叉树是否为平衡二叉树 ( 12 分 ) 四编写一算法, 利用叶子结点中的空指针域将所有叶子结点链接为一个带头结点的双链表, 算法返回头结点的地址 ( 13 分 ) 五对于一个使用邻接表存储的有向图 G, 可以利用深度优先遍历方法, 对该图中结点进行拓扑排序其基本思想是 : 在遍历过程中, 每访问一个顶点, 就将其邻接到的顶点的入度减一, 并对其未访问的入度为 0 的邻接到的顶点进行递归 ( 18 分 ) 1. 给出完成上述功能的图的邻接表定义 ( 结构 ):( 4 分 ) 2. 定义在算法中使用的全局辅助数组 ( 4 分 ) 3. 写出在遍历图的同时进行拓扑排序的算法 :( 10 分 ) 六回答下列问题 (20 分 ): 1. 试找出满足下列条件的二叉树 (4 分 ) (1) 先序序列与后序序列相同 (2) 中序序列与后序序列相同 (3) 先序序列与中序序列相同 (4) 中序序列与层次遍历序列相同 2. 已知一棵二叉树的中序序列和后序序列分别为 DBEAFIHCG 和 DEBHIFGCA, 画出这棵二叉树 (4 分 ) 3. 已知一棵二叉树的中序序列和后序序列, 写一个建立该二叉树的二叉链表存储结构的算法 ( 12 分 )

7 2000 年考研试题一简要回答下列问题 (20 分 ): 1. 内存中一片连续空间 ( 不妨蛇地址从 1 到 M) 提供给两个栈 S1 和 S2 使用, 怎样分配这部分存储空间, 使得对任一个栈, 仅当这部分空间全满时才发生上溢 ( 3 分 ) 2. 假设字符 a,b,c,d,e,f 的使用频度分别是 0.07,0.09,0.12,0.22,0.23,0.27, 写出 a,b,c,d,e,f 的 Huffman( 哈夫曼 ) 编码 ( 5 分 ) 3. 一棵共有 n 个结点的树, 其中所有分支结点的度均为 K, 求该树中叶子结点的个数 ( 4 分 ) 4. 下图表示一个地区的通讯网, 边表示城市间的通讯线路, 边上的权表示架设线路花费的代价, 如何选择能沟通每个城市且总代价最省的 n-1 条线路, 画出所有可能的选择 ( 4 分 ) 在起泡 ( 冒泡 ) 排序过程中, 有的关键字在某趟排序中可能朝着与最终方向相反的方向移动, 试举例说明之快速排序中有没有这种现象?(4 分 ) 二设有一个由正整数组成的无序 ( 向后 ) 单链表, 编写完成下列功能的算法 (15 分 ): 1. 找出最小值结点, 且打印该数值 ; 2. 若该数值是奇数, 则将其与直接后继结点的值交换 ; 3. 若该数值是偶数, 则将其直接后继结点删除 ; 三解答下列问题 (14 分 ): 1. 将算术表达式 (( a+b)+c*(d+e)+f)*(g+h) 转化为二叉树 (4 分 ); 2. 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树 b1 中, 写出计算该表达式值的算法 ( 10 分 ) 四解答下列问题 (21 分 ): 1. 画出有向图十字链表存储结构中头接点和表结点的结点结构 ( 5 分 ) 2. 下面哪一方法可以判断出一个有向图是否有环 ( 回路 )( 4 分 ): ( 1 ) 深度优先遍历 (2) 拓扑排序 (3) 求最短路径 (4) 求关键路径 3. 假设一个有向图 G 已经以十字链表形式存储在内存中, 试写一个判断该有向图中是否有环 ( 回路 ) 的算法 ( 12 分 ) 五写出删除二叉排序树 bt 中值为 x 的结点的算法 ( 二叉排序树以二叉链表的形式存储, 删除后仍然保持二叉排序性质 )( 15 分 )

8 六设有大小不等的 n 个数据组 (n 个数据组中数据的总数为 m), 顺序存放在空间区 D 内每个数据占一个存储单元, 数据组的首地址由数组 S 给出,( 如下图所示 ), 试编写将新数据 X 插入到第 I 个数据组的末尾且属于第 I 个数据组的算法, 插入后, 空间区 D 和数组 S 的相互关系仍保持正确 (15 分 ) D L S[1..n] S[1] S[2].. s[n] 未用空间

9 2002 年考研试题一回答下列问题 :( 24 分 ) 1. 如果用一个循环数组 q[0..m-1] 表示队列时, 该队列只有一个队列头指针 front, 不设队列尾指针 rear, 而改置计数器 count 用以记录队列中结点的个数 (1) 编写实现队列的基本运算 : 判空入队出队 (3 分 ) (2) 队列中能容纳元素的最多个数是多少?(1 分 ) 2. 设有对角矩阵 a[1..n,1..n] 把非零元素按列存储在向量 b[1..3*n-2] 中, 使得 b[k]=a[i,j]. 求 :( 1 ) 用 I,j 表示 k 的下标变换公式 (2 分 ) (2) 用 k 表示 I,j 的下标变换公式 (2 分 ) 3. 设二叉排序树中关键字由 1 到 1000 的整数组成, 现要查找关键字为 363 的结点, 下述评关键字序列哪一个不可能是在二叉排序树中找到的序列? 说明原因 ( 4 分 ) (1)51,250,501,390,320,340,382,363 (2)24,877,125,342,501,623,421, 设有 n 个无序元素, 按非递减次序排序, 但只想得到前面长度为 k 的部分序列, 其中 n>>k, 最好采用什么排序方法? 为什么?(2 分 ) 如果有这样一个序列 {59,11,26,34,17,91,25}, 得到的部分序列是 :{11,17,25}, 对于该例使用所选择的方法实现时, 共执行多少次比较?(3 分 ) 5. 在 B- 树和 B+ 树中查找关键字时有什么不同?(2 分 ) 6. 写出对关键字序列 {503,087,512,061,908,124,897,275,653,426} 建立一棵平衡二叉树的过程, 并写出调整平衡时的指针变化 ( 5 分 ) 二解答下列问题 :( 10 分 ) 1. 画出对长度为 10 的有序表进行二分查找的判定树并求其等概率时查找成功的平均查找长度 (5 分 ) 2. 设有一组关键字 {9,01,23,14,55,20,84,27}, 采用哈希函数 :H(key)=key mod 7, 表长为 10, 用开放地址法的二次探测再散列方法 Hi=(H(key)+di)mod10(di=1*1,2*2,3*3.) 解决冲突要求 : 对该关键字序列构造哈希表, 并计算查找成功的平均查找长度 (5 分 ) 三已知 L 为没有头结点的的单链表中第一个结点的指针, 每个结点数据域存放一个字符, 该字符可能是英文字母字符或数字字符或其他字符, 编写算法构造三个以带头结点的单循环链表表示的线性表, 使每个表中只含同一类字符 ( 要求用最少的时间和最少的空间 )( 15 分 ) 四对以二叉链表存储的非空二叉树, 从右向左依次释放所有的叶子结点, 释放的同时把结点值存放到一个向量中要求 : 1. 用文字写出实现上述过程的基本思想 (3 分 ) 2. 写出算法 (12 分 ) 五设二叉排序树已经以二叉链表的形式存储在内存中, 使用递归方法, 求各结点的平衡因子并输出要求 : 1. 用文字写出实现上述过程的基本思想 (3 分 ) 2. 写出算法 (12 分 ) 六假设一个有向图 g 已经以右图所示的逆邻接表形式存储在内存中, 要求 : 1. 写出逆邻接表的存储结构定义 (3 分 ) 2. 用文字写出在逆邻接表上实现拓扑排序的基本思想 (3 分 ) 3. 写出在逆邻接表上实现拓扑排序的算法 (15 分 )

10 2003 年数据结构试题一简要回答下列问题 (20 分 ) 1. 对于有 n 个顶点的无向图和有向图, 采用邻接矩阵表示, 如何判断以下问题 : 图中有多少条边? 任意两个顶点 i 和 j 之间是否有边相连? 任意一个顶点的度是多少?(7 分 ) 2. 判别下列序列是否为堆 ( 小根堆或大根堆 ), 若不是, 则将其调整为堆 (8 分 ): ( 1 )( 100,86,48,73,35,39,42,57,66,21) (2)( 12,70,33,65,24,56,48,92,86,33) (3)( 05,23,20,35,28,38,29,61,56,76,40,100) 3. 设 A 和 B 均为下三角矩阵, 每一个都有 n 行 n 列因此在下三角区域中各有 n(n+1)/2 个无素另设有一个二维数组 C, 它有 n 行 n +1 列试设计一个方案, 将两个矩阵 A 和 B 中的下三角区域元素存放于同一个 C 中要求将 A 的下三角区域中的元素存放于 C 的下三角区域中,B 的下三角区域中的元素转置后存放于 C 的上三角区域中并给出计算 A 的矩阵元素 a ij 和 B 的矩阵元素 b ij 在 C 中的存放位置下标的公式 ( 5 分 ) 二已知 f 为单链表的表头指针, 链表中存储的都是整型数据, 试设计算法将此链表的结点按照递增次序进行就地排序 ( 15 分 ) 三给出中序线索二叉树的结点结构, 试编写在不使用栈和递归的情况下先序遍历中序线索二叉树的算法 (20 分 ) 四设关键字是一个由 26 个小写字母组成的字符串, 哈希表的长度为 26 试编写算法, 建立哈希表, 并以第一个字符的字典顺序输出哈希表中的所有关键字设哈希函数为 hash(x)=x 中的第一个字符在字典顺序中的序号, 采用线性探测再散列法来解决冲突 ( 假设函数 f(x) 能够计算出 x 中的第一个字符在字典顺序中的序号 )( 20 分 ) 1

11 2004 年数据结构试题一完成下列问题 (20 分 ) 1. 对下面的关键字集 {30,15,21,40,25,26,36,37,10,20}, 写出快速排序的每趟结果和最终结果 (6 分 ) 2. 已知有一个 10 个顶点的连通图, 顶点编号为 1 至 10, 其边的关系集合表示为 {(1,2),( 1, 3 ), ( 1, 8 ),( 2, 4 ),( 3, 9 ),( 3, 10),( 5, 7 ),( 6, 7 ),( 7, 8 ),( 8, 9 ) }, 试画出该连通图及以顶点 1 为根的深度优先生成树 ( 6 分 ) 3. 已知二叉树的存储结构为二叉链表,LinkList 和 BiTree 为已定义的指针类型,ListNode 为已定义的结点类型, 阅读下面算法并回答 :( 8 分 ) LinkList L=NULL; void inorder_list (BiTree T){ LinkList p; If (T){ Inorder_list(T->lchild); If ((!T->lchild)&&(!T->rchild)){ p=(listnode *)malloc (sizeof(listnode)); p->data=t->data; p->next=l; L=p; }//if Inorder_list (T->rchild); }//if }//Inorder_list (1) 说明该算法的功能 ; (2) 对于一棵有 8 结点的完全二叉树 ( 假设结点顺序为 A B C D E F G H), 画出执行上述算法后所建成立的结构二某商店有一批手机, 按价格从高到低构成一个单链表, 结点包括数量价格指针现新到 n 台价格不同的手机, 编写将新到手机插入到原链表中的算法 ( 20 分 ) 三假设哈希函数为 H(key), 编写用链地址方法解决冲突的哈希表的插入和删除算法 ( 20 分 ) 四设用输入广义表表示的字符串来创建二叉链表结构的二叉树, 具体规定如下 : 广义表的表名作为树的根结点, 每个结点的左子树和右子树用逗号分隔, 若仅有右子树, 则逗号不能省略 ; 以特殊符号 $ 表示广义表的结尾 ( 15 分 ) 1. 若输入的字符串为 A(B(C), D ( E (,F), G )), 画出所表示的二叉树 2. 实现用上述方法创建二叉树的算法

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程

2018 年天津城建大学攻读硕士学位研究生入学考试试题 (A) 卷考试科目代码 :825 考试科目名称工程信息技术招生专业 : 建筑与土木工程一单项选择题 ( 本题共 20 小题, 每题 2 分, 共 40 分 ) 1. 计算机所处理的数据一般具有某种内在联系, 这是指 ( ) A. 数据和数据之间存在某种联系 B. 数据项和数据项之间存在某种联系 C. 元素内部具有某种结构 D. 元素和元素之间存在某种联系 2. 在计算机中表示数据时, 数据的物理地址和逻辑地址相同并且连续, 称其为 ( ) A. 链式存储结构 B. 顺序存储结构 C.