数据结构模拟习题10.doc

模拟试题10一、选择题（每小题1分，共10分）1、若线性表最常用的操作是存储第i个元素及其前驱元素的值，则采用_B_存储方式最节省时间。(A)单链表(B)双向链表(C)单循环链表(D)顺序表2、串的长度是_D_。(A)串中不同字母的个数(B)串中不同字符的个数(C)串中所含字符的个数，且大于0(D)串中所含字符的个数3、数组A15,16的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为_A_。(A)1140(B)1145(C)1120(D)11254、若用数组S1.n作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是_C_。(A)S1的栈底位置为0，s2的栈底位置是n+1(B) S1的栈底位置为0，s2的栈底位置是n/2(C) S1的栈底位置为1，s2的栈底位置知是n(D) S1的栈底位置为1，s2的栈底位置是n/25、队列操作的原则是_A_。(A)先进先出 (B)后进先出(C)只能进行插入(D)只能进行删除6、在有n个结点的二叉链表中，值为非空的链域的个数为_.(A)n-1(B)2n-1(C)n+1(D)2n+17、某二叉树的中序序列和后序序列正好相反，则该二叉树一定是_的二叉树。(A)空或只有一个结点(B)高度等于其结点数(C)在任一结点无左孩子(D)任一结点无右孩子8、在具有n个结点且为完全二叉树的二叉排序树中查找一个关键值，其平均比较次数的数量级为_。（A）O(n) (B)O(log2n) (C)O(nlog2n) (D)O(n2)9、若表R在排序前已按键值递增顺序排列，则_算法的比较次数最少。(A)直接插入排序(B)快速排序(C)归并排序(D)选择排序10、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（log2n）的是_。(A)堆排序(B)冒泡排序(C)简单选择排序(D)快速排序二、判断题（每题1分，共10分，对的打，错的打）1、线性表的唯一存储形式就是链表。（ ）2、已知指针P指向链表L中的某结点，执行语句P=P-next不会删除该链表中的结点。（ ）3、在链队列中，即使不设置尾指针也能进行入队操作。（ ）4、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ）5、对称矩阵的存储只需要存储一半的数据元素。（ ）6、一棵二叉树的中序遍历序列与该二叉树转换成森林的后序遍历序列相同。（ ）7、用Prim算法和KruskAI算法求最小代价生成树的代价不一定相同。（ ）8、折半查找说法的前提之一是线性表有序。（ ）9、对相同关键字集合，以不同次序插入初始为空的树中，一定得到不同的二叉排序树。（）10、对一无序数据序列而言，用堆排序比用直接插入排序花费的时间多。（）三、填空题（每题2分，共16分）1、设单链表中指针P指向结点A，若要删除A之后的结点（假设存在），则需要修改指针的操作为_。2、对于一个以顺序实现的循环队列Q0.m-1,队头，队尾指针分别为f,r，队列判空的条件是_。3、已知字符串S1=ABCDEFGHIJKLMNOPQRSTUVW，由如下运算可得到串S2:S2=CONCAT(SUB(S1,19,3),SUB(S1,4,2),SUB(S1,14,1),SUB(S1,20,1),则S2=_。4、具有64个结点的完全二叉树的深度为_。5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数_。6、图1中v3的入度和出度分别为_。7、具有n个定点的连通图至少有_条边，而具有n个顶点的强连通图则至少有_条边。8、在有序表A118中，采用二分查找算法查找元素值等于A7的元素，所比较过的元素的下标依次为_。9、直接选择排序算法在最好情况下所做的交换元素的次数为_。四、简答题（每小题5分，共30分）1、已知一棵树的双亲表示存储映像图如下所示，请画出该树的逻辑示意图。下标DataParent123456789101112ABCDEFGHIJKL5161085583842、已知一带权有向图的邻接矩阵表示如下，请画出其逻辑图。3、已知一个有向图如图2所示，请画出从A点出发的深度优先生成树。 4、以1,3,6,7,9,15,22为权值，构造一棵Huffman树，并求出其WPL值。5、已知图3所示的二叉排序树的各结点的值依次为19，请写出该二叉排序树的按层次遍历的结果。6、对下面数据表，写出采用快速排序法的前两层递归调用的结果。（25，10，20，31，5，100，16，3，44，61，18，81，38，40，15）五、程序填空题（第1，2题各6分，第三题3分，共15分）1、以下算法为二分查找算法，在空格处填上合适语句或表达式使算法完整。（每空2分）int BinSearch(SqList R,KeyType K)/参数R为线性表，元素从0到n，字段key为关键字，参数K为待查关键字int i=0,j=n; /*查找区间初始化*/int m;while (iK)_; /*将查找区间定为左半边*/else_; /*将查找区间定为右半边*/ ；/*找不到该元素*/2、以下算法将元素递增排列的顺序存储线性表A和B的元素的交集存入线性表C中，在空格处填上合适语句或表达式使算法完整（6分）void SqList_InterseCt(SqList A,SqList B,SqList &C) int i=1,j=1,k=0; /*下标初始化，A、B、C的下标都从1开始*/ while(i=A.num&j=B.num) /*A,B表均未到表尾*/ if（A.elemi0) printf(w, ); p(w-1); p(w-1); 六、编程题（共15分）1、编写函数，用于实现将一棵二叉树中所有子树左、右交换。二叉树类型定义如下：（满分6分）typedef struct node datatype data; struct node *left; struct node *right; *BTREE;2、写出函数用于删除元素递增排列的带头结点单链表L中值大于mink且小于maxk的所有元素，并给出其时间复杂度。已知链表类型定义如下：（满分9分）typedef struct node int data; struct node *next; *LinkList;模拟题10答案一、选择题12345678910B DACACDBAA二、判断题12345678910三、填空题1、p-next=p-next-next2、f=r3、STUDENT4、75、1296、2和17、n-1 n(n-1)/28、94679、0四、简答题1、2、3、A,C,F,G,D,E,B4、WPL=41+43+63+15*2+73+93+222=1565、层次遍历结果：5，1，9，4，6，2，7，3，86、第一趟：15102018531625446110081384031 第二趟：31051518201625314038448110061 五、程序填空题、阅读题1、（1）j=m-1(2) i=m+1(3) return -12、（1）i+ (2) A.elemiB.elemj (3) k+3、3211211六、编程题1、实现一棵二叉树所有子树的左右交换。 void exchange(BTREE Bt) BTREE p; if(Bt!=NULL) exchange(Bt-left); exchange(Bt-right); p=Bt-left; Bt-left=Bt-right; Bt-right=p; 2、在带头结点的单链表L中，删除值大于mink且小于max