河南财经政法大学-811计算机应用基础数据结构【2014】考研真题
2023-06-21
999+
34.5KB
4 页
侵权投诉
河南财经政法大学
2014 年硕士研究生入学考试业务课试题
专业名称：计算机应用技术
考试科目：数据结构（共 150 分）
一、选择题（本题共 10 个小题，每小题 3分，
共计 30 分）
1． 设一组权值集合 W={2，3，4，5，6}，则由该权值集合构造的
哈夫曼树中带权路径长度之和为（ ）。
(A) 20 (B) 30 (C) 40 (D) 45
2．执行一趟快速排序能够得到的序列是（ ）。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
3．设一条单链表的头指针变量为 head 且该链表没有头结点，则其
判空条件是（ ）。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
4．时间复杂度不受数据初始状态影响而恒为 O(nlog2n)的是（ ）。
(A) 堆排序 (B)冒泡排序
(C) 希尔排序 (D) 快速排序
5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉
树满足的条件是（ ）。
(A) 空或只有一个结点 (B) 高度等于其结点数
(C) 任一结点无左孩子 (D) 任一结点无右孩子
6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的
是（ ）。
(A) 堆排序 (B)冒泡排序 (C)快速排序 (D)希尔排序
7．设某棵三叉树中有 40 个结点，则该三叉树的最小高度为（ ）。
(A) 3 (B) 4 (C) 5 (D) 6
8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂
度为（ ）。
第 1 页 共 4 页
(A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1og2n)
9．二路归并排序的时间复杂度为（ ）。
(A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(1og2n)
10. 深度为 k 的完全二叉树中最少有（ ）个结点。
(A) 2k-1-1 (B) 2k-1 (C) 2k-1+1 (D) 2k-1
二、填空题（本题共 10 个小题，每小题 3分，共
计30 分）
1．for(i=1，t=1，s=0；i<=n；i++) {t=t*i；s=s+t；}的时间复
杂度为_________。
2．设指针变量 p 指向单链表中结点 A，指针变量 s 指向被插入的新
结点 X，则进行插入操作的语句序列为_____________________
_____（设结点的指针域为 next）。
3 ． 设 有 向 图 G 的 二 元 组 形 式 表 示 为 G
=（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<
4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序
列__________。
4．设无向图 G 中有 n 个顶点，则该无向图中每个顶点的度数最多
是_________。
5．设二叉树中度数为 0 的结点数为 50，度数为 1 的结点数为 30，
则该二叉树中总共有_______个结点数。
6．设 F 和 R 分别表示顺序循环队列的头指针和尾指针，则判断该
循环队列为空的条件为_____________________。
7．设二叉树中结点的两个指针域分别为 lchild 和 rchild，则判断
指针变量 p 所指向的结点为叶子结点的条件是_______________
____________________________。
8．简单选择排序和直接插入排序算法的平均时间复杂度为_______
____。
9．快速排序算法的空间复杂度平均情况下为__________，最坏的
情况下为__________。
10.散列表中解决冲突的两种方法是_____________和____________
_。
三、判断题（本题共 10 个小题，每小题 3分，
共计 30 分）
（请在小题括号内打√或×）
第 2 页 共 4 页
标签： #河南财经政法大学
摘要：
展开>>
收起<<
河南财经政法大学2014年硕士研究生入学考试业务课试题专业名称：计算机应用技术考试科目：数据结构（共150分）一、选择题（本题共10个小题，每小题3分，共计30分）1．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。(A)20(B)30(C)40(D)452．执行一趟快速排序能够得到的序列是（）。(A)[41，12，34，45，27]55[72，63](B)[45，34，12，41]55[72，63，27](C)[63，12，34，45，27]55[41，72](D)[12，27，45，41]55[34，63，72]3．设一条单链表的头指针变量为...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
