2013年试题（A卷）

1、当为解决问题设计算法而选择数据结构时，应重点从那些方面考虑?
2、在编制通讯录管理系统时，如何设计数据的存储结构并解释为什么?
3、一组含权植不同的字母已对应好Huffman编码，如果某一字母对应的编码为001101,请问什么形式的编码不可能是该编码集合中的合法编码(可以采用? *等通配符号) ?
4、在单链表和双向循环链表中，若仅知指向结点A的指针P,问能否访问到结点A的直接前驱结点?为什么?
5、设数据存储在数组中，问下面的哪个操作适合预先进行排序处理?为什么? (1) 找最大(最小)值; (2) 计算算术平均值; (3) 找出现次数最多的值。.
6、举例说明什么是顺序队列的假溢出现象?解决假溢出的方法有哪些?
7、根据数据的组织形式，数据文件分为哪两类?
8、简述C语言中局部变量和全局变量的区别。
9、在二叉树的先序遍历序列中，任何一个结点均在其孩子结点的前面，这种说法对吗?为什么?
10、计算算法中基本语句执行(有下画线)的次数并分析算法的时间复杂度。

1、阅读顺序表的算法，指出算法的功能并分析算法的时间复杂度。

int TTT(Sqlist *&L, int i, int &e)
{
    int j;
    if (i > 1 || i > L->length)
        return 0;
    i--;
    e = L->data[i];
    for (j = 1; j < L->length - 1; j++)
        L->data[j] = L->data[j + 1];
    L->length--;
    return 1;
}

2、阅读单链表的算法,指出算法的功能并分析实现该算法的效率能否提高到O(1)?

int AAA(linkList *L)
{
    linklist *p = L;
    int i = 0;
    while (p->next != NULL)
    {
        i++;
        p = p->next;
    }
    return (i);
}

3、请分析图A和图B数据组织的特点和主要用途。

 4、设给定的叶结点的权值集合为W={2, 5, 6, 9, 11},请构造出关于W的Huffman
树(约定左子树的权值小于右子树的权值)，并计算其带权路径长度WPL。

5、已知一个有序表(8, 9, 13, 20， 33, 38， 48, 51, 56, 77, 83)顺序存
储于一维数组B[11]中。

1. 计算折半查找下列数据元素时的查找次数(38 的查找次数已给出)。
2. 分析折半查找算法能提高查找效率的原因。

6、已知序列{88, 5, 26, 1, 49, 66},给出采用冒泡排序时每一*趟的示意图。

1、用一个整型数组S (设大小为MAX) 作为两个栈的共享空间。
要求:

1. 说明共享的方法以及栈满、栈空的条件。
2. 用C语言实现公共的入栈操作push (I,X) ,I 为0号栈或1号栈，X为入栈的值。

2、设有一个任意的整数序列，存储在文本文件data. txt中，数据间用空格间隔，编写算法实现将data. txt中的数据按递增排序并将结果写入文件out. txt中。

1. 描述算法的实现思路，包括存储结构的设计:
2. 用C语言实现该算法。

3、设计一个算法实现判断两棵完全二叉树是否相等，所谓二叉树a和b相等是指其对应子树的值都相等。

1. 设计完全二叉树的存储结构，并简述算法的实现思路;
2. 用C语言实现该算法。