数据结构(第二版)模拟测试题4套及答案.doc

试卷B一、选择题（本题共20分,每题2分）1在数据结构中，从逻辑上可以把数据结构分成（ ） 。 A动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ）count=0; for(k=1;k=n;k*=2) for(j=1;j=n;j+) count+; A.O(nlog2n) B.O(n) C.O(log2n) D.O(n2) 3. 以下描述错误的是：（ ）A. 线性表是n个数据元素的有限非空集合。B. 栈和队列都是操作受限的线性表。C. 串（或字符串）是由零个或多个字符组成的有限序列。D. 非空栈中的栈顶指针top始终指向栈顶元素的下一个位置。4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q（最大队列长度MAXSIZE）为满队列的条件是( )。A. Q.front=Q.rear B. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZE D. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。 A. 3 B. 4 C. 5 D. 6 6. 设矩阵A（如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 Bn(n+1)/2中，对下三角部分中任一元素 ai,j(ij)，在一维数组 B 的下标位置k的值是（ ）。A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j 7. 有一个有序表为5, 18，23, 33, 42, 54,56,78，当折半查找56时，经过（ ）次比较后查找成功。A. 1 B. 2 C. 3 D. 88. 一组记录的排序关键字为（39，19，36，68，35，84），则利用快速排序方法进行正序排列时，以第一个记录为基准得到的一次划分结果为（ ）。A. 35，36，19，39，68，84 B. 19，35，36，39，68，84C. 35，19，36，39，84，68 D. 35，19，36，39，68，849.若对下图a中的二叉树进行先序线索化，则结点x的左、右线索指向的结点分别是（ ）A. e,c B. e,a C. d,c D. b,abdxeac (a) (b)10. 已知一有向图的邻接表存储结构如上图b所示，根据有向图的广度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是（ ）。 A. v1，v2，v3，v5，v4 B. v1，v3，v2，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2二、填空题（本题共 20 分，每题2分）1. 设无向图G中顶点数为n，则图G最多有_条边2. 在一个长度为n（n1）的顺序表中的第i个元素（1in）之前插入一个元素时，需向后移动_个元素。3. 在一个双向链表中，要删除p所指结点，应执行的操作序列为_。4. 有一棵树如右图所示，回答下面问题： 树的度：_；树的深度：_； 结点C的孩子结点：_；结点F的祖先结点：_。5. 一棵完全二叉树的第5层有5个结点，则这棵完全二叉树共有_个结点。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0ABCDE6. 已知无向图G的邻接矩阵如下图所示，则图G是_图(连通/非连通)，顶点A的度为_。7. 在一棵平衡二叉树中，每个结点的左子树深度与右子树深度之差可以是 。8若一组记录的关键字序列为（50，40，95，20，15，70，60，45，80），要对其按关键字从小到大进行堆排序时，则创建的初始堆序列为_。9.对n个不同的关键字从小到大进行冒泡排序，最好情况下，需要经过比较_次将其排好；最坏情况下，需要经过比较_次排好。10. 已知一个有向图的边集为,，则由该图产生的一种可能的拓扑序列为_ 。 三、应用题（本题共40分，1-4每小题5分，5-6题每小题10分）1. 利用普里姆算法，对于下面所示的连通图，从结点a出发，构造最小生成树。 2. 设给定权集 w=2，4，3，7，8，9，试构造关于 w 的一棵Huffman树，并计算所构造Huffman树的带权路径长度 WPL。3. 已知一棵二叉树的中序序列为CBEDAHGIJF，后序序列为CEDBHJIGFA，画出该二叉树。 4. 设数据集合D=24，13，53，37，90，48，依次取D中各数据，构造一棵平衡二叉树，画出构造过程（说明平衡旋转的类型）及结果。5. 假设有一组关键字32，01，23，14，55，20，84，27，68，要求：（1）散列函数为 H(key) = key % 13，计算这组关键字的散列地址并填入下表：Key320123145520842768H（key）冲突次数（2）采用线性探测法解决冲突，在0-12的散列地址空间中对该关键字序列构造散列表，将各关键字填入下表： 地址0123456789101112关键字（3）计算成功查找时的平均查找长度ASLS ，要求写出计算过程和结果：ASLS =6. 下图是一个有7个顶点的网图，边上的权值为相邻两顶点的距离。使用Dijkstra算法，计算顶点a到所有其余顶点的最短路径。计算过程和结果填入下表，要求：(1)从第1步至第6步，每步选择的顶点填入表格倒数第二行；（4分）(2)表格中D值在填写时，请注意存储两部分信息：顶点a至其余顶点的“当前最短距离”，以及相应的路径顶点信息。将每一步的计算过程填入相应的位置。（6分）终点从a到各个终点的D值和最短路径的求解过程步骤1步骤2步骤3步骤4步骤5步骤6b距离值顶点序列c距离值顶点序列d距离值顶点序列e距离值顶点序列f距离值顶点序列g距离值顶点序列筛选顶点终点集S四、算法设计题（本题共20分）1. 编写算法，实现将值为e的元素插入到单链表L的第i个结点的位置上。(本题10分)单链表结构定义如下：typedef struct LNode ElemType data; Struct Lnode *next; Lnode,*LinkList; 2. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。（本题10分）参考答案一、选择题 答案 （本题共20分，每小题2分）1.B 2. A 3.A 4.C 5. C6.D 7. C 8.D 9.A 10.B二、填空题 答案 （本体共20分，每小题2分）1. n(n-1)/2。2. n-i+1 。3. p-prior-next=p-next; p -next-prior =p-prior; free(p);4. 3_;4 ，G; A,B5. 206. 连通图; 27. 0,1,-1 8. 15,20,60,45,40,70,95,50,80(小顶堆)/ 95,80,70,45,15,50,60,40,20（大顶堆）9. n-1;n(n-1)/210. a,c,b,d,e 三、应用题 答案要点（本题共40分，1-4每小题5分，5-6题每小题10分）1. 最小生成树2.解：哈夫曼树如图其带权路径长度 WPL=72+82+43+24+34+92=80 3. 二叉树的结构为：4. 平衡二叉树的构造过程及结果：RL243753904813 132453903748 5.（1）关键字的散列地址并填入下表：（4分）key320123145520842768H(Key)6110137613冲突次数000100232（2）采用线性探测法解决冲突，在0-12的散列地址空间列构造散列表，（3分） 地址0123456789101112关键字011455276832208423（3）计算成功查找时的平均查找长度ASLS ，要求写出计算过程和结果：（3分）ASLS =(15+21+32+41)/9=17/96.最短路径： （10分）终点从a到各个终点的D值和最短路径的求解过程步骤1步骤2步骤3步骤4步骤5步骤6b距离值151515151515顶点序列（a,b）（a,b）（a,b）（a,b）（a,b）（a,b）c距离值2顶点序列(a,c)d距离值12121111顶点序列(a,d)(a,d)(a,c,f,d)(a,c,f,d)e距离值1010顶点序列(a,c,e)(a,c,e)f距离值6顶点序列(a,c,f)g距离值161614顶点序列(a,c,f,g)(a,c,f,g)(a,c,f,d,g)筛选顶点cfedgb终点集Sa,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,fe,d,g,b四、 算法设计题 （只列出答案要点，可以有不同的答案，酌情给分）1、参考代码如下：（10分） status ListInsert(LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个位置插入值为e的新结点p=L; j=0;while(p&jnext; +j;if(!p|ji-1) return ERROR;s=(LinkList) malloc (sizeof(LNode);s-data=e;p-next=s;s-next=p-next;2. 主要代码如下：（10分）算法思路：对二叉排序树来说，其中序遍历序列为一个递增有序序列，因此，对给定的二叉树进行中序遍历，如果始终能保持前一个值比后一个值小，则说明该二叉树是一棵二叉排序树。中序遍历整棵二叉树，访问根结点时将根结点信息存入一个数组中，以用来比较中序遍历后序列是否为空。比较数组元素时，从下标为0的数组元素开始比较，先将下标为i=0的ai与下标为1的ai+1比较，如果aiai+1，则结束比较，即该二叉树不是二叉排序树，否则继续比较，直至比较完整个数组元素。intIsSearchTree(structBitree*root) if (!root)return1; elseif(!(root-lChild)&!(root-rChild) /左,右子树都没有 return1; elseif(root-lChild)&!(root-rChild) /只有左子树 if(root-lChild-dataroot-data) return0; /0:不是二叉排序树 elsereturnIsSearchTree (root-lChild);elseif (root-rChild)&!(root-lChild)/只有右子树 if(root-rChild-datadata) return0; /0:不是二叉排序树elsereturnIsSearchTree(root-rChild);else /左,右子树都有 if(root-lChild-dataroot-data)|(root-rChild-datadata) return0; /0:不是二叉排序树else return(IsSearchTree(root-lChild)&IsSearchTree(root-rChild);试卷一一、选择题（本题共30分,每题2分）1. 计算机识别、存储和加工处理的对象被统称为_。A. 数据 B. 数据元素 C. 数据结构 D. 数据类型2. 已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列_。A1234B4321 C2143D41233. 链表不具有的特点是_。A. 随机访问 B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比4. 设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是_InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x)A. a B. b C.NULL D.x5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行_。Ap=q-next; p-next=q-next;free(p);Bp=q-next; q-next=p; free(p);Cp=q-next; q-next=p-next; free(p);Dq-next=q-next-next; q-next=q; free(p);6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是_。A110 B108 C100 D1207. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面关于线性表的叙述错误的是_。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是_。A.Push(A) Push(B) Pop(A) Pop(B)B.Push(A) Push(B) Pop(B) Pop(A)C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B)10.下列查找方法中哪一种不适合元素的链式存储结构_。A顺序查找 B分块查找 C二分查找 D散列查找11. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是_。A. 快速排序 B.希尔排序 C.堆排序 D.冒泡排序12. 设一棵二叉树的深度为k，则该二叉树中最多有_个结点。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四个选项中，能构成堆的是_。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20, 15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边_。An(n-1)/2 Bn-1 Cn Dn+115.栈和队列的共同特点是_。A. 都是操作受限的线性表 B.都是先进后出 C. 都是后进先出 D.无共同点二、填空题（本题共 10分，每空1分）1. 若经常需要对线性表进行查找操作，则最好采用_存储结构。2. 某带头结点单链表的头指针为L，判定该单链表非空的条件_。3. 数据的逻辑结构包括集合、_、_和图状结构四种类型。4. 图的两种遍历方式为：广度优先遍历和_。5. 线性表的链式存储结构中的结点包含_域和_域。6. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_上。7. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct int stack100; int top; seqstack;void push(seqstack *s,int x)if (s-top=99) printf(“overflow”);else _(1)_;_(2)_;三、应用题（本题共40分） 1 设散列表长度为11，散列函数h(key)=key % 11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）2有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）3已知图G=(V,E)，其中V=1,2,3,4,5, E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)。要求完成如下操作：（6分）（1）写出图的邻接矩阵（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。4已知序列503，87，512，61，908，170，897，275，653，462，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）（1）直接插入排序（2）基数排序5对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分） 6. 将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）ABCDEFGH四、算法题（本题共20 分）1完成中序遍历二叉树。Typedef struct node Char data; Struct node *lchild;Struct node *rchild;BTreeNode,*LinkBtree; Void InOrder(LinkBtree Bt_pointer) If(Bt_pointer!=NULL) _(1)_; _(2)_; _(3)_; 2.完成二分查找算法：#Define n 10typedef int KeyType;typedef struct KeyType key; NodeType;Typedef NodeType SeqListn+1;int BinSearch (SeqList R,KeyType k)int low=1,high=n,mid;while(_（4）_) mid=(low+high)/2; if(Rmid.key=k) return mid; if(Rmid.keyk) _（5）_; else _（6）_;return 0;3.编写算法实现直接插入排序。（8分） 参考答案一、选择题（本题共30分,每题2分）123456789101112131415ADABCBBDACBDCBA二、填空题（本题共10分，每空1分）1） 顺序 2）L-next!=NULL3） 线性结构 树形结构 4） 深度优先遍历5） 数据 指针 6）左子树7） s-top+ s-stacks-top=x 三、应用题（本题共40分）1、（6分）H(1)=1 H(13)=2 H(12)=1 冲突 ， H1=2 冲突， H2=3 H(34)=1 冲突 ， H1=2 冲突， H2=3 冲突， H3=4 H(38)=5 H(33)=0 H(2)=2 冲突 ， H1=3 冲突， H2=4 冲突， H3=5 冲突， H4=6 H(22)=0 冲突 ， H1=1 冲突， H2=2 冲突， H3=3 冲突， H4=4 冲突，H5=5 冲突， H6=6 冲突， H7=7 ASL=(1+1+3+4+1+1+5+8)/8=24/8=3 2、（6分）1104961212829321415Wpl=2493、图的邻接矩阵：（3分） 广度优先序列： 1 2 3 4 5（3分）0 1 1 1 01 0 1 0 11 1 0 1 01 0 1 0 10 1 0 1 0 4、 1）（503）87 512 61 908 170 897 275 653 462（5分） （87 503）512 61 908 170 897 275 653 462 （87 503 512）61 908 170 897 275 653 462（61 87 503 512）908 170 897 275 653 462（61 87 503 512 908）170 897 275 653 462（61 87 170 503 512 908）897 275 653 462（61 87 170 503 512 897 908）275 653 462（61 87 170 275 503 512 897 908）653 462（61 87 170 275 503 512 653 897 908）462（61 87 170 275 462 503 512 653 897 908） 2）第一趟： 170 61 512 462 503 653 275 87 897 908（5分） 第二趟： 503 908 512 653 61 462 170 275 87 897 第三趟： 61 87 170 275 462 503 512 653 897 9085、（5分） ABDEFGHC6. （7分）层序遍历序列:ABECFDGH四、算法题（本题共20分）1、 （1）InOrder (Bt_pointer -lchild); （2分） (2) printf(“%c”, Bt_pointer -data);（2分） (3) InOrder (Bt_pointer -rchild); （2分）2、 （4） low=high （5）high=mid-1; （6） low= mid+1; （6分）3、 void InsertSort(int a,int n) （8分） int i,j; for(i=2;i=n;i+) a0=ai; j=i-1; while(a0next; p-next=q-next;free(p);Bp=q-next; q-next=p; free(p);Cp=q-next; q-next=p-next; free(p);Dq-next=q-next-next; q-next=q; free(p);6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是_。A110 B108 C100 D1207. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是_。A. n-i B. n-i+1 C. n-i-1 D. i8下面关于线性表的叙述错误的是_。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是_。A.Push(A) Push(B) Pop(A) Pop(B)B.Push(A) Push(B) Pop(B) Pop(A)C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B)10.下列查找方法中哪一种不适合元素的链式存储结构_。A顺序查找 B分块查找 C二分查找 D散列查找11. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是_。B. 快速排序 B.希尔排序 C.堆排序 D.冒泡排序12. 设一棵二叉树的深度为k，则该二叉树中最多有_个结点。 A 2k-1B. 2kC. 2k-1D. 2k-113. 下列四个选项中，能构成堆的是_。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20, 15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1514. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边_。An(n-1)/2 Bn-1 Cn Dn+115.栈和队列的共同特点是_。A. 都是操作受限的线性表 B.都是先进后出 C. 都是后进先出 D.无共同点二、填空题（本题共 10分，每空1分）8. 若经常需要对线性表进行查找操作，则最好采用_存储结构。9. 某带头结点单链表的头指针为L，判定该单链表非空的条件_。10. 数据的逻辑结构包括集合、_、_和图状结构四种类型。11. 图的两种遍历方式为：广度优先遍历和_。12. 线性表的链式存储结构中的结点包含_域和_域。13. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_上。14. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedef struct int stack100; int top; seqstack;void push(seqstack *s,int x)if (s-top=99) printf(“overflow”);else _(1)_;_(2)_;三、应用题（本题共40分） 1 设散列表长度为11，散列函数h(key)=key % 11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）2有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）3已知图G=(V,E)，其中V=1,2,3,4,5, E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)。要求完成如下操作：（6分）（1）写出图的邻接矩阵（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。4已知序列503，87，512，61，908，170，897，275，653，462，分别写出执行下列排序算法的