[ 数据结构II模拟试题5 ]
一、单选题（每小题2分，共10小题，20分） 1. 下面说法错误的是
(1）算法原地工作的含义是指不需要任何额外的辅助空间
n
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低
A．(1) B.(1),(2) C.(1),(4) D.(3) 2．下列程序的时间复杂度为
i=0；s=0；
while（s B. O（2n） 2 C. O（n） D. O（n） 3．若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为 A．无头结点的双向链表 B．带尾指针的循环链表 C．无头结点的单链表 D．带头指针的循环链表 4. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150， 则元素A［9］［7］的地址为 A. 429 B. 432 C. 435 D. 438 5．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 A．A，B，C，D B．D，C，B，A C. A，C，D，B D. D，A，B，C 6. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为 A．5 B．6 C．7 D．8 7．以下说法不正确的是 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索 8. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的 关键字时，所需进行的比较次数为 A. n-1 B. n C. n+l D. n+2 9．设置溢出区的文件是 A．索引非顺序文件 B．ISAM文件 C．VSAM文件 D．顺序文件 10. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一 趟两两归并的结果是 A.{25,36,48,72,23,40,79,82,16,35} 1 B.{25,36,48,72,16,23,40,79,82,35} C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82} 二、填空题（每小题2分，共10小题，20分） 11.下面程序段中带下划线的语句的执行次数的数量级是( )。 i=1； WHILE(i 12．已知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结点p的（ ）结点。 q=p; while(q->next!=p)q=q->next; 13. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返 回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为 （ ）。 14．设Q[0..N-1]为循环队列，其头、尾指针分别为P和R，则队Q中当前所含元素个数为（ ）。 15．一棵含999个结点的完全二叉树的深度为（ ）。 16．在 AOV网 中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它表明存在（ ）。 17．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二 叉树B的左子树中有n1-1个结点，右子树中有（ ）个结点。 18. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高， 采用（ ）的方法可降低所需的代价。 19．应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（ ），通过“剪枝”来加速搜索过程。 20. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得 到的输出序列是( )。 三、应用题（每小题5分，共4小题，20分） 21．比较线性表和栈的基本操作的不同点。 22．有一个二叉树按层次顺序存放在一维数组中，如下图所示： 试求：（1）该树的后序遍历序列。 （2）画出该树的后序线索树。 1 2 3 4 5 6 7 8 9 10 11 A C B E D 23．分析顺序查找算法的“监视哨”设置作用 24．对n个整数的序列进行直接选择排序。 （1）算法描述。 （2）并给出实例（52 49 80 36 14 58 61 23 ）的排序过程。 四、算法阅读与分析题（每小题10分，共2小题，20分） 25．算法实现串的堆分配存储结构的插入子串操作，阅读算法，在空白处填入语句或注释。 bool StrInsert (Hstring& S, int pos, Hstring T) { // 若1≤pos≤StrLength(S)＋1，则在串S的第pos个字符之前插入子串T if (pos < 1 || pos > S.length+1) 2 return FALSE; // 插入位置不合法 char S1[S.length] ; // S1 作为辅助串空间用于暂存 S.ch if (（1）) { // T非空，则为S重新分配空间并插入 T p=S.ch; i=0; while (i < S.length) S1[i++] = *(p+i); // （2） S.ch = new char（3）; // 为S重新分配串值存储空间 for ( i=0, k=0; i S.ch[k++] = S1[i]; // 保留插入位置之前的子串 j = 0; while (j S.ch[k++] =（4） // 插入 T while ( i S.ch[k++] = S1[i++]; // 复制插入位置之后的子串 S.length+=T.length; // （5） } // if return TRUE; } // StrInsert 26．设有大小不等的n 个数据组（n个数据组中数据的总数为m），顺序存放在空间区D内,每个数据占一个存储单 元，数据组的首地址由数组S给出，操作后，空间区D和数组S的相互关系仍保持正确。阅读算法，指出功能 和语句s[j]++;的作用。 void Insert（int s[]，ElemType D[]，ElemType x，int i, int m）{ if（i<１|| i>n）｛ printf（“参数错误”）；exit（０）； ｝// if if（i==n） D[m]=x； // 在第n个数据组末尾插入元素x else｛ for（j=m-1;j>=s[i+1];j--）D[j+1]=D[j]; // 第i＋１个数据组及以后元素后移 D[s[i+1]]=x; for(j=i+1;j<=n;j++) s[j]++; } // m++; //空间区D的数据元素个数增1。 }// Insert 五、算法设计题（每小题10分，共2小题，20分） 27．有n个结点的完全二叉树存放在一维数组A[1..n]中，设计算法BiTree Creat实现二叉链表的二叉树 。 28．设计算法purge_Sq实现删除顺序表SqList中重复元素，指出其算法的时间复杂度。 [ 数据结构II模拟试题5答案] 一、单选题 1、D 2、A 3、B 4、C 5、D 6、D 7、B 8、A 9、B 10、A 二、填空题 11. log2n 12．前驱13.″EFGH″14．（ R-P+N）% N；15．10 16．死循环17．n2+n3 18. 附加文件 19．限界函数20. 4231 三、应用题 21．参考答案 3 主要区别是对插入和删除操作的限制。 如线性表允许在表内任一位置进行插入和删除；而队列只允许在表尾一端进行插入，在表头一端进行删除；所以也称队列为受限的线性表。表头为队列头；表尾为队列尾。 插 入 删 除 线性表 Insert(L,i,x) Delete(L,i) (1≤i≤n+1) (1≤i≤n) 队列 Insert(L,n+1,x) Delete(L,1) 22．参考答案 （1）后序遍历序列 C E D B A （2）后序线索树 A C B E D 23．参考答案 为了考虑查找不成功的情况,在每次进行关键字的比较前，首先要判断循环变量i是否数组越界，这对算法来说是必要的。如果每步省略数组下标是否越界的判断，则可以大大提高算法运行的效率。为此，可以利用预留的0号单元，作为所设的“监视哨”控制循环变量i的出界。 假设数据从后向前比较，监视哨设在数组低端 L.elem [0] = k 将算法中的判断语句 while (i <= L.length &&L.elem [i] != k) ++i; 改为 while (L.elem [i] != k) --i; 这样，当在查找表中不存在其关键字等于给定值的数据元素时，i必等于0,并且这样的处理并不影响查找成功的情况。 24．参考答案 （1）直接选择算法描述： [1] 第1趟，从n个记录中，经过比较选出关键字值为最小的记录，并与第1个记录交换位置。 [2] 第2趟，从余下的n-1个记录中选择出当前关键字最小的排序，并与第 2个记录交换位置。 [3] 第i趟，在无序的第i个到第n个的n-i+1 个记录中选出关键字最小的记录，与第i个记录进行互换。 [4] 以此类推，直至第n-1趟排序结束。 （2）初始状态 52 49 80 36 14 58 61 23 i=1 [14] 49 80 36 52 58 61 23 i=2 [14 23] 80 36 52 58 61 49 i=3 [14 23 36] 80 52 58 61 49 i=4 [14 23 36 49] 52 58 61 80 i=5 [14 23 36 49 52] 58 61 80 i=6 [14 23 36 49 52 58] 61 80 i=7 [14 23 36 49 52 58 61] 80 排序结果 [14 23 36 49 52 58 61 80 ] 4 四、算法阅读与分析题 25．参考答案 （1）T.length （2）暂存串S （3）[S.length + T.length ] （4）T.ch[j++]; （5）更新串 S 的长度 26．参考答案 （1）功能：将新数据x插入到第i个数据组的末尾且属于第i 个数据组的算法，插入后，空间区D和数组S的相互关系仍保持正确。 （2）s[j]++;的作用：维护空间区D和数组S的关系。 五、算法设计题 27．参考答案 BiTree Creat(ElemType A[],int i){ // n个结点的完全二叉树存于一维数组A中，初始调用时,i=1。建立以二叉链表表示的完全二叉树. BiTree tree; if (i<=n){ tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i]; if(2*i>n) tree->lchild=null； else tree->lchild=Creat(A,2*i)； if(2*i+1>n) tree->rchild=null； else tree->rchild=Creat(A,2*i+1)； }// if return (tree)； }//Creat 28．参考答案： void purge_Sq( SqList &L ) {// 删除顺序表L中的重复元素 k = -1; // k 指示新表的表尾 for (i=0; i while(j<=k && L.elem[j]!=L.elem[i]) ++j; // 在新表中查询是否存在和L.elem[i]相同的元素 if ( k==-1 || j>k ) // k=-1 表明当前考察的是第一个元素 L.elem[++k] = L.elem[i]; } // for L.length = k+1; // 修改表长 } // purge_Sq 此算法的时间复杂度为O (L.length2 )。 5
相关推荐：
loading