《2017年南通大学计算机科学与技术学院919C考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年南通大学计算机科学与技术学院919C考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南通大学计算机科学与技术学院919C考研导师圈点必考题汇编一、填空题1 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】 【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。 2 N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_个非零元素。【答案】2（N-1）【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非
2、零元素。 3 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 第 2 页，共 68 页为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长
3、度； sub （S , i , 1） 返回S 中第i 个字符； 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12）取栈顶操作符 操作符取出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后若ch 是操作数且栈非空，则形成部分中缀表达式栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理 4 对n 个记录的表rl.n进行简单选择排序，所需进行的关键字间的比较次数为_。【答案】n （n-1）/2【
4、解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+.+l=n（n-l ）/2。 5 在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【答案】出度为0【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。 6 求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树e【答案】克鲁斯卡尔【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。 第 3 页，共 68 页 7 对单链表中元素按插入方法排序
5、的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。 置空链表，然后将原链表结点逐个插入到有序表中当链表尚未到尾，p 为工作指针查P 结点在链表中的插入位置，这时q 是工作指针将P 结点链入链表中是q 的前驱，u 是下个待插入结点的指针【答案】（1）（2）（3）（4）（5） 8 高度为h 的堆中，最多有_元素，最少有_个元素。【答案】 当最后一层只有 【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为 9 组成串的数据元素只能是_。【答案】字符10设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：【答案】33【解析】设存储的元素的行标为i ，列标为j 。若则的地址为 将代入得33。则的地址为若，）则的地址为_。二、选择题11最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。A.B.C.D. 【答案】B【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采用来判定队满，其中表示队列的长度。第 4 页，共 68 页一、填空题考研试题
