招生专业与代码：计算机系统结构081201、计算机软件与理论081202、计算机应用技术081203、电子信息(专业学位) 085400
考试科目名称及代码：计算机基础综合848
考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。
第一部分 数据结构（75分）
一、 单项选择题(每题2分，共20分)
-
某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A.单链表
B.仅有头指针的单向循环链表
C.双链表
D.仅有尾指针的单向循环链表
-
一个栈的输入序列为1，2，3…，n，若输出序列的第一个元素是n，那么输出第i（1
A. n-i
B. i
C. n-i+1
D. 不确定
-
若一颗二叉树具有15个度为2的结点，10个度为1的结点，则度为0的结点个数是（ ）。
A. 16
B. 25
C. 40
D. 不确定
-
根据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。
A. 000，001，010，011，1
B. 000，001，01，10，11
C. 00，100，101，110，111
D. 0000，0001，001，01，1
-
设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（ ）。
A.a在b的右方
B. a在b的左方
C. a是b的祖先
D. a是b的子孙
-
对一棵二叉排序树按（ ）遍历，可得到结点值从小到大的排序序列。
A. 先序
B. 中序
C. 后序
D. 层次
-
已知一个有序表为(5，13，19，21，37，56，64，75，80，88，92)，则折半查找64需要比较（ ）次。
A. 1
B. 2
C. 3
D. 4
-
在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。
A. 1/2
B. 1
C. 2
D. 3
-
一个序列中有100000个元素，若只想得到其中前10个最大元素，则最好采用（ ）方法。
A. 快速排序
B. 堆排序
C. 插入排序
D. 归并排序
-
下列四个序列中，哪一个是堆（ ）。
A. 70，60，40，10，30，25，20，15
B. 70，60，30，15，25，40，20，10
C. 70，40，60，10，25，30，20，15
D. 70，40，60，30，15，25，20，10
二．判断题(每题1分，共10分，正确的打√，错误的打×)
-
数据结构研究的是数据的物理结构、逻辑结构以及它们之间的相互关系。 ( )
-
线性表的顺序存储结构适用于频繁插入或删除数据元素的情况。( )
-
一颗满二叉树同时又是一颗平衡树。( )
-
一棵m阶B-树中每个结点最多有m棵子树，非终端结点最少有2棵子树。( )
-
带权无向图的最小生成树是唯一的。( )
-
在各种查找方法中，平均查找长度与结点个数无关的查找方法是哈希查找。( )
-
拓扑排序是按AOE 中每个结点事件的最早发生事件对结点进行排序。( )
-
存在这样的二叉树，对它采用任何次序进行遍历，结果相同。( )
-
对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是O(n2) 。( )
-
若 中有几条关键路径，提高一条关键路径上的活动的速度，不能导致整个工程缩短工期。( )
三．简答题（共3小题，每题8分，共24分）
-
请按照关键字24，13，20，32，29，53的次序构造一棵二叉平衡树，并给出过程。（8分）
-
由n个权值构成的哈夫曼树共有多少个结点4分）为什么4分）
-
一个有六个顶点{V0,V1,V2,V3,V4,V5}的 络的邻接矩阵如图1所示，求出从顶点V0到其他各顶点之间的最短路径，并写出计算过程。（8分）
五、 应用题(每小题10分，共20分)
-
某文件系统的一个文件控制块（FCB）占64个字节，盘块大小为2K字节，则每个盘块可存放的FCB数目是多少果一个文件目录中有384个FCB，则查找一个文件平均需要启动磁盘多少次入索引结点（i结点）后，如果文件名占14个字节，索引结点占2个字节，大小为2K字节的盘块可存放的目录项数目是多少找到一个文件，平均需要启动磁盘多少次10分）
-
某银行在两个门口分别放置了排队取 机，客户进门时在取 机上按取 键，取 机打印输出含有排队序 和前面等待人数的纸条给客户。若干柜员每人桌面放有一台已设好窗口 的叫 机，按下叫 键若有客户等待就播放排在最前面的客户的 码和窗口 ，没有客户则程序等待。请用信 量机制模拟叫 系统的功能。（10分）
其他年份真题及答案：https://app2098.acapp.acwing.com.cn/
文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34297 人正在系统学习中
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！