江西师范大学硕士研究生入学考试初试科目

《江西师范大学硕士研究生入学考试初试科目》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、江西师范大学硕士研究生入学考试初试科目考　试　大　纲科目代码、名称:863、数据结构与程序设计适用专业:081200计算机科学与技术一、考试形式与试卷结构（一）试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。（二）答题方式答题方式为闭卷、笔试。试卷由试题和答题纸组成；答案必须写在答题纸相应的位置上。（三）试卷题型结构1．单项选择题：10小题，每小题2分，共20分2．填空题：10小题，每小题2分，共20分3．程序填空与程序分析题题：4小题，每小题6分，共24分4．解答题：4小题，第小题10分，共40分5．算法与程序设计题：3小题，第1、2小题

2、每小题14分，第3小题18分，共46分二、考查目标（复习要求）全日制攻读硕士学位研究生入学考试数据结构与程序设计科目考试内容包括《数据结构》课程主要内容，要求考生系统掌握相关学科的基本知识、基础理论和基本方法，并能运用相关理论和方法分析、解决程序设计中的实际问题。三、考查范围或考试内容概要第一章　概论1．数据结构的基本概念与术语2．算法与算法分析第二章　线性表及其顺序存储1．线性表2．顺序表及其应用3．栈的概念及其应用4．队列的概念及其应用第9页，共9页第三章　线性表及其链式存储1．链式存储2．单链表3．带头结点的单链表及其应用4．循环单链表与双链表5．

3、链式栈与链式队列第四章　字符串、数据与特殊矩阵1．字符串及模式匹配2．特殊矩阵的压缩存储3．稀疏矩阵第五章　递归1．递归的基本概念与递归程序设计2．递归程序设计执行过程的分析3．递归程序到非递归程序的转换第六章　树1．树的概念2．树的存储结构3．树的遍历第七章　二叉树1．二叉树的基本概念2．二叉树的存储结构3．二叉树的遍历（递归与非递归）4．穿线二叉树的基本概念与构造5．树、森林和二叉树的转换第八章　图1．图的基本概念2．图的存储结构（邻接矩阵法、邻接表法）3．图的遍历4．生成树与最小生成树5．最短路径6．拓扑排序7．关键路径第9页，共9页第九章　检索1

4、．检索的基本概念2．线性表的检索3．二叉排序树4．平衡二叉排序树5．Huffman树6．B-树7．散列表的检索8．查找算法的分析及应用第十章　排序1．排序的基本概念2．插入排序（直接插入排序、折半插入排序、希尔排序）3．选择排序（简单选择排序、堆排序）4．交换排序（冒泡排序、快速排序）5．二路归并排序（mergesort）6．基数排序7．各种内部排序算法的比较8．内部排序算法的应用参考教材或主要参考书：1．《数据结构》（C语言版）第二版，李云清，杨庆红，揭安全编著，人民邮电出版社，ISBN:978-7-115-20703-6第9页，共9页四、样卷江西师范

5、大学硕士研究生入学考试试题（样卷）专业:081200计算机科学与技术科目：数据结构与程序设计注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其它答题纸上的一律无效！（本试题共计页）一、选择题（每小题2分，共20分）1、若语句S的执行时间为O（1），那么下列程序段的时间复杂度为：（）for（i=0;inext=p;p->ne

6、xt=s;（B）p->next=s;s->next=p;（C）s->next=p->next;p=s;（D）s->next=p->next;p->next=s;3、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）（注：只含有一个根结点的树高为1）（A）2h（B）2h-1（C）2h+1（D）h+14、一组记录的关键码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。（A）84，79，56，38，40，46（B）79，46，56，38，40，80（C）84，79，56，46，40，38（D）8

7、4，56，79，40，46，385、设二叉排序树中关键字由1至1000的整数构成，现要检索关键字为363的结点，下述关键字序列哪一个不可能是二叉排序树上搜索到的序列（）。（A）2，252，401，398，330，344，397，363（B）924，220，911，244，898，258，362，363（C）952，202，911，240，912，245，363（D）2，399，387，219，266，382，381，278，3636、已知某完全二叉树采用顺序存储结构，结点数据信息A、B、C、D、E、F、G、H，顺序存放在数组的前8个单元，则该完全二叉树的

8、后序遍历序列为（）。（A）HDEBFGCA（B）HEDBFGCA（C）HDEBA