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

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 2017 年设读硕士学位研究生入学考试试题 考试科目:计算机科学专业基础综合 科目代码:874 试题共8 页（答案必须写在答题纸上，写在试题上不给分） 数据结构与算法（65 分） 一.单项选择题（每小题2 分，共17 小题，共34 分） 1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结 构是（） A.栈 微 B.队列 C.树 D.图 信 2.通常说顺序表具有随机存取特性，指的是 公 A.查找值为的元素的时间与顺序表中元素个数无关 众 B 查找值为的元素的时间与顺序表中元素个数有关 号 C.查找序号为的元素的时间与顺序表中元素个数无关 计 D.查找序号为的元素的时间与顺序表中元素个数有关 算 3.链栈与顺序栈相比有一个明显的优点，即 （） 机 A.进栈操作更方便 B.通常不会出现栈上溢出的情况 与 C.总是不会出现栈空的情况 D.出栈操作更方便 4.折半查找的时间复杂性为（） 软 2 B.O(n) C.O(nlog n) 件 D.O(log n) A.O(n ) 2 考 2 5.在待排序的元素序列基本有序的前提下效率最高的排序方法是（）研 A.选择排序 B.插入排序 C.快速排序 D.归并排序 6 设无向连通图的顶点个数为n，则该图最少有（）条边。 A.n B.n/2 C.n-1 D.n(n-1)/2 7.一棵度为5.结点个数为n 的树采用孩子链存储结构时，其中空指针域的个数是 （） A.5n B.4n+1 C.4n D.4n+1 8.用 Prim 算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的顶 点集合U＝{1,2,3} ，已选取的边的集合TE ＝{(1,2),(2,3)} ，要选取下一条权值最小的边，应当 从 （）组边中选取 第1页 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan A.{(1 ，4) ，(3，4) ，(3，5)} B.{(4 ，5)，(1，3)} C.{(12) ，(2，3)} D.{(3，4) ，(3，5)，(4，5)} 9.快速排序是利用哪类算法实现的（） A.分治策略 B.动态规划法 C.贪心法 D.回溯法 10.若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图 （） A.是个有根有向图 微 B.是个强连通图 信 C.度为0 的顶点 公 D.含有顶点数目大于1 的强连通分量 11.设一组权值集合W ＝{2 ，3，4 ，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度 众 之和为（） 号 A.20 B.40 计 C.45 D.48 12.二叉排序中，按 （）遍历叉排序得到的序列是一个有序序列。