中山大学 2014 年913专业基础（数据结构）考研真题

                     

贡献者： xzllxls

　　 声明：“该内容来源于网络公开资料，不保证真实性，如有侵权请联系管理员”

1. 一、单项选择题(每题 2 分，共 40 分)

　　 1.算法复杂度通常是表达算法在最坏情况下所需要的计算量。一般不用来表达算法复杂度的表达式为( )。
(A). $O(n^2)$ $\qquad$ (B). $O(100)$
(C). $O(nlogn)$ $\qquad$ (D). $O(1.5^2)$

　　 2.数据结构有四类基本结构，不是其四类结构之一的是( )。
(A).集合 $\qquad$ (B).线性结构
(C).存储结构 $\qquad$ (D).树形结构

　　 3.在存储信息过程中，通过对关键字的计算来确定其存储位置的数据结构是( )。
(A). Hash 表 $\qquad$ (B).二叉搜索树
(C).链式结构 $\qquad$ (D).顺序结构

　　 4.有关单向链表的正确描述是( )。
(A).在 0(1)时间内找到指定的关键字
(B).在插入和删除操作时无需移动链表结点
(C).在 0(1)时间内删除指定的关键字
(D).单向链表的存储效率高于数组的存储效率

　　 5.假设 Head 是不带头结点的双向循环链的头结点指针。判断链表为空的条件是( )。
(A). Head = NULL
(B). Head->next == Head
(C). Head.next = NULL
(D). Head->next = NULL

　　 6.在下列关于 “字符串” 的陈述中，正确的描述是( )。
(A).字符串- -定有一个结束符
(B).字符串只能用连续存储空间来存储
(C).“空串” 与 “空白串"是同一个含义
(D).字符串是一种特殊的线性表

　　 7.关于队列的不正确描述是( )。
(A).FIFO
(B).可用链表实现动态队列
(C).可访问队列中任何元素
(D).可用动态连续存储空间实现动态队列

　　 8.假设循环队列的长度为 QSize,其头、尾下标分别为 Front 和 Rear。在队列不满的情况下，“入队” 后相应下标变化的语句为( )。
(A). Rear=Rear+1 (B). Rear=(Rear+1)%Qsize
(C). Front=Front+1
(D). Front=(Front+1)%QSize

　　 9.用链表来实现堆栈，next 是链表结点中的指针字段，Top 为栈顶指针。在确定堆栈非空的情况下，出栈的语句是( ), 其中:所有变量都合法定义了，fee(Poin)是释 放指针 Point 所指向的存储空间。
(A). Top = Top->next;
(B). fe(Top); Top = Top->next;
(C). Top = Top->next; fee(Top);
(D). Pt=Top; Top= Top->next; fee(P);

　　 10.设 A[10][10]为一个对称矩阵，数组下标从[0][0]开始。为了节省存储，将其下三角部分按行存放在一维数组 B[0..54]。B[40]所对应的数组元素( )。
(A). A[3][8]
(B). A[2][8]
(C). A[3][7]
(D). A[2][7]

　　 11.若一棵二叉树的后序和中序序列分别是 dfebca 和 dabfeac,则其先序序列是( )。
(A). abdfec
(B). abdefe
(C). acbdef
(D). acbefd

　　 12.用一维数组来存储满二叉树，若数组下标从 0 开始，则元素下标为 K(k20)的左子结点下标是()C 不考虑数组 下标越界问题)。
(A). $2k-1$
(B). $2k$
(C). $2k+1$
(D). $2k+2$

　　 13.假设 $T_L$ 和 $T_R$ 是二叉搜索树 T 的左右子树，$H(D)$ 表示树 $T$ 的高度。若树 $T$ 是 $AVL$ 树，则( )。
(A). $H(T_L)-H(T_R)=0$
(B). $H(T_L)-H(T_R)=1$
(C). $H(T_L)-H(T_R)\leqslant1$
(D). $|H(T_L)-H(T_R)|\leqslant1$

　　 14.用邻接矩阵存储有 $n$ 个顶点 $(0,..-1)$ 和 $e$ 条边的无向图 $(0\leqslant e\leqslant(n-1)/2)$。在图中没有无向边 $(i,j)(0\leqslant i,j\leqslant n-1)$ 的情况下，增加此边后，修改邻接矩阵的时间复杂度是( )。
(A). $O(1)$
(B). $O(m)$
(C). $O(e)$
(D). $O(n+e)$

　　 15.用邻接矩阵存储有 $n$ 个顶点 $(0,1,...,-1)$ 和 e 条边的有向图 $(0\leqslant e\leqslant n(n-1))$。计算结点 $i(0\leqslant i\leqslant n-1)$ 入度的时间复杂度是( )。
(A). $O(1)$
(B). $O(m)$
(C). $O(e)$
(D). $O(n+e)$

　　 16.下列排序算法中，时间复杂度最差的是( )。
(A).选择排序
(B).归并排序
(C).快速排序
(D).堆排序

　　 17.对 $n$ 个数进行排序时，对基于比较的排序算法，其时间复杂度下界为( )。
(A). $O(n^2)$
(B). $O(logn)$
(C). $O(nlogn)$
(D). $O(n)$

　　 18.用基数(桶)排序算法对仅由字母和数字组成字符串进行排序(不区分字母大小写)时，需要桶的个数是( )。
(A). 10
(B). 26
(C). 36
(D). 62

　　 19.假设有 $n$ 个无序关键字，有关其查找算法的不正确描述是( )。
(A).关键字可存储在数组中
(C).关键字可存储在单向链表中
(C).最坏搜索效率为 $O(n)$
(D).平均搜索效率为 $O(logn)$

　　 20. 在下列算法中，求连通图的最小生成树算法是( )。
(A). $DFS$ 算法
(B). $KMP$ 算法
(C). $Dijkstra$ 算法
(D). $Kruskal$ 算法

2. 二、解答题(每题 10 分，共 50 分)

　　 1.已知一个无向图的顶点集为 ${1,2,3,4,5,6,7}$，其邻接矩阵如下所示(0-无边,1-有边)。

　　 (1).画出该图的图形;
(2).根据邻接矩阵从顶点 4 出发进行宽度优先遍历(同一个结点的邻接结点按结点编号的大小为序)，画出相应的宽度优先遍历树。

　　 2.简单描述求图最小生成树的 Prim 算法(普里姆算法)的基本思想，并按算法步骤从结点 $D$ 开始，列出图 $2$ 的最小生成树的求解过程。

　　 3.简单叙述合并排序算法(Merge Sort)的基本 思想。按递增顺序对下面所给数值进行排序，并按步骤列出每步排序后的数值序列。假设在排序过程需要划分时，用函数"$\lfloor x \rfloor$"来处理。
待排序的数值序列: 87 56 10 23 44 83 72

　　 4.己知有下列 13 个元素的散列表:

　　 其散列函数为 h(key) = (3key + 5) % m(m=13),处理冲突的方法为线性探测再散列法，探查序 列为: h=(h(key)+d)%m，d= 1,2,3, ... m-1。
问:在表中对关键字 50 和 56 进行查找时，所需进行的比较次数为多少?依次写出每次计算公式和值。

　　 5. 假设在通信中，字符 a, b,c,d, e,f,g 出现的频率如下:
a: 10% $\qquad$ b: 12% $\qquad$ c:7% $\qquad$ d: 21% $\qquad$ e:9% $\qquad$ f 28% $\qquad$ g: 13%
(1)根据 Huffrman 算法(赫夫曼算法)画出其赫夫曼树:
(2)给出每个字母所对应的赫夫曼编码，规定:结点左分支边上标 0，右分支边上标 1;
(3)计算其加权路径的长度 WPL.

3. 三、阅读理解题，按空白编号填写相应的 C/C++语言语句，以实现函数功能。(每空 2 分，每题 10 分，共 30 分)

　　 1.假设定义了下面的链式堆栈类，试编写相关成员函数。

struct Node {
    int key;
    Node *next;
    
public:
    Node() { next = NULL; };
};

class Stack {
public:
    Stack0 { Top= NULL;};
    ~Stack0,
    bool Push(const int &key);
    bool Empty() { returm (Top=-NULD); };
    ...
    
private:
    Node *Top;
};

(1)成员函数 Push(const int &key): 若申请不到存储空间，返回 false, 否则，把参数 key 压进堆栈，并返回 true.

bool Stack:Push(const int &key)
{
    Node *Pt = new Node();
    if(__ (1)____ ) return false;
    Pt->key= key;
    ____(2)____;
    ____(3)____;
    return true;
}

(2)析构函数-Stack():释放堆栈所用的所有存储空间。

Stack:~Stack()
{
    Node *Pt;
    while(___(4)___ ){
        Pt=Top;
        ____(5)____ ;
        delete Pt;
    }
}

2.假设用不带头结点的单向链表存储一-元多项式，并按指数有序存储(从大到小)。其链表结点的结构定义如下:

typedef struct_PNode {
    int Coef;  // 系数
    int Expn;  // 指数(规定:指数>=0)
    struct_PNode *next;
} PNode;

(1)函数 PNode *Copy(PNode *P1):把 P1 指向的多项式复制一份，并返回新多项式的首地址(不考虑申请结点内存失败的情况)。

PNode *Copy(PNode *P1)
{
    PNode *Head, *Pt1, *Pt2;
    Head = NULL;
    while (P1 != NULL) {
        Ptl = (PNode *) clloc(1, sizeof(PNode);
        Pt1-> Coef= P1->Coef;
        Ptl> Expn= PI->Expn;
        if(___ (1)____ ) Head = Pt1;
        else Pt2->next= Ptl;
        ____(2)____;
        P1 = P1->next;
    }
    ____(3)____;
}

(2)函数 Time(PNode *P1, PNode P2):计算多项式 P1←P1$\times$P2,其中: P2 是一个多项式结点。运算过程中，不考虑数值的溢出问题。

void Time(PNode *P1, PNode P2)
{
    PNode *Pt;
    for (Pt= P1; Pt!= NULL; Pt= Pt->next) {
        ____(4)____;
        ____(5)____;
    }
}

假设: PI 是多项式"$3x^5-2x^3+x^2-10$” 的首地址，P2=(-4,2), 即: P2 为 $-4x^2$.执行 Time(P1, P2)后，P1 指向的多项式为: $-12x^2+8x^5-4x^4+40x^2$.

　　 3.假设二叉树 $T=< T_L, root_s, T_R>$ 中叶子数的定义如下:
$Leaves(T)= \left\{\begin{aligned} &0, & T\text{是空树} \\ &1, & T\text{的根结点是叶结点} \\ & Leaves(T_L), Leaves(T_R)) & \text{其他} \end{aligned}\right. $

typedef struct_ BinNode {
int key;
struct_ BinNode *LChild, *RChild;
} BinNode;

(1)函数 Leaves(root)是求以结点 root 为根的二叉树中的叶子数。

int Leaves(BinNode *root)
{
    if( root == NULL ) return 0;
    if(____(1)____) return 1;
    return(____(2)____);
}

(2)函数 PostOrder(root)是后序遍历以结点 root 为根的二叉树。

void PostOrder(BinNode *root)
{
    if(__ (3)___ ){
        ____(4)____;
        ____(5)____;
        printf("Key: %d\n", root->key);
    }
}

4. 四、算法设计题(每题 15 分，共 30 分)

　　 用 C/C++语言实现下面函数的功能。
1.假设用链表存储集合，空链表示空集。存储集合的链表结点定义如下:

typedef struct_Element {
    int element; // 集合元素
    struct_Element *next;
} Element;    // 集合的结点定义

例如: A={11,22}，B=。这些集合的存储链表如下图所示。

　　 (1) Element *Union(Elerment *A, Element *B)，其功能是生成集合 A 和 B 的并集链表，返回并集链表的头指针(不考虑申请结点失败的情况)。(10 分)
(2) void Display(char *Name, Element *A),其功能是显示集合 A 中的元素列表，其中: Name 是集合 A 的符号名或任何字符串。(5 分) 例如有下列语句:

Element *A, *B, *C;
C = Union(A, B);    // C是集合A和B并集的首地址，集合A和B已按要求存储好
Display("A=",A);    // 输出结果: A={11,22}
Display("Set B:", B);  // 1输出结果: Set B:{}

　　 2.已知二叉搜索树(Binary Search Tree)或二叉排序树(Binary Sorting Tree)的结点定义如下:

typedef struct_ BSNode {
    int key;
    struct_BSNode *LChild, *RChild; // 左子树的关键字比根的小，右子树的关键字比根的大
} BSNode;

编写函数 int Insert(BSNode **root, int key),其功能是在以结点*root 为根的二叉搜索树中插入关键字 key。若插入成功，则返回 0。若关键字已存在，则返回 1。若申请结点失败，则返回 2.