




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、韩山师范学院2009年专升本插班生考试试卷计算机科学与技术 专业 数据结构 样卷题号一二三四五六七八九十总分评卷人得分一、单项选择题(每题2分,共40分)。题号12345678910答案题号11121314151617181920答案1.关于线性表的描述,错误的是( )。 A. 线性表是线性结构 B. 线性表就是单链表 C. 线性表的顺序存储结构,必须占用一片连续的存储单元 D. 线性表的链式存储结构,不必占用连续的存储单元2.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法3.与单链表相比,双链表的优
2、点之一是( )。A.插入、删除操作更简单 B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活4. 对个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为( )。A. n+1 B. n C. n-1 D. n(n-1)/25如果结点A有3个兄弟,而且B为A的双亲,则B是度为( )A3 B4 C5 D16在具有N个单元的顺序存储循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队满的条件为( )。Afront = rear B(rear+1) % MAXSIZE = frontCfront - rear=1 Drear % MAXSIZE = fr
3、ont7. 某二叉树的前序遍历序列为 ABDGCEFH ,中序遍历序列为 DGBAECHF ,则后序遍历序列为( )。 A. BDGCEFHA B. GDBECFHA C. BDGAECHF D. GDBEHFCA 8设无向图的顶点个数为n,则该图最多有( )条边。A. n-1 B. n(n-1)/2 Cn(n+1)/2 D. 09. 在一个长度为N的线性表中顺序查找值为x的元素时,在等概率的情况下查找成功时的平均查找长度为( )。A. N B. N/2 C. (N+1)/2 D. (N-1)/210深度为5的二叉树至多有( )个结点。A.16B.32C.31D.1011. 堆的形状是一棵(
4、)。 A. 二叉排序树 B.满二叉树 C. 完全二叉树 D. 平衡二叉树12下列关于数据结构的叙述中,正确的是( )。A. 数组是同类型值的集合 B. 树是一种线性结构C. 递归算法的程序结构比迭代算法的程序结构更为精炼D. 用一维数组存储二叉树,总是以先序遍历的顺序存储各结点13. 在具有 n(n1) 个结点的完全二叉树中,结点 i(2*in) 的左孩子结点是( )。 A. 2*i B. 2*i+1 C. 不存在 D. 2*i-1 14. 在有n个结点的二叉树中,值为非空的链域的个数为()。A.n-1B.2*n-1 C.n+1 D.2*n+115. 若对一个已排好序的序列进行排序,在下列四种
5、方法中,哪种比较好( )。A. 冒泡法 B. 直接选择法 C. 直接插入法 D. 归并法 16. 设单链表中指针p指向结点A,若A的后继结点存在,则删除该后继结点需要修改指针的操作为( )。Ap-next=p-next-next Bp=p-nextCp=p-next-next Dp-next=p17. 队列操作的原则是( )。A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除18. 对树进行层次遍历时,通常是采用( )作为辅助来实现算法的。A栈 B. 队列 C. 树 D. 图 19. ( )是顺序存储方式的优点。A. 存储密度大 B. 插入运算方便 C. 删除运算方便 D.
6、 可方便地用于各种逻辑结构的存储表示20. 数组A56的每个元素占5个单元,将其按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A5,5的地址为( )。A.1140 B.1145 C.1120 D.1125二、判断题(每题1分,共10分)。以下各种说法,你认为对的在前面括号打,错误的打。()1队列只能采用链式存储方式。 ()2.二叉树的度一定是2。()3.线性结构也是一种树结构。()4.有向图用邻接表表示后,顶点i的入度等于该顶点对应的单链表的元素个数。()5满二叉树一定有偶数个结点。()6直接插入排序的关键码比较次数与初始排列有关。()7顺序存储方式只能用于存储线性结构。( )
7、8. 给出不同的输入序列建造二叉排序树,一定得到不同的二叉排序树。()9在对链队列作出队操作时,不会改变front指针的值。( )10. 堆排序是不稳定排序。三、填空题(每空2分,共18分)。1中缀算式(3+4)*2 /(8-5)所对应的后缀算式为_ _。2. 某算法的时间复杂度为(5*n2+1000*n*log2n+4*n-8)/(10*n),其数量级表示为_。3. 用1000个结点构造的二叉树,最少_层,最多_层。4. 假定一个线性表为(12,23,74,55,63,40,82,36),若按Key % 3条件进行划分,使得同一余数的元素成为一个子表,则得到的三个子表分别为_、_和_。5.
8、假定一棵二叉树广义表表示为a(b(c),d(e,f),其中序遍历序列为_,层次遍历序列为_。四、程序填空题(每个语句2分,共12分)1下面是向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请将缺失语句填上。void Insert(BTreeNode*& BST, const ElemType& item) if( BST = NULL ) BTreeNode* p = new BTreeNode;p-data = item; _; BST = p;else if( item data ) _; else _; 2下面是向单链表的末尾添加一个元素的算法。请将缺失的语句填上。V
9、oid InsertRear( LNode*& HL, const ElemType& item ) LNode* newptr;newptr = new LNode;if ( newptr = NULL )cerr Memory allocation failare! data = item;_if ( HL = NULL ) HL = newptr;else_;while ( ) p = p-next;p-next = newptr;五、算法设计题(20分)1编写算法函数,把顺序表List原地置逆。(10分)顺序表的数据结构如下: typedef struct int data100; int last;/最后元素的下标 SeqList;函数原形为:void fnReverse( SeqList &List );2.二叉树采用左右孩子指针存储结构:Struct TreeNodeInt data;/
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 农户农田住宿管理办法
- 河南造林资金管理办法
- 核酸采集人员管理办法
- 短视频算法优化策略-洞察及研究
- 10kV电力贯通线设计与施工方案探讨
- 茎秆特征及抗倒伏能力影响
- 体育机构管理办法提纲
- 社会学核心理论体系梳理与考核要点解析
- 村屯信息收集管理办法
- 基层银行绿色金融实践:业务推进与风险管理研究
- 2025年广东省中考生物试卷真题(含答案解析)
- 第10课+辽夏金元的统治(大概念教学课件)2024-2025学年高一历史上册教学课件(统编版2019)
- 装置保运方案(3篇)
- 中国聚丙烯酰胺行业市场发展分析及前景趋势与投资研究报告2025-2028版
- 青年教师教学工作坊组织计划
- 驻非洲员工管理制度
- 工程内业资料管理制度
- 摩托车协议过户协议书
- 2025年食品检验员考试试卷及答案
- 四川省德阳市2025年七年级下学期语文期末试卷及答案
- 黎族文化课件
评论
0/150
提交评论