《2022年数据结构精选考研试题知识 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构精选考研试题知识 .pdf（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、注：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：20分1、 算法的定义和性质2、 为什么说数组与广义表是线性表的推广？3、 什么是结构化程序设计？4、 哈希方法的基本思想5、 给出一不稳定排序方法名称与实例二、构造结果： 24分 （1） 确定 x:=x+1 语句在下面程序段中的频率，要求写出分析过程。for i:=1 to n dofor j:=1 to I dofor k:=1 to j do x:=x+1（2） 画出对长度为 8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、
2、中序、后序遍历的结果序列（4） 假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为2 ，3，5，7，11，4，13，15 ，试为这 8 个字母设计哈夫曼编码（5） 在地址空间为015 的散列区中，对以下关键字序列构G 造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec ） ， H(x)=i/2，其中i 为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。（6） 构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算
3、法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。15 分四、编写一非递归算法，对一棵二叉排序树实现中序遍历。15 分五、编写程序，完成下列功能：15 分1 读入整数序列，以整数0 作为序列的结束标志（0 不作为序列元素） ，建立一个单链表。2 实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 24 页 - - - - - -
4、 - - - 六、给出有向图G 的邻接表表示。找出其一棵最小生成树。11 分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 24 页 - - - - - - - - - 注：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：20分1、 算法的定义和性质2、 为什么说数组与广义表是线性表的推广？3、 什么是结构化程序设计？4、 哈希方法的基本思想5、 给出一不稳定排序方法名称与实例二、构造结果： 24分 （1） 确定 x:=x+1 语句在下面
5、程序段中的频率，要求写出分析过程。for i:=1 to n dofor j:=1 to I dofor k:=1 to j do x:=x+1（2） 画出对长度为 8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列（4） 假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为2 ，3，5，7，11，4，13，15 ，试为这 8 个字母设计哈夫曼编码（5） 在地址空间为015 的散列区中，对以下关键字序列构G 造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun
6、,Jul Aug,Sep,Oct,Nov,Dec ） ， H(x)=i/2，其中i 为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。（6） 构造有 7 个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。15 分四、编写一非递归算法，对一棵二叉排序树实现中序遍历。15 分五、编写程序，完成下列功能：15 分1 读入整数序列，以整数0 作为序列的结束标志（0 不作为序列元素） ，建立一个单链表。2 实现单链表原地逆转，即单链表中结点指针方向
7、反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 24 页 - - - - - - - - - 六、给出有向图G 的邻接表表示。找出其一棵最小生成树。11 分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 24 页 - - - - - - - - - 注 编写程序
8、可选用PASCAL 或 C 语言算法描述采用类语言，应加上必要的注释所有答案均要求写在答题纸上一、 回答问题15分1结构化程序设计2面向对象开发方法与面向过程开发方法的不同之处3数据类型含义与作用4稳定排序与不稳定排序二、简述方法与原因20分1分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。2实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法，若不能，请简述原因。3. 有 n 个非零的数， 仅要求将负数排列在正数的前面，但并不要求对其排序， 简述处理方法。4说明在图的遍历中，设置访问标志数组的
9、作用。5. 在一个连通无向图上，欲求从一点VI到另一点 VJ（VIVJ）所经结点数目最少的路径，在深度优先搜索、 广度优先搜索、 从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。三、构造结果25分1. 二叉树按二叉链表方式存放，其中的data 域为 char 类型，已有按前序方式构造二叉树的算法，若输入序列为AB CD ED G ，请给出构造的相应二叉树。2. 已知 Ackerman函数定义如下：n+1 当 m=0 时akm(m,n) = akm(m-1,1) 当 m 0,n=0时akm(m-1, akm(m,n-1)当 m 0,n0时名师资料总结 - -
10、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 24 页 - - - - - - - - - 写出 akm(2,1) 时调用时变化过程与执行结果。3. 对于正整数 A、B，说明下面程序段定义了什么函数功能，要求重写程序段，使之完成原函数功能，且执行时间仅可能短。Unsigned intf(a,b)inta,b;if(a*b=0)return(a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a 相当整除)4. 写出在中序线索树BT中找结点 X的后继结点的函数过程。5. 对
11、以下关键字序列建立哈希表 （jan,feb,mar,apr,may,jun,jul） ，哈希函数为H （K）=关键字中第一个字母在字母表中的序号）MOD 7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路， 用非递归形式写出算法。 10分1 一棵树采用孩子 -兄弟方式存放，结点结构为fchdatansiblevel其中 fch表示指向第一个孩子， nisib表示指向下一个兄弟,level表示结点层次。设
12、根结点层次为 1，其它以此类推，编写一算法，将树中所有结点层次值置入相应 level域。10分六、 以顺序存储结构表示串 , 设计算法 , 求串 S中出现的第一个最长重名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 24 页 - - - - - - - - - 复子串及其位置并分析算法的时间复杂度.10分七、 编写程序，要求完成：建立一个带头结点的线性链表，用以存放输入的二进制数， 链表中每个结点的 data 域存放一个二进制位。在此链表上实现对二进制数加1的运算，并输出
13、运算结果。10分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 24 页 - - - - - - - - - 注：编写程序可用PASCAL 或 C 语言；算法描述可采用类语言，加上必要注释；一、解释和简答下列问题：（20分）1） 算法的定义和特性2） 抽象数据类型3） 广义表与字符串属于线性表的理由4） 封装5） 排序算法的稳定性6） 结构化程序设计二、写出要求结果： （30分）1 已知一二叉树中序序列为DBGEAFC ， 后序序列为DGEBFCA ，给出其对应的二叉树。
14、2给定权值 8 ，12，4，5，26，16，9 ，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。1 有一线性表，要求重新排列，使所有的正数均在非正数之前，要求用最小交换次数实现，你认为应采用什么方法？4只想得到 N 个元素序列中第K 个最大元素之前的部分递减有序序列（KN ） ，列出 3种速度快的方法名称与原因。5 在 地 址 空 间 为 012 的 散 列 区 中 ， 对 以 下 关 键 字 序 列 建 哈 希 表 ：（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct ） 。用线性探测法处理冲突，求出在等概率的情况下查找成功与不成功的平均查找长度。6下面给出求
15、N 价 hanoi 塔的过程：PROCEDURE hanoi(n： integer；x,y,z：char)；beginif n=1 then move(x,1,z)elsehanoi(n-1,x,z,y) ；move(x,n,z)；hanoi(n-1,y,x,z)end请写出执行hanoi(3,a,b,c)时递归过程的实在参量变化过程及move 的搬动过程。三、数学归纳法证明非空满K 叉树的叶子结点数目为(K-1)N+1 ，其中 N 为分支结点数目。（10分）四、编写程序，判断一带头结点的双向链表是否对称，对称是指表中各元素满足ai=an-i+1结点结构为如下：(10分)nextdadapri
16、or五、有一个由英文书目构成的文件（书名不定长度，以“；”为分割符）；读入该文件，对这一书目单按字典排序，将结果以文件方式存储。编程实现之。（10分）六、二叉树按链表方式存放，且树中结点的关键字均不同。写一个判别给定二叉树是否为二叉排序树的非递归算法。（10分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 24 页 - - - - - - - - - 写一个算法， 确定一个N 个顶点的无向图是否包含回路，此算法的时间代价应为O （ N）（10分）名师资料总结 - - -
17、精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 24 页 - - - - - - - - - 注：编写程序可选用盘Pascal 或 C 语言，算法描述可选用类语言，必要时加上注释一、简答下列问题：1 结构化程序设计2 参数传递的常用方式及含义3 数据类型4 几种基本数据结构的名称及特征5 算法定义与性质6二、写出要求结果1 PROGRAM PF(OUTPUT);VER T,M:INTEGER;FUNCTIONF(N:INTEGER):INTEGER;BEGINM:=N+M;F:=MENDBEGI
18、NM:=10;T:=(M+1)*F(10);WRITELN(T);M:=10;T:=F(10)*(M+1);WRITELN(T);M:=10;T:=M*F(10)+F(10);WRITELN(T);END.写出程序输出结果，说明为什么T 的树出结果不同。2 有过程定义如下：PROCEDURE PRIT(N:INTEGER);BEGINVAR N1:INTEGER;N1:=TRUNC(N/10);TRUNC(x)表示取 x 的整数部分 S:=S*10+(N MOD 10);IF N10 THEN PRIT(N1);WRITELN(NMOD 10)END;问：置 S 初值为 0，用 PRIT（ 1
19、2345）调用此过程，写出打印结果；当执行完此次调用后， S值是多少？3给定一组权值（7，18，3，32，5，26，12，8） ，构造一棵哈夫曼树，并计算带权路径长度。4 将树转换成二叉树5 对给定以下关键字序列（Jan,Feb,Mar,Apr,May,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 24 页 - - - - - - - - - Jun,Jul,Aug） ，哈希函数H（ Key）为 Key 的第一字母表中序号 MOD 7，采用线性探测再散列方法处理冲突，
20、要求：构造一个装填因子为0.8的哈希表求出等概率情况下查找成功与查找不成功的平均查找长度6 在 m 行 n 列的稀疏矩阵中，有七个非零元素，若用十字链表表示，共需要多少个结点？三、编写一程序，要求打印以下的杨辉三角形（n 可设为 10） 10分11 11 2 1n行 1 3 3 11 4 6 4 11 5 10 10 5 12 1 6 15 20 15 1:四、一个数组中元素为正数或负数，编写一程序，完成在On 时间内原地重排数组，不要求整个排序，只要求负数排在正数之前。10分五、二叉树按二叉链表方式存放：编写统计任一二叉树中非终端结点数目的非递归算法10分编写求一二叉树高度的递归算法。5分六
21、、设有向图以邻接表方式存储，请利用队列技术编写一个判别图中是否存在由顶点Vi到顶点 Vj路径的算法。（其中 i j） 12分七、已知有如下单链表（a1,a2, ,an）,n 为偶数。要求写出一个时间复杂度为On ，辅助空间为O(1)的算法，将上述链表转换成：即（ an,an-2, a2,a1,a3, an-1）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 24 页 - - - - - - - - - 注：编写程序可选用任一种高级语言（C 或 PASCAL 等）一、简答
22、问题：15分1. 结构化程序设计；2. 简述面向对象开发方法的特点；3. 何谓程序中的千年虫问题，简述一种解决问题的方法；4. 给出抽象数据类型和特征，并举例说明；5. 简述广义表属于线性结构的理由。二、写出要求结果45分1. 有函数定义如下：FUNCTIONGC(M,N:INTEGER);INTEGERBEGINIF N=0 THEN GC:=MELSE GC:=GC(N ， M MOD N)END写出此函数功能，并改写它，使其执行速度仅可能地短。2. 设 T、M 为全程量，有函数定义如下：FUNCTIONFA(N:INTEGER) ：INTEGERBEGINM:=N+M;FA:=M;END
23、在主程序段中，有如下语句：M:=10;T:=(M+2)*FA(10);WRITELN(T);M:=10;T:=FA(10)*(M+2);WRITELN(T);写出程序输出结果，说明为什么T 的输出结果不同的原因。3. 对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT） ,哈希函数为H(K)=（关键字中第一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并分别计算出在等概率情况下查找成功与不成功的平均查找长度。4. 在数轴上有N 个彼此相邻不交的区间，每个区间的下界和上界都是整数。N 个区间顺序为 1N。要查找给
24、定的X 落入的区间号，你认为应怎样组织数据结构，选择什么方法最快，并简述原因5. 对 N 个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N 个元素的初始排列，对N=7，给出快速排序的一个最好情况的初始排列实例（7个元素可取自集合 1，2，3，4， 5，6，7 ） 。6. 在前序线索树上，要找出结点P 的直接后继结点，请写出相关语句。ltaglcdatartagrc7. 给出循环队列中元素个数的计算式（设队列的最大长度为N，队首指针FRONT，队尾指针为 REAR ） 。8. 有向图的拓扑排序能否用图的深度搜索模式来查找？若能，请简述方法，若不能，请简述原因。9. 写出三个形如A:
25、=B 的语句，完成将单链表LA 整表释放的功能，可利用链栈指针AV（即将 LA 表归还到可利用栈） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 24 页 - - - - - - - - - 三、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为AZ 这26个字母和 09这10个数字） 10分 四、已知两个线性表A、B，均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法，求出A 与 B 的交集 C，要求 C 另
26、开辟存储空间，要求C 同样以元素值的递增有序的单链表形式存贮。8分五、要求二叉树按二叉链表形式存储。（1） 写一个建立二叉树的算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 24 页 - - - - - - - - - 答案请答在答题纸上，答在本试题上的答案一律无效注 编写程序可选用PASCAL 或 C 语言算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上一、简答问题： 30分1结构化程序设计2面向对象程序设计与面向过程程序设计各自的特点与区别
27、3简述队列与广义表属于线性表的理由4简述不稳定排序含义、并给出证明某一种排序方法是不稳定的排序方法5函数的副作用二、选择题：20分1下面方法可以判断出一个有向图中是否有环（回路）A深度优先遍历B. 拓扑排序C.最短路径D.关键路径2. 已知一算术表达式的中缀形式为AB *C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为。A. A+B*C/DEB. A+B*CD/EC. -+*ABC/DE D.-+A*BC/DE3. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用 遍历方法最合适。A前序 B中序 C 后序D 按层次4. 排序趟数与序列的原始状态有关的排序方法是排序
28、法。A. 插入 B选择 C. 冒泡 D 快速5. 下面给出的四种排序法中排序法是不稳定性排序法。A插入B冒泡 C 二路归并D 堆6. 若需在 O （nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是:A快速排序B. 堆排序 C.归并排序D.直接插入排序7. 下述二叉树中，满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序A. 二叉排序树B. 哈夫曼树C. AVL树 D.堆8下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费时间反而最多。A、堆排序B、冒泡排序C 、快速排序D 、SHELL排序9设循环队列中数组的下标范围是1n，其头尾指针分
29、别为f ，r，若队列中元素个数为。A、r-fB 、r-f+1C 、 （r-f+1 ）mod n D 、 （r-f+n ）mod n10.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列A、存在 B、不存在三、写出要求结果： 50分1下列 C 与 PASCAL 函数的功能相同有如下 C 函数定义：有如下 PASCAL 过程定义：void bin(int b , int n) PROCEDURE bin（VAR b：array，n：integer）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
30、- - - - - - - 第 14 页，共 24 页 - - - - - - - - - BEGINif (n=1) b1=1; b2=1;if (n=1) b1=1; b2=1;else bin(b, n-1); else bin(b, n-1);bn+1=1; bn+1=1;For (i=n; i=2; i-) For i=n downto 2 dobi= bi+ bi-1 bi= bi+ bi-1 END若调用 bin(A, 5), 给出 A 数组中第 1个至第 6个数组元素的输出结果。2给出求 N阶 hanoi 塔的函数定义如下：hanoi(intn，char x,char y,ch
31、ar z) ； if(n=1)move(x,1,z)else hanoi(n-1,x,z,y)；move(x,n,z) ；hanoi(n-1,y,x,z)请写出执行 hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程。3已知一个循环单链表la,av是可利用栈的头指针， 请用3个赋值语句， 完成将整个循环单链表释放的功能（即将la 表整个归还到可用空间栈） 。4. 在 地 址 空 间 为 0-12 的 散 列 区 中 ， 对 以 下 关 键 字 序 列 ：（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct ）建哈希表，设哈希函数为H（X）=i/2，其中
32、 i 为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一， 要求构造哈希表， 并求出在等概率的情况下查找成功与不成功的平均查找长度。5在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助于一棵折半判定树来模拟，树中结点的值为记录在文件中的位置序号。 若文件中有 l7个记录，请画出这棵折半判定树； 当文件中有 n 个记录时，给出该判定树的深度。6设某城市有 N 个车站，并有 M 条公交线路连接这些车站，设这些公交车都是单向的，这 N 个车站顺序编号为 0至 N-1，要求输入该城市的公交线路数、车站个数以及各公交线路上各站编号，要求从站0出发乘公交车至站N
33、-1的最少换车次数，简述应如何设置数据结构、应当采用的基本处理方法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 24 页 - - - - - - - - - 7下图是带权的有向图 G的邻接表表示法。给出从结点V1到结点 V8的最短路径。8在后序线索树中，要找出X 结点的前趋结点，请写出相关语句LtagLcDataRtagRc四编写程序 ，实现在链式存储方式下的模式匹配。设主串 s和子串 t 分别以单链表存储， t 和 s 中每个字符均用一结点表示：dataNext实
34、现在链式存储方式下的模式匹配，即求子串t 在主串 s中第一次出现的位置指名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 24 页 - - - - - - - - - 针。12分五、编写算法：已知二叉树采用二叉链表方式存放，其中要求对二叉树从1开始进行连续编号，要求每个结点 v 的编号等于其左子树上最小编号加1，结点 v 的编号等于其右子树结点中最大编号加 1，请回答采用什么次序的遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。13分六
35、、编写算法：已知深度为 h 的二叉树采用顺序存储结构已存放于数组BT 1：2h1中，请写一算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为根结点所在链结点的指针由BT给出。13分七、编写程序：已知全省有 m个学生参加计算机等级考试， 其成绩值均为界于 0100之间的整数值，且成绩中有许多值重复出现多次，请按下列方法进行排序：另设数组num0:100 ，且令 numi 计算统计整数i 在成绩数组中重复出现的次数，之后按 num重排成绩数组，以达成绩数组递增有序。编写程序实现上述要求。12分（2） 写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K、具有 N 个结
36、点的二叉树的每一个结点都与深度为K的满二叉树中编号从1至 N 的结点一一对应（此题以此定义为准）。12分六、给定一公园的导游图，自给适当的数据结构，编写算法实现下列要求：游客从大门进入，选择一条最佳路线，使游客可以不重复的游览各景点，最后回到大门。 10分 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 24 页 - - - - - - - - - 答案请答在答题纸上，答在本试题上的答案一律无效注 编写程序可选用PASCAL 或 C 语言算法描述采用类语言，算法应加上必
37、要的注释，所有答案均要求写在答题纸上一、简答问题： 30分1结构化程序设计（目的、构成与方法）2简述栈、队列、串、数组的共同点和不同点，它们属于线性表原因3简述面向对象方法的特点4线性结构与非线性结构的差别5算法特性与算法时间复杂度二、选择题：20分1 已知一算术表达式的中缀形式为AB *C-D/E，后缀形式为 ABC*+DE/-，其前缀形式为( )。A. A+B*C/DEB. A+B*CD/EC.-+*ABC/DE D.-+A*BC/DE2 利用逐点插入法建立序列 (50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行（）元素间的比较。A4次
38、B5次 C. 7次 D 10次3在有 n 个叶子结点的哈夫曼树中，其结点总数为( ) 。A、不确定B、2n C 、2n+1 D 、2n-14 若需在 O （nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是:A快速排序B.堆排序 C.归并排序D.直接插入排序5若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )A. 存在 B. 不存在6 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是( )A. n B. 2n1 C. 2n D. n-17 下述二叉树中， 哪一种满足性质： 从任一节点出发到根的路径上所经过的节点序列按其
39、关键字有序( )A.二叉排序树B. 哈夫曼树C. AVL树 D. 堆8 已知待排序的 n 个元素可分为 n/k 个组，每个组包含 k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为()A. O （nlog2n） B. O(nlog2k)C. O(klog2n)D. O(klog2k)9数组 A1.5,1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A5，5 的地址是( )。A、1140 B、1145 C 、1120 D 、112510. 在有 n 个叶子结点的哈夫曼树中，其结点总数为(
40、) 。A、不确定B、2n C 、2n+1 D 、2n-1三、写出要求结果： 50分1下列 C 与 PASCAL 函数的功能相同有 C 函数定义如下：有 PASCAL 过程定义如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 24 页 - - - - - - - - - int gc(:int m, n) FUNCTION GC(M,N:INTEGER);INTEGER BEGINif (n=0 ) return(m); I F N=0 THEN GC:=Melser
41、etun (n，m /n); ELSE GC:=GC(N ，M MOD N) END写出此函数功能，并改写它，使其执行速度仅可能的短。2给出求 N阶 hanoi 塔的函数定义如下：hanoi(intn，charx,chary,charz) ； if(n=1)move(x,1,z)else hanoi(n-1,x,z,y)；move(x,n,z) ；hanoi(n-1,y,x,z)；请写出执行 hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程。3在前序线索树中，要找出X结点的后继结点，请写出相关语句LtagLcDataRtagRc4一棵非空的二叉树其前序序列与后序序列正好
42、相反，给出满足条件的二叉树。5在数轴上有 n 个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1N。试问：要查找某个给定值x 所在区间，你认为应选择什么方法查找最快，简述原因。6已知关键字序列为：（ 75, 33, 52, 41, 12, 88, 66, 27 ）哈希表长为10 ，哈希函数为：H(K)=K MOD7, 解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。7只想得到 N个元素序列中第 K个最大元素之前的部分递减有序序列（Kn ），统计其中 1-n中各个数值个数到C数组（2） 将数组 C1:n 中所有奇数移到偶数之前
43、，要求时间复杂度为O(n)。8 分四、编写一程序，将一个循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅含奇次项或偶数项，并要求利用原链表中的结点空间来构成这两个链表。8 分五、棵树采用孩子 - 兄弟方式存放，结点结构为fchdatansiblevel其中 fch表示指向第一个孩子， nisib表示指向下一个兄弟,level表示结点层次。设根结点层次为 1， 其它以此类推， 编写一算法， 将树中所有结点层次值置入相应level域。8 分六、一棵二叉树的内部路径长度等于从树根到每个结点路径长度之和，二叉树用二叉链表存放，请用递归算法，编写一个二叉树内部路径长度算法。8 分七、一棵二
44、叉树用二叉链表存放，且二叉树中结点各不相同。编写一算法，查找数据域为x 的结点，并打印输出值为x 结点的所有祖先。 8 分八、 有 NN 个元素 （N=2m）构成的二维阵列，将其转换成一个四叉树表示，转换原则如下：将阵列4等分为四个子区域，做为四叉树的四个分支，若该子区域所有元素值均为0或均为 1，则对应的四叉树为叶子结点，填值为1或0；若该子区域值不一致，则对该区域可再划分，形成下一层的子树，递归重复，直到每个子区域对应相应叶结点或到达元素这一级为止。要求：写出从二维阵列转换生成四叉树的算法基本思路，再给出从二维阵列转换生成四叉树的算法。 7 分名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 24 页 - - - - - - - - -