中山大学 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;
};
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;
}
Stack:~Stack()
{
Node *Pt;
while(___(4)___ ){
Pt=Top;
____(5)____ ;
delete Pt;
}
}
typedef struct_PNode {
int Coef; // 系数
int Expn; // 指数(规定:指数>=0)
struct_PNode *next;
} PNode;
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)____;
}
void Time(PNode *P1, PNode P2)
{
PNode *Pt;
for (Pt= P1; Pt!= NULL; Pt= Pt->next) {
____(4)____;
____(5)____;
}
}
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;
int Leaves(BinNode *root)
{
if( root == NULL ) return 0;
if(____(1)____) return 1;
return(____(2)____);
}
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; // 集合的结点定义
(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;