Jun,Jul,Aug），哈希函数H（Key）为Key的第一字母
表中序号MOD 7，采用线性探测再散列方法处理冲突， 要求：①构造一个装填因子为0.8的哈希表
②求出等概率情况下查找成功与查找不成功的平均查找长度 6． 在m行n列的稀疏矩阵中，有七个非零元素，若用十字链 表表示，共需要多少个结点？
三、编写一程序，要求打印以下的杨辉三角形（n可设为10） [10分]
1
1 1
1 2 1
n行 1 3 3 1
1 4 6 4 1 1 5 10 10 5 1
2 1 6 15 20 15 1 :
四、一个数组中元素为正数或负数，编写一程序，完成在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. 简述广义表属于线性结构的理由。
二、写出要求结果[45分]
1. 有函数定义如下：
FUNCTION GC(M,N:INTEGER);INTEGER BEGIN
IF N=0 THEN GC:=M
ELSE GC:=GC(N，M MOD N)
END
写出此函数功能，并改写它，使其执行速度仅可能地短。 2. 设T、M为全程量，有函数定义如下：
FUNCTION FA(N:INTEGER)：INTEGER
BEGIN
M:=N+M;FA:=M;
END
在主程序段中，有如下语句：
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个区间
顺序为1~N。要查找给定的X落入的区间号，你认为应怎样组织数据结构，选择什么方法最快，并简述原因
5. 对N个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N个元素
的初始排列，对N=7，给出快速排序的一个最好情况的初始排列实例（7个元素可取自集合{1，2，3，4，5，6，7}）。
6. 在前序线索树上，要找出结点P的直接后继结点，请写出相关语句。
ltag lc data rtag rc 7. 给出循环队列中元素个数的计算式（设队列的最大长度为N，队首指针FRONT，队
尾指针为REAR）。
8. 有向图的拓扑排序能否用图的深度搜索模式来查找？若能，请简述方法，若不能，请简述原因。
9. 写出三个形如A:=B的语句，完成将单链表LA整表释放的功能，可利用链栈指针
AV（即将LA表归还到可利用栈）。
三、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A~Z这26个字母和0~9这10个数字）[10分]
四、已知两个线性表A、B，均以带头结点的单链表作存储结构，且表中元素按值递增有序
排列。设计算法，求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增有序的单链表形式存贮。[8分] 五、要求二叉树按二叉链表形式存储。
（1） 写一个建立二叉树的算法。
答案请答在答题纸上，答在本试题上的答案一律无效
[注] 编写程序可选用PASCAL 或 C 语言
算法描述采用类语言，算法应加上必要的注释，所有答案均要求写在答题纸上
一、简答问题：[30分]
1．结构化程序设计
2．面向对象程序设计与面向过程程序设计各自的特点与区别 3．简述队列与广义表属于线性表的理由
4．简述不稳定排序含义、并给出证明某一种排序方法是不稳定的排序方法 5．函数的副作用
二、选择题： [20分]
1．下面 方法可以判断出一个有向图中是否有环（回路） A．深度优先遍历 B. 拓扑排序 C.最短路径 D.关键路径
2. 已知一算术表达式的中缀形式为A＋B *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为 。
A. –A+B*C/DE B. –A+B*CD/E C. -+*ABC/DE D.-+A*BC/DE
3. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用 遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次
4. 排序趟数与序列的原始状态有关的排序方法是 排序法。 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．设循环队列中数组的下标范围是1~n，其头尾指针分别为f，r，若队列中元素个数为 。
A、r-f B 、r-f+1 C、（r-f+1）mod n D、（r-f+n）mod n
10.若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列
A、存在 B、不存在
三、写出要求结果：[50分]
1． 下列C与PASCAL函数的功能相同
有如下C函数定义： 有如下PASCAL过程定义：
void bin(int b[ ], int n) PROCEDURE bin（VAR b：array，n：integer）
{ BEGIN
if (n==1) {b[1]=1; b[2]=1;} if (n==1) {b[1]=1; b[2]=1;} else { bin(b, n-1); else { bin(b, n-1);
b[n+1]=1; b[n+1]=1;
For (i=n; i>=2; i--) For i=n downto 2 do
b[i]= b[i]+ b[i-1] b[i]= b[i]+ b[i-1] } } END
若调用bin(A, 5), 给出A数组中第1个至第6个数组元素的输出结果。
2．给出求N阶hanoi塔的函数定义如下：
hanoi(int n，char x, char y, char 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，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。
5．在排序连续顺序文件中采用折半查找方法查找记录存在与否的过程可以借助
于一棵折半判定树来模拟，树中结点的值为记录在文件中的位置序号。
① 若文件中有l 7个记录，请画出这棵折半判定树； ② 当文件中有n个记录时，给出该判定树的深度。
6．设某城市有N个车站，并有M条公交线路连接这些车站，设这些公交车都是
单向的，这N个车站顺序编号为0至N-1，要求输入该城市的公交线路数、车站个数以及各公交线路上各站编号，要求从站0出发乘公交车至站N-1的最少换车次数，简述应如何设置数据结构、应当采用的基本处理方法。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构精选考研试题(3)在线全文阅读。
相关推荐：