当前位置：问答库＞考研试题

一、算法设计题

1． 设要求按

是一个记录构成的数组，

是一个整数数组，其值介于1〜100之间，现

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

2． 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”) ，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如:

若输入“ABCD12321DCBA”是回文，则输出“Yes”； 若输入“ABCD123DCBA”，不是回文，则输出“NO”。

要求:定义相关数据类型，不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。

【答案】算法如下:

//本算法判断数据域为字符且长为n 的单链表是否是”回文" ，返回1或0表示成功或失败

//字符栈，容量足够大

//设链表带头结点

//前一半字符入栈，链表指针后移

//若链表有奇数个结点，则跳过中间结点

//不是回文

3． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:

它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。

【答案】算法如下:

//输出由Hm 指向的十字链表中每一行的非零元素个数

//数组A 记各行非零元个数，i 记行号

//循环完各行列表头

//P是稀疏矩阵行内工作指针，num 记该行非零个

数

//完成行内非零元的查找

//指针后移

//存该行非零元个数

//移到下一行列表头

//输出各行非零元个数

第

}算法结束

行非零元个数为

}

//稀疏矩阵非零元个数

4． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？

【答案】算法如下:

关键字

链指针

用链地址法解决冲突，构造哈希表，哈希函数用

初始化

输入n(本例中n=9)

个关键字按题意x 互不相同

4等插入结点链入同义词表

构造的哈希表如图所示:

图构造的哈希表

查找成功时的平均查找长度

。

5． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。

【答案】算法如下: