四川大学-874-2016-真题.pdfVIP

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 2016 年攻读硕士学位研究生入学考试试题 考试科目:计算机科学专业基础综合 科目代码:874＃ 适用专业:计算机科学与技术.计算机应用技术.计算机技术.软件工程 （试题共9 页）（答案必须写在答题纸上，写在试题上不给分） 数据结构与算法分析（共65 分） 一.单项选择题（每小题2 分，共18 小题，共36 分） 1.程序段 微 for(i=n-1;=1;--i) 信 for(j=i;ji;++j ) 公 众 if(A[j]) ali 与al+1 对换; 号 其中n 为正整数，则最后一行的语句最多执行 （）次。 A.O(n) 2 计 3 D.O(nlogn) B.O(n ) C.O(n ) 算 2.将两个有N 个元素的有序表归并成一个有序表，其最少比较次数为 （）。 机 A.N B.2N C.N-1 D.2N-2 3.下列编码中属前缀编码的是（） 与 软 A. ｛1，01 ，000 ，001 ｝ 件 B. ｛0 ，1，00 ，11 考 C. ｛0 ，10，110，11 ｝ 研 D. ｛1，01 ，011 ，010 ｝ 4.在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（） A.O(1) BO(n) C.O(nlogn) 2 D.O(n ) 5.若用一个不带头结点的循环单链表表示队列，则最好用 （）标识链队。 A.首结点指针 B 尾结点指针 C.首结点和尾结点两个指针 D 任何结点指针 6.一个10 阶对称矩阵A[1...10,1...10]采用压缩存储方式，将其下三角和主对角部分按行优先 存储到一维数组B[1...m] 中，则A[5][8]元素在B 中的位置k 是 （）。 A.32 B.37 C.45 D.60 第1页 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 7.下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（） A.直接插入排序 B.起泡排序 C.快速排序 D.基数排序 8.采用邻接矩阵表示一个具有n 个顶点m 条边的无向图，该矩阵的大小是 （）。 A.2n*2m B.m*m C.n*m D.n*n 9.设某哈夫曼树中有199 个结点，则该哈夫曼树中有（）个叶子结点。 A.99 B.100 C.101 D.102 10. 以下关于广度优先遍历算法的叙述中正确的是 A.广度优先历算法不适合有向图。 微 B.对任何有向图调用一次广度优先遍历算法便可访问所有的顶点 信 C.对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点