【答案】模式匹配；
模式串 2． 已知如下程序段 语句1执行的时间复杂度为_____语句2执行的时间复杂度为_____语句3执行的时间复杂度为_____语句4执行的时间复杂度为_____。
【答案】1n＋1 2n 3nn＋3/2 4nn＋l/2 【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋n＋l 加起来就是nn＋3/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即nn＋l/2。
3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法， 请在算法空格处填上正确的语句。
设线索二叉树的结点数据结构为 其中left 指向其左孩子， 第 2 页，共 67 页 ， left 指向其前驱；
，right 指向其右孩子，，，right 指向其后继。
【答案】 4． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1 【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
5． 在一个具有n 个单元的顺序栈中，假定以地址高端即下标为n 的单元 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。
【答案】top ﹣1 【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。
6． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。
7． 文件由_____组成；
记录由_____组成。
【答案】记录；
数据项 8． 组成串的数据元素只能是_____。
【答案】字符 9． 设二维数组A 的行和列的下标范围分别为[08]和[010]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b50处的元素为_____。
【答案】A[2][3] 【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是ll*i＋j ＋l ﹣l*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。
10．实现字符串拷贝的函数strcpv 为 _____ 第 3 页，共 67 页 【答案】s＝*t或*s＝*t＝\0’ 二、单项选择题 11．设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。
A. 线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 【答案】D 【解析】用栈更合适，如果是左括号，进栈；
如果是右括号，看栈顶是不是左括号，如果是，则左括号出栈；
否则不配对可以直接结束算法 。处理完所有符号号，如果栈为空则配对成功。
12．有向带权图如下图图所示, 若采用迪杰斯特拉Dijkstta算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图 A.d , e , f B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
第 4 页，共 67 页 ------------------------------------- ------------------------------------- 一、填空题 ------------------------------------- ------------------------------------- 考研试题 -------------------------------------