数据结构(第二版)-模拟试题自测卷AB卷带答案1.doc
试卷一一、选择题（本题共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.key>k) _（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(a0<aj) aj+1=aj; j-; aj+1=a0;试卷二一、选择题（本题共20分,每题2分）1.下面程序段的时间复杂度为（ ）。for(i=1;i<=n;i+) for(j=1;j<=n;j+) s+;A. O(n) B. O(n2) C. O(2*n) D. O（i*j）2. 线性表采用链式存储时，结点的存储地址（ ）。A必须是不连续的 B部分地址必须是连续的C连续与否均可 D和头结点的存储地址相连续3.若让元素1，2，3依次进栈，则出栈时的序列不可能出现的是（ ）。 A3，2，1 B1，2，3 C3，1，2 D2，1，34.下面说法不正确的是()A串S1=“this_is_a_string”的长度是16。 B串S2=“this”是串S1的子串。C串S3=“thisis”在串S1中的位置是1。D串S4=“a”在串S1中的位置是9。 5. 一个非空广义表的表头（ ）。A不可能是子表 B只能是子表C只能是原子 D可以是子表或原子6.完全二叉树()满二叉树A 不一定是 B一定不是 C一定是 D不能确定关系7. 用链表表示线性表的优点是（ ）A. 便于随机存取B. 便于插入和删除操作C. 花费的存储空间较顺序存储少D. 元素的物理顺序与逻辑顺序相同8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边()。An(n-1)/2 Bn-1 Cn Dn+19.下列查找方法中哪一种不适合元素的链式存储结构()A顺序查找 B分块查找 C二分查找 D散列查找10.下面哪种排序方法稳定性最好()。 A希尔排序 B冒泡排序 C快速排序 D堆排序二、填空题（本题共 20分）1. 数据的逻辑结构可以分为两大类：_和_。2. 在二叉树的第i层上最多有_个结点。3. 无向图中恰好有_条边，才称为无向完全图。4. 用单链表方式存储的线性表，存储每个结点需要有两个域，一个是_，另一个是_。5. 设二维数组A5×6的每个元素占4个字节，已知LOC（a00）=1000，则A一共占用_字节。如果按行优先存储时，a25的起始地址是_。6. 3个结点的树有_种形态，3个结点的二叉树有_种形态。7. 一个广义表为（a，（a，b），d，e，（i，j），k），则该广义表的深度为_。8. 栈的插入操作在_进行，删除操作在_进行。9. 在二叉树中，结点的最大度数是_。10. 判定一个有向图中是否存在回路，即是否含有环，可以使用_方法。11. 二分查找的效率较高，但是要求查找表中的关键字_，并且要求表的存储为_。12. 在构造散列表的过程中，不可避免会出现冲突，通常解决它的方法有_和_。13从任何一个结点开始都能成功查找其他结点的单链表是 表。三、应用题（本题共 50分，每题10分）1. 一棵二叉树如右面的图所示，要求： （1）写出对此二叉树进行中序遍历时得到的结点序列。 （2）画出由此二叉树转换得到的森林。2. 已知图G的邻接表如下，写出从顶点O出发的深度优先和广度优先遍历的顶点序列。 0 0 2 1 3 1 0 0 2 2 0 3 0 1 3 0 2 03. 对于下面所示的连通图，写出由Prim算法生成的最小生成树。 4.下图所示为AOE网，求其关键路径和关键活动。 四、算法填空题（本题共10 分）下列两个算法分别为二分查找算法和冒泡排序算法，阅读下面程序代码，填充空白位置，使算法完整。#Define n 10typedef int KeyType;typedef struct KeyType key; NodeType;typedef NodeType SeqListn+1;1. int BinSearch (SeqList R,KeyType k)int low=1,high=n,mid;while(low<=high) mid=(low+high)/2; if(Rmid.key=k) return mid; if(Rmid.key>k) _1_; else _2_;return 0; 2. void BubbleSort (SeqList R) int i,j Boolean exchange; For( i=1;i<n;i+) exchange=false;for(j=1;j<=n-I;j+) if(Rj+1.key<Rj.key) _3_; _4_; Rj=R0; _5_if (!exchange) return;参考答案一、选择题（本题共20分,每题2分）12345678910BCCCDAbBCB二、填空题（本题共20分,每空1分）1） 线性结构 ，非线性结构 2） 2i-13） n(n-1)/2 4） 数据域 ，指针域5） 1120 ，1068 6） 2 ，57） 5 8） 栈顶， 栈顶9） 2 10） 拓扑排序11） 有序， 顺序存储 12） 开放定址法， 拉链法13） 单循环链表三、应用题（本题共50分）1） DEFBAC -8分 8分2）深度优先遍历：0231 6分广度优先遍历：0213 6分3） -12分4）顶点vevl活动ell-eV100a1011V234a2000V322a3341V466a4341V567a5220V688a6253a7660a8671 -6分关键路径是：V1-V3-V4-V6 -2分关键活动是：a2,a5,a7 -2分四、算法填空题（本题共10分,每空2分）1） high=mid-1; -2分2） low= mid+1; -2分3） R0=Rj+1; -2分4） Rj+1=Rj; -2分5） exchange=true; -2分
