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

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 2018 年攻读硕士学位研究生入学考试试题 考试科目:计算机科学专业基础综合 科目代码:874 （试题共8 页）（答案必须写在答题纸上，写在试题上不给分） 数据结构与算法（65 分） 一、单项选择题（每小题2 分，共17 小题，共34 分 1.下面关于“算法”的描述，错误的是 （ ） A.算法必须是正确的 B.算法必须要能够结束 微 信 C.一个问题可以有多种算法解决 公 D.算法的某些步骤可以有二义性 众 2.下面函数的时间复杂度是 （ ） void func(int n){ 号 int sum ＝0,i, j; 计 for(i ＝1; in; i++) 算 for(j ＝1; jn; j* ＝2) 机 sum++; 与 2 软 A.O(log n) B.O(n ) C.(nlog n) D.O(n) 2 2 件 3.下面关于线性表的叙述中，错误的是 （ ） 考 A.线性表采用顺序存储，必须占用一片连续的存储单元 研 B.执行查找操作时，链式存储比顺序存储的查找效率更高。 C.线性表采用链式存储，不必占用一片连续的存储单元。 D.线性表采用链式存储，便于插入和删除操作。 4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用 （ ）最节省时间 A.单链表 B.带头指针的单循环链表 C.带尾指针的单循环链表 D 带头结点的双循环链表 第1页 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 5.一个栈的输入序列为1，2，3，，n，若输出序列的第一个元素是n，则输出的第i (1=i=n) 个元素是 （ ） A.不确定 B.n-i+1 C.i D.n-i 6.若一棵完全二叉树有666 个结点，则该二叉树中叶子结点的个数是 （ ） A.156 B.155 C.333 D.334 7.对于下列关键字序列，不可能构成某二叉查找树中一条查找路径的序列是 （ ） A.99 ，28，86，36，94，65 B.97，18，89，34，76，42 C.16，91，68，29，33，50 微 D.21，27，80，76，29，39 信 8.下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键 字有序 （ ） 公 众 A.二叉查找树 B.哈夫曼树 C.AVL 树 D.堆 号 9.在右图的AVL 树中插入关键字18 后得到一棵新AVL 树，在新AVL 树中，关键字11 所在 计 结点的左、右孩子结点中保存的关键字分别是 （ ） 算 A.7 ，16 B.9，18 机 C.9，26 D.7，18 与 软 件 10.将一棵树T1 转化为对应的二叉树T2