023310000数据结构课程考试说明

023310000数据结构课程考试说明一、课程使用教材、大纲数据结构课程指定使用的教材为《数据结构》（附大纲），苏仕华主编，外语教学与研究出版社，2012年版。二、本课程的试卷题型结构及试题难易度试卷题型结构表课程代号023310000课程名称数据结构题型单选题填空题简答题解答题算法阅读题算法设计题合计每题分值113668题数1512353240合计分值151293018161002．试卷按识记、领会、简单应用、综合应用四个认知层次命制试题，四个认知层次在试卷中所占的比例大致分别为：识记占20％、领会占25%、简单应用占35％、综合应用占20％。3．试卷难易程度大致可分为易、中、难三个等级，不同难易度所占的分数比例大致为易30%、中50%、难20%。三、各章内容分数的大致分布章次内容分值第一章概论7分左右第二章线性表15分左右第三章栈和队列10分左右第四章多维数组和广义表8分左右第五章树和二叉树15分左右第六章图15分左右第七章排序15分左右第八章查找15分左右合计100分四、考核重点及难点：章次重点难点第一章概论概念算法的描述和分析算法复杂性分析第二章线性表线性表的逻辑结构线性表的顺序存储、链式存储的表示方法、基本算法及综合应用双链表顺序存储和链式存储的比较第三章栈和队列栈和队列的逻辑结构、操作特点，顺序存储和链式存储上的基本算法，以及栈和队列的综合应用递归算法执行中栈的状态变化，循环队列对边界的处理第四章多维数组和广义表多维数组的存储方式矩阵的压缩存储广义表的表头和表尾的求解压缩存储特殊矩阵和稀疏矩阵的各种运算和应用第五章树和二叉树树和二叉树的定义、性质、存储、各种遍历及其应用树和森林的相互转化哈夫曼树定义、构造和编码二叉树序列确定二叉树二叉树有关的算法实现第六章图图的概念、存储、遍历图的最小生成树、最短路径算法最小生成树最短路算法第七章排序五种内排序方法的基本思想和特定；各自的稳定性、复杂性分析、及其相互比较各种排序算法的实现和性能分析第八章查找顺序查找、二分查找、分块查找、二叉排序树、散列查找的基本思想和实现二分查找和二叉排序树的算法实现五、各题型试题范例及解题要求1．单项选择题（每小题1分，共15分）解题要求：在下列每小题的四个备选答案中，选出一个正确答案，并将其字母标号填入题干的括号内。范例：串是一种特殊的线性表，其特殊性体现在（）A．可以顺序存储 B．数据元素是单个字符C．数元素是字符串D．可以进行插入和删除操作答案：（B）2．填空题（每空1分，共12分）解题要求：直接将答案填在横线上，不需要写出过程。范例：二叉树的第i层的节点个数最多为。答案：2i-13．简答题（每小题3分，共9分）解题要求：写出要点或简述理由。范例：什么样问题的算法可以利用栈结构？请举例说明。解答：当问题满足先进后出（或后进先出）原则时，可利用队列结构；（2分）利用栈的算法有：递归实现、二叉树的非递归前序遍历、拓扑排序等。（1分，给出一例即得分）4．解答题（每小题6分，共30分）题4图解题要求：需要分布完成是写出计算过程，否则只给结果分。范例：已知一个无向图如题4图所示，以①为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。解答：以①为起点，用PRIM算法构造该无向图的最小生成树的过程见答4图答4图 （注：每步得2分，最多得6分。）5．算法阅读题（每小题6分，共18分）解题要求：已知算法功能补全缺失语句，或看完整算法写功能并回答问题。范例1：以下函数为链队列的入队操作，x是要入队的结点的数据域的值，front、rear分别是链队列的对头、队尾指针structnode{ ElemTypedata; structnode*next;};

structnode*front，*rear;void

InQueue(ElemType

x){ struct

node

*p; p=(structnode*)

eq\o\ac(○,1); p->data=x; p->next=NULL; eq\o\ac(○,2); rear=eq\o\ac(○,3);} 解答1：eq\o\ac(○,1)malloc(sizeof(structnode))；（2分）eq\o\ac(○,2)rear->next=p；(2分)eq\o\ac(○,3)p（2分）。范例2：顺序表类型定义如下：typedefintSeqList[100]；阅读下列算法，并回答问题：voidf2(SeqListr，intn){inta,b，i； if(r[0]<r[1]){a=r[0]；b=r[1];}else{a=r[1]；b=r[0]；} for(i=2；i<n；i++) if(r[i]<a)a=r[i]; elseif(r[i]>b)b=r[i]； printf(“a=%d，b=%d。n”，a，b)；}(1)给出该算法的功能；(2)给出该算法的时间复杂度。 解答2：(1)算法的功能是求最大值和最小值；（3分）(2)算法的时间复杂度是O(n)。(3分)6.算法设计题（每小题8分，共16分）解题要求：按给定的结构，写出实现功能的完整的算法函数，由于实现算法的函数不会完全一致，不易给出分步得分，分数可大体如下安排：eq\o\ac(○,1)有思想；（2分）eq\o\ac(○,2)写出关键语句；（4分）eq\o\ac(○,3)完成细节。（2分） 范例：二叉树的存储结构类型定义如下typedefstructnode{intdata； structnode*lchild，*rchild；}BinNode；typedefBinNode*BinTree；编写递归算法，求只有一个孩子结点的结点总数，并求出相应结点值的和。函数的原型为：voidf6(BinTreeT，int*count,int*sum)//*count为只有一个孩子的结点总数，*sum为结点值纸盒，均初始化为0 解答：算法函数 voidf6(BinTreeT,int*count,int*sum) { if(T){ if((T->lchild&&(!T->rchild))||(T->rchild&&(!T->lchild))){ *count+=1; *s