一、选择题(24分)
1.下列程序段的时间复杂度为( )。
i=0,s=0; while (s
(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)
2.设某链表中最常用的操作是在链表的尾部插入或删除元素,则选用下列( )存储方式最节省运算时间。
(A) 单向链表 (B) 单向循环链表
(C) 双向链表 (D) 双向循环链表
3.设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B插入结点X的操作序列为( )。
(A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p;
(C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q;
4.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为( )。
(A) 5,3,4,6,1,2 (B) 3,2,5,6,4,1
(C) 3,1,2,5,4,6 (D) 1,5,4,6,2,3
5.设有一个10阶的下三角矩阵A(包括对角线),按照从上到下、从左到右的顺序存储到连续的55个存储单元中,每个数组元素占1个字节的存储空间,则A[5][4]地址与A[0][0]的地址之差为( )。
(A) 10 (B) 19 (C) 28 (D) 55
6.设一棵m叉树中有N1个度数为1的结点,N2个度数为2的结点,……,Nm个度数为m的结点,则该树中共有( )个叶子结点。
(A) (B) (C) (D)
7. 二叉排序树中左子树上所有结点的值均( )根结点的值。
(A) < (B) > (C) = (D) !=
8. 设一组权值集合W=(15,3,14,2,6,9,16,17),要求根据这些权值集合构造一棵哈夫曼树,则这棵哈夫曼树的带权路径长度为( )。
(A) 129 (B) 219 (C) 189 (D) 229
9. 设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。
(A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2
10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉中共有( )个结点。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l
11.设一组初始记录关键字的长度为8,则最多经过( )趟插入排序可以得到有序序列。
(A) 6 (B) 7 (C) 8 (D) 9
12.设一组初始记录关键字序列为(Q,H,C,Y,P,A,M,S,R,D,F,X),则按字母升序的第一趟冒泡排序结束后的结果是( )。
(A) F,H,C,D,P,A,M,Q,R,S,Y,X
(B) P,A,C,S,Q,D,F,X,R,H,M,Y
(C) A,D,C,R,F,Q,M,S,Y,P,H,X
(D) H,C,Q,P,A,M,S,R,D,F,X,Y
二、填空题(48分,其中最后两小题各6分)
1. 设需要对5个不同的记录关键字进行排序,则至少需要比较_____________次,至多需要比较_____________次。
2. 快速排序算法的平均时间复杂度为____________,直接插入排序算法的平均时间复杂度为___________。
3. 设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较_________次。
4. 设在长度为20的有序表中进行二分查找,则比较一次查找成功的结点数有_________个,比较两次查找成功有结点数有_________个。
5. 设一棵m叉树脂的结点数为n,用多重链表表示其存储结构,则该树中有_________个空指针域。
6. 设指针变量p指向单链表中结点A,则删除结点A的语句序列为:
q=p->next;p->data=q->data;p->next=___________;feee(q);
7. 数据结构从逻辑上划分为三种基本类型:___________、__________和___________。
8. 设无向图G中有n个顶点e条边,则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________;用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。
9. 设散列表的长度为8,散列函数H(k)=k % 7,用线性探测法解决冲突,则根据一组初始关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是________。
10. 设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟冒泡排序结束后的结果为_____________________。
11. 设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟简单选择排序后的结果为______________________。
12. 设有向图G中的有向边的集合E={<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>},则该图的一个拓扑序列为_________________________。
13. 下面程序段的功能是建立二叉树的算法,请在下划线处填上正确的内容。
typedef struct node{int data;struct node *lchild;________________;}bitree;
void createbitree(bitree *&bt)
{
scanf(“%c”,&ch);
if(ch=='#') ___________;else
{ bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; ________;createbitree(bt->rchild);}
}
14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法,请在下划线处填上正确的内容。
typedef struct node {int data; struct node *next;} lklist;
void lklistcreate(_____________ *&head )
{
for (i=1;i<=n;i++)< p="">
{
p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;
if(i==1)head=q=p;else {q->next=p;____________;}
}
}
三、算法设计题(22分)
1. 设计在链式存储结构上合并排序的算法。
2. 设计在二叉排序树上查找结点X的算法。
3. 设关键字序列(k1,k2,…,kn-1)是堆,设计算法将关键字序列(k1,k2,…,kn-1,x)调整为堆。
2019年考研《计算机数据结构》测试题(1)
本站小编 免费考研网/2018-01-28
相关话题/计算机
考研计算机网络谢希仁版复习要点
专业课考研资料 本站小编 免费考研网 2018-01-282018年中科院计算机学科综合(专业)863考研真题
2018年863回忆版 一、单选题(共80分) 1. 下列选项中,()可以执行特权指令 A. 普通用户的程序B. 设备驱动程序C. 动态库函数D. 管理员用户的程序 2. 下列选项中,导致创建新进程的操作是() 1) 管理员启动Web 服务2) 用户启动浏览器程序3) 用浏览器访问新的网页 A. 仅1和2B. 仅2和3C. 仅1和3D. 1、 ...专业课考研资料 本站小编 免费考研网 2018-01-262017年中科院计算机学科综合(专业)863考研真题
中国科学院大学2017 年招收攻读硕士学位研究生入学统一考试试题科目名称:计算机学科综合(专业)考生须知:1. 本试卷满分为 150 分, 全部考试时间总计 180 分钟。 2.所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效。一、单项选择题(选择题太多,没有时间抄写下来。题目的主要考察内容是 数据结构和组成原理)二、 ...专业课考研资料 本站小编 免费考研网 2018-01-26上海交通大学2006年考研真题-计算机通信网
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2005年考研真题-微型计算机原理与应用
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2005年考研真题-计算机通信网
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2005年考研真题-计算机基础I
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2005年考研真题-计算机基础(II)
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2003年考研真题-计算机基础(I)
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2004年考研真题-计算机基础(I)
专业课考研经验 本站小编 FreeKaoyan 2018-01-23上海交通大学2005年考研真题-计算机基础(2)
专业课考研经验 本站小编 FreeKaoyan 2018-01-23河北工业大学2007年考研真题-计算机软硬件基础(含离散数学和组成)
专业课考研经验 本站小编 FreeKaoyan 2018-01-23河北工业大学2006年考研真题-计算机组成
专业课考研经验 本站小编 FreeKaoyan 2018-01-23北京大学2007年考研真题-计算机算法填空
070e1a5a653aa513902760243cbc4e81.rar070e1a5a653aa513902760243cbc4e81.rar(3.00 KB) ...专业课考研经验 本站小编 FreeKaoyan 2018-01-23北京大学2007年考研真题-计算机试题建模
04886576b8efa2a2b58a9a86cc84f9a7.rar04886576b8efa2a2b58a9a86cc84f9a7.rar(44.75 KB) ...专业课考研经验 本站小编 FreeKaoyan 2018-01-23