搜索
[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分]1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？3、什么是结构化程序设计？4、哈希方法的基本思想5、给出一不稳定排序方法名称与实例二、构造结果：[24分]（1）确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。fori:=1tondoforj:=1toIdofork:=1tojdox:=x+1（2）画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。（3）已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．（4）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．（5）在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar,Apr,May,Jun,JulAug,Sep,Oct,Nov,Dec），H(x)=[i/2]，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。（6）构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分]四、编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分]五、编写程序，完成下列功能：[15分]1．读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0六、给出有向图G的邻接表表示。找出其一棵最小生成树。[11分][注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释一、回答下列问题：[20分]1、算法的定义和性质2、为什么说数组与广义表是线性表的推广？3、什么是结构化程序设计？4、哈希方法的基本思想5、给出一不稳定排序方法名称与实例二、构造结果：[24分]（1）确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。fori:=1tondoforj:=1toIdofork:=1tojdox:=x+1（2）画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。（3）已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．（4）假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．（5）在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar,Apr,May,Jun,JulAug,Sep,Oct,Nov,Dec），H(x)=[i/2]，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。（6）构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。三、写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分]四、编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分]五、编写程序，完成下列功能：[15分]1．读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。2．实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。例：输入序列为：1，8，4，3，0六、给出有向图G的邻接表表示。找出其一棵最小生成树。[11分][注]编写程序可选用PASCAL或C语言算法描述采用类语言，应加上必要的注释所有答案均要求写在答题纸上一、回答问题[15分]1．结构化程序设计2．面向对象开发方法与面向过程开发方法的不同之处3．数据类型含义与作用4．稳定排序与不稳定排序二、简述方法与原因[20分]1．分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。2．实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法，若不能，请简述原因。3.有n个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简述处理方法。4．说明在图的遍历中，设置访问标志数组的作用。5.在一个连通无向图上，欲求从一点VI到另一点VJ（VI≠VJ）所经结点数目最少的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。三、构造结果[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,n≠0时写出akm(2,1)时调用时变化过程与执行结果。3.对于正整数A、B，说明下面程序段定义了什么函数功能，要求重写程序段，使之完成原函数功能，且执行时间仅可能短。Unsignedintf(a,b)inta,b;{if(a*b==0)return(a+b)elsereturn(f(b-(b/a)*a,a);(注：b/a相当整除)}4.写出在中序线索树BT中找结点X的后继结点的函数过程。5.对以下关键字序列建立哈希表（jan,feb,mar,apr,may,jun,jul），哈希函数为H（K）=关键字中第一个字母在字母表中的序号）MOD7，用线性探测再散列法或链地址法之一处理冲突，要求构造一个装填因子为0.7的哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。四、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。[10分]1．一棵树采用孩子-兄弟方式存放，结点结构为fchdatansiblevel其中fch表示指向第一个孩子，nisib表示指向下一个兄弟,level表示结点层次。设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域。[10分]六、以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度.[10分]七、编写程序，要求完成：建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。在此链表上实现对二进制数加1的运算，并输出运算结果。[10分][注]：编写程序可用PASCAL或C语言；算法描述可采用类语言，加上必要注释；一、解释和简答下列问题：（20分）1）算法的定义和特性2）抽象数据类型3）广义表与字符串属于线性表的理由4）封装5）排序算法的稳定性6）结构化程序设计二、写出要求结果：（30分）1．已知一二叉树中序序列为DBGEAFC，后序序列为DGEBFCA，给出其对应的二叉树。2．给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。1．有一线性表，要求重新排列，使所有的正数均在非正数之前，要求用最小交换次数实现，你认为应采用什么方法？4．只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（KN），列出3种速度快的方法名称与原因。5．在地址空间为0~12的散列区中，对以下关键字序列建哈希表：（Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct）。用线性探测法处理冲突，求出在等概率的情况下查找成功与不成功的平均查找长度。6．下面给出求N价hanoi塔的过程：PROCEDUREhanoi(n：integer；x,y,z：char)；beginifn=1thenmove(x,1,z)else[hanoi(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分)nextdadaprior五、有一个由英文书目构成的文件（书名不定长度，以“；”为分割符）；读入该文件，对这一书目单按字典排序，将结果以文件方式存储。编程实现之。（10分）六、二叉树按链表方式存放，且树中结点的关键字均不同。写一个判别给定二叉树是否为二叉排序树的非递归算法。（10分）写一个算法，确定一个N个顶点的无向图是否包含回路，此算法的时间代价应为O（N）（10分）[注]：编写程序可选用盘Pascal或C语言，算法描述可选用类语言，必要时加上注释一、简答下列问题：1．结构化程序设计2．参数传递的常用方式及含义3．数据类型4．几种基本数据结构的名称及特征5．算法定义与性质6．二、写出要求结果1．PROGRAMPF(OUTPUT);VERT,M:INTEGER;FUNCTIONF(N:INTEGER):INTEGER;BEGINM:=N+M;F:=MENDBEGINM:=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．有过程定义如下：PROCEDUREPRIT(N:INTEGER);BEGINVARN1:INTEGER;N1:=TRUNC(N/10);{TRUNC(x)表示取x的整数部分}S:=S*10+(NMOD10);IFN10THENPRIT(N1);WRITELN(NMOD10)END;问：置S初值为0，用PRIT（12345）调用此过程，写出打印结果；当执行完此次调用后，S值是多少？3．给定一组权值（7，18，3，32，5，26，12，8），构造一棵哈夫曼树，并计算带权路径长度。4．将树转换成二叉树5．对给定以下关键字序列（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug），哈希函数H（Key）为Key的第一字母表中序号MOD7，采用线性探测再散列方法处理冲突，要求：①构造一个装填因子为0.8的哈希表②求出等概率情况下查找成功与查找不成功的平均查找长度6．在m行n列的稀疏矩阵中，有七个非零元素，若用十字链表表示，共需要多少个结点？三、编写一程序，要求打印以下的杨辉三角形（n可设为10）[10分]111121n行133114641151010512161520151:四、一个数组中元素为正数或负数，编写一程序，完成在O[n]时间内原地重排数组，不要求整个排序，只要求负数排在正数之前。[10分]五、二叉树按二叉链表方式存放：①编写统计任一二叉树中非终端结点数目的非递归算法[10分]②编写求一二叉树高度的递归算法。[5分]六、设有向图以邻接表方式存储，请利用队列技术编写一个判别图中是否存在由顶点Vi到顶点Vj路径的算法。（其中i≠j）[12分]七、已知有如下单链表（a1,a2,……,an）,n为偶数。要求写出一个时间复杂度为O[n]，辅助空间为O(1)的算法，将上述链表转换成：即（an,an-2,……a2,a1,a3,……an-1）[注]：编写程序可选用任一种高级语言（C或PASCAL等）一、简答问题：[15分]1.结构化程序设计；2.简述面向对象开发方法的特点；3.何谓程序中的千年虫问题，简述一种解决问题的方法；4.给出抽象数据类型和特征，并举例说明；5.简