目录
一、简答题（每题6分，共60分）
二、程序阅读及分析题(6小题，每小题10分，共60分)
三、算法设计题（10*3=30分）
一、简答题（每题6分，共60分）
1、若需要频繁地对一个线性表的数据进行插入和删除操作，从算法的效率来分析适合采用何种存储结构?
2、请简述顺序存储结构的优点和不足。
3、设有4个元素，入栈的次序为: A、B、C、D,问以B第一个出栈的序列有哪些情况?
4、在线性表的单链表和单循环链表存储结构中，若仅知道指向结点A的指针P，能否删除结点A?为什么?
5、求含有n个结点采用顺序存储的完全二叉树中的第一个叶子结点的编号，要求简单步骤。
6、简述C语言变量的静态存储方式和动态存储方式的区别。
7、简述C语言采用寄存器变量的优势。
8、含n个结点的三次树最小高度是多少?最大高度是多少?
9、计算算法中基本语句(有下画线)的执行次数，并分析时间复杂度。
void func(int n){
int i = 0, s = 0;
while (i
10、对线性表进行二分查找时，要求线性表必须以顺序方式存储且结点关键
字有序排序，这种说法对吗?为什么?
二、程序阅读及分析题(6小题，每小题10分，共60分)
1、阅读单链表算法，指出算法的功能并分析算法的时间复杂度。
int TTT(linklist *L, int e)
{
linkList *p = L->next;
int n = 1;
while (p != NULL && p->data != e)
{
p = p->next;
n++;
}
if (p == NULL)
return (0);
else
return (n);
}
2、阅读顺序表算法，指出算法的功能并分析算法的时间复杂度。
void BBB(SqList *&L, int a[], int n)
{
int i;
L = (SqList *)malloc(sizeof(SqList));
for (i = 0; i < n; i++)
L->data[i] = a[i];
L->Length = n;
}
3、已知某二叉树的中序序列为CBDAFEG,后序序列为CDBFGEA.
- 构造出这棵二叉树;
- 请给出该二叉树的先序序列。
4、假设用于某通讯的电文仅由6个字符{a,b,c,d,e, f}组成，各个字母在电
文中出现的次数分别为{5，20，10, 6, 36, 15}。要求:
- 构造出相应的Huffman树(约定左子树的权值小于右树的权值);
- 为这6个字符设计不等长的Huffman编码(约定左为0右为1)。
5、已知序列{35, 7, 6, 15， 19, 3,11},给出采用直接插入排序时每一趟的
示意图。
6、设有关键码序列(15, 22, 3, 55，60, 70, 80, 21)，采用除留余数法构
造哈希表，哈希函数为H(key)=key%11。
(1)若采用线性探查法解决冲突，请分配每个关键码在哈希表中位置。
存放地址 0 1 2 3 4 5 6 7 8 9 10 关键码
(2)计算哈希表在等概率下查找成功时的平均查找长度。
三、算法设计题（10*3=30分）
1.设有一个任意的字符串序列。存储在文本文件中，编写算法实现判断该字
符串序列是否对称。
- 描述算法的实现思路，包括存储结构的设计。
- 用C语言实现该算法。
2、已知长度为n的线性表，数据为整型，设计算法删除线性表中所有值为
item的数据元素
要求:
- 设计合适的存储结构，描述算法的实现思路，并分析算法的时间复杂度。
- 用C语言实现该算法。
3.设计一个算法求完全二叉树中指定结点的层数，即对用户输入的任何结点
值x计算出该结点在完全二叉树中的层次，定义空树的层次为0。
- 设计合适的存储结构，并描述算法的实现思路。
- 用C语言实现该算法。
