数据结构II试卷3
数据结构II模拟试题3 一、单选题(每小题2分，共10小题，20分)1. 若将数据结构形式定义为二元组(K，R)，A. 操作的有限集合C.类型的有限集合2. 下述程序段中语句的频度是s=0;for(i=1;i<m;i+)for(j=0;j<=i;j+)s+=j;(m +1)(m -1)A. 2(m + 2)(m -1)C.2其中K是数据元素的有限集合，则R是K上B. 映象的有限集合D.关系的有限集合m( m - 1 )B. 2m( m +1).23. 若要在单链表中的结点p之后插入一个结点s,则应执行的语句是A. s->next=p->next; p->next=s;C. p->next=s->next; s->next=p;B. p->next=s; s->next=p->next;D. s->next=p; p->next=s->next;4. 已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为typedef struct node char data8;struct node *next; LinkStrNode;A. 1/4B. 1/2C. 2/3D. 3/45. 设有一个顺序栈，6个元素1、2、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则 栈的容量至少应该是A. 2B. 3C. 5D. 66. 一个具有1025个结点的二叉树的高h为A. 11B. 10C. 11至1025之间D. 10至1024之间7. 在一个具有n个顶点的有向图中，所有顶点的出度之和为Dut，则所有顶点的入度之和为A. DoutB.叽-1"C. Dout+1D. n8. 已知散列表的存储空间为T0.18，散列函数H (key) =key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T5=39，T6=57和T7=7，则下一个关键字23插入的位置是B. T4A. T2C. T8D. T109. 设计求迷宫问题的路径算法采用的主要技术是A.回溯法B.分支限界法C.分治法D. A和B10. 下列关键字序列中，构成小根堆的是A.84,46,62,41,28,58,15,37B.84,62,58,46,41,37,28,15C.15,28,46,37,84,41,58,62D.15,28,46,37,84,58,62,41二、填空题（每小题2分，共10小题，20分）11. 下面程序段中带有下划线的语句的执行次数的数量级是（）i=n*nWHILE i<>1 i=i/2;12. 已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是（）。13. 设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B0，元素a52存储在B11，则矩阵元素a36存储在（）中。1114. 假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17,则当前尾指针的值为（）。15. 已知完全二叉树T的第5层只有7个结点，则该树共有（）个叶子结点。16. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生，该算法弧上的权出现（）情况时，不能正确产生最短路径。17. 高度为h的2-3树中叶子结点的数目至多为（）。18. 假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行（）次探测。12.子集树通常有2n个叶子结点，结点的总个数为2n+1-1，算法的时间复杂度为（）。10. 已知广义表LS为空表，则其深度为（）。三、应用题（每小题5分，共4小题，20分）21. 三对角矩阵压缩存储计算推导。22. 举例说明两类典型的解空间树。23. 所谓最小不平衡子树是指：以离插入结点最近、且平衡因子绝对值大于1的结点作根结点的子树。可归纳为四 种情况：LL型、RR型、LR型和RL型。已知调整前LR型示意图。（1）画出调整后的结构示意图。（2）调整后的指针及平衡因子变化。a插入新结点S后失去平衡24. 按下列三元组的顺序输入：弧尾、弧头、权值，有向图G中的输入序列为：（1,2,3）、（1,3,4）、（1,4,5）、（3,2,1）、 （3,5,2）、（4,5,7）、 （6,4,5）、（6,5,4）（1）画出该图的邻接矩阵。（2）判断该图G是否为有向无环图，若是则画出其该图的逻辑结构，并在图上标出关键路径。四、算法阅读与分析题（每小题10分，共2小题，20分）25. 下面的算法的功能是在数组A1.n中，建立一个带有头结点的循环链表，并对链表中的数据从小到大排列， 重复的数据在链中只保存一个。阅读算法，在空白处填入语句或注释。LinkList Creat_CL（ElemType A,int n）/由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点h=(LinkedList)malloc(sizeof(LNode);/ 申请结点h->next=h; / (1)for(i=0;i<n;i+)pre=h; p=h->next;while( (2)&& p->data<Ai) / 查找 Ai的插入位置 pre=p; p=p->next;/ whileif(p=h | p->data!=Ai) / (3)s=(LinkList)malloc(sizeof(LNode);s->data=Ai;(4)s->next=p; /将结点、链入链表中/ if/for(5)/ Creat_CL26. 阅读算法，指出功能和变量s的作用。void LinkedList_Select_Sort(LinkedList &L)/单链表上的简单选择排序算法for(p=L;p->next->next;p=p->next) q=p->next; x=q->data;for(r=q,s=q;r->next;r=r->next)/在q后面寻找元素值最小的结点if(r->next->data<x) x=r->next->data; s=r;if(s!=q) /找到了值比q->data更小的最小结点s->next p->next=s->next;s->next=q;t=q-next;q-next=p-next-next;p->next->next=t; /交换q和s->next两个结点/for/LinkedList_Select_Sort五、算法设计题(每小题10分，共2小题，20分)27. 设二叉树采用二叉链表存储结构，结点的数据域data为字符类型。设计实现使用栈后序遍历非递归算法。28 .设计算法InsertOrderList实现有序顺序表OrderList的插入算法，指出其时间复杂度。数据结构II模拟试题3答案一、单选题I、D 2、A 3、B 4、C 5、D 6、D 7、B 8、A 9、B 10、A二、填空题II. log2n2 12. p->next! =NULL 13. B 17) 14. 10 15. 11 16.负值 17. 3h-i 18. (k+1)/2 19. O(2n) 20. 1三、应用题21. 参考答案三对角矩阵是除主对角线及主对角线上下各一个元素外，其余元素都为零的矩阵。对处于三对角区的元素气.，它前面的i-1行中有非零元素3*(i-1)-1个，它处于本行中的第j-i+2个非零元 素处，所以为第3*( i-1)-1+ j-i+2=2*( i-1)+ j个非零元素，此式也正好符合第一行的两个非零元素的情况。故有k=2*( i-1)+ j对角矩阵公式K=2(i-1)+j-1|i-j|W1(k=0,1,23n-2)22. 参考答案(1) 子集树所给的问题是从n个元素的集合中找出满足某种条件的子集时，相应的解空间是子集树。这类子集树通常有2 个叶子结点，结点的总个数为2n+1-1，算法的时间复杂度为O(2n)。如背包问题。(2) 排列树当所给的问题是确定n个元素满足某种性质的排列时，该问题的解空间树为排列树。排列树通常有n!个叶子结 点。此类问题的算法的时间复杂度为O(n!)。如旅行售货商问题。23. 参考答案(1)画出调整后的结构示意图。C,CBLRALSR(2)调整后的指针及平衡因子变化。调整前 A->bf=2； B-bf=T； B=A->lchild； C=A->rchild；调整后 B-rchild=C-lchild； A-lchild=C-rchild； C->lchild=B； C->rchild=A；调整后二叉树的根结点C应接回原A处。令A原来的父指针为FA。if (S-key<C-key) / 在 Cl 下插入 S A->bf=-1；B->bf=0 ； C->bf=0； if (S->key >C->key) / 在 Cr下插入 S A->bf=0；B->bf=1 ；C->bf=0； if (S->key =C->key)/ C本身就是插入的新结点S A->bf=0；B->bf=0；24.参考答案：(1)1234561-1345-1-12-1-1-1-1-1-13-11-1-12-14-1-1-1-17-15-1-1-1-1-1-16-1-1-154-1(2)该图G是有向无环图。关键路径三条。1-3-21-4-56-4-5四、算法阅读与分析题25. 参考答案(1) 形成空循环链表(2) p!=h(3) 重复数据不再输入(4) pre->next=s;(5) return h;26. 参考答案(1) 功能：实现单链表的直接选择排序。(2) 作用：变量s是当前最小值结点的指针。五、算法设计题27. 参考答案void postorder_f(BinTree T) Stack s; /定义栈 sBinTree p,q;if (T= =NULL) return;InitStack(s);P=T;dowhile (p)Push(s,p);if (p->lchild)p=p->lchild;else p=p->rchild;while (!Stack Empty(s)&&StackTop(s, q)&&q->rchild= =p)Pop(s,p);printf(p->data);
