广东财经大学 2021 年数据结构考研真题考试年度：20 21 年 考试科目代码及名称：809 - 数据结构 （自命题） 适用专业：085400 电子信息 ［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］一、单项选择题（每小题 2 分，共 40 分）1. 关于线性表的说法正确的是（ ）。A.线性表的特点是每个元素都有一个前驱和一个后继元素B.线性表是特征相同的 n（n≥0）个元素构成的有限序列C.线性表采用顺序存储便于进行插入和删除操作D.线性表采用链式存储便于进行随机查找操作2. 表长为 n 的顺序存储的线性表，当在任何位置删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为（ ）。A.(n-1)/2 B.n/2 C.(n+1)/2 D.n3. 假设单链表结点结构为（data,next），删除指针 p 所指结点的后继结点 q 的语句序列是（ ）。 A.p->next=q->next; free(q); B.p->next=q; free(q); C.free(q);p->next=q->next; D.free(q);p->next=q;4. 设有一个递归算法如下所示，计算 F(8)需要调用该递归函数的次数为（ ）。 int F(int n) { if(n<=3) return 1; else return F(n-2)+F(n-4)+1; } A.7 B.8 C.9 D.105. 若循环队列 Q 存储在数组 queue[0..n]中，front 是队首位置，rear 是队尾位置（初始rear=front=0），则元素 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.63 B.64 C.126 D.1278. 已知完全二叉树的第 7 层有 20 个叶结点，则该二叉树最多有（ ）个结点。 A.83 B.147 C.214 D.215 9. 设 F 是一个森林，B 是由 F 变换得到的二叉树。若 F 中有 n 个非终端，则 B 中右指针域为空的结点有（ ）个。 A.n-1 B.n C.n+1 D.n+210. 由权值为 15,3,5,10 的四个叶结点构成的哈夫曼树的带权路径长度为（ ）。 A.46 B.59 C.66 D.8811. 具有 n 个顶点的有向完全图用邻接表表示时，共有（ ）个弧结点。A.n(n-1)/2 B.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.4 B.5 C.6 D.715. 关于 B-树和 B+树的叙述不正确的是（ ）。A.B-树和 B+树都是平衡的多叉树B.B-树和 B+树都可用于文件的索引结构C.B-树和 B+树都能有效支持顺序检索D.B-树和 B+树都能有效支持随机检索16. 假设散列表长度为 11，散列函数为 H(key)=key%7，冲突处理方法为开放地址法的二次探测再散列。已知表中已有记录的关键字为 32,17,9,27，现要将关键字为 45 的记录加入表中，则放入的位置是（ ）。 A.1 B.3 C.5 D.717. 从未排序序列中依次取出元素与已排序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的排序方法称为（ ）。A.插入排序 B.冒泡排序 C.选择排序 D.归并排序18. 快速排序法在（ ）情况下最有利于发挥其长处。A.待排序数据量大 B.数据中含有多个相同的关键字C.数据按关键字已基本有序 D.数据按关键字完全无序19. 下列排序算法中，占用辅助空间最多的是（ ）。 A.希尔排序 B.快速排序 C.堆排序 D.归并排序20. 下列排序方法中，其中（ ）是稳定的。 A.堆排序，冒泡排序 B.快速排序，堆排序 C.选择排序，归并排序 D.归并排序，冒泡排序二、填空题（每...
