广东财经大学硕士研究生入学考试试卷
考试年度：2021年考试科目代码及名称：809-数据结构（自命题）
适用专业：085400电子信息
［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］
一、单项选择题（每小题2分，共40分）
1.关于线性表的说法正确的是（）。
A.线性表的特点是每个元素都有一个前驱和一个后继元素
B.线性表是特征相同的n（n≥0）个元素构成的有限序列
C.线性表采用顺序存储便于进行插入和删除操作
D.线性表采用链式存储便于进行随机查找操作
2.表长为n的顺序存储的线性表，当在任何位置删除一个元素的概率相等时，删除一个元
素所需移动元素的平均个数为（）。
A.(n-1)/2B.n/2C.(n+1)/2D.n
3.假设单链表结点结构为（data,next），删除指针p所指结点的后继结点q的语句序列是
（）。
A.p-nextq-next;free(q);B.p-nextq;free(q);
C.free(q);p-nextq-next;D.free(q);p-nextq;
4.设有一个递归算法如下所示，计算F(8)需要调用该递归函数的次数为（）。
intF(intn)
{if(n3)return1;
elsereturnF(n-2)+F(n-4)+1;}
A.7B.8C.9D.10
5.若循环队列Q存储在数组queue[0..n]中，front是队首位置，rear是队尾位置（初始
rearfront0），则元素e入队的操作是（）。
A.Q.queue[Q.rear]e;Q.rear(Q.rear+1)%n;
B.Q.queue[Q.rear]e;Q.rear(Q.rear+1)%(n+1);
C.Q.rear(Q.rear+1)%n;Q.queue[Q.rear]e;
D.Q.rear(Q.rear+1)%(n+1);Q.queue[Q.rear]e;
6.关于串的叙述中不正确的是（）。
A.串是字符的有限序列
B.空串是由空格构成的串
C.串既可以采用顺序存储，也可以采用链式存储
D.模式匹配是串的一种重要运算
7.按照从上至下、由左至右的顺序依次编号，深度为7的完全二叉树编号最大的叶结点编
号是（）。
A.63B.64C.126D.127
8.已知完全二叉树的第7层有20个叶结点，则该二叉树最多有（）个结点。
A.83B.147C.214D.215
9.设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端，则B中右指针域
为空的结点有（）个。
1
A.n-1B.nC.n+1D.n+2
10.由权值为15,3,5,10的四个叶结点构成的哈夫曼树的带权路径长度为（）。
A.46B.59C.66D.88
11.具有n个顶点的有向完全图用邻接表表示时，共有（）个弧结点。
A.n(n-1)/2B.n(n-1)C.2n(n-1)D.n-1
12.下面的（）算法适合构造一个稠密图的最小生成树。
A.Prim算法B.Kruskal算法C.Floy算法D.Dijkstra算法
13.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用（）查找
法。
A.顺序查找B.折半查找C.分块查找D.哈希查找
14.对50个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
A.4B.5C.6D.7
15.关于B-树和B+树的叙述不正确的是（）。
A.B-树和B+树都是平衡的多叉树
B.B-树和B+树都可用于文件的索引结构